
1 ...
3456

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 1. finds the points B_i with minimal xvalue in each inner polygon and puts them into a list A. 2. selects the polygon n with minimal xvalue from the list A, uses the point 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 with respect to the bridge 4. composes a new outer polygon using the bridge 5. 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 xvalue; besides, I sort the min xvalue 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 (twoway) 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
> xvalue; besides, I sort the min xvalue 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".
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 xvalues, 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 selfintersection
occurs, triangulate() seems to go into an eternal loop which OpenSCAD needs
about 10 minutes to break and treat as overflow error.
The nonconvex case of the outer polygon is indeed quite pathetic  isn't
any nonconvex 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 multibridge 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 nonpathetic 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
condition and then triangulate(). In the condition, where selfintersection
occurs, triangulate() seems to go into an eternal loop which OpenSCAD needs
about 10 minutes to break and treat as overflow error.
Right. I inserted some assert()s in triangulate() to escape the loop when an ear is not found.
The nonconvex case of the outer polygon is indeed quite pathetic  isn't
any nonconvex 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 multibridge points and unravel the
sequences or revise triangulate() to be able to deal with it.
After the first bridge, the outer polygon is nonconvex 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 earcut 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 multibridge 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
all this in a nonpathetic 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.
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:
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, 23, 20, 9], [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);
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


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
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 selfintersection 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 selfintersecting by an edge. And even so, CGAL render it when r>1e16.
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, 12r]]
;
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

1 ...
3456
