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 einem robusten 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, miteinzubeziehen.
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 die Tetrahedrisierung 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-Halbierung oder 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 zunächst auf strukturelle Kanten untersucht. Im weiteren wird die lokale Transformation von Dreiecken mit der Verfeinerung von strukturellen Kanten kombiniert. Ein speziell entwickeltes System zur Ableitung 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-basierte Zerteilung. 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.