Fully Incremental 3D Delaunay Refinement Mesh Generation

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 find 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.