Incrementally constructing and updating constrained Delaunay tetrahedralizations with finite-precision coordinates

Constrained Delaunay tetrahedralizations (CDTs) are valuable for discretizing three-dimensional domains with constraints such as edges and polygons. But they are difficult to generate and maintain robustly when finite-precision coordinates yield vertices on a line that are not perfectly collinear and polygonal facets that are not perfectly flat. This work focuses on two key operations, polygon insertion and vertex insertion in CDTs. These operations suffice to incrementally construct and update a CDT from a Delaunay triangulation of the vertices. We experimentally compare two recent algorithms for inserting a polygon into a CDT: a bistellar flip algorithm of Shewchuk (Proc. 19th Annual Symposium on Computational Geometry, June 2003) and a cavity retriangulation algorithm of Si and Gärtner (Proc. Fourteenth International Meshing Roundtable, September 2005). We modify these algorithms to robustly succeed in practice for polygons whose vertices deviate from exact coplanarity. Vertex insertion in a CDT is much more complicated than in a Delaunay tetrahedralization. Adding a single vertex into a CDT may not yield a new CDT. Multiple vertices may need to be inserted together to ensure the existence of a CDT. We propose a new algorithm for vertex insertion. Given a new vertex to be inserted into a CDT, this algorithm adds one or more Steiner points incrementally. It guarantees a new CDT including that vertex.