The triangulation of a polygon is a basic building block for many graphics applications. For instance, high-speed rendering typically relies on polygonal and curved surfaces being subdivided into triangles that can be handled efficiently by the graphics hardware. Triangulating a polygon also is a fundamental operation in computational geometry, and it has received wide-spread interest over the last two decades. Through a series of improvements, the worst-case complexity of triangulating a polygon has been brought down to linear, achieved by Chazelle's seminal algorithm.
Virtually all published triangulation algorithms assume that the polygon is simple, i.e., that the vertices of the polygon are the only points of the plane that belong to two edges, and that no point of the plane belongs to more than two edges. Obviously, the requirement to be simple prevents a polygon from having self-intersections. However, it also excludes so-called "degenerate" situations, such as an edge passing through another vertex, zero-length edges, and edges that partially overlap. Unfortunately, real-world polygons cannot be assumed to be truly simple polygons that are in general position. Rather, real-world polygons tend to exhibit all types of deficiencies, such as self-intersections, or holes that overlap with the outer boundary.
FIST, my code for fast industrial-strength triangulation, can triangulate a multiply-connected polygonal area (in 2D or 3D) defined by one "outer boundary" (closed polygonal loop) and (possibly) several "holes" (closed polygonal loops or points within the outer boundary). In an ideal world, all polygons lie within one plane, are simple, and do not overlap pairwise. Furthermore, all holes lie strictly within their outer boundary. A recursive nesting of the holes is not supported. The orientations and nesting order of the polygons do not matter; FIST determines which polygon forms the outer boundary and assigns appropriate orientations to all polygons.
For 3D polygons, FIST first projects the 3D vertices onto a plane in order to reduce the 3D triangulation problem to a 2D triangulation problem. As far as vertices that are not co-planar are concerned, this does not constitute a problem provided that the projection does not create deficiencies such as self-intersections. FIST uses a fairly reliable heuristic for finding a decent plane. However, as is well-known, the general problem of projecting or triangulating a general 3D polygon in a "nice" way is provably very difficult from a computational point of view. That is, for a general 3D polygon it is not even clear how to define a "correct" triangulation. Granted, a human often has a good intuition of what a "good" triangulation would be. Experience tells me that the heuristics employed by FIST tend to produce "good" triangulations even for problematic data. However, there is no guarantee that FIST will come up with an ideal plane or triangulation if the vertices are highly not co-planar. (Minor deficiencies introduced by the projection typically still do not result in an "incorrect" triangulation.)
If one or several of the pre-conditions on the input are violated - e.g., if polygons overlap or if they have self-intersections - then FIST applies heuristics in order to succeed with computing a triangulation. The bottom line is that FIST will always come up with a triangulation such that
So, what happens if a polygon contains (self-)intersections? Unfortunately, no universally accepted definition for "triangulation of a polygon" exists if the polygon is allowed to be not simple. Personally, I can think of at least three different definitions which will result in strikingly different triangulations being "correct":
Neither of these approaches is trivial to implement, and which one is more desirable depends entirely on the user's needs. In any case, let me clearly state that FIST only supports the first approach, and cannot be extended to support the other approaches! What constitutes a proper triangulation of a polygon that is not simple really is application-dependent.
FIST can handle holes or isolated points within the outer boundary polygon. Starting with FIST 3.5 (April 14, 2006), the presence of holes does no longer constitute an efficiency problem; FIST has been run successfully on data sets that contained tens of thousands of holes! (The largest polygon tested contains 454,196 holes and a total of 7,699,446 vertices.)
FIST is based on repeatedly clipping ears of a polygon. The main focus of my work was on designing and implementing an algorithm that is
The algorithm was implemented in ANSI C, based on floating-point arithmetic. Geometric hashing is used in order to speed up the ear-clipping process in practice. Extensive tests have shown that geometric hashing works well in order to make this approach competitive with (or even faster than) other popular triangulation algorithms that have a better worst-case complexity.
Particular care has been taken in order to make the algorithm reliable. Due to a series of heuristics that serve as a back-up for the standard ear-clipping process if the code detects deficiencies in the input polygon, FIST can handle any type of polygonal input data, be it simple or not. FIST will never crash when applied to polygonal data which has deficiencies. Rather, it will always attempt to generate a meaningful triangulation, and the intuitive "correctness" of the triangulation will gracefully degrade the more the polygon is messed up. Note, though, that FIST will slow down when it has to handle input that has self-intersections.
FIST forms the core of a package for triangulating the faces of 3D polyhedra. FIST can input OBJ files, and can output OBJ and SGO files. A small subset of FIST 1.6 was integrated into Java3D by Sun Microsystems in 1998. However, please note that the current version of FIST is much more powerful than what is provided as part of Java3D. (And even in 1998 the Java-transcribed version of FIST could not rival with FIST concerning both the speed of computation and the quality of the triangulation generated; Sun Microsystems decided to omit important parts of FIST 1.6 from its Java-transcribed version . . .)
I appreciate your interest in FIST. Still, FIST creates quite a bit of email traffic, and you would save yourself and myself time by not asking whether FIST can do anything in addition to what is described above. Let me clearly state that FIST
Financial support and generous hardware grants for this project were provided Sun Microsystems, and by NSF Grant CCR-9504192. A good deal of the work for FIST was carried out while I was with the Computational Geometry Lab of the State University of New York at Stony Brook, Stony Brook, USA. (Work on FIST is an ongoing project, though, and I am still spending a considerable amount of time on extending, improving and maintaining FIST.)
The source code for FIST is available for both academic and commercial use. Indeed, the code has been in wide-spread use, both commercially and within academic research projects. Send me an email and I will let you know the details of how you could use my code. However, in order to avoid any disappointment, let me warn you upfront that FIST has not been released into the public domain!
Recent parts of this research were supported by the Austrian FWF Grant L367-N15.
M. Held, W. Mann
"An Experimental Analysis of Floating-Point Versus Exact Arithmetic".
Proc. 23rd Canadian Conf. on Computational Geometry, Toronto, Canada, p. 489--494, Aug 2011.
M. Held (2001):
"FIST: Fast Industrial-Strength Triangulation of Polygons".
Algorithmica 30(4): 563-596, 2001.
The following images show triangulations computed by means of FIST. (Click on an image icon in order to see the full-size image. The full-size images have 800x800 pixels.)
|A multiply-connected polygonal area with three holes, and its triangulation. The triangulation was computed using "fancy" ear clipping.|
|A simple polygon, and its Constrained Delaunay triangulation. The CDT was computed using Shewchuk's "Triangle" code. The next row of images shows triangulations computed by "sequential", "random", "sorted", and "fancy" ear clipping. The right-most image shows a triangulation computed by Narkhede and Manocha's implementation of Seidel's randomized algorithm.|
|A Sierpinski polygon, and its triangulation. The triangulation was computed using "fancy" ear clipping.|
|A complex star-shaped polygon, and its triangulation. The triangulation was computed using "sorted" ear clipping.|
|A degenerate simply-connected polygonal area, and its triangulation. Note that some of the edges of the polygon overlap. The triangulation was computed using "fancy" ear clipping.|
|A degenerate multiply-connected polygonal area with two holes, and its triangulation. Note that some of the edges of the outer polygon overlap. The triangulation was computed using "fancy" ear clipping.|
|A degenerate simply-connected polygonal area, and its triangulation. Note that some of the edges of the polygon (partially) overlap. The triangulation was computed using "fancy" ear clipping. This triangulation contains zero-area triangles (e.g., where edges overlap or where vertices coincide).|
|A degenerate multiply-connected polygonal area, and its triangulation. Note that some of the edges of the polygon (partially) overlap. The triangulation was computed using "fancy" ear clipping. This triangulation contains zero-area triangles (e.g., where edges overlap or where vertices coincide).|
|A self-overlapping multiply-connected polygon with one hole, and its triangulation. The triangulation was computed using "sorted" ear clipping. Note that a few triangles overlap in 2D! (Please see my comments above on the diverse options for triangulating self-intersecting input prior to telling me that the triangulation is incorrect.)|
|A "multiply-connected" polygonal area with three "not-so-simple" holes, and its triangulation. The triangulation was computed using "sorted" ear clipping. Note that the dual of this triangulation does form a tree. I take votes whether this is the correct triangulation of this area. . . (Again, please see my comments above on the diverse options for triangulating self-intersecting input.)|
|Two different views of a curved polygonal surface (in 3D) triangulated by FIST. Note that the polygonal curve does not lie in a plane.|
|Two different views of a polygonal spiral (in 3D) triangulated by FIST. Note that the polygonal curve does not lie in a plane.|
file last modified: Tuesday, 06-Aug-2013 11:58:46 CEST
Copyright © 2013 Martin Held. All rights reserved.