Triangulation of Arbitrary Polyhedra

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Scientific Computation Research Center, Rensselaer Polytechnic Institute, Troy, NY 12180 USA
kaan@scorec.rpi.edu

Abstract
In this study, an algorithm is developed for the triangulation of arbitrary non-convex complex polyhedral regions (cavities) with prescribed boundaries. The boundary of a cavity is specified by a set of triangular mesh faces which bound an empty region. The algorithm is needed for completing the volume meshing process of difficult complex sub-domains. Recovery of the boundary of an arbitrary polyhedra is not an easy task. In some cases recovery of the boundary facets will require inserting extra vertices, but mesh quality and algorithm robustness demand that the number of inserted vertices be kept to a minimum. To address this need, a robust Delaunay algorithm with an efficient face recovery method is the most appropriate approach. The algorithm begins with Delaunay vertex insertion which is followed by a face recovery method that conserves the boundary of the cavity by utilizing local mesh modification operations such as edge split, collapse and swap. The face recovery algorithm takes into account the geometric intersections between the Delaunay mesh of the cavity and the boundary facets. To integrate the cavity mesh into the previously meshed portion of the domain a merging algorithm, which ensures geometrical and topological compatibility, is applied. The algorithm is robust and had been tested against complex manifold and non-manifold cavities.

Although the algorithm is designed to be applicable for difficult sub-domain meshing, the complete volume mesh prescribed by surface triangulation can be meshed by the present algorithm. Therefore, if the model is composed of non-manifold parts, the cavity meshing procedure can be applied consecutively to each non-manifold region represented by triangular surface mesh faces.

The computational tips of 3D Delaunay triangulation are also described in the context to clarify the issues that makes the algorithm robust such as numerical instability, searching the location of to-be inserted vertex and Delaunay degeneracy.