flattening curved surfaces

classic Classic list List threaded Threaded
53 messages Options
123
Reply | Threaded
Open this post in threaded view
|

flattening curved surfaces

jon_bondy
I have a bit of code at the end of this question.  It produces a shape
with 4 curved sides, each of which lies on the surface of a cylinder.  
Note that this is an example shape: I want to work with families of
similar shapes, not just with this one example.

I would like a way to take each of the 4 surfaces and produce a 2D shape
that, when cut out and bent, would conform to the original surface.  The
idea is to be able to create the original shape out of, say, cardboard
by cutting out the 4 2D shapes and then taping them together.

I have a conceptual idea of how this would be done in a traditional
programming language if I had a list of the coordinates along each of
the 4 boundary lines.  I considered re-writing the code, below, as a
sweep, and generating the coordinates explicitly, but a) that is not
trivial (to me), and ii) I want to solve the more general case where the
equations that determine the shape are not known.  I looked at the
generated STL file, and the coordinates are there, but not organized in
the way that I would want them to be.

This may be more effort than I want to expend, but I wondered if anyone
had a brilliant insight.

Thanks!

Jon


le = 10;    // length
d1 = 25;    // diameter of top
d2 = 35;    // diameter of bottom
d  = -8;    // delta to drop center of bottom

$fn = 100;

module shape() {
     translate([0, 0, -6])
         intersection() {
             translate([-le/2, 0, 0])
                 difference() {
                     rotate([0, 90, 0])
                         cylinder(h = le, d = d1);
                     translate([-1, 0, d])
                         rotate([0, 90, 0])
                             cylinder(h = le + 2, d = d2);
                     }

             intersection() {
                 translate([10, 0, 0])
                     cylinder(h = 100, d = 30);
                 translate([-10, 0, 0])
                     cylinder(h = 100, d = 30);
                 }
             }
         }

shape();

*difference() {
     shape();
     translate([0, 0, -4])
         scale([0.8, 0.8, 2])
             shape();
     }


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

frankv
You might want to look at map projections... cartographers have been working on this for centuries  (for the oblate spheroid class of surfaces).

On 25/12/2016 13:40, "jon" <[hidden email]> wrote:
I have a bit of code at the end of this question.  It produces a shape with 4 curved sides, each of which lies on the surface of a cylinder.  Note that this is an example shape: I want to work with families of similar shapes, not just with this one example.

I would like a way to take each of the 4 surfaces and produce a 2D shape that, when cut out and bent, would conform to the original surface.  The idea is to be able to create the original shape out of, say, cardboard by cutting out the 4 2D shapes and then taping them together.

I have a conceptual idea of how this would be done in a traditional programming language if I had a list of the coordinates along each of the 4 boundary lines.  I considered re-writing the code, below, as a sweep, and generating the coordinates explicitly, but a) that is not trivial (to me), and ii) I want to solve the more general case where the equations that determine the shape are not known.  I looked at the generated STL file, and the coordinates are there, but not organized in the way that I would want them to be.

This may be more effort than I want to expend, but I wondered if anyone had a brilliant insight.

Thanks!

Jon


le = 10;    // length
d1 = 25;    // diameter of top
d2 = 35;    // diameter of bottom
d  = -8;    // delta to drop center of bottom

$fn = 100;

module shape() {
    translate([0, 0, -6])
        intersection() {
            translate([-le/2, 0, 0])
                difference() {
                    rotate([0, 90, 0])
                        cylinder(h = le, d = d1);
                    translate([-1, 0, d])
                        rotate([0, 90, 0])
                            cylinder(h = le + 2, d = d2);
                    }

            intersection() {
                translate([10, 0, 0])
                    cylinder(h = 100, d = 30);
                translate([-10, 0, 0])
                    cylinder(h = 100, d = 30);
                }
            }
        }

shape();

*difference() {
    shape();
    translate([0, 0, -4])
        scale([0.8, 0.8, 2])
            shape();
    }


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

cacb
In reply to this post by jon_bondy
On 25. des. 2016 01:39, jon wrote:
> I have a conceptual idea of how this would be done in a traditional
> programming language if I had a list of the coordinates along each of
> the 4 boundary lines.  I considered re-writing the code, below, as a
> sweep, and generating the coordinates explicitly, but a) that is not
> trivial (to me), and ii) I want to solve the more general case where the
> equations that determine the shape are not known.  I looked at the
> generated STL file, and the coordinates are there, but not organized in
> the way that I would want them to be.

Whether your idea is really worth pursuing is a issue in itself, but if
you want to try it is probably easier to export to AMF, OpenSCAD can do
it. https://en.wikipedia.org/wiki/Additive_Manufacturing_File_Format

AMF is an XML file format containing the result of booleans in a form
very similar to an OpenSCAD polyhedron, with unique vertices separate
from the (triangular) faces and each face defined as 3 vertex indices.
This means you have topology to work with, not just a "polygon soup" as
in STL. With STL you would have to rediscover a topology first, a
non-trivial task in the general case.

So in principle, using a traditional programming language, you could
read the AMF and detect the "boundary lines" by evaluating the angles
between neighbouring faces (finding neighbouring faces requires topology
evaluation). That would be just the start of another non-trivial task to
detect the faces bound by those boundaries. It could certainly succeed,
but a general solution would take quite some effort.

Using only OpenSCAD, something like that is not possible at all, since
there is no way in the language to access the vertices and faces of the
result of a boolean operation.

Carsten Arnholm

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

jon_bondy
That was not the answer I was hoping for, but it certainly is the answer
I was looking for!

Thank you!


On 12/24/2016 8:46 PM, Carsten Arnholm wrote:

> On 25. des. 2016 01:39, jon wrote:
>> I have a conceptual idea of how this would be done in a traditional
>> programming language if I had a list of the coordinates along each of
>> the 4 boundary lines.  I considered re-writing the code, below, as a
>> sweep, and generating the coordinates explicitly, but a) that is not
>> trivial (to me), and ii) I want to solve the more general case where the
>> equations that determine the shape are not known.  I looked at the
>> generated STL file, and the coordinates are there, but not organized in
>> the way that I would want them to be.
>
> Whether your idea is really worth pursuing is a issue in itself, but
> if you want to try it is probably easier to export to AMF, OpenSCAD
> can do it.
> https://en.wikipedia.org/wiki/Additive_Manufacturing_File_Format
>
> AMF is an XML file format containing the result of booleans in a form
> very similar to an OpenSCAD polyhedron, with unique vertices separate
> from the (triangular) faces and each face defined as 3 vertex indices.
> This means you have topology to work with, not just a "polygon soup"
> as in STL. With STL you would have to rediscover a topology first, a
> non-trivial task in the general case.
>
> So in principle, using a traditional programming language, you could
> read the AMF and detect the "boundary lines" by evaluating the angles
> between neighbouring faces (finding neighbouring faces requires
> topology evaluation). That would be just the start of another
> non-trivial task to detect the faces bound by those boundaries. It
> could certainly succeed, but a general solution would take quite some
> effort.
>
> Using only OpenSCAD, something like that is not possible at all, since
> there is no way in the language to access the vertices and faces of
> the result of a boolean operation.
>
> Carsten Arnholm
>
> _______________________________________________
> OpenSCAD mailing list
> [hidden email]
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
>
>
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 2016.0.7924 / Virus Database: 4739/13648 - Release Date:
> 12/24/16
>
>


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

runsun
In reply to this post by jon_bondy
jon_bondy wrote
Note that this is an example shape: I want to work with families of
similar shapes, not just with this one example.
I imagine that if it's possible to generate those shapes in polyhedron, it won't be hard to achieve what you want.
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

cacb
In reply to this post by jon_bondy
On 25. des. 2016 02:52, jon wrote:
> That was not the answer I was hoping for, but it certainly is the answer
> I was looking for!
>
> Thank you!

You are welcome. At least it may have saved you some time chasing the
unobtainable.

Carsten Arnholm


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

nophead
Incidental to the question but when I put a # in front of the first cylinder it doesn't show the whole cylinder. It does for the other three cylinders. Why is that?

On 25 December 2016 at 09:16, Carsten Arnholm <[hidden email]> wrote:
On 25. des. 2016 02:52, jon wrote:
That was not the answer I was hoping for, but it certainly is the answer
I was looking for!

Thank you!

You are welcome. At least it may have saved you some time chasing the unobtainable.


Carsten Arnholm


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Ronaldo
In reply to this post by cacb
cacb wrote
On 25. des. 2016 01:39, jon wrote:
Using only OpenSCAD, something like that is not possible at all, since
there is no way in the language to access the vertices and faces of the
result of a boolean operation.
Carsten is right but there is a workaround. A python code by Neon22 converts AMF files (possibly exported by OpenSCAD) to a text file in the OpenSCAD polyhedron format. See this discussion. By using its output file in you OpenSCAD code, you will have access to the model vertices and a code may be devised to find and unfold the developable surfaces. However, the latest doesn't seem to be a trivial task. See for instance: http://complexitys.com/english/geometry/developable-surfaces/#.WF9isH10ca9

Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Parkinbot
In reply to this post by jon_bondy
Jon,
I like your approach and I don't think it is too difficult to implement, if you restrict the design to a set of constraints, which your parser can assume to hold without further testing. (Also I don't see any advantage in using AMF instead of STL.)

Rules:
1. (unrolling) - Your design is composed by a set of surfaces, which are unrollable in 2D. This puts a bunch of restrictions on the surfaces (!!!)
2. (separation) - two edge-adjacent triangles belong to different surfaces, if the scalar product of their normals exceeds some threshold parameter TH.

So what does your algorithm? It reads the triags into a set T and
a) finds and hooks the three (common edge) neighbours to each triag in T.
b) calculates the scalar products of each two neighboured triag normals and classifies by means of the threshold TH, if the two triags belong to the same surfaces or not. Not-on-the-same-surface neighbours will be unhooked.
c) select any triag in T and move it to a set S. Continue with all its same-surface neighbours and so on, until all same-surface triags are in S.
d. repeat with c until T is empty and get a set SS of surfaces.
e) unroll each surface S in SS into 2D. For example start with any triag t
   i) find an affine transformation f that maps t undistorted to 2D (always can be found).
   ii) apply f to all direct neighbours and find for each of them a rotation g that maps them to the 2D plane
   iii) continue with ii using g(f(t)) until done.

You see, the scheme is quite straight forward (and easy to implement) and the only difficulty you will encounter is step e), where it turns out whether your design obeys to rule 1 or not.  If it doesn't, you will have to find a way (=heuristics) to deal with it. This can get more nasty.
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

jon_bondy
I KNEW there was a reason that I was about to retire!  This should keep
me out of trouble for a while!  Thanks for the pseudo code!

Jon


On 12/25/2016 8:40 AM, Parkinbot wrote:

> Jon,
> I like your approach and I don't think it is too difficult to implement, if
> you restrict the design to a set of constraints, which your parser can
> assume to hold without further testing. (Also I don't see any advantage in
> using AMF instead of STL.)
>
> Rules:
> 1. (unrolling) - Your design is composed by a set of surfaces, which are
> unrollable in 2D. This puts a bunch of restrictions on the surfaces (!!!)
> 2. (separation) - two edge-adjacent triangles belong to different surfaces,
> if the scalar product of their normals exceeds some threshold parameter TH.
>
> So what does your algorithm? It reads the triags into a set T and
> a) finds and hooks the three (common edge) neighbours to each triag in T.
> b) calculates the scalar products of each two neighboured triag normals and
> classifies by means of the threshold TH, if the two triags belong to the
> same surfaces or not. Not-on-the-same-surface neighbours will be unhooked.
> c) select any triag in T and move it to a set S. Continue with all its
> same-surface neighbours and so on, until all same-surface triags are in S.
> d. repeat with c until T is empty and get a set SS of surfaces.
> e) unroll each surface S in SS into 2D. For example start with any triag t
>     i) find an affine transformation f that maps t undistorted to 2D (always
> can be found).
>     ii) apply f to all direct neighbours and find for each of them a rotation
> g that maps them to the 2D plane
>     iii) continue with ii using g(f(t)) until done.
>
> You see, the scheme is quite straight forward (and easy to implement) and
> the only difficulty you will encounter is step e), where it turns out
> whether your design obeys to rule 1 or not.  If it doesn't, you will have to
> find a way (=heuristics) to deal with it. This can get more nasty.
>
>
>
>
> --
> View this message in context: http://forum.openscad.org/flattening-curved-surfaces-tp19727p19736.html
> Sent from the OpenSCAD mailing list archive at Nabble.com.
>
> _______________________________________________
> OpenSCAD mailing list
> [hidden email]
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
>
>
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 2016.0.7924 / Virus Database: 4739/13649 - Release Date: 12/24/16
>
>


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Ronaldo
In reply to this post by Parkinbot
Parkinbot wrote
I like your approach and I don't think it is too difficult to implement, if you restrict the design to a set of constraints, which your parser can assume to hold without further testing. (Also I don't see any advantage in using AMF instead of STL.)
I have suggested AMF file export because this is the input file format Neon22's python code requires to generate the polyhedron data.

Do you call that a not difficult to implement solution?

Rely on thresholds is not a good strategy. For instance, subdivide a square in 4 triangles meeting at its center and move up slightly two opposed vertices and move down the other two. It will not be a developable surface but may pass a reasonable threshold. The main property of triangulated developable surfaces that may be handy is that the sum of the internal angles of the triangles incident at each vertex of such surfaces should be 360 degrees.

One strategy to find the pieces of developable surfaces could be to calculate that sum at each vertex of the triangulation and collect those vertices that have the required sum of 360 degrees and are in the same connected component of the triangulation. To do that you possibly will need a triangulation data structure that is not trivial to implement in OpenSCAD.
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

cacb
In reply to this post by Ronaldo
On 25. des. 2016 13:16, Ronaldo wrote:
> Carsten is right but there is a workaround. A python code by Neon22 converts
> AMF files (possibly exported by OpenSCAD) to a text file in the OpenSCAD
> polyhedron format. See this  discussion
> <http://forum.openscad.org/Wrapping-text-around-a-complex-geometry-td18145.html#a18156>

That is a good idea, but he appears to manually modify the converted
code to get the modified coordinates, a bit cumbersome. Another idea
along the same lines would be to do the coordinate modification in the
conversion code, which would essentially become a 'morphing conversion',
see below.

On the issue of unfolding the surfaces to be traced on paper, it is not
possible in the general case, I agree. A spherical surface cannot be
unfolded on a flat surface for example.

On morphing, I tried it using jons model (scaled up 10x and using
$fn=300 in OpenSCAD). Since all sides are curved in the first place, it
lends itself to easy morphing (to some degree). An image of the original
shape is attached. Example morphing code (angelscript), using the AMF
generated by OpenSCAD:

----
    polyhedron@ cs = polyhedron("curved_surfaces.amf");
    double px=8;
    double pz=4;
    const double pi = 4.0*atan(1.0);
    // compute transformed vertices
    pos3d@[] vert(nv);
    for(uint iv=0; iv<nv; iv++) {
       pos3d@ p   = cs.vertex(iv);
       double par = (p.y() - ymin)/(ymax - ymin);
       double sx  = 1+0.1*cos(px*pi*par);
       double sz  = 1.2+0.1*cos(pz*pi*par);
       @vert[iv]  = scale(sx,1,sz)*p;
    }
    // transfer the faces
    pface@[] faces(nf);
    for(uint iface=0; iface<nf; iface++) {
       @faces[iface] = cs.face(iface);
    }
    polyhedron@ cs_morphed = polyhedron(vert,faces);
----

The second image shows the result. Lots of opportunities with such an
approach...

However, for a model containing flat surfaces, it actually gets a bit
more complicated, since you normally don't have vertices to modify
within those flat surfaces. One way to solve that problem is to "remesh"
the surfaces to obtain much smaller triangles, and many more vertices.
Then you can apply the same technique as above.

Carsten Arnholm






_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

curved_surfaces1.png (19K) Download Attachment
curved_surfaces2.png (25K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Parkinbot
In reply to this post by Ronaldo
Ronaldo,

I understood that Jon wanted to use a traditional programming language providing support for file read operations and structs, but reading his post again, I am not so sure about this any more.
I have a conceptual idea of how this would be done in a traditional programming language if I had a list of the coordinates along each of the 4 boundary lines.
Of course there can be other (more sophisticated) strategies for surface separation applied. But I don't think that will be needed.  

Do you call that a not difficult to implement solution?
Well, parsing some STL (which is already partly sorted), building a topology from it and applying a predicate to adjacent triags indeed doesn't seem too be difficult in my eyes.
Indeed it is something like a twenty-liner to convert a wellformed STL into some scad file for reimport. Undoubtedly it IS somehow clumsy to continue in OpenSCAD than, mainly because of its "peculiar" language design and poor data structures, but even there ...  

My opinion: If you are already using a traditional programming language, why not stay there to also keep control over your output - unless you are fine with some DXF output.
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Parkinbot
In reply to this post by Ronaldo
Ronaldo wrote
Rely on thresholds is not a good strategy. For instance, subdivide a square in 4 triangles meeting at its center and move up slightly two opposed vertices and move down the other two. It will not be a developable surface but may pass a reasonable threshold.
You can always construct those counter examples. My opinion is: Know what you do, already when you do your design. This is what I meant by rule 1.

The main property of triangulated developable surfaces that may be handy is that the sum of the internal angles of the triangles incident at each vertex of such surfaces should be 360 degrees.
Isn't that too strict? Doesn't it hold only for planar surfaces?


Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Ronaldo


2016-12-25 14:32 GMT-02:00 Parkinbot <[hidden email]>:
Ronaldo wrote
> The main property of triangulated developable surfaces that may be handy
> is that the sum of the internal angles of the triangles incident at each
> vertex of such surfaces should be 360 degrees.

Isn't that too strict? Doesn't it hold only for planar surfaces?

Certainly is not too strict. If a set of triangle around a vertex are part of a developable surface this condition must be met. Otherwise, when they are laid down on a plane, either they will not close (for angle sum lesser then 360) or they will overlap. Note that this condition should be met at the internal vertices. For the border vertices the sum should be lesser than 360.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Parkinbot
Ronaldo wrote
Certainly is not too strict.
I doubt that. Have a look at a cylinder. It contains 3 surfaces that doubtless can be unrolled into 2D. Two of them meet your condition, the third one doesn't. A threshold can be easily selected to separate the triags.
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Ronaldo
Parkinbot wrote
Have a look at a cylinder. It contains 3 surfaces that doubtless can be unrolled into 2D. Two of them meet your condition, the third one doesn't. A threshold can be easily selected to separate the triags.
If the only vertices of your cylinder (a prism to be precise) is at the borders of the two planar faces, then none of them satisfies the condition. So they cannot be in the interior of the developed surfaces. Any other vertex not in those borders will satisfy the condition and will be eligible to be inside.

Observe that the problem of finding a partition of developable surfaces for a given polyhedron has many solutions. A trivial one is to define a partition of isolated triangles. Another is a partition of triangle pairs. In the case of a prism, it is possible to find a unique partition for the whole surface. There is no better solution, only wrong ones.
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Parkinbot
It is very tiring to discuss such obvious things and subtleties. Again: I am perfectly sure that the sketched algorithm will work. If you know a better solution, then please present it in a constructive way, so that we follow it.
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

Neon22
This post was updated on .
In reply to this post by jon_bondy
I have seen several implementations of this. There are a couple of guidelines which you might wish to follow just to simplify the code.
- triangulate before unrolling. less cases to deal with.
- mark the edges you wish to preserve when unrolling. (I use wings3d)
- to avoid overlaps, unroll, test and move around to a different face if it overlaps. Else split the shape to a new boundary so overlaps can be avoided.
- check your progress against pepakura - a free version of which can be downloaded to view opened files.
Pepakura is designed for paper folding and low polygon polyhedra which approximate the more detailed surface. It is quite robust.

After you have it all unrolled you're into packing algorithms but that's a different tail...
(https://github.com/Jack000/SVGnest)
Reply | Threaded
Open this post in threaded view
|

Re: flattening curved surfaces

runsun
In reply to this post by Parkinbot
Parkinbot wrote
So what does your algorithm? It reads the triags into a set T and
a) finds and hooks the three (common edge) neighbours to each triag in T.
I supposed that at this stage, the coordinates of each points are already known ?
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
123