Next: 5.6 Steiner Points and Up: 5.5 Boundary Integrity Previous: 5.5.1 Constrained Delaunay Triangulation

## 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 and one must rely on heuristic techniques [162]. If the facets of form dihedral angles of no less than 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 . This results in a mesh which covers the convex hull. Afterwards follows a refinement to recover the missing edges and facets of . 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.