Constrained Delaunay Tetrahedrization: A Robust and Practical Approach

We present a numerically robust algorithm for computing the constrainedDelaunay tetrahedrization (CDT) of a piecewise-linear complex, which hasa 100% success rate on the 4408 valid models in the Thingi10k dataset.We build on the underlying theory of the well-known tetgen software,but use a floating-point implementation based on indirect geometric predicatesto implicitly represent Steiner points: this new approach dramaticallysimplifies the implementation, removing the need for ad-hoc tolerances ingeometric operations. Our approach leads to a robust and parameter-freeimplementation, with an empirically manageable number of added Steinerpoints. Furthermore, our algorithm addresses a major gap in tetgen's theorywhich may lead to algorithmic failure on valid models, even when assumingperfect precision in the calculations.Our output tetrahedrization conforms with the input geometry withoutapproximations. We can further round our output to floating-point coordinatesfor downstream applications, which almost always results in valid floating-point meshes unless the input triangulation is very close to beingdegenerate