A Hybrid Method for Triangulation
of Three-Dimensional Domains

Daniel Rypl, Zdeněk Bittnar

Department of Structural Mechanics
Faculty of Civil Engineering
Czech Technical University in Prague
Thákurova 7, 166 29 Prague, Czech Republic


The present paper deals with the discretization of 3D domains into tetrahedral boundary conforming meshes using a hybrid approach based on the combination of the Delaunay triangulation (DT) with the advancing front technique (AFT). 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 DT of the boundary points is obtained using modified Watson's point insertion algorithm. However, the actual appearance of boundary faces in the final triangulation is achieved by proper ordering of point insertion. This is driven by the dependency, represented in the form of oriented graph, of the violation of the empty-sphere property of all boundary faces. The cyclic dependencies (closed loops in the graph) are eliminated via the nodal perturbations, classification of some of the violations as safe and (as the last resort) by forming a new tetrahedron using the AFT. Once all the cyclic dependencies are eliminated, the point insertion process controlled by the dependency graph is started and the constrained DT 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.