Simple polygon triangulation
I am searching for a simple polygon triangulation algorithm to implement in
OpenSCAD language. Yes, I know that OpenSCAD is not a general purpose
language. But all methods I found for this problem are essentially iterative
and require complex data structure hard to implement even in a general
purpose functional language. The robust methods are complex to implement.
Even the Seidel algorithm, which is allegedly the easier to code, relies on
a data structure that required more that 120 lines of code of a C++
implementation I found.
Besides, all methods I found are restricted to polygons in the plane. Which
method is used to triangulate the faces of polyhedron in OpenSCAD preview?
It seems to be more general.
Any help is welcome.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
good question ;-)
so you'd need a convexity test first.
-
If convexity is given, you can triangulate by either
a) using one corner as common point (this is trivial)
b) pull up a new triangle at one at the CW or CCW endpoint, until you're
done. This gives you two choices for each new triangle. If both choices are
valid, you get a possible recursion retrace point for sceanrios where both
choices fail. -
For a non-convex polygon, you can decompose the shape into a set convex
shapes and use 1a. So your question could be, how to decompose a non-convex
polygon into a set of convex polygons. -
I think alternatively you could also try 1b and find some additional test
for doing the right choice.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16759.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On Mar 27, 2016, at 18:02 PM, Ronaldo rcmpersiano@gmail.com wrote:
Besides, all methods I found are restricted to polygons in the plane. Which
method is used to triangulate the faces of polyhedron in OpenSCAD preview?
It seems to be more general.
We use a modified version of libtess2 (https://github.com/memononen/libtess2)
I haven’t managed to find a robust general purpose triangulator which supports slightly non-planar polygons as well as polygons with holes. Even CGAL crashes on some corner-case polygons. libtess2 is the best I’ve found so far.
The “Triangle” library is rumored to be very good, but it’s not open source: https://www.cs.cmu.edu/~quake/triangle.html
-Marius
Maybe contacting the author, he could change the licence, or give a special
permission, considering OpenSCAD is non commercial.
jpmendes
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16764.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On 03/28/2016 05:19 PM, jpmendes wrote:
Maybe contacting the author, he could change the licence, or
give a special permission, considering OpenSCAD is non commercial.
The first would be nice, the second one can't work. A special
license for OpenSCAD would make it non-distributable.
ciao,
Torsten.
Hi, Kintel. Thank you for the references. I will take a look on libtess2.
I visited the Triangle page you mentioned and downloaded the triangle.c
code. It is intended to perform Delaunay triangulations. Relying on its
ability to compute constrained Delaunay triangulation may be it could be
used to triangulate a simple planar polygon. It could be an alternative to
me if I had triangulation data structures implemented over OpenSCAD lists.
That was in my future plans but this might be a huge work.
I already implemented an ear-trim kind of method to triangulate simple
almost planar polygons. It is not very efficient however. And very thin
triangles is unavoidable.
Regarding the Triangle copyright, the text bellow is found in the triangle.c
file. I am not sure if it would restrict its use in OpenSCAD code.
/* (triangle.c)
/
/
/
/ Version 1.6
/
/ July 28, 2005
/
/
/
/ Copyright 1993, 1995, 1997, 1998, 2002, 2005
/
/ Jonathan Richard Shewchuk
/
/ 2360 Woolsey #H
/
/ Berkeley, California 94705-1927
/
/ jrs@cs.berkeley.edu
/
/
/
/ This program may be freely redistributed under the condition that the
/
/ copyright notices (including this entire header and the copyright
/
/ notice printed when the `-h' switch is selected) are not removed, and
/
/ no compensation is received. Private, research, and institutional
/
/ use is free. You may distribute modified versions of this code UNDER
/
/ THE CONDITION THAT THIS CODE AND ANY MODIFICATIONS MADE TO IT IN THE
/
/ SAME FILE REMAIN UNDER COPYRIGHT OF THE ORIGINAL AUTHOR, BOTH SOURCE
/
/ AND OBJECT CODE ARE MADE FREELY AVAILABLE WITHOUT CHARGE, AND CLEAR
/
/ NOTICE IS GIVEN OF THE MODIFICATIONS. Distribution of this code as
/
/ part of a commercial system is permissible ONLY BY DIRECT ARRANGEMENT
/
/ WITH THE AUTHOR. (If you are not directly supplying this code to a
/
/ customer, and you are instead telling them how they can obtain it for
/
/ free, then you are not required to make any arrangement with me.)
*/
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16771.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On 03/28/2016 07:34 PM, Ronaldo wrote:
Regarding the Triangle copyright, the text bellow is found in
the triangle.c file. I am not sure if it would restrict its use
in OpenSCAD code.
I'm not a lawyer, so I can't give official advice about this,
but in my understanding "Private, research, and institutional
use is free." is a big conflict with GPL.
ciao,
Torsten.
I agree but between "Private, research, and institutional use is free." and
"Distribution of this code as part of a commercial system is permissible
ONLY BY DIRECT ARRANGEMENT WITH THE AUTHOR" there is a large space for a
deal.
2016-03-28 15:29 GMT-03:00 Torsten Paul Torsten.Paul@gmx.de:
On 03/28/2016 07:34 PM, Ronaldo wrote:
Regarding the Triangle copyright, the text bellow is found in
the triangle.c file. I am not sure if it would restrict its use
in OpenSCAD code.
I'm not a lawyer, so I can't give official advice about this,
but in my understanding "Private, research, and institutional
use is free." is a big conflict with GPL.
ciao,
Torsten.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 03/29/2016 01:24 AM, Ronaldo Persiano wrote:
I agree but between "Private, research, and institutional use is free." and
"Distribution of this code as part of a commercial system is permissible
ONLY BY DIRECT ARRANGEMENT WITH THE AUTHOR" there is a large space for a deal.
Yes, there might be room for a deal, but that will not help as long
as there is any additional GPL code used. Any special agreement
just for OpenSCAD is not compatible with GPL.
The only way to use that code is if it's released with a license
that is compatible with GPL (e.g. BSD/MIT is compatible, a long
list is available at http://www.gnu.org/licenses/license-list.html).
Note that this is not so much about the OpenSCAD code itself, this
could be mainly up to Marius to decide, but we use a number of GPL
libraries and we do have to respect their decision.
ciao,
Torsten.
Parkinbot wrote
good question ;-)
so you'd need a convexity test first.
-
If convexity is given, you can triangulate by either
a) using one corner as common point (this is trivial)
b) pull up a new triangle at one at the CW or CCW endpoint, until you're
done. This gives you two choices for each new triangle. If both choices
are valid, you get a possible recursion retrace point for sceanrios where
both choices fail. -
For a non-convex polygon, you can decompose the shape into a set convex
shapes and use 1a. So your question could be, how to decompose a
non-convex polygon into a set of convex polygons. -
I think alternatively you could also try 1b and find some additional
test for doing the right choice.
I delayed my answer to your suggestions because I needed to take a look on
the convex decomposition methods. From my search, I found that:
a. the convex decomposition of simple polygons is a task so hard as to
triangulate it; some methods triangulate the polygon to find its convex
decomposition;
b. it is not difficult to find simple polygons whose convex decomposition
is itself a triangulation; the case I have in hands and that stimulated me
to implement a simple polygon triangulation falls exactly in that category;
its boundary is composed by two Bezier curves and two line segments;
c. convex decomposition methods require, in general, some kind of data
structure to reduce their complexity and those data structure are likewise
hard to implement in OpenSCAD language.
The ear-cut methods seem to be easier to implement in OpenSCAD. The simplest
ones are sub-optimal in complexity but require just lists as data structure.
I implemented a very simple version of one of those methods and it seems
that, for less than a thousand vertices, the time to triangulate a polygon
is of order n^2. This seems fair to me by now.
A question which is not well addressed yet is how to deal with almost planar
polygonals. The ear-cut method requires that the planar polygon vertices are
ordered in a CCW circulation. In 3D space, there is no well defined
orientation for circulating a polygon. In a planar polygon in 3D, the normal
to the polygon plane may be used to induce an orientation to the vertex
circulation. If the polygon normal is well chosen, it induces the correct
CCW orientation. If the orientation is not CCW, it is sufficient to invert
the normal. A simple check of the orientation correctness is a first issue.
Almost planar polygonals pose more issues since no normal really exists. My
approach is to find a vector that reduces to the polygonal plane normal when
the polygonal vertices are in a plane. I call it a false normal. A least
square adjustment is an alternative but too expensive. The crude method I
tried it is not fool proof. It takes the barycenters of two disjoint subsets
of the vertices and do a cross product of the vectors from the starting
vertex and the barycenters. Unhappily, this cross product may be near zero
inducing errors later on.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16803.html
Sent from the OpenSCAD mailing list archive at Nabble.com.