Robust Three Dimensional Delaunay Refinement.

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. Keywords: mesh generation, tetrahedral, unstructured, Delaunay, Ruppert’s Algorithm. 1.