A Practical Delaunay Meshing Algorithm for a Large Class of Domains
Cheng, Siu-Wing, Tamal K. Dey, and Joshua A. Levine
Proceedings, 16th International Meshing Roundtable, Springer-Verlag, pp.477-494, October 14-17 2007
16th International Meshing Roundtable
Seattle, Washington, U.S.A.
October 14-17, 2007
Dept. of CSE, HKUST, Hong Kong. Email: firstname.lastname@example.org
Dept. of CSE, Ohio State University, Ohio, USA.
Recently a Delaunay refinement algorithm has been proposed that can
mesh domains as general as piecewise smooth complexes . This class includes
polyhedra, smooth and piecewise smooth surfaces, volumes enclosed by them, and
above all non-manifolds. In contrast to previous approaches, the algorithm does not
impose any restriction on the input angles. Although this algorithm has a provable
guarantee about topology, certain steps are too expensive to make it practical.
In this paper we introduce a novel modification of the algorithm to make it implementable
in practice. In particular, we replace four tests of the original algorithm
with only a single test that is easy to implement. The algorithm has the following
guarantees. The output mesh restricted to each manifold element in the complex
is a manifold with proper incidence relations. More importantly, with increasing
level of refinement which can be controlled by an input parameter, the output mesh
becomes homeomorphic to the input while preserving all input features. Implementation
results on a disparate array of input domains are presented to corroborate
Download Full Paper (PDF Format)
Contact author(s) or publisher for availability and copyright information on above referenced article