Mesh generation for technology CAD in three dimensions

Abstract

Die Zerteilung eines räumlichen Modelles in eine sehr große Zahl kleiner Elemente wird für die numerische Lösung von partiellen Differentialgleichungen mittels der Finiten-Elemente-oder der Finiten-Volumen-Methode benötigt. Die Herstellung solch einer Zerteilung wird Gittergeneration genannt. Das Lösen der partiellen Differentialgleichungen ermöglicht die Simulation des zugrunde liegenden physikalischen Verhaltens (zum Beispiel Stromfluss und elektrisches Potential). In der Halbleiterindustrie stieg während des letzten Jahrzehntes der Bedarf nach einemrobusten und rigorosen Gittergenerator für komplexere räumliche Strukturen. War eine dreidimensionale Simulation in den Anfängen noch undenkbar, so wird sie mit der Rechenleistung heutiger Computer möglich und wünschenswert, um strukturbedingte physikalische Effekte erfassen zu können. Um die Restriktionen anfänglicher Gittergenerations-Methoden zu vermeiden und den Anforderungen in der Halbleiterindustrie gerecht zu werden, ist es besonders wichtig den aktuellen Stand der Forschung anderer Gebiete, in welchen dreidimensionale Gittererzeugung schon länger angewandt wird, mit einzubeziehen. Der Hauptbeitrag dieser Dissertation ist die Entwicklung eines Gittergenerators basierend auf der Theorie der Delaunay-Triangulation. Ein effizienter Algorithmus wurde entworfen, welcher robuste Gittergeneration unter endlicher Rechengenauigkeit und ohne Verwendung von numerischen Fließkommafiltern ermöglicht. Hierzu wurde ein bestehender aber vergleichsweise selten genutzter Delaunay-Triangulations-Algorithmus um die Behandlung von degenerierten Punktmengen, wie etwa kosphärischer und kozirkularer Punktmengen, erweitert. Ein ausgeklügelter Mechanismus vermeidet die Benutzung von fixen Epsilon-Umgebungen, die immer zu klein oder zu groß sein können und in einer nicht robusten Implementation resultieren würden. Eine fortschreitende Front erfasst die gewünschten Gebiete und erzeugt die Tetrahedrisierung. Unerwünschte Regionen werden auch nicht temporär vergittert. Es ist bekannt, dass es Strukturen gibt die nicht tetrahedrisierbar sind, ohne weitere Punkte einzufügen. Um die Herstellung eines Gitters garantieren zu können, auch wenn die fortschreitende Front so eine Struktur formt, werden Tetrahedra mit negativem Volumen erlaubt. Diese werden elegant und gemeinsam mit anderen nachteiligen Elementen in einem Nachbearbeitungsschritt eliminiert. Ein Acht-Baum/octree zur Speicherung der Punkte hat sich in Kombination mit dem gewählten Delaunay-Algorithmus als besonders effizient für dieTetrahedrisierung erwiesen.Ein bedeutender Teil der Arbeit ist der Verfeinerung einer allgemeinen Oberflächen-Triangulation gewidmet, um sie in eine konforme Delaunay-Triangulation zu integrieren. Hierzu wurde mit diversen Methoden experimentiert, wie zum Beispiel der Kanten-Halbierungoder der orthogonalen Projektion eines Dreiecks-Punktes auf die gegenüberliegende Dreiecks-Kante. Nachdem sich keine dieser Techniken als wirklich robust erwiesen hat, wurde eine umfassendere Lösung entwickelt. Die Oberflächen-Triangulation wird zunachst auf strukturelle Kanten untersucht. Im weiteren wird die lokale Transformation von Dreiecken mit der Verfeinerung von strukturellen Kanten kombiniert. Ein speziell entwickeltes System zurAbleitung eines günstigen Verfeinerungs-Punktes (nicht unbedingt ein Halbierungs-Punkt) garantiert die Terminierung der Iterationsschleife nach einer minimalen Anzahl von Verfeinerungen. Auf diese Kanten-basierte Zerteilung folgt letztendlich eine Dreiecks-basierteZerteilung. Dabei wird die zu einem Delaunay-Dreieck duale Voronoi-Kante zur Ableitung eines Verfeinerungs-Punktes herangezogen. Dies erlaubt eine zusätzliche Verbesserung der Qualität der Oberflächen-Dreiecke im Bezug auf Seitenverhältnis und Winkel. Die Effizienz des entwickelten Gittergenerators wird anhand einer Sammlung von Beispielen dokumentiert.

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 ofthe 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. T'he 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.