posted on 1988-09-01, 00:00authored byGary L. Miller, Todd Phillips
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.