Fast Meshing for Acute PLCs

We present a new 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 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 sizing precomputation as in prior work. The collar surface dividing these two regions is represented implicitly using surface reconstruction techniques. This new approach allows the collar to be dynamically generated , allowing the whole algorithm to run in a single pass. For inputs with∆ bounded by a polynomial in n, this runtime is optimal.