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.
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/
Parkinbot, wrote:
My code
- finds the points B_i with minimal x-value in each inner polygon and puts
them into a list A. - selects the polygon n with minimal x-value from the list A, uses the
point B_n as bridge and excludes polygon n from the list A. - finds the nearest point with smaler x value in the outer polygon with
respect to the bridge - composes a new outer polygon using the bridge
- 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:
[image: case1.PNG]
Even if a check is made to avoid possible crosses like this, there is a
subtle case hidden bellow the bridges.
[image: case2.PNG]
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.
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/
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.
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/
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.
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
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.
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
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.
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:
r = 0.0001;
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);
cube(50);
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.
I have opened an issue about that in
https://github.com/openscad/openscad/issues/2842.
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/
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.
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/