SERGE GOSSELIN
Department of Mechanical Engineering, The University of British Columbia, 2054-6250 Applied Science Lane, Vancouver, British Columbia, Canada, V6T 1Z4, Canada
CARL OLLIVIER-GOOCH
Department of Mechanical Engineering, The University of British Columbia, 2054-6250 Applied Science Lane, Vancouver, British Columbia, Canada, V6T 1Z4, Canada

Received 26 September 2009
Revised 26 July 2010

This article presents an algorithm to construct constrained Delaunay tetrahedralizations of geometric domains bounded by piecewise smooth surfaces. Meshes are built from the bottom-up by first discretizing the boundary curves and then by sampling the smooth surfaces. The sampling procedure refines the Delaunay triangulation restricted to these surfaces, targeting topological violations and poor quality triangles. Unlike previously published algorithms adopting a similar approach, we propose to sample each smooth surface patch independently. This obviates the need for a boundary protection scheme around small dihedral angles in the input and can also lead to coarser constraining triangulations. Starting from a Delaunay tetrahedralization of the point samples, a combination of mesh reconfigurations and vertex insertions is then used to obtain a tetrahedralization constrained to the boundary surfaces. The algorithm is designed to produce tetrahedralizations that can be used in conjunction with a Delaunay refinement algorithm implemented on a Bowyer-Watson framework.

Constrained Delaunay tetrahedralizations; surface sampling Delaunay refinement; mesh generation; quality triangulations