5.5.2 Conforming Delaunay Triangulation

A conforming Delaunay Triangulation (RDT) is shown in Fig. 5.3-c. The boundary edges are split into smaller edges by inserting additional points. The refinement of the boundary extends the initial set of vertices. The Delaunay Triangulation of this extended set of points is conform with the boundary edges. All elements satisfy the Delaunay criterion. A key question is how to insert those additional points to ensure that all boundary edges are contained in the Delaunay Triangulation and that the number of required points is minimal [139,59]. It is especially in three dimensions a challenge to avoid overrefinement due to small boundary features. The insertion of points can induce further refinement in other areas and an endless feedback loop can evolve. The problem to guarantee a bound on refinement has not been solved for arbitrary three-dimensional inputs $I$ and one must rely on heuristic techniques [162]. If the facets of $I$ form dihedral angles of no less than $90^{\circ}$ the complexity of the situation alleviates [164,108]. However, for small dihedral angles the heuristics remain to be optimized. A special refining scheme designed for sharp angles often exhibited by semiconductor devices is presented in Section 6.3. It should be noted that due to the lack of existence of a three-dimensional CDT the refinement of the boundary cannot be entirely avoided for any method which aims to integrate a boundary into a Delaunay Triangulation.

One can distinguish two approaches when to perform the refinement of the boundary.

Convex Hull and Segmentation

This is the commonly used approach where a Delaunay Triangulation algorithm is first applied to the points of $I$. This results in a mesh which covers the convex hull. Afterwards follows a refinement to recover the missing edges and facets of $I$. At last a segmentation step is necessary to carve out those parts of the mesh of the convex hull which form the desired tessellation of the geometrical model.

Modified Advancing Front

The boundary refinement precedes the tetrahedralization. It is guided by the Delaunay criterion which is applied to the edges and facets of $I$. The following step is the construction of the Delaunay Triangulation by an incremental search/advancing front style algorithm. The mesh is grown from the boundary as initial front only in regions where it is required (Section 6.4). A mesh which covers the convex hull and the necessary segmentation step is avoided.

Regarding the first approach the location of refinement points is often derived from intersections between the Delaunay Triangulation and the not yet recovered edges and facets. This is not always ideal and a refinement based on geometrical quality measures as for example discussed in the next section is of advantage. The triangulation of a refined edge of $I$ is trivially unique. However, the triangulation of a refined facet of $I$ can be non-unique which complicates the identification and recovery into a three-dimensional Delaunay Triangulation.

Although the second approach seems more obvious and possesses some advantages it is not common at all. This is probably due to three reasons. First, the refinement cannot be based on intersections of the boundary with the Delaunay Triangulation, because it is performed prior to the tetrahedralization. This is not a big disadvantage, because anyhow such a refinement proves to be not ideal for complex inputs in three dimensions as was mentioned above. Second, the advancing front style Delaunay algorithm is not common itself. Its performance depends heavily on the efficiency of the point location. Third, a robust implementation of the advancing front style Delaunay algorithm especially for degenerate cases under finite precision arithmetics is a quite difficult task. Chapter 6 addresses these issues. The developed boundary refinement scheme and the robust implementation of the modified advancing front algorithm combined with a fast point location will be discussed in detail.