carrier image

A New Constrained Delaunay Tetrahedralization Algorithm

Hang Si

Research Notes, 19th International Meshing Roundtable, Springer-Verlag, October 3-6 2010


19th International Meshing Roundtable
Chattanooga, Tennessee, USA.
October 3-6, 2010

Weierstrass Institute for Applied Analysis and Stochastics, Berlin, Germany.

Constrained Delaunay tetrahedralizations (CDTs) have many optimal prop- erties similar to those of Delaunay tetrahedralizations (DTs) [8, 9]. They are eligible structures for mesh generation. A major task in constructing CDTs is how to recover the domain bound- aries, i.e., edges and faces. At rst hand, one might think it is an easy task since it has been addressed intensively in the literature. Unfortunately, this problem is far from being solved in 3D. Classical engineering algorithms [3, 12, 2] come with no performance guarantee. Their details (involving swaps and point in- sertions) are complicated to realize. On the other hand, CDT algorithms with theoretical guarantees are proposed [6, 7, 11]. The algorithm [11] is available in the program TetGen [10]. In this paper, we present a new algorithm for constructing CDTs for 3- dimensional polyhedral domains. This algorithm is based on our previous one [11]. A new facet recovery algorithm is proposed. It can handle facets which are not exactly planar { a problem ubiquitously exists in engineering data and the use of exact geometric predicates. We distinguish the inconsis- tencies between 2 and 3 dimensional constrained Delaunay simplices. These inconsistencies are removed by facet re-meshing and Steiner point insertions. This algorithm has no complex detail and is easy to implement. It can be extended to handle boundary consists of smoothly curved surfaces.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article