Three Dimensional Boundary Conforming Delaunay Mesh Generation

Abstract

This work is motivated by the aim to support numerical methods to solve partial differential equations. Among them are finite element and finite volume methods. For these, a given domain must first be subdivided into many simple cells. The quality of the subdivision will tremendously affect the accuracy and convergence of the method. A boundary conforming Delaunay mesh is a partition of a polyhedral domain into Delaunay simplices and all boundary simplices satisfy the Gabriel property. It is important in Voronoi-box based finite volume schemes. It allows to carry important qualitative properties from the continuous to the discrete level. In this work, we study meshing problems for the generation of three-dimensional good quality boundary conforming Delaunay meshes. A simple and efficient algorithm to generate boundary conforming Delaunay meshes is Delaunay refinement. Shewchuk's algorithm is reanalyzed, achieving new results on the termination (angle) condition, on the bounds on characteristics of the tetrahedral shape and on the mesh size distribution. In practice, it is observed that this algorithm usually greatly outperforms the proven estimates. Next we propose an adaptive Delaunay refinement algorithm which guarantees the termination for all valid inputs. It is known that not all polyhedra can be tetrahedralized without using additional points (so-called Steiner points). The three-dimensional boundary conforming Delaunay mesh generation problem has many difficulties. An algorithm to construct constrained Delaunay tetrahedralizations is presented. This algorithm adds few Steiner points on the domain boundary. The correctness is proven for an arbitrary valid polyhedral domain. The complexity issues are discussed. It is practically efficient.

Alternate abstract:

Diese Arbeit wird durch das Ziel motiviert, numerische Methoden für die Lösung partieller Differentialgleichungen zu unterstützen. Zu diesen Methoden zählen das Finite-Elemente- und das Finite-Volumen-Verfahren. Um diese zu nutzen, muss ein gegebenes Gebiet zunächst in viele einfache Zellen unterteilt werden. Die Genauigkeit und Konvergenz der Methode wird von der Qualität der Unterteilung stark beeinflusst. Ein randkonformes Delaunay-Gitter ist eine Unterteilung eines polyedrischen Gebiets in Delaunay-Simplices, sodass alle Randsimplices die verallgemeinerte Gabriel-Eigenschaft haben. Diese Bedingungen sind für das Voronoi-box basierte Finite-Volumen-Verfahren wichtig, um wesentliche, qualitative Eigenschaften vom stetigen auf das diskrete Problem zu übertragen. In dieser Arbeit untersuchen wir das Problem der Erzeugung dreidimensionaler randkonformer Delaunay-Gitter mit guter Qualität. Ein einfacher und effizienter Algorithmus, um randkonforme Delaunay-Gitter zu erzeugen, ist die Delaunay-Verfeinerung. Der Algorithmus von Shewchuk wird neu analysiert. Neue Ergebnisse für den Abschluss des Verfahrens in endliche vielen Schritten in Abhängigkeit vom Winkel der Ausgangsgeometrie, für die Grenzen geometrischer Kenngrössen der erzeugten Tetrader und für die Verteilung der Gittergrösse werden erzielt. In der Praxis ist festzustellen, dass dieser Algorithmus gewöhnlich schneller als die bewiesenen Abschätzungen terminiert. Weiterhin schlagen wir einen adaptiven Algorithmus für die Delaunay-Verfeinerung vor, welcher die Terminierung für alle gültigen Eingabegitter garantiert. Es ist bekannt, dass nicht alle Polyeder tetraedrisiert werden können, ohne zusätzliche Punkte (so genannte Steiner-Punkte) einzuführen. Die Erzeugung dreidimensionaler randkonformer Delaunay-Gitter ist mit vielen Schwierigkeiten verbunden. Ein Algorithmus zur Erzeugung eingeschränkter Delaunay-Tetraedrisierungen wird vorgestellt. Dieser Algorithmus fügt wenige Steiner-Punkte am Gebietsrand hinzu. Die Korrektheit wird für ein beliebiges, gültiges polyedrisches Gebiet bewiesen. Fragen der Komplexität werden diskutiert. Der Algorithmus ist praktisch effizient.