Robust Three Dimensional Delaunay Refinement

Proceedings, 13th International Meshing Roundtable, Williamsburg, VA, Sandia National Laboratories, SAND #2004-3765C, pp.145-156, September 19-22 2004

MESHING
RESEARCH
CORNER

13th International Meshing Roundtable
Willimasburg, Virginia, USA
September 19-22, 2004

Steven E. Pav
University of California at San Diego, La Jolla, CA.
spav@ucsd.edu

Noel J. Walkington
Carnegie Mellon University, Pittsburgh, PA.
noelw@andrew.cmu.edu

Abstract
The Delaunay Refinement Algorithm for quality meshing is extended to three dimensions. The algorithm accepts input with arbitrarily small angles, and outputs a Conforming Delaunay Tetrahedralization where most tetrahedra have radius-to-shortest-edge ratio smaller than some user chosen µ > 2: Those tets with poor quality are in well defined locations: their circumcenters are describably near input segments. Moreover, the output mesh is well graded to the input: short mesh edges only appear around close features of the input. The algorithm has the added advantage of not requiring a priori knowledge of the "local feature size," and only requires searching locally in the mesh.

Download Full Paper (PDF Format)