Surface chamfering for robust tetrahedral meshing

We present an algorithm that produces high quality tetrahedral meshes conforming with input polyhedra. Our meshing algorithm is based on Ruppert's Delaunay refinement where convergence is guaranteed thanks to a novel chamfering approach that removes all acute angles from the input. On such a modified input Delaunay refinement produces a Delaunay tetrahedrization where all the faces have bounded angles. The input portions that were removed by the chamfering are re-inserted in this tetrahedrization to achieve exact conformance at the cost of a small number of bad-shaped tetrahedra near the formerly acute input angles. Numerical robustness is guaranteed along all the phases thanks to a clever use of modern indirect geometric predicates and the definition of a new type of implicit point to represent Steiner vertices on the input faces. In practice, our prototype implementation produces meshes having a quality comparable to the state-of-the-art tetgen software: while tetgen fails on 37% of the 3942 valid models in the Thingi10k dataset, our method succeeds on all of them.