Runtime-Efficient Meshing for Piecewise-Linear Complexes

We present a new meshing algorithm to mesh an arbitrary piecewise-linear complex in three dimensions. The algorithm achieves an O(n logΔ + m) runtime where n, m, and Δ are the input size, the output size, and spread respectively. This runtime represents the first non-trivial runtime guarantee for this class of input. The new algorithm extends prior work on runtime-efficient meshing by allowing the input to have acute input angles (called creases). Features meeting at creases are handled with protective collars. A new procedure is given for creating these collars in an unstructured fashion, without the need for expensive size precomputations as in prior work. Output tetrahedra have quality radius-edge ratios in a region away from the “creases”. Adjacent to creases, output tetrahedra have no large dihedral angles. The collar surface dividing these two regions is represented implicitly using surface reconstruction techniques. This new approach allows the algorithm to run in a single pass.