Symmetry- and similarity-aware volumetric meshing

Abstract

Die Erzeugung von volumetrischen Gittern spielt eine wichtige Rolle in diskretisierungs-basierten rechnergestützten Entwicklungsprozessen. In diesem Zusammenhang relevante Objekte besitzen oft Symmetrien oder bestehen aus gleichartigen Bausteinen, welche jedoch von Algorithmen zur Erzeugung oder Adaptierung von volumetrischen Gittern bisher nicht berücksichtigt werden, was zu ungenutztem Speicher- und Laufzeitoptimierungspotential führt. Beispielsweise kann bei einem regulären 16-Eck anstelle des Gitters des Gesamtobjekts nur das Gitter eines Tortenecks generiert und gespeichert werden. In diesem Fall ist eine Ersparnis an Speicherbegarf und Laufzeit von einen Faktor 16 zu erwarten, auch wenn die benötigte Zusatzinformation, in diesem Fall die 16-malige Kopie und Rotation des Tortenecks, einen zusätzlichen Aufwand bedeutet. In dieser Arbeit wird untersucht, ob und wie Symmetrien und Ähnlichkeiten bei Erzeugung, Verwendung, und Speicherung von volumetrischen Gittern vorteilhaft genutzt werden können. Im Speziellen werden Auswirkungen und Optimierungen auf den Speicherverbrauch, die Algorithmenlaufzeit, und die Gitterelementqualität analysiert. Zu diesem Zweck wird eine Theorie entwickelt, welche sich mit potentiell mehrfacher Instanzierung von sogenannten Vorlagenstrukturen anhand von geometrischer Transformationen beschäftigt. Die vorgestellte Theorie benutzt einen abstrakten Ansatz, um sowohl Symmetrien als auch andere Ähnlichkeiten zu unterstützen. Zusätzlich werden Mechanismen vorgestellt, welche die Kohärenz der Schnittstellen von verschiedenen Vergitterungsinstanzen sicherstellen. Basierend auf diesen theoretischen Ansätzen werden Datenstrukturen und Algorithmen zum Erzeugen und Adaptieren von Gittern entwickelt. Konkret werden zwei Algorithmen zum Erzeugung von Vorlagengittern vorgestellt und untersucht, welche auch für Spiegelungs- und Rotationssymmetrien sowie deren Kombinationen spezialisiert werden. Zusätzlich wird eine Auswahl von populären Gitteradaptierungsalgorithmen auf deren Benutzbarkeit mit Vorlagenstrukturen untersucht. Die Vorteile der vorgestellten Datenstrukturen und Algorithmen werden in einer Leistungsvergleichstudie untersucht und diskutiert. Für alle zwei-dimensionalen und für die meisten drei-dimensionalen Objekte sind die Verbesserungen beim Speicherverbrauch und in der Algorithmenlaufzeit von der Erzeugung von Vorlagengittern mindestens so hoch wie erwartet. Für drei-dimensionale Objekte mit hoher Rotationssymmetrieordnung sind die Verbesserungen geringer, allerdings mindestens ein Faktor 15. Wenn der Speicherverbrauch der Systemmatrix einer Finite-Elemente-Methode berücksichtigt wird, sinken die Verbesserungen im Speicherverbrauch allerdings sigifikant. Um diese Verluste zu kompensieren, wird eine Datenstruktur für die Systemmatrix entwickelt, welche auf den Konzepten der Vorlagengitter basiert. Die Qualität der Gitterelemente von Vorlagengittern ist in den meisten Fällen mindestens so gut wie die von konventionell erzeugten Gittern und minimal schlechter sonst. Zusätzlich werden die Effekte von symmetrischen und nicht symmetrischen Gittern auf Simulationen basierend auf der Finite-Elemente-Methode untersucht. Wenn das Simulationsgebiet symmetrisch ist, dann ist die mathematische Lösung des Simulationsproblems, bei dem die Randbedingungen des Initialproblem mit der Symmetrietransformation transformiert werden, gleich der transformierten Lösung des Initalproblems. Eine Analyse zeigt allerdings, dass ein symmetrisches Gitter benötigt wird damit, die vorige Aussage auch für die nummerischen Lösungen einer Finite-Elemente-Methode zutrifft.

Volumetric mesh generation plays an important role in computer-aided engineering processes. Often, objects used in computer-aided engineering, for example a gear, show symmetries or similarities. So far, available volumetric mesh generation and adaptation algorithms do not consider symmetries or similarities and thus ignore potential memory and algorithm optimizations. For example, instead of generating and storing a mesh of a regular 16-polygon, the mesh of one single slice can be generated and stored together with the information that this so-called mesh template is copied and rotated 16 times to yield the desired 16-polygon mesh. In this particular case, improvements in memory and algorithm runtime of a factor of 16 are expected. This work investigates how the generation, usage, and storage of volumetric meshes can benefit from symmetries and similarities. In particular, impacts and optimizations in memory usage, algorithm runtime, and mesh element quality are investigated. For this reason, a theory based on so-called templated structures is developed. These templated structures contain mesh templates which are instanced (potentially) multiple times using geometrical transformations to obtain the resulting mesh. The proposed theory uses an abstract approach to support both, symmetries as well as similarities. Furthermore, theoretical mechanisms are developed to tackle potential conformity issues at mesh instance interfaces. Based on these theoretical approaches, data structures and algorithms for adapting and generating templated meshes are developed in this thesis. In particular, two different algorithms for templated mesh generation are proposed and investigated. These algorithms are also specialized for symmetries, being reflective and rotational symmetries and their combinations. Additionally, a selection of popular mesh adaptation algorithms is investigated for their use with templated structures. The benefits of the proposed data structures and algorithms are investigated and discussed in a benchmark-based survey. Expected memory savings and runtime speedups of the templated mesh generation process are indeed achieved for all considered two-dimensional and most three-dimensional objects. For three-dimensional objects with high rotational symmetry orders, the improvements are lower than expected but at least a factor of 15. Memory savings drop significantly when including memory requirements for the system matrix of a finite element method. Therefore, a templated matrix data structure is developed, which compensates these losses. Mesh element qualities of templated meshes are as good as conventionally generated meshes in most scenarios and minimally worse otherwise. Additionally, effects of symmetric and non-symmetric meshes on finite element based simulations are investigated. If the simulation domain is symmetric, the mathematical solution to the boundary value problem with boundary conditions transformed by the symmetry transformation is equal to the transformed solution of the initial problem. However, an analysis shows, that a symmetric mesh is required for this statement to hold for the numerical solutions with a finite element method.