Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery

Proceedings, 11th International Meshing Roundtable, Sandia National Laboratories, pp.193-204, September 15-18 2002

MESHING
RESEARCH
CORNER

11th International Meshing Roundtable
Ithaca, New York, USA
September 15-18, 2002

University of California at Berkeley,
Berkeley, CA, U.S.A.
jrs@cs.berkeley.edu

Abstract
In two dimensions, a constrained Delaunay triangulation (CDT) respects a set of segments that constrain the edges of the triangula-tion, while still maintaining most of the favorable properties of ordinary Delaunay triangulations (such as maximizing the minimum angle). CDTs solve the problem of enforcing boundary conformity ensuring that triangulation edges cover the boundaries (both interior and exterior) of the domain being modeled. This paper discusses the three-dimensional analogue, constrained Delaunay tetrahedralizations (also called CDTs), and their advantages in mesh generation. CDTs maintain most of the favorable properties of ordinary Delaunay tetrahedralizations, but they are more difficult to work with, because some sets of constraining segments and facets simply do not have CDTs. However, boundary conformity can always be enforced by judicious insertion of additional vertices, combined with CDTs. This approach has three advantages over other methods for boundary recovery: it usually requires fewer additional vertices to be inserted, it yields provably good bounds on edge lengths (i.e. edges are not made unnecessarily short), and it interacts well with provably good Delaunay refinement methods for tetrahedral mesh generation.

Download Full Paper (Postscript Format)