Delaunay mesh construction
Ramsay Dyer, Hao Ran Zhang, Torsten Bert Möller · 2007
We present algorithms to produce Delaunay meshes from arbitrary triangle meshes by edge flipping and geometry-preserving refinement and prove their correctness. In particular we show that edge flipping serves to reduce mesh surface area, and that a poorly sampled input mesh may yield unflippable edges necessitating refinement to ensure a Delaunay mesh output. Multiresolution Delaunay meshes can be obtained via constrained mesh decimation. We further examine the usefulness of trading off the geometry-preserving feature of our algorithm with the ability to create fewer triangles. We demonstrate the performance of our algorithms through several experiments.