Boundary recovery for three dimensional conforming Delaunay triangulation

https://doi.org/10.1016/j.cma.2003.12.058Get rights and content

Abstract

We present an efficient boundary recovery method for conforming Delaunay triangulation of three dimensional domains. Our method combines local transformations like edges/faces swappings and modified constrained Delaunay refinement like edges/faces splittings to recover the missing boundary edges and faces. Its convergence is theoretically proved. Its effectiveness is also demonstrated through some meshing examples.

Introduction

Efficient and robust mesh generation is an essential part of many scientific and engineering computational challenges. In the field of unstructured meshing, methods such as Advancing-front, Octree and Delaunay [9], [10], [11], [12], [14], [15], [16], [17] have been extensively studied in the last two decades. In particular, tremendous progress has been made on the theoretical analysis and robust implementation of Delaunay-based methods. Currently, several important issues on Delaunay based triangulations remain under investigation, one of which is on preserving the integrity of the boundary, or in another word, the boundary recovery.

The input data for a Delaunay-based algorithm are often given as a discrete description of the domain boundary which, in the three dimensional space, may represent a surface triangulation of the boundary. Delaunay-based methods usually produce a triangulation that forms the convex hull of the points on the boundary. For an arbitrary domain, such a triangulation may not match with the prescribed boundary surface, i.e., it may not satisfy the constraints (edges and faces in 3D) of the surface triangulation. A problem then arises, namely, how to recover the geometric constraints from the constructed triangulation of the boundary. This problem has been successfully resolved in two dimensional spaces [2], [3]. In three dimensions, due to the Schrondert configuration [14], [15], the existence of a constrained Delaunay triangulation that matches with a prescribed surface triangulation is not guaranteed. George et al. [14] and Weatherill [15] introduced ingenious techniques to reconstruct a prescribed surface triangulation. They recovered the surface edges and faces by a series of edge/face swaps (or flips), and occasional heuristic insertions of interior points (Steiner points). The heuristic procedures have not been proved to work in all cases, as several examples in Baida [13] provided evidences that the above methods may fail in certain situations. Schewchuk [16] and Shephard [17] proposed Delaunay refinement methods to construct a conforming triangulation to match with the surface geometry. Their methods use local mesh modifications such as edge/face splitting to recover a constraint as the concatenation of edges/faces. On one hand, the effectiveness of such kind of conforming boundary recovery has been demonstrated in many cases, even though no theoretical proof is provided for the convergence of these methods. On the other hand, the refinement steps may require the insertion of an excessive number of points to the missing constraints, hence violate the local sizing specification (prescribed by the surface triangulation or by other methods). Moreover, when inserting a point to a constraint in the Delaunay method, the recovered constraints may be deleted in the refinement process.

In this paper, an algorithm is presented which combines local transformations (edge/face swaps) with a modified Delaunay refinement (edge/face splits) to recover the boundary constraints in a conforming manner. As a main objective of this paper, a theoretical proof of the convergence of the method is provided.

The algorithm presented here involves two stages, with the first stage consisting of three basic local edge/face swaps that are applied to recover a portion of the missing constraints. These basic local transformations are not as complicated as those in [14]. For each missing constraint, comparisons are only made between the set of tetrahedra connecting the missing item and the required configurations of the three basic swaps. Whenever a match is found, a corresponding swapping is performed to recover the missing item. Numerical experiments show that these local transformations usually recover almost 80% of the missing constraints. In the second stage, the refinement method is used to recover the remaining missing items. Different from the previous works [16], [17] where one first recovers edges and then faces, the missing faces are recovered sequentially and at the same time, their missing edges are also recovered. For each missing edge of a missing face, the intersection points of the edge with the current triangulation of the boundary points are found, and the nearest-mid intersection points are added one by one in a modified Delaunay insertion procedure until the recovery of the edge is achieved. When the missing edges of a missing face are all recovered, if the face is still missing, the intersection points of the face with the current triangulation are computed and they are inserted one by one into the modified Delaunay insertion procedure until the face is recovered. The modified Delaunay insertion shares the following property: when inserting a point to a constraint, no existing or recovered constraint is deleted.

Regarding our two-stage recovery algorithm, the use of local transformations in the first stage greatly reduces the need for points insertion in the second stage, thus the algorithm not only keeps the boundary recovery simple but also keeps the mesh in good conformation with the local sizing specification. The idea of keeping recovered constraints non-violated, that is, protected, was also addressed by Wright and Jack [19], but the protection method used there only becomes viable by recognizing a consistent node ordering of the faces of the inserted polyhedra, or Cavity [19]. The proposed method given in this paper via the modification of the Delaunay kernel is systematic and applicable for all cases. It can also be easily implemented. Moreover, since the number of missing constraints are finite, the convergence of the boundary recovery procedure becomes an easy consequence. The combination of local transformations and Delaunay refinement method can adequately address the various issues of conforming boundary recovery and also makes the recovery procedure very efficient and effective.

The remaining part of the paper is organized as follows: an overview of our method is described in Section 2 which covers the basic steps of the boundary recovery algorithm. Section 3 discusses the modified Delaunay insertion procedure. Our new recovery algorithm is explained in detail in Section 4. Section 5 presents the convergence proof of the recovery. Some application examples and preliminary comparisons with other recovery schemes are presented in Section 6. Finally, conclusion remarks are given in Section 7.

Section snippets

An overview of the method

Let S be the input surface triangulation of the boundary, which can be generated by various methods [4], [5], [6]. Let P={vertices of S, i.e. the boundary points}  {eight vertices of the bounding box which covers the entire domain}. Denote the Delaunay triangulation of P by Td. Our goal is to modify Td locally and to obtain a triangulation T such that each element of S either exists in T or is the union of a set of triangles of T, and the geometry of the boundary of T conforms with that of S.

Modified Delaunay insertion

Let {Pk} be a finite set of points in Rd and for each k, the Voronoi cell of Pk is the set Vk defined by Vk={p:∥pPk∥⩽∥pPj∥,jk}. {Vk} forms the well-known Voronoi (or Dirichlet) Tessellation of the entire space with respect to the points set {Pk}. The Delaunay triangulation of {Pk} is defined as the dual of the Voronoi Tessellation; see [1], [16] for more details on the properties of Delaunay triangulation.

To construct a Delaunay triangulation of a set of points, the most effective approach

Boundary recovery algorithm

Let S, Td, T be defined as in Section 2. Here, we give a detailed algorithmic description on how to derive a conforming triangulation T from the initial Delaunay triangulation Td.

Three procedures are presented: the initial comparison; the local transformation; and the edge/face splitting for the remaining constraints.

Proof of convergence

Based on the algorithm in the Section 4, we know that our boundary recovery contains two parts: first the local transformation, then the edges/faces splitting.

For the local transformations, it is obvious that the three single step flippings (swappings) do not delete any existing or recovered constraint. Hence, the proof of the convergence of our boundary recovery scheme is reduced to the proof of the convergence of the second part.

In the following, we first prove that adding an intersection

Application examples

Our boundary recovery which combines local transformations (edge/face swapping) with Delaunay refinement method (edges/faces splitting) has been introduced into a complete mesh generation procedure to deal with various geometric models. As some preliminary illustrations, the surface triangulations and the cross-sectional views of their conforming 3D triangulations of four examples, none having interior points, i.e., having only boundary vertices, are presented in Fig. 10, Fig. 11, Fig. 12, Fig.

Conclusions and future works

An efficient boundary recovery algorithm is presented, which combines the local transformations: edges/faces swapping with the Delaunay refinement method: edges/faces splitting. In the splitting of constraints, we modify the Delaunay insertion procedure and guarantee that when inserting an intersection point to a constraint, existing or recovered constraints in the volumetric triangulation will never be deleted. This enhances the efficiency of the algorithm and guarantees the convergence of the

Acknowledgements

The authors would like to thank the referee for valuable suggestions and comments.

References (19)

  • H. Borouchaki et al.

    Fast Delaunay triangulation in three dimensions

    Comput. J. Numer. Methods Engrg.

    (1995)
  • P.J. Frey et al.

    3D Delaunay mesh generation coupled with an advancing-front approach

    Comput. Methods Appl. Mech. Engrg.

    (1998)
  • D.F. Watson

    Computing the n-dimensional Delaunay tessellation with applications to Voronoi polytopes

    Comput. J.

    (1981)
  • H. Borouchaki et al.

    Aspects of 2-D Delaunay mesh generation

    Int. J. Numer. Methods Engrg.

    (1997)
  • N.P. Weatherill

    The integrity of geometrical boundaries in the two-dimensional Delaunay triangulation

    Comput. Appl. Numer. Methods

    (1990)
  • L.P. Chew, Guaranteed quality mesh generation for curved surfaces, in: Proc. 9th Annual Comput. Geom., 1993, pp....
  • S.H. Lo

    Automatic mesh generation over intersecting surfaces

    Int. J. Numer. Methods Engrg.

    (1995)
  • H. Borouchaki et al.

    Parametric surface meshing using a combined advancing-front generalized Delaunay approach

    Int. J. Numer. Methods Engrg.

    (2000)
  • H. Borouchaki et al.

    Optimal Delaunay point insertion

    Int. J. Numer. Methods Engrg.

    (1996)
There are more references available in the full text version of this article.

Cited by (26)

  • Improved boundary constrained tetrahedral mesh generation by shell transformation

    2017, Applied Mathematical Modelling
    Citation Excerpt :

    It is NP complete to predict whether a polyhedron can be tetrahedralized without adding Steiner points [1], and the lower bound of the number of Steiner points is shown to be quadratic [3]. Due to these theoretical difficulties, many heuristic schemes are employed to reduce the number of Steiner points [4–19]. These schemes can be classified into the preprocessing scheme and the postprocessing scheme.

  • Boundary recovery for 3D Delaunay triangulation

    2014, Finite Elements in Analysis and Design
    Citation Excerpt :

    For each Steiner point, a Delaunay triangulation on missing facets is constructed and flat elements of zero volume are created to recover the related topological structure. Du and Wang [14] inserted Steiner points on boundaries through a heuristic approach [20] to reduce the number of Steiner points. They used an edge-swap procedure on the missing boundary facets to remove some of the Steiner points.

  • Adaptive and unstructured mesh cleaving

    2014, Procedia Engineering
  • Three-dimensional constrained boundary recovery with an enhanced Steiner point suppression procedure

    2011, Computers and Structures
    Citation Excerpt :

    A point splitting procedure is then used to move Steiner points away from boundaries. Interestingly, Du and Wang [2] gave a similar suggestion for constrained boundary recovery by first achieving the conformal condition by the insertion of Steiner points [13] and then splitting Steiner points to recover boundaries in a constrained way. Another type of three-dimensional boundary recovery algorithm is constrained Delaunay triangulation of the piecewise linear system [14–18].

  • Constrained Delaunay tetrahedral mesh generation and refinement

    2010, Finite Elements in Analysis and Design
    Citation Excerpt :

    Chazelle [8] showed that a large number of Steiner points may be needed to tetrahedralize a simple polyhedron. A number of engineering methods have been proposed, see e.g., [26,27,54,6,29,25,18,19]. A common feature of these methods is: at first, an initial Delaunay tetrahedralization of the vertex set of a polyhedron P is constructed.

View all citing articles on Scopus

Supported in part by China state major basic research project G199903280 and US NSF-CCR 9988303.

View full text