Fully Incremental 3D Delaunay Refinement Mesh Generation

Proceedings, 11th International Meshing Roundtable, Sandia National Laboratories, pp.75-86, September 15-18 2002

MESHING
RESEARCH
CORNER

11th International Meshing Roundtable
Ithaca, New York, USA
September 15-18, 2002

Department of Computer Science,
Carnegie Mellon University, Pittsburgh, PA 15213.

Abstract
The classical meshing problem is to construct a triangulation of a region that conforms to the boundary, is as coarse as possible, and is constructed from simplices having bounded aspect ratio. In this paper we present a fully incremental Delaunay refinement algorithm. The algorithm is an extension of one introduced by Ruppert. The algorithm is fully incremental in the sense that it does not need any preprocessing to nd an initial Delaunay triangulation or an initial refinement to refine away all encroached simplices of input faces. The paper includes a careful statement of the algorithm, an outline of a proof of correctness even when the input may be degenerate, and bounds on the mesh size. The input angle assumption has been relaxed to arccos (1/2sqrt(2)) (about 70 degrees) for all but dihedral angles.

Download Full Paper (Postscript Format)