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. <http://forum.openscad.org/file/t887/fsp_triag.png> Here the rest of the code, that produced the image use <polygon_triangulation_2.scad> 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 |
Parkinbot, wrote: My code 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 |
Ronaldo wrote
> 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; Ok, this is no real difference. Sorting will safe time only when a really large number of inner polygons is given. Ronaldo wrote > 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: I see, you are right with the first argument. The function Nearest() is a bit too simple (also found another problem with it). I have to rethink and revise it. Thanks! I also see your second argument and tested it. You are right. triangulate() has a problem, when the order is wrong. Btw. triangulate() then almost bricks OpenSCAD. Sometimes a recursion is the better choice. This is why I hate to write (and to debug) algorithms in OpenSCAD. -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
Here is a test case for what I called "subtle case hidden bellow the bridges".
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 |
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 |
I have also done a test using FSP with two inner polygons in a sort of race Right. I inserted some assert()s in triangulate() to escape the loop when an ear is not found. The non-convex case of the outer polygon is indeed quite pathetic - isn't After the first bridge, the outer polygon is non-convex anyway. No way to escape from that. Brute force is also unavoidable. Your code circulates all polygon vertices to find the minimum. To check for any edge crossed by a bridge candidate we have to circulate outer again. With the nearest vertex strategy that is clumsy because we don't really have a set of candidates to choose from. Brute force is also used to check visibility in the ear-cut method in order to assure a candidate triangle is an ear. It is standard. I revised my implementation of polyHoles() and polyHolePartition() and they are fine now. The multi-bridge point problem is naturally solved by what you called the paper "strange search". In my opinion OpenSCAD is a not well enough equipped language to implement I understand your point but I was successful coding Eberly's method. And I believe that we would not need triangulation or even partitions to sweep polygons with holes. FSP should be enough. Like you, I have found cases where FSP faces in polyhedron is not acceptable on F6. But I have also found cases where they are acceptable. So, it seems that CGAL (or possibly its "entourage") has an inconsistent behavior that I would call a bug. If that OpenSCAD inconsistency is corrected in the right direction, FSP would be eligible as a good way to model polyhedrons with holes without boolean operations (or any kind of partitions) as its is good for primitive polygon and its extrusions. I bring your attention to the following simple test:
We may understand that as the polyhedron representation of a linear_extrude of a polygon with holes expressed by a FSP. It works right with F6 as is. But if we set the perturbation value of r to zero, we get a wrong result where the holed faces are missing. It is clear to me that there are two different ways OpenSCAD takes in this example depending on the value of r. I expect that is corrected in order to get consistent results with the linear_extrude of FSP. It is your turn, @Kintel. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
I have opened an issue about that in https://github.com/openscad/openscad/issues/2842. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
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 ... <http://forum.openscad.org/file/t887/fsp2.png> -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
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 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:
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 |
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 |
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 |
Interestingly, after flushing the cache I got the same result like you on
RC2. -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
Free forum by Nabble | Edit this page |