Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery
Shewchuk, Jonathan Richard
Proceedings, 11th International Meshing Roundtable, Springer-Verlag, pp.193-204, September 15-18 2002
11th International Meshing Roundtable
Ithaca, New York, USA.
September 15-18 2002
University of California at Berkeley,
Berkeley, CA, U.S.A.
In two dimensions, a constrained Delaunay triangulation (CDT) respects a set of segments that constrain the edges of the triangulation,
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 (PDF Format)
Contact author(s) or publisher for availability and copyright information on above referenced article