The partitioning of a spatial model into a very large number of small elements is required for solving partial differential equations with the finite element or finite volume method. The generation of such a tessellation is called mesh generation. Solving the partial differential equations allows the simulation of the underlying physical behavior (as for example electrical current and potential).
During the past decade the demand for a robust and rigorous mesh generator for more complex structures has risen in the semiconductor industry. While a three-dimensional simulation was not possible in the beginnings, today's computers have made such a simulation feasible and desirable to be able to account for structure-dependent physical effects. Investigating the state of the art in other fields where three-dimensional mesh generation was applied longer ago is especially important to avoid limitations of earlier approaches and to meet the demands of the semiconductor industry.
The main contribution of this thesis is the development of a mesh generator based on the Delaunay Triangulation. An algorithm was devised to allow for robust mesh generation under finite precision arithmetics without the use of floating point filters. An existing but fairly seldom used Delaunay Triangulation algorithm was extended to work for typical degenerate point sets such as cospherical and cocircular point sets. A sophisticated mechanism avoids the use of fixed epsilon regions which can always be either too small or too large and which would result in a non-robust implementation. An advancing front passes through the desired regions and generates the tetrahedralization. Undesired regions are never meshed, also not temporarily. It is known that structures exist which cannot be tetrahedralized without inserting further points. The generation of a mesh is guaranteed for cases when the advancing front forms such a structure by allowing tetrahedra with negative volume. They are elegantly removed together with other badly shaped elements in a post-processing step. A bucket octree to store the points has proven especially efficient for tetrahedralization with the chosen Delaunay algorithm.
A major part of the work was devoted to the refinement of a general surface triangulation to be integrated into a conforming Delaunay Triangulation. Several techniques such as edge bisection or the orthogonal projection of a triangle vertex onto the opposite triangle edge were tested. Since none of these techniques proved robust enough for the given purpose, a more elaborate solution was devised. The surface triangulation is at first examined for structural edges. Afterwards, local transformations of triangles are combined with a refinement of structural edges. A specially developed system to derive a suitable refinement point (not necessarily by bisection) guarantees the termination of the refinement loop after a minimal number of point insertions. Finally, a triangle-based refinement follows the edge-based refinement. The Voronoi edge which is the dual of a Delaunay triangle is used to derive a refinement point. This allows an additional improvement of the quality of the surface triangles with respect to their aspect ratio and angle. The efficiency of the developed mesh generator is documented with a set of examples.