Triangulation of arbitrary polyhedra to support automatic mesh generators

International Journal for Numerical Methods in Engineering, John Wiley, Vol 49, Num 1, pp.167-191, September 10-20 2000

MESHING
RESEARCH
CORNER

Special Edition on Unstructured Mesh Generation
International Journal for Numerical Methods in Engineering, Vol 49 Number 1-2, 10-20 September 2000

Correspondence to: B. Kaan Karamete, Scientific Computation Research Center, Rensselaer Polytechnic Institute, 110 8th Street, CII Building 7011, Troy, NY 12180, U.S.A.
E-mail: kaan@scorec.rpi.edu

Abstract
An algorithm is presented for the triangulation of arbitrary non-convex polyhedral regions starting with a prescribed boundary triangulation matching existing mesh entities in the remainder of the domain. The algorithm is designed to circumvent the termination problems of volume meshing algorithms which manifest themselves in the inability to successfully create tetrahedra within small subdomains to be referred to herein as cavities. To address this need, a robust Delaunay algorithm with an efficient and termination guaranteed face recovery method is the most appropriate approach. The algorithm begins with Delaunay vertex insertion 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 and a new set of tools which we call complex splits. The local mesh modifications are performed in such a manner that each original surface triangulation is represented either as was, or as a concatenation of triangles. When done in this manner, it is always possible to split the matching mesh entities, ensuring that a compatible mesh is created. The algorithm is robust and has been tested against complex manifold and non-manifold cavities resulting in a valid mesh of the entire domain.