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 . 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.
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.