Keywords: constrained Delaunay triangulation, advancing front technique, boundary recovery process, boundary conformity.

The present paper deals with the discretization of 3D domains based on a hybrid approach using a combination of the advancing front technique and the Delaunay triangulation. The motivation of this approach is to use the merits of both methods and to suppress their drawbacks. The Delaunay triangulation is attractive for its strong mathematical background but the meshes produced are generally not boundary conforming. The advancing front technique is appealing due to its nice point placement strategy but there is no guarantee in 3D that the algorithm will complete. The main objective is to provide a robust and reasonably efficient methodology for the generation of boundary conforming tetrahedral meshes in 3D computational domains defined by many constraining faces of reasonable aspect ratio that might be very closely spaced and of broadly ranging size.

The proposed approach uses the Delaunay triangulation as the core method. However, in order to prevent the costly boundary recovery and to ensure the conformity to the original boundary, the method is modified to either avoid the need to perform the boundary recovery at all or to limit it to a simple topological transformation that can be efficiently accomplished without the need to insert Steiner points. The key idea is to build from the beginning the constrained Delaunay triangulation using the altered Watson's point insertion algorithm. The modification is related to the creation of the cavity by preventing the removal of existing tetrahedra attached to a constraining face on opposite side to the point being inserted. This implies that the use of an in-sphere predicate must be accompanied by an in-plane predicate to reliably ensure that all sides of the cavity are visible from the point being inserted. But this only ensures that the newly inserted point will not violate the boundary conformity of the constraining faces already present in the intermediate constrained Delaunay triangulation. The actual appearance of boundary faces in the final triangulation is achieved by proper ordering of point insertion. This is driven by a dependency graph built on the basis of the appearance of individual constraining faces in the Delaunay triangulation. The violation of a constraining face generally occurs if there is a boundary point inside the smallest sphere circumscribed to that face. This is a very simple criterion. A more precise but also computationally more expensive rule may be adopted. The Delaunay faces, which are those not violated by any boundary point, can be inserted without any problem. Faces violated by any number of points can be safely added if none from those points has been already inserted. This implies that points cannot be inserted if the dependency graph is cyclic. It is therefore necessary to eliminate all cyclic dependencies from the graph. This is performed by point perturbation, by classification of some of the violations as safe, and, as a last resort, by insertion of a new tetrahedron inside the domain (considered, however, as being out of the domain for the purpose of the insertion of the next points) using the advancing front technique. After all cyclic dependencies have been eliminated, the boundary points are inserted using the modified Watson's algorithm following the dependency hierarchy of the dependency graph. In this way, the constrained Delaunay triangulation respecting all constraining faces (including the new ones created together with new tetrahedra) is constructed. This triangulation is then enriched by the insertion of internal points, while preserving all the relevant boundary constraints. The resulting mesh is then obtained by discarding all the tetrahedra out of the domain (except those formed during the cycle elimination process) and by moving all the perturbed points back to their original positions. This 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.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £135 +P&P)