Inhaltszusammenfassung:
Die digitale Abbildung von Objekten aus der realen Welt ist eine zentrale Herausforderung in der Computergrafik.
Dabei wird häufig mit Modellierung gearbeitet, oder aber mit der Rekonstruktion von 3D-Abtastungen, worauf der Fokus dieser Arbeit liegt.
Für gewöhnlich werden die Daten, die durch eine nicht-invasive 3D-Abtastung des Objekts erfasst werden, in Form einer Punktwolke gespeichert.
Diese lose Menge an dreidimensionalen Positionen stellt die Geometrie der abgetasteten Oberfläche nur implizit dar.
Es existiert bereits eine Vielzahl etablierter Verfahren und Methoden, um geschlossene Oberflächen aus dieser Art der Darstellung zu rekonstruieren.
Allerdings haben viele dieser Verfahren auch Schwachstellen:
Sie scheitern unter bestimmten Bedingungen, die Ergebnisse beinhalten Artefakte oder es mangelt an Details in der Rekonstruktion.
Unser erklärtes Ziel ist es, diese Herausforderung auf noch unbetretenen Wegen anzugehen, ohne uns durch bereits existierende Forschung den Blick für bessere Lösungen trüben zu lassen.
So basiert diese Dissertation auf vier Beiträgen, die grundlegenden Neuerungen zum aktuellsten Stand der jeweiligen Forschungsbereiche darstellen.
Unser erstes Verfahren zur Rekonstruktion einer soliden Objekthülle ist in der Lage, Oberflächennetze zu erstellen, die sich allein aus viereckigen Elementen zusammensetzen.
Diese Netze haben eine adaptive Auflösung, welche auf der Abtastdichte der Punktwolke basiert, während sich der Netzfluss entsprechend an der Ausprägung bestimmter Objektdetails orientiert.
Im Kontrast zu anderen gängigen Verfahren benötigt unseres für die Rekonstruktion keine Orientierungsfelder, Parametrisierungen oder Normalen-Information; eine einfache unorientierte Punktwolke genügt bereits als Eingabe.
Dafür wird eine hierarchische Raum-Partitionierungsstruktur verwendet, welche die Punktwolke in kleine, zweckmäßige Regionen aufteilt und als solche bündelt.
Jeweils vier davon werden zu einer viereckigen Kachel zusammengefasst.
Diese Kacheln werden dann der Hierarchie entlang von unten nach oben miteinander verbunden, was letztendlich zu einer komplett geschlossenen Oberfläche führt.
Verfahren zur Erstellung von Netzstrukturen für Volumina setzen neben der standardmäßigen Hülle oft noch weitere Eingabedaten voraus, wie Orientierungsfelder, parametrisierte funktionale Abbildungen, manchmal sogar manuell erstellte Trennebenen, Singularitätsgraphen oder markierte Objektkanten.
Unser Volumennetzverfahren ist dabei in der Lage, die Oberflächenvorberechnung zu überspringen und Hexaeder-Netze direkt von einer Punktwolke zu rekonstruieren, natürlich aber auch von einer Oberfläche, falls diese verfügbar ist.
Des Weiteren führen wir mit diesem Verfahren eine neue generalisierte Netzform ein, die sogenannten Höchstens-Hexaeder-Netze.
Dabei wird das Netz auf Primitive beschränkt, die maximal einem Hexaeder entsprechen oder topologisch kleiner sind.
Auf diese Weise enthält es keine generellen und beliebigen Polyeder, wie es in anderen Hexaeder-dominierten Netzen der Fall ist.
Ein fundamentaler Schritt im Verfahren zur Erstellung dieser Volumennetze ist es, die Hexaeder aneinander, aber auch an der gegebenen Eingabeform, auszurichten.
Dafür wird Lloyds Algorithmus, ein iteratives Optimierungsverfahren, in Kombination mit der L-Unendlich-Norm verwendet.
Die dritte Hauptkomponente der vorliegenden Arbeit befasst sich explizit mit dem Energieterm einer Zelle, den es in einer solchen L-Unendlich-Optimierung zu minimieren gilt.
Dafür werden die Zellen in einzelne Tetraeder zerlegt, um selbige sodann durch eine weitere Dimension für Dichte zu erweitern.
Dies ermöglicht es letztendlich, die L-Unendlich-Energie analytisch zu formulieren und geometrische Schwerpunkte entsprechend herzuleiten.
Darüber hinaus zeigen wir, wie es gelingen kann, Masseneigenschaften mit Tetraeder-Geometrie unter variabler Dichte exakt zu bestimmen.
Auf diese Weise können parametrisierte Dichtefelder nun auch so optimiert werden, dass bei gleichbleibender Geometrie gewünschte Masseneigenschaften erreicht werden.
Dies wird unter anderem an einem 3D-gedruckten Bauteil mit optimierten Rotationseigenschaften demonstriert.
Das vierte vorgestellte Verfahren bezieht sich wieder auf die ursprüngliche Herausforderung, eine Punktwolke möglichst akkurat zu rekonstruieren.
Besondere Anforderungen an Genauigkeit gelten hierbei den sehr feinen Oberflächendetails, scharfen Kanten und einer allgemein hohen Netz-Uniformität.
Dieses hohe Maß an Präzision wird durch eine wachsende Netzstruktur erreicht:
Ausgehend von einer trivialen Startform oder groben Approximation des Zielobjekts, beginnt sich das Netz progressiv der Zielhülle anzunähern.
Das zu rekonstruierende Objekt kann hierbei als volumetrische Funktion, Oberflächennetz oder Punktwolke angegeben werden.
Diese Methode ist zudem dafür geeignet, Verbesserungen an bereits bestehenden Rekonstruktionen vorzunehmen, was wir an Beispielen unserer eigenen Vierecks- und Hexaeder-Netze experimentell aufzeigen.
In der Einführung dieser Arbeit erläutern wir zunächst den thematischen Zusammenhang der einzelnen technischen Verfahren und gehen vertiefend auf die dazu benötigten theoretischen Grundlagen ein.
In den darauffolgenden Kapiteln werden jeweils ein Verfahren, die Motivation dahinter sowie die damit erreichten Ergebnisse detailliert behandelt.
Abschließend werden mögliche Weiterentwicklungen und der gesamtwissenschaftlichen Beitrag dieser Arbeit nochmals zusammenfassend zu diskutieren.
Abstract:
The digital representation of real-world objects is a classical challenge in computer graphics, most commonly approached with either modeling or, where our focus lies, reconstructing the object from a scan.
The information collected during a non-intrusive 3D scan of an object usually gets stored in the form of a point cloud.
This loose set of three-dimensional positions only implies the geometry of the sampled surface.
There is an established collection of different techniques and approaches to actually recover a closed hull from this kind of information.
However, many of those methods still struggle under certain circumstances, produce artifacts, lack detail, or come with other drawbacks.
Our goal is to explore this challenge in novel and unconventional ways rather than increment on existing research.
This thesis is based on four main contributions, each presenting valuable additions to the state-of-the-art in their individual fields.
Our first surface meshing procedure is able to produce pure quad-meshes with adaptive resolution and feature-aligned structures.
In contrast to other standard methods, ours does not require frame-fields, parameterization, or even normal information;
a simple unoriented point cloud is already sufficient as input.
A hierarchical space partitioning structure is utilized to cluster meaningful neighborhoods of the point cloud and interconnect them with quadrangular tiles, using a bottom-up algorithm.
Volume meshing procedures usually require at least a surface and some kind of auxiliary input like frame-fields, parameterized mappings, sometimes even handcrafted split planes, singularity graphs, or annotated feature edges.
Our hex-meshing pipeline is able to skip the surface precomputation step and reconstruct hex-dominant volume meshes directly from point clouds, and naturally also from surfaces if given.
Furthermore, our procedure introduces a novel generalized mesh class, called at-most-hexa meshes:
It constrains the meshes to only feature hexahedral or smaller primitives but no general, larger, and arbitrarily shaped polyhedra as it is common in other hex-dominant meshes.
A fundamental part of this volume meshing procedure is properly aligning hexahedral cells within the given volume, using a Lloyd relaxation under the L-Infinity norm.
Our third contribution allows us to analytically formulate the L-Infinity energy within a cell of the before mentioned relaxation procedure, using tetrahedral geometry extended with a density domain.
Moreover, we propose various other application scenarios of tetrahedral meshes under linearly varying density; like analyzing, optimizing, and even 3D printing such geometry with altered mass properties.
The fourth contribution introduces another installment of a meshing technique in a rather classical sense, focused on accurate surface reconstructions with fine details, sharp features, and an overall high mesh uniformity.
This is realized using a growing mesh complex:
Starting from a small trivial initialization mesh or a rough approximation of the target, the mesh progressively assimilates towards the target hull, which can be given as a volumetric function, mesh or point cloud.
Furthermore, we show how this method can be adapted to improve the reconstruction accuracy of other meshing pipelines, exemplarily demonstrated on our own quad- and hex-meshed results.
Due to the common origin and related fields of research, we first draw the links between the individually proposed contributions in introductory background sections.
Each technique is described and discussed in a dedicated chapter but eventually concluded with a joint discussion on future improvements and achieved results.
point cloud
Print-on-Demand