Boundary Conforming Discretization
of Three-Dimensional Domains

In this paper, an algorithm for the discretization of 3D domains into tetrahedral boundary conforming meshes is presented. The algorithm is based on the Delaunay triangulation with special point ordering. The conformity of the resulting mesh with the initial triangulation of the domain boundary is ensured a priori thus the boundary recovery postprocessing step is eliminated. The constrained Delaunay triangulation of the boundary points is obtained using modified Watson's point insertion algorithm. The actual appearance of boundary faces in the final triangulation is achieved by proper ordering of point insertion that is driven by the dependency, represented in the form of an oriented graph, of the violation of the empty-sphere property of all boundary faces. The cyclic dependencies (closed loops in the graph) are eliminated by using the nodal perturbations, by classification of some of the violations as safe and (as the last resort) by forming a new tetrahedron using the advancing front technique. Once all the cyclic dependencies are eliminated, the point insertion process controlled by the dependency graph is started and the constrained Delaunay triangulation of the boundary points is built. In the next phase, additional points are inserted in the interior of the domain, while preserving the boundary constraints, to make the elements of appropriate size with aspect ratio close to one. The resulting mesh is then subjected to optimization in terms of the combination of Laplacian smoothing and topological transformations, in order to remove the potential slivers and to improve the overall mesh quality.