Keywords: tetrahedral mesh generation, boundary mesh generation, boundary recovery, constrained Delaunay tetrahedralization.

Let be a piecewise linear complex (PLC), i.e., is a set of vertices, together with a set of segments, and a set of facets, each facet is a polygon, possibly with holes, isolated segments and vertices in it; the intersection between elements of is closed. The constrained Delaunay tetrahedralization (CDT) of is a tetrahedralization of with the following properties: (1) each segment of is an edge of the tetrahedralization, each facet of is a union of triangular faces of it; and (2) it is as close as possible to the Delaunay tetrahedralization of . It is known that the CDT of an arbitrary PLC may not exist and the problem of whether a PLC has a CDT is proved to be NP-hard [1]. In this paper, we present a new algorithm for triangulating any PLC into a CDT. This algorithm resembles that of Shewchuk [4] but differs in the creation of the additional points and the recovery of missing facets.

A new simple segment recovery algorithm is proposed. It aims on the recovery of all segments in a Delaunay tetrahedralization without creating too short edges. The basic idea is to use the local geometric information to split a missing segment in such a way that the resulting subsegments are as long as possible. Given a Delaunay tetrahedralization of the vertices of a PLC , the Delaunay segment recovery algorithm recovers all segments of by inserting additional points. It results a new Delaunay tetrahedralization including all segments of as its edges. A missing segment is split by application of one of three rules depending on its type. For a segment containing a sharp corner, a protection sphere sector for the sharp corner will be automatically formed during the execution. We prove the termination of this algorithm by showing that the length of every finally resulting subsegment is bounded by the local feature size [2] divided by constant depending only on . This algorithm has two advantages over other methods for the same purpose: (1) it usually produces meshes without unnecessary short edges; and (2) it handles small input angles automatically - there is no need to preprocess sharp corners. Moreover, its result is a Delaunay tetrahedralization for which the existence of a CDT can be guaranteed [3].

The facet recovery algorithm takes the Delaunay tetrahedralization , which is the result of the Delaunay segment recovery algorithm, reconstructs missing facets of to get a CDT of . This step needs no additional point insertion. A new cavity retetrahedralization method is proposed to transform a set of Delaunay tetrahedra, forming a CDT, into a set of constrained Delaunay tetrahedra.

This algorithm has been implemented in our 3D Delaunay mesh generator - TetGen [5]. The implementation shows this algorithm can be made robust and efficient. We discuss some issues that arise in implementing the algorithm and describe our implementation. Throughout our tests on large amounts of examples, this algorithm produced meshes with a reasonable additional points and edge lengthes. Some results of publicly available examples are included in the paper.

1

J. Ruppert and R. Seidel, "On the Difficulty of Triangulating Three-dimensional Non-convex Polyhedra", Discrete Comput. Geom. 7: 227-254, 1992. doi:10.1007/BF02187840

2

J. Ruppert, "A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation", J. Algorithms 18(3):548-585, May 1995. doi:10.1006/jagm.1995.1021

3

J. R. Shewchuk, "A Condition Guaranteeing the Existence of Higher-Dimensional Constrained Delaunay Triangulations", Proceedings of the Fourteenth Annual Symposium on Computational Geometry (Minneapolis, Minnesota), pages 76-85, 1998. doi:10.1145/276884.276893

4

J. R. Shewchuk, "Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery", Eleventh International Meshing Roundtable (Ithaca, New York), pages 193-204. Sandia National Laboratories, September 2002.

5

H. Si, "TetGen: A 3D Delaunay Tetrahedral Mesh Generator, Version 1.2 User Manual", Technical Report No. 4, Weierstrass Institute for Apply Analysis and Stochastics, 2002.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)