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

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.

2000-01-20