FIST

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.