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