FIST: fast industrial-strength triangulation of polygons. We discuss a triangulation algorithm that is based on repeatedly clipping ears of a polygon. The main focus of our work was on designing and engineering an algorithm that is (1) completely reliable, (2) easy to implement, and (3) fast in practice. The algorithm was implemented on ANSIC, based on floating-point arithmetic. Due to a series of heuristics that get applied as a back-up for the standard ear-clipping process if the code detects deficiencies in the input polygon, our triangulation code can only handle any type of polygonal input data, be it simple or not. Based on our implementation we report on different strategies (geometric hashing, bounding volume trees) for speeding up the ear-clipping process in practice. The code has been tuned accordingly, and the CPU-time statistics document that it tends to be faster than other popular triangulation codes. All engineering details that ensure the reliability and efficiency of the triangulation code are described in full details. We also report experimental data on how different strategies for avoiding sliver triangles affect the CPU-time consumption of the algorithm. Our code, named FIST as an acronym for fast industrial-strength triangulation, forms the core of a package for triangulation the faces of three-dimensional polyhedra, and it has been successfully incorporated into several industrial graphics packages, including an implementation for Java 3D by Sun Mircrosystems.
Keywords for this software
References in zbMATH (referenced in 10 articles )
Showing results 1 to 10 of 10.
- Eder, Günther; Held, Martin; Palfrader, Peter: Parallelized ear clipping for the triangulation and constrained Delaunay triangulation of polygons (2018)
- Bos, L.; Calvi, J.-P.; Levenberg, N.; Sommariva, A.; Vianello, M.: Geometric weakly admissible meshes, discrete least squares approximations and approximate Fekete points (2011)
- Huber, Stefan; Held, Martin: Motorcycle graphs, stochastic properties motivate an efficient yet simple implementation (2011)
- Shi, Xinwei; Koehl, Patrice: Adaptive skin meshes coarsening for biomolecular simulation (2011)
- Fernández, José; Tóth, Boglárka; Cánovas, Lázaro; Pelegrín, Blas: A practical algorithm for decomposing polygonal domains into convex polygons by diagonals (2008)
- Lien, Jyh-Ming; Amato, Nancy M.: Approximate convex decomposition of polyhedra and its applications (2008)
- Sommariva, A.; Vianello, M.: Product Gauss cubature over polygons based on Green’s integration formula (2007)
- Lien, Jyh-Ming; Amato, Nancy M.: Approximate convex decomposition of polygons (2006)
- Held, M.: FIST: fast industrial-strength triangulation of polygons (2001)
- Held, Martin: VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments (2001)