Unwrap a polyhedron

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

Unwrap a polyhedron

gilboonet
Hello, I'm trying to unfold a polyhedron using OpenSCAD. It's something that is at the core of my cardboard craft, I first wrote it using OpenJSCAD v1 and since 2 years now I'm using a vanilla JavaScript version, but I'm aware that OpenSCAD is not JavaScript and I need to get close to OpenSCAD concepts and forget iterative coding in order to make good use of recursion.

I use Wings3d to export a 3d model as polyhedron data (using its export to .jscad)
I have two arrays, points[] and polygons[]

With those arrays I'm able to get 3d triangles of each polygons of the polyhedron (function getFacePoints()).

To transform those 3d triangles into 2d triangles, I use a neat formula from Stack overflow (function 2dize()).

Next step is to start from one face, then look for its neighbors (they share 2 points), rotate each neighbor triangle if needed, then continue for each new triangle. Later it will be useful to do that recursively and check at each step for triangles intersection, later again check if the net still fits into page, and it will be done.

Do you think such process is possible with OpenSCAD ?

I'm now looking for a way to find a face neighbors. I will continue the post if I find a way to do so.



Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

NateTG
It is possible to do something like that using OpenSCAD, but I'm not sure why you'd want to do to that.   If you have:

points=[ [...],[...],...];
faces=[ [...],[...],...];

As suitable for use in the polyhedron built-in, then you can do something like:

halfedges=[
   for (i=[0:len(faces)-1])
      for(j=[i:len(faces[i])-i])
         [
             faces[i][j]*len(points)+faces[i][(j+1)%len(faces[i]),
             i
         ]
]

Which will produce a list of [index,face] pairs.  Then if you want to know which face is on the other side of an edge that goes from a to b, you can then use:

facelist=search (b*len(points)+a,halfedges)

To find the face the other side.

If you continue to pursue the project, checking for overlap will probably be one of the more painful parts.


Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

cacb
On 2021-03-31 16:12, NateTG wrote:
> It is possible to do something like that using OpenSCAD, but I'm not
> sure why you'd want to do to that.

I agree. I have done it in C++ and would not try to use any scripting
language to do it.

Carsten Arnholm
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

gilboonet
cacb wrote
On 2021-03-31 16:12, NateTG wrote:
> It is possible to do something like that using OpenSCAD, but I'm not
> sure why you'd want to do to that.

I agree. I have done it in C++ and would not try to use any scripting
language to do it.

Carsten Arnholm
Why I'm doing this with scripting tools is because I'm not experienced enough to code 3d in C++ (I'm a 51 years old craftsman not a CS specialist nor professional), but I'm working on this since 2015 in order to have something like Pepakura, and it works well, I managed to have the automatic version unwrap a 2000 triangles model (took hours) that I successfully built on cardboard (took 2 weeks). My primary goal is to unwrap furniture clothe so I won't need more than 2000 triangles most of times. The fact is that automatic unwrapping is very slow with javaScript, for the moment I'm using a strategy that works nicely : I paint my volume so that it has groups of faces that I unwrap separately, it considerably improves the speed, but I'm now hoping that OpenSCAD could help me more. At first I wanted to use TensorFlow but I didn't understand how it works.

I'm already impressed by the speed, the sensation of power that OpenSCAD gives. I will try to understand the code that NateTG gave me, it is so much simple than what I did, but I'm afraid that I need to take little steps not to lose tack of what I'm doing.

I managed to have the faces neighbors using search(), now I need to start basic unwrapping without checking for overlap. On the OpenJSCAD version, what I did to check overlap was very foolish, I built a 2g geometry with all faces already unwrapped and check if this geometry and the current one intersects, takes very long but works. On vanilla JavaScript I tried lots of things but none worked, so this version is only semi-automatic. Yesterday I used it to unwrap the hand model that I'm using here.


Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

Ronaldo
In reply to this post by gilboonet
This subject has been discussed here. See: http://forum.openscad.org/flattening-curved-surfaces-tp19727.html

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

gilboonet
Ronaldo wrote
Thank you, I remember I read that thread several times while I was looking for a way to optimize my script. To unfold the concerned  shape, I saved it to STL, then opened it in Wings3d, select the 4 surfaces separately and colored their faces in order to have them group, then export it to OBJ where the data (vertices, faces, groups) can be easily read. It took about 2 minutes to unfold them all with a vanilla js script. So I hope it will be at least 2 times faster with OpenSCAD. Sadly, what I've read from now makes me think that it won't be possible (or at best it will be hard) to write an automatic version as I didn't find a way to have an OpenSCAD script make conditional actions based on an intersection result (I only need to check if the intersection return something), but for the moment I will try to write the rotation of a neighbor triangle.
 

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

Ronaldo
 ... but for the moment I will try to write the rotation of a neighbor triangle.
This little magic code may do the job:

function unit(v) = v/norm(v);

module connect(a,b,c,d) {
    translate(c)
      mirror(unit(a-b)+unit(c-d))
        mirror(a-b)
          translate(-a)
            children();
}

t1 = [ [3,2], [13,6], [1,12] ];
t2 = [ [-3,2], [-13,6], [-1,5] ];

color("gray") {
  polygon(t1);
  polygon(t2);
}

color("magenta")
  connect(t2[1],t2[2],t1[1],t1[2]) polygon(t2);

color("blue")
  connect(t2[0],t2[1],t1[0],t1[1]) polygon(t2);


 

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

gilboonet
Ronaldo wrote
>  ... but for the moment I will try to write the rotation of a neighbor
> triangle.
> This little magic code may do the job:
Thank you again, I will look at your code that seems interesting, I failed to use mirror to attach neighbors on OpenJSCAD. I managed to have my first neighbor rotation done using the logic I developed on my other versions. And now I'm kind of stuck as I must update data of that neighbor that I rotated and it's something that I'm not sure is possible within OpenSCAD logic. It I can update those points I will only need to keep on doing the same with other neighbors, otherwise for each new neighbor I will need to do everything again ?
 

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

NateTG
In reply to this post by gilboonet
gilboonet wrote
... It took about 2 minutes to unfold them all with a vanilla js script. So I hope it will be at
least 2 times faster with OpenSCAD. Sadly, what I've read from now makes me
think that it won't be possible (or at best it will be hard) to write an
automatic version as I didn't find a way to have an OpenSCAD script make
conditional actions based on an intersection result ...
OpenSCAD tends to be pretty slow.  In general, I would expect JavaScript to do the same things more quickly.   So if "unfold" is taking to too long in JS, it might be useful to check whether you're doing the "unfold" in a particularly inefficient way.

One of the biggest frustrations that I have with OpenSCAD is that there's no good for user code to take advantage of the geometry engine.

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

gilboonet
NateTG wrote
OpenSCAD tends to be pretty slow.  In general, I would expect JavaScript to
do the same things more quickly.   So if "unfold" is taking to too long in
JS, it might be useful to check whether you're doing the "unfold" in a
particularly inefficient way.
The way I currently unfold is simplistic, I start from a face, then if you click on "auto" button it unfold closest neighbor and keep on till there's nothing to do, it is here. I planned to make something more complex but I didn't manage to have a solid overlap detection function, so I didn't go further. What do you mean by an inefficient way ? Is there a way to weight an unfold path efficiency ? (a tree to climb up and down till every faces are unfold ?) I hope that OpenSCAD could be helpful to develop such technique.

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

Ronaldo
With immutable variables, the only way I see to mark already processed triangles is to generate the whole thing with new marks. And that is inefficient.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

gilboonet
I think I have a little chance to make it if I can create a list of neighbors to unfold starting from the first one that I choose. It starts with its direct neighbours, then continue with their neighbors and so on, but I cannot see how to create that with OpenSCAD, I need to read more about list comprehension.

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

NateTG
gilboonet wrote
I think I have a little chance to make it if I can create a list of neighbors
to unfold starting from the first one that I choose. It starts with its
direct neighbours, then continue with their neighbors and so on, but I
cannot see how to create that with OpenSCAD, I need to read more about list
comprehension.
...
I imagine the easiest way to do something like that in OpenSCAD would be recursion.  For example with a function that takes a partial net, tries to add one face to the net, and then calls itself with the new partial net if it works.

There are relatively simple shapes (like a small cube stacked on top of the center of a big cube) that don't have 'one piece' nets.  So it might make sense to take a "breadth first" approach to flattening without overlaps, and then looking for minimal cuts to make printable pieces from it.


Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

NateTG
In reply to this post by gilboonet
Here's a quick and dirty unfolder that I wrote. It  uses a stupid method for generating the unfolding tree that is unlikely to scale well.  I think recursion is necessary to make one with better scaling behavior.

 I also don't have fancy polyhedra to hand for testing it, but it's still cute with animation on.

unfold.scad

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

adrianv
In reply to this post by Ronaldo
I don't think that this process is particularly horrible in terms of efficiency.  You have the polygon as a list of vertices and faces.  You first need to construct a list of the faces that are across each edge.   This can be done by enumerating the edges and then sorting the list.  Then you can look at a face and find the faces that are adjacent with a simple list index.  Tracking which faces have been placed already does of course require updating a list, but it doesn't have to be a huge data structure,  just a simple list with one boolean entry per face.  I wouldn't think you'd want to do thousands of polygons, but this would be fine for moderate sized cases, certainly it should be doable for <100 faces.  Updating a length 100 list of booleans isn't going to be a huge time suck.  I think checking intersection is probably the most time consuming step, because you'll have to check lots of segments as more of the net is assembled.  

There are only two ways you could do this: recursion for C-style for loop.  The C-style for loop is paradoxically slower than recursion in my tests, and can be harder to use than one would expect.  I would do it with recursion.  It seems like the most complicated aspect of this would be maintaining a stack, because you need to be able to pop the stack to return to the last branch point as you search the tree.  

Here's how it's possible to compute the faces that are associated with edges using the BOSL2 library.  This runs in 3s with 3500 faces, which should be a lot more than you'd ever want to make a net for.  

include<BOSL2/std.scad>

// Returns list of edges in sorted order with the pair of faces for each edge
// edge table has the form
//    [[v1,v2],[f1,f2]]     the edge [v1,v2] connects f1 to f2
//                          vertices are indices into the vertex list and faces
//                          indices into face list
// facetable
//    entry i lists the edges that compose face i as indices into the edge table above
function edge_faces(vnf) =
   let(
       faces=vnf[1],
         // [v1,v2,face_index]
       edgelist= [ for(faceind=idx(faces), j=[0:len(faces[faceind])-1])
                    let(
                        v1=faces[faceind][j],
                        v2=faces[faceind][(j+1)%len(faces[faceind])]
                     )
                     v1<v2 ? [v1,v2,faceind,j] : [v2,v1,faceind,j]
                 ],
       sedge = sort(edgelist),
       edgetable = [for(i=[0:2:len(sedge)-1])
                      assert(sedge[i][0]==sedge[i+1][0] && sedge[i][1]==sedge[i+1][1],
                             str("Found unpaired edge, ", sedge[i-1]," ",sedge[i]," ",
                                 sedge[i+1]," ",sedge[i+2]," ",sedge[i+3]," ",sedge[i+4]," ",len(sedge)))
                      //  add check for too many of the same edge?
                      [select(sedge[i],0,1), [sedge[i][2], sedge[i+1][2]]]],
       facetable = group_data(subindex(sedge,2), [for(i=idx(sedge)) floor(i/2)], sortidx(sedge,[2,3]))
      )
     [edgetable,facetable];

// Function: group_data
// Given a vector of group numbers and a vector of values, produces an
// output with all the values in each group: [[v0_0,v0_1,v0_2,..], [v1_0,v1_1,v1_2,...],...]
// The first list in the output will be all items corresponding to group 0, the second list group 1, and
// so on.  If no members exist for a group the empty list is output.  
function group_data(group, value, sidx) =
   assert(is_list(group) && is_list(value) && len(group)==len(value),"Must provide lists of matching length")
   let(
        sidx = is_def(sidx) ? sidx : sortidx(group),
        cuts =[each repeat(0,1+group[sidx[0]]),
               for(i=[1:len(group)-1]) let(delta = group[sidx[i]]-group[sidx[i-1]])  each if (delta>0) repeat(i,delta),
               len(group)]
   )
   [for(i=[0:len(cuts)-2])
       [for(j=[cuts[i]:1:cuts[i+1]-1]) value[sidx[j]]]];


Ronaldo wrote
With immutable variables, the only way I see to mark already processed
triangles is to generate the whole thing with new marks. And that is
inefficient.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]


Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

gilboonet
In reply to this post by NateTG
NateTG wrote
Here's a quick and dirty unfolder that I wrote.
Thanks a lot for that script. I need to dig it as at first look I didn't understand it.

NateTG wrote
I also don't have fancy polyhedra to hand for testing it
I have lots of low poly models that I usually use for my tests; it's easy to grab polyhedron data from them :
- open this link into your internet browser
- choose a model from the (choisir volume) list
- choose JSCAD or js from the first list (after "Ready"), save the file
The data are into faces and vertices arrays

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

gilboonet
In reply to this post by adrianv
adrianv wrote
Here's how it's possible to compute the faces that are associated with edges
using the BOSL2 library.  This runs in 3s with 3500 faces, which should be a
lot more than you'd ever want to make a net for.  
Thank you too for the script, apparently recursion is the way to go. That's very interesting for me as it introduces me to BOSL. 3500 faces is lots more than my usual model, that's great that it runs so fast. Now I need to try to understand your code. About running time of the process, I think that it's only the unfolding that takes time, the rendering of the net with all numbers also takes lot of time. At first I did it with text primitive, then added a function to cache text injection, then replaced the built-in text polygons with a minimalistic set of polygons, and finally (but not only to improve speed, also to improve rendering quality) I rendered the net with svg injection. With a 2000 faces model I ended with a svg containing 13K lines (700 Ko).


Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Unwrap a polyhedron

NateTG
In reply to this post by gilboonet
gilboonet wrote
I have lots of low poly models that I usually use for my tests; it's easy to
grab polyhedron data from them :
- open  this link
<https://gilboonet.github.io/OpenJSCAD.org/packages/web/scripts.html>   into
your internet browser
- choose a model from the (choisir volume) list
- choose JSCAD or js from the first list (after "Ready"), save the file
The data are into faces and vertices arrays
Thanks, that helped me discover a bug.  Line 51 of the script that I uploaded should have been:

theta=$t*atan2(unto*uw,unto*unfrom)

rather than

theta=$t*-((nfrom*nto > 0)? ...


Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]