Titelaufnahme
Titelaufnahme
- TitelFrom Continuous Parametrizations to Discrete Hexahedral Meshes : Reliable Algorithms for a Versatile Pipeline / Hendrik Brückler ; Supervisor: Prof. Dr. Marcel Campen
- Autor
- Gutachter
- Erschienen
- Umfang1 Online-Ressource (xi, 229 Seiten) : Diagramme
- HochschulschriftUniversität Paderborn, Dissertation, 2026
- AnmerkungTag der Verteidigung: 25.02.2026
- Verteidigung2026-02-25
- SpracheEnglisch
- DokumenttypDissertation
- Schlagwörter (GND)
- URN
- DOI
Links
- Social MediaShare
- Nachweis
- IIIF
Dateien
Klassifikation
Zusammenfassung
Hexaedernetze (im Englischen: hex meshes) sind eine stark nachgefragte Repräsentationsform von digitalen volumetrischen Objekten, vor allem für Physik-Simulation. Solche Hexaedernetze zerteilen ein gegebenes Volumen in bündig miteinander abschließende, würfelartige Einheiten. Die Erzeugung solcher Netze für beliebige Eingabevolumina ist ein bekanntermaßen komplexes Problem, für das es bisher keine vollständig zufriedenstellende algorithmische Lösung gibt. Unter der Vielzahl an Lösungsansätzen, haben solche, die auf Volumen-Parametrisierung beruhen, theoretisch das größte Potenzial beliebige Eingaben handhaben zu können und hochqualitative Netze zu erzeugen. Bei solchen Methoden wird das Eingabe-Volumen in eine dynamisch bestimmte 3D-Form transformiert wird, für die ein Hexaedernetz trivial gegeben ist. Die entsprechende Rücktransformation dieses Netzes erzeugt dann ein gültiges Netz im Original-Volumen. Allerdings sind Ansätze dieser Art aufgrund ihrer angestrebten Allgemeingültigkeit besonders komplex, und konkrete Instanzen weisen derzeit eine Vielzahl von Problemen auf, die ihre praktische Anwendbarkeit stark einschränken. In dieser Arbeit werden Algorithmen entwickelt, die als garantiert zuverlässiger Ersatz für fehleranfällige Lösungen aus der bisherigen Literatur dienen. Zusammen ermöglichen sie gängigen Netzerzeugungs-Pipelines, eine wesentlich einfachere Art von Parametrisierungen, kontinuierliche seamless maps, anzustreben, indem sie eine zuverlässige Möglichkeit bieten, diese in die diskreten integer-grid maps zu überführen, die letztendlich zu Hexaedernetzen äquivalent sind. Die Arbeit gliedert sich in drei Hauptteile. Nach der Formalisierung von Netzen und Parametri\-sierungen strebt der erste Hauptteil eine grobe Zerlegung eines gegebenen Eingabevolumens in quaderartige Teilvolumina an. Diese Zerlegungen werden als T-Netze formalisiert, und dienen als Datenstrukturen und Werkzeuge für die Formulierung der nachfolgenden robusten Algorithmen. Im zweiten Teil werden solche T-Netze verwendet, um das komplexe globale Problem—die Umwandlung einer seamless map in eine integer-grid map—durch einfachere, aber äquivalente Stellvertreter-Probleme zu ersetzen. Die beschriebenen, garantiert gültigen Lösungen der einzelnen Stellvertreter-Probleme können dann wieder zu einer global gültigen Lösung zusammengesetzt werden. Entscheidend hierbei ist, dass die algorithmische Komplexität weitgehend von der geometrischen Komplexität des Eingabevolumens und seiner Darstellung entkoppelt wird; stattdessen hängt sie lediglich von der (viel geringeren) Komplexität des groben T-Netzes ab. Im letzten Teil werden Möglichkeiten untersucht, die Vielseitigkeit und praktische Nutzbarkeit der zuvor etablierten Pipeline zu verbessern. Insgesamt schließen die entwickelten Algorithmen zwar nicht alle bestehenden Lücken parametrisierungsbasierter Ansätze, erhöhen jedoch die Erfolgsrate moderner Pipelines erheblich, wie über den Verlauf der Arbeit demonstriert wird. Dabei erzeugen sie Netze von ähnlicher bis höherer Qualität als frühere, fehleranfällige Lösungen—sofern letztere überhaupt gültige Ausgabe erzeugen. Um die Nutzbarkeit der vorgeschlagenen Methodik in Forschung und Anwendungen zu begünstigen, werden Anwendungsmöglichkeiten der vorgeschlagenen Algorithmen über den Rahmen dieser Arbeit hinaus aufgezeigt und Open-Source-Implementationen für alle involvierten Algorithmen veröffentlicht.
Abstract
Hexahedral meshes are the preferred volume discretization in many application domains, most importantly for physically-based simulations. The generation of such meshes for arbitrary input volumes, referred to as \emph{hex meshing}, is a notoriously hard problem for which no fully satisfactory algorithmic solution exists to date. Hex meshing methods based on parametrizations of the input volume offer the greatest potential in terms of input generality and output quality.In such methods the volume is mapped onto a dynamically determined 3D shape, on which a hexahedral mesh is trivially defined. The class of parametrization methods, due to their ambition of providing a truly general solution to hex meshing, is known to be particularly complex, so concrete instances of this class currently suffer from a variety of robustness issues that prevent their reliable application in practice. This thesis develops various algorithms that serve as guaranteed-robust replacements for fragile solutions from prior literature. Together, they provide a reliable way of transforming continuous maps, so called seamless maps, into the discrete integer-grid maps eventually required for hex meshing, so that upstream pipelines can target this much simpler continuous type of maps. The thesis is structured in three main parts. After establishing a general framework for representing meshes and parametrizations, the first main part of the thesis focuses on finding a coarse decomposition of a given input volume into cuboid-like sub-volumes. In analogy to concepts from surface meshing, these decompositions are formalized as volume T-meshes, and serve as both data structures and tools for the formulation of our subsequent robust algorithms. In the second part, such T-mesh volume decompositions are used to replace the complex global problem—of transforming a seamless into an integer-grid map—by simpler but equivalent proxy problems, for which guaranteed-valid algorithmic solutions are described. The solutions of these proxy problems can then be composed back into a global solution. A key factor, contributing to the effectiveness of this approach, is that the algorithmic complexity is largely decoupled from the geometric complexity of the input volume and its representation; instead it depends only on the (much lower) complexity of the coarse T-mesh. The final part then explores ways to further improve the efficiency, versatility and usability of the pipeline established above, while maintaining all robustness guarantees. In total, while not closing all existing robustness gaps of parametrization-based hexahedral meshing, the proposed algorithms vastly increase the success rate of state-of-the-art pipelines, as demonstrated throughout the thesis, while achieving at least similar and sometimes higher levels of result quality, with respect to results produced by prior fragile solutions—provided the latter produce valid output at all. To foster adoption by the community, potential applications of the proposed algorithms beyond the scope of this thesis are pointed out and open source reference implementations for all algorithms are released.
Inhalt
Lizenz-/Rechtehinweis
