# Unwrap a polyhedron

18 messages
Open this post in threaded view
|

## Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

Open this post in threaded view
|

## Re: Unwrap a polyhedron

 ... 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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// 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])]                      )                      v10) 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]
Open this post in threaded view
|

## Re: Unwrap a polyhedron

 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]