# Polyhedron tube with irregular sides -- is it possible ?

112 messages
1 ... 3456
Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

 Ronaldo, OK, there was a small bug in FSP() in the third part of the fsp path. It should be let(fsp = [for(i=[0:obest]) outer[i],  // outer polygon with bridge to inner            for(i=[ibest+N:-1:ibest]) bestinner[i%N],            for(i=[obest:len(outer)-1]) outer[i%len(outer)]]) After correcting that your triangulate() works well with my function. You are right, the angles get a bit small, but I think this is unavoidable.   Here the rest of the code, that produced the image use o = circle(r=100, N=4); i0 = T([-41, 25, 0], circle(r=20, N=3)); i1 = T([-40, -15, 0], circle(r=20, N=3)); i2 = T([45, -10, 0], circle(r=20, N=3)); i3 = T([0, 0, 0], circle(r=20, N=3)); X = FSP(o, [i0, i1, i2, i3]); Y = triangulate(X); showlines(X,Y); polygon(X); line(X, color = "green"); module showlines(P, Tr)  for(t=Tr) line([P[t[0]], P[t[1]], P[t[2]], P[t[0]]], color="green"); -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

 Parkinbot, wrote:My code 1. finds the points B_i with minimal x-value in each inner polygon and putsthem into a list A. 2. selects the polygon n with minimal x-value from the list A, uses thepoint B_n as bridge and excludes polygon n from the list A. 3. finds the nearest point with smaler x value in the outer polygon withrespect to the bridge4. composes a new outer polygon using the bridge5. does recursion until list A is empty.   My code diverges from yours mainly in two steps:Step 1. I look for bridges from right to left, so I take the maximum x-value; besides, I sort the min x-value array so I process the list in order and don't need to remove already processed holes from the list;Step 3. my code follows David Eberly's algorithm very closely; when I saw your code I asked myself why Eberly's algorithm is so much complex? I have found the answer: the nearest point strategy fails because it cannot assure that the bridges will not cross other edges like in:Even if a check is made to avoid possible crosses like this, there is a subtle case hidden bellow the bridges.Suppose that the yellow hole has been processed and the blue bridge is in place. Looking for the nearest point to the left extreme of the red hole, we will find two polygon vertices with the same coordinates: the right extremes of the (two-way) blue bridge. The choice between those two incarnations of the same point is not arbitrary because one of them will generate a polygonal which crosses itself at that point.I shall revise my code of polyHoles and polyHolePartition considering that last case because of some shortcuts I had introduced in the Eberly's method. They may cause troubles.  _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

 Here is a test case for what I called "subtle case hidden bellow the bridges". out = [ [0,0], [-70,25],  [-70,-25] ];hol0 = [ [-25,-5], [-50,0], [-50,10] ];hol1 = [ [-28,0], [-40,5], [-35,8] ];hol2 = [ [-30,-5], [-45,-10], [-45,-5]];FSP  = [ [0,0], [-25,-5], [-30,-5], [-45,-10], [-45,-5], [-25,-5],          [-50,0], [-50,10], [-25,-5] ,          [0,0], [-28,0], [-40,5], [-35,8], [-28,0],         [0,0], [-70,25],  [-70,-25],         ];FSP is one possible correct output for comparison. polyHoles fails with this case and generates a polygon crossing itself.If you use min x-values, rotate all polygons by 180 degrees. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

 I have also done a test using FSP with two inner polygons in a sort of race condition and then triangulate(). In the condition, where self-intersection occurs, triangulate() seems to go into an eternal loop which OpenSCAD needs about 10 minutes to break and treat as overflow error. The non-convex case of the outer polygon is indeed quite pathetic - isn't any non-convex case a bit like this? One has to either check each point in the "view" area against each edge in the view area in a brute force manner or must implement some strange search, as proposed in the paper. And then, as you found out, one has to check for multi-bridge points and unravel the sequences or revise triangulate() to be able to deal with it. In my opinion OpenSCAD is a not well enough equipped language to implement all this in a non-pathetic fashion. Therefore I have to say sorry. I don't have the time (and motivation) to dive deeper into this very specific and more or less only theoretic framework of a stupid work around, which is not at all helpful in my practical work. Compared to all this effort, a lazy union sweep differenced from the outer polygon is just a snap and already part of my library. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

 In reply to this post by Ronaldo You are perfectly right with the convexity argument and an algorithm should be as water tight as possible. I wouldn't sign that brutal force is unavoidable. In my experience you always can avoid brutal force by intelligent sorting or hashing. E.g. for an earcut, you can sort the vertices by x and by y and then use a bounding box check travelling first along one of the routes and then along the other. But it can be very tiring (and inefficient) to implement the data structures needed to implement such strategies in OpenSCAD. Also, the FSP algo can profit from it, because you know that at least one vertex in the pairs of vertices defining the edges to be checked must have a larger x value (OK, the smaller x gets the more brute force it gets). But depending on the problem and the overhead of a more sophisticated algorithm (or the time that is needed to implement and to test it) it can have advantages to use a brutal force approach - especially if it is not an everyday problem you are solving, or a sufficiently simple problem. It is like you don't construct a special purpose machine for every purpose, even you could. I checked your nice example. It also holds with a cube(1) and only one vertex having a +r. It looks like the problem occurs in the moment, when CGAL decides that none of the inner faces needs tesselation. You also can set r=0 and tesselate an inner face yourself (e.g. [8, 23, 20, 9] -> [8, 23, 20], [8, 20, 9])  to get a valid result ... -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

 You are right. I was unclear when I said the brute force is unavoidable. I meant it is not practical to use anything else in OpenSCAD because of the reasons you enumerated very well. Optimal algorithms are usually unfitted to be coded in OpenSCAD because of its poor data structure resources. I checked your nice example. It also holds with a cube(1) and only one vertex having a +r. It looks like the problem occurs in the moment, when CGAL decides that none of the inner faces needs tesselation. You also can set r=0 and tesselate an inner face yourself (e.g. [8, 23, 20, 9] -> [8, 23, 20], [8, 20, 9])  to get a valid result ... I could not reproduce the results of your suggestion to triangulate one face in version RC2. I revised the polyhedron in order to have a self-intersection for any value of r:verts = [[0, 0, -50], [0, 50, 0], [0, 0, 50], [0, -50, 0],         [100, 0, -50], [100, 50, 0], [100, 0, 50], [100, -50, 0],         [0, 0, -12], [0, -12, 0], [0, 0, 12], [0, 12, 0],         [200, 50, -50], [177.639, 94.7214, 0], [200, 50, 50], [222.361, 5.27864, 0],         [200, 50, -12], [205.367, 39.2669, 0], [200, 50, 12], [194.633, 60.7331, 0],         [100, -12+r, 0], [100, 0, 12], [100, 12, 0], [100, 0, -12+r]] ;So the last face now it is not planar (for r>0) but it is still self-intersecting by an edge. And even so, CGAL render it when r>1e-16.To check the CGAL render stability, I usually union the model with a cube that intercepts the model because I have found cases where it may render well with a disjoint cube but it  does not with an intercepting one. In this case, a cube(6) would be  by an enough. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

 Hmm, I also couldn't reproduce it first. But then I changed the order of the tesselated triags from [8, 23, 20], [8, 20, 9] into  [8, 20, 9], [8, 23, 20]. This made the difference. So the code that CGAL digests is:     r = 0;     verts =  [[0, 0, -50], [0, 50, 0], [0, 0, 50], [0, -50, 0],               [100, 0, -50], [100, 50, 0], [100, 0, 50], [100, -50, 0],               [0, 0, -12], [0, -12, 0], [0, 0, 12], [0, 12, 0],               [200, 50, -50], [177.639, 94.7214, 0], [200, 50, 50], [222.361, 5.27864, 0],               [200, 50, -12], [205.367, 39.2669, 0], [200, 50, 12], [194.633, 60.7331, 0],               [100, -12, 0], [100, 0, 12+r], [100, 12, 0], [100, 0, -12-r]] ;                    faces = [ [0, 4, 5, 1],    [1, 5, 6, 2],         // 4 external faces                [2, 6, 7, 3],    [3, 7, 4, 0],                [9, 20, 21, 10], [10, 21, 22, 11],     // 4 internal faces                [11, 22, 23, 8],  [8, 20, 9], [8, 23, 20],                [0, 1, 2, 3, 0, 8, 9, 10, 11, 8],      // back face with hole                [7, 6, 5, 4, 7, 20, 23, 22, 21, 20]];  // front face with hole           polyhedron(verts, faces);     cube(1); -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Polyhedron tube with irregular sides -- is it possible ?

 Unfortunately it still doesn't work for me neither with version RC2 nor with 2019.01.10.ci1115 (git 95f53797) under Windows 7/64 .I have also tried "flush cache/F5/F6" without success. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org