Meshing Piecewise Linear Complexes by Constrained Delaunay Tetrahedralizations

Proceedings, 14th International Meshing Roundtable, Springer-Verlag, pp.147-164, September 11-14 2005

MESHING
RESEARCH
CORNER

14th International Meshing Roundtable
San Diego, CA, USA
September 11-14, 2005

Hang Si and Klaus Gartner
Weierstrass Institute for Applied Analysis and Stochastics, Berlin, Germany
{si, gaertner}@wias-berlin.de

Abstract
We present a method to decompose an arbitrary 3D piecewise linear complex (PLC) into a constrained Delaunay tetrahedralization (CDT). It successfully resolves the problem of non-existence of a CDT by updating the input PLC into another PLC which is topologically and geometrically equivalent to the original one and does have a CDT. Based on a strong CDT existence condition, the redefinition is done by a segment splitting and vertex perturbation. Once the CDT exists, a practically fast cavity retetrahedralization algorithm recovers the missing facets. This method has been implemented and tested through various examples. In practice, it behaves rather robust and efficient for relatively complicated 3D domains.

Download Full Paper (PDF Format)