Analyse effizienter Algorithmen zur Oberflächenrekonstruktion von Punktwolken

Bachelorarbeit , 2015 , 64 Seiten , Note: 1.7

Ingenieurwissenschaften - Computertechnik

Um reale Objekte unserer Welt einem breiteren Publikum zuzuführen, sie zu sichern und zu analysieren sind zahlreiche Vorgehensweisen entstanden, ihre äußere Erscheinung virtuell zu erfassen.

Bestehende Verfahren zu Digitalisierung von Körpern registrieren die Oberfläche dieser jedoch nicht unmittelbar: Aus den Daten des vermessenden Apparates wird zunächst eine Menge von Punkten im dreidimensionalen Raum erzeugt, die die Außenhülle des jeweiligen Gegenstandes widerspiegelt. Ein Algorithmus zur Oberflächenrekonstruktion wandelt diese Wolke aus Punkten im Folgeschritt in ein Netz aus Dreiecken um, mithilfe dessen die Gestalt des Originals im Erfolgsfall kontinuierlich und effizient angezeigt werden kann.

In dieser Ausarbeitung werden verschiedene Algorithmen vorgestellt, die der Umwandlung einer solchen Punktwolke in eine virtuelle Oberfläche dienen. Da die Punktwolken bei Anwendung moderner Erfassungsapparate sehr viele Elemente enthalten können, werden lediglich solche analysiert, die auch große Mengen von Punkten in annehmbarer Laufzeit verarbeiten
können.

Weiterhin sind Punktwolken nach der praktischen Vermessung häufig regional undicht oder mit Messfehlern behaftet. Dementsprechend wird zu den verschiedenen Verfahren zur Oberflächenrekonstruktion jeweils dargelegt, inwiefern sie zur originalgetreuen Rekonstruktion von mangelhaft registrierten Arealen fähig sind.

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

1 Einführung
1.1 Inhalt der Ausarbeitung
1.2 Aufbau der Arbeit

2 Grundlagen
2.1 Was bedeutet effizient
2.1.1 Beispiel bezüglich der Effizienz eines Algorithmus
2.1.2 typische Laufzeitkomplexitäten
2.2 Die Punktwolke
2.2.1 Definition
2.2.2 Eigenschaften einer Punktwolke

3 Typen von Algorithmen
3.1 Typ A: Algorithmen mit inkrementeller Oberflächenrekonstruktion basierend auf einem Initial-Dreieck
3.2 Typ B: Skulpturierende Algorithmen
3.3 Typ C: Implizite Algorithmen

4 Ball-Pivoting (Typ A)
4.1 Grundprinzip
4.2 2D-Analogie zur Veranschaulichung
4.3 Größe der Detektionskugel
4.4 Suche nach Initialdreieck
4.5 Erweiterung des Dreiecksnetzes
4.6 Ausgabegarantien
4.7 Evaluation

5 Voronoi-Delaunay-basierte skulpturierende Algorithmen (Typ B)
5.1 2D-Analogie
5.2 Das Delaunay-Diagramm
5.3 Vorteilhafte Eigenschaften der Delaunay-Triangulation
5.4 Ein Inkrementeller Flipping-Algorithmus
5.4.1 2D-Flipping-Algorithmus
5.4.2 3D-Flipping-Algorithmus
5.5 Dualität zum Voronoi-Diagramm
5.6 Voronoi-Filtern basierend auf der medialen Achse
5.7 Der Cocone-Algorithmus
5.8 Evaluation

6 Implizite Algorithmen (Typ C)
6.1 Implizite Repräsentation eines 3D-Objekts
6.1.1 Vorzeichenbasierte implizite Repräsentation . .
6.1.2 Konstantenbasierte implizite Repräsentation . .
6.2 Isoflächen-Extraktion
6.2.1 Marching Cubes
6.2.2 Marching-Triangles
6.3 Evaluation

7 Fazit

7.1 Ausblick

Abbildungsverzeichnis

1.1 3D-Beispielpunktwolke

1.2 3D-Beispieloberflächenrekonstruktion

2.1 3D-Punktwolke mit Normalen

2.2 Vergleich von 2D-Punktwolken mit unterschiedlichen Qualitäten

3.1 Punktwolke und eine Beispieltriangulation

3.2 Beispiel für Delaunay-Tetraedisierung

3.3 Schema für implizite Algorithmen

4.1 3D-Ball-Pivoting-Beispielschema

4.2 2D-Ball-Pivoting Konzept

4.3 2D-Ball-Pivoting bei uniformer Punktwolke

4.4 2D-Ball-Pivoting bei nicht-uniformer Punktwolke

4.5 3D-Ball-Pivoting-Ergebnis bei nicht-uniformer Punktwolke

4.6 nicht-uniformer Ergebnisvergleich des Ball-Pivoting-Algorithmus mit unterschiedlichen Detektionsradien

4.7 Ausgabe-Dreiecksnetz des Ball-Pivoting-Algorithmus bei einer Skulptur (108K Punkte)

4.8 Anwendungsbeispiel Ball-Pivoting-Algorithmus bei Skulptur (1M Punkte)

5.1 2D-Punktwolke und deren Delaunay-Triangulation

5.2 Zusammenhänge einer 2D-Punktwolke, Dreiecksumkreisen und der resultierenden Triangulation

5.3 Vergleich der Umkreise von 2D-Dreiecken

5.4 Tetraeder mit Umkugel

5.5 Vergleich einer willkürlichen Triangulation mit einer Delaunay-basierten

5.6 2D-Flipping-Schema

5.7 Lokales 2D-Flipping-Beispiel

5.8 Zerlegung eines Tetraeders bezüglich eines zentralen Punkts ins vier kleinere . .

5.9 Zusammenhang zwischen 2D-Delaunay-Triangulation und Voronoi-Diagramm . .

5.10 2D-Punktwolke und deren Voronoi-Delaunay-Diagramm

5.11 2D-Voronoi-Diagramm und mediale Achse

5.12 Voronoi-Zelle und der Cocone

5.13 Cocone-Ergebnis bei nicht-uniformer Punktwolke

5.14 Ausgabe-Dreiecksnetz des Cocone-Algorithmus bei einer Skulptur (108K Punkte)

5.15 Lokaler Vergleich Cocone und Ball-Pivoting bei Krümmung

5.16 Anwendungsbeispiel Cocone-Algorithmus bei Skulptur (1M Punkte)

6.1 2D-Objekt und vorzeichenbasierte bzw. konstantenbasierte implizite Repräsen- tation

6.2 2D-Schema zur Erzeugung einer vorzeichenbasierten impliziten Repräsentation

6.3 Beispiel für adaptive implizite Approximation mit verschiedenen Tiefen

6.4 Beispiel für Gewichtungsfunktion

6.5 Schema zur Erzeugung einer konstantenbasierten impliziten Repräsentation . .

6.6 Beispieltriangulation mit unterschiedlichen Auflösungen

6.7 Konstellationen eines Marching-Square-Algorithmus

6.8 Annäherung des Randes einer impliziten Repräsentation durch einen Marching- Square-Algorithmus

6.9 Konstellationen eines Marching-Cubes-Algorithmus

6.10 Beispiel für erfolgreiche Marching-Triangles Projektion

6.11 Beispiel für Marching-Triangles Projektionskonflikt

6.12 Implizite Rekonstruktion mit unterschiedlicher Genauigkeit

6.13 vorzeichenbasierte implizite Rekonstruktion mit unterschiedlichen Iso-Werten .

6.14 Nicht-uniforme implizite Rekonstruktion

6.15 Implizite Rekonstruktion bei einer Skulptur (108K Punkte)

6.16 Lokaler Vergleich vorzeichen- und konstantenbasierte implizite Rekonstruktion

6.17 Anwendungsbeispiel Cocone-Algorithmus bei Skulptur (1M Punkte)

7.1 Rekonstruktionsalgorithmen bei nicht-uniformer Punktwolke im Vergleich

7.2 Rekonstruktionsalgorithmen bei Skulptur im Vergleich

7.3 Rekonstruktionsalgorithmen bei Kopf im Vergleich

Tabellenverzeichnis

2.1 Tabelle typischer Laufzeitkomplexitäten

Abstrakt

Um reale Objekte unserer Welt einem breiteren Publikum zuzuführen, sie zu sichern und zu analysieren sind zahlreiche Vorgehensweisen entstanden, ihre äußere Erscheinung virtuell zu erfassen.

Bestehende Verfahren zu Digitalisierung von Körpern registrieren die Oberfläche dieser jedoch nicht unmittelbar: Aus den Daten des vermessenden Apparates wird zunächst eine Menge von Punkten im dreidimensionalen Raum erzeugt, die die Außenhülle des jeweiligen Gegenstandes widerspiegelt. Ein Algorithmus zur Oberflächenrekonstruktion wandelt diese Wolke aus Punkten im Folgeschritt in ein Netz aus Dreiecken um, mithilfe dessen die Gestalt des Originals im Erfolgsfall kontinuierlich und effizient angezeigt werden kann.

In dieser Ausarbeitung werden verschiedene Algorithmen vorgestellt, die der Umwandlung einer solchen Punktwolke in eine virtuelle Oberfläche dienen. Da die Punktwolken bei An- wendung moderner Erfassungsapparate sehr viele Elemente enthalten können, werden lediglich solche analysiert, die auch große Mengen von Punkten in annehmbarer Laufzeit verarbeiten können.

Weiterhin sind Punktwolken nach der praktischen Vermessung häufig regional undicht oder mit Messfehlern behaftet. Dementsprechend wird zu den verschiedenen Verfahren zur Oberflächenrekonstruktion jeweils dargelegt, inwiefern sie zur originalgetreuen Rekonstruktion von mangelhaft registrierten Arealen fähig sind.

Kapitel 1 Einführung

Im Rahmen der fortschreitenden Informationstechnologie sind zahlreiche Ansätze entstanden, reale 3D-Objekte aus unserer Welt originalgetreu zu digitalisieren.

Dies umfasst nicht nur Kulturgut und Fossilien, deren optische Erscheinung so vor natür- lichem Verfall, Kriegen oder Katastrophen sonstiger Art gesichert werden kann. Auch in der modernen Medizin, die computergestützte Tomografie nutzt, besteht Bedarf nach Verfahren, die ein 3D-Abbild der erfassten Körperregionen visualisieren. So können die entsprechenden Fachkräfte beispielsweise bei dem zügigen Erkennen und Prüfen von Körperteilen unterstützt werden.

Zum physischen Erkennen des jeweiligen 3D-Objekts sind heute verschiedene Apparate vorhanden, die in Abhängigkeit von der Beschaffenheit des Körpers und dem verfügbaren Kapital eingesetzt werden. Diese erstrecken sich von handelsüblichen Kameras, Laser-Scannern, Röntgengeräten bis hin zu magnetresonanzbasierten Messtechniken.

Die verbreitet eingesetzten Vorgehen zum physischen Erfassen registrieren die gewünschte virtuelle Oberfläche des Objekts jedoch nicht direkt. Im Allgemeinen ergeben sie optisch perspektivenabhängige 2D-Aufnahmen, 2D-Schnittbilder oder Sammlungen vieler 3D-Messpunkte. Diese Mengen von 3D-Punkten werden im Folgenden als Punktwolken bezeichnet, welche aus 3D-Messpunkten an der Oberflächen des jeweiligen realen Objekts bestehen. Es existieren bereits Methoden, letztere Punktwolken aus vielen 2D-Aufnahmen oder Schnittbildern zu generieren, diese Techniken sind jedoch nicht Gegenstand dieser Arbeit.

1.1 Inhalt der Ausarbeitung

In dieser Ausarbeitung werden Algorithmen präsentiert, die aus jenen Punktwolken virtuelle Oberflächen rekonstruieren können. Die so erzeugte virtuelle Oberfläche besteht dann aus einem Netzwerk von Polygonen, welche sich pro dargestelltem Detail mit geringer Computerleistung anzeigen lassen.

Zudem wird berücksichtigt, dass die modernen physischen Verfahren zur Erfassung der Punktwolken oftmals Millionen oder gar Milliarden 3D-Punkte pro Objekt erzeugen. Es werden

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1: Punktwolke

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.2: Oberflächenrekonstruktion

also nur solche Algorithmen erläutert, bei denen Ausprägungen bzw. Umsetzungen nachweisen, dass diese sich für Punktwolken jener Größenordnung eignen.

Außerdem werden die vorgestellten Algorithmen bezüglich ihrer Eigenschaften analysiert und bezüglich verschiedener Einsatzkriterien evaluiert. Denn die Punktwolke einer Foto-basierten Erfassung hat andere Eigenschaften als die eines Laser-Scanners oder Röntgengeräts. Ebenso stehen bei der Digitalisierung einer Skulptur mit Inschrift andere Merkmale im Vordergrund als bei einer medizinischen Notfallaufnahme.

1.2 Aufbau der Arbeit

Diese Arbeit gliedert sich in sieben Kapitel. Auf die Einführung folgt zunächst eine allgemei- ne Erklärung, was im Kontext der Oberflächenrekonstruktion unter effizient zu verstehen ist. Daran schließt eine elementare Definition der Punktwolke an, die auch praxisbezogene Erfas- sungsproblematiken miteinschließt. Daraufhin werden in Kapitel 3 die bestehenden Verfahren zur effizienten Oberflächenrekonstruktion in Kategorien unterteilt, welche dann jeweils in einem eigenen Kapitel grundlegend erklärt werden. Abschließend werden die Algorithmen zusammen- fassend verglichen.

Kapitel 2 Grundlagen

2.1 Was bedeutet effizient

Der Titel der Arbeit besitzt den Präfix „Analyse und Evaluation effizienter Algorithmen“. In diesem Abschnitt der Ausarbeitung soll beschrieben werden, was im Kontext der Oberflächenrekonstruktion aus Punktwolken unter effizient zu verstehen ist.

Hinsichtlich der Informationsverarbeitung meint Effizienz die Sparsamkeit eines Algorithmus bezüglich der Rechenzeit, die er zur Lösung eines festgelegten Problems beansprucht. Das hier zu lösende Problem besteht in der Rekonstruktion einer virtuellen Oberfläche aus einer einem realem Objekt zugehörigen Punktwolke.

Die Rechenzeit hängt offensichtlich von der Anzahl der 3D-Punkte einer Punktwolke ab. Denn ein zuverlässiger Algorithmus muss jeden der Punkte verarbeiten, um eine originalgetreue virtuelle Repräsentation der Oberfläche zu erzeugen. Zumeist bedeuten mehr Punkte auch mehr Details, was eine adäquate Vorgehensweise zu berücksichtigen hat. Moderne Verfahren zum Erfassen eines 3D-Objekts erzeugen erfahrungsgemäß Punktwolken, die mindestens Millionen Einträge von 3D-Punkten enthalten. Solche mit mehr als eine Milliarde sind aber durchaus auch keine Seltenheit.

Dieser Zusammenhang zwischen der nötigen Rechenzeit und der Mächtigkeit der Punktwolken kann genutzt werden, um die Menge der infrage kommenden Algorithmen einzugrenzen. So lässt sich jedes Vorgehen durch eine Laufzeitkomplexität charakterisieren, die das Verhältnis der Rechenzeit zur Eingabe-Mächtigkeit beschreibt.

2.1.1 Beispiel bezüglich der Effizienz eines Algorithmus

Man nehme an, es existiere ein Algorithmus, dessen Laufzeit quadratisch von der Anzahl zu verarbeitender Punkte abhängt. Verdoppelt man also unter seiner Anwendung die Anzahl der Punkte, so vervierfacht sich die Laufzeit. Dementsprechend verhält sich bei diesem Algorithmus die Menge der auszuführenden Rechenschritte quadratisch zu der Anzahl an Punkten. Denn die Laufzeit eines einzelnen Rechenschritts, wie beispielsweise einer Addition, bedarf bei einem

Computer näherungsweise konstante Zeit.

Pro Rechenschritt benötige die ausführende Rechenmaschine eine Nanosekunde. Dieser Wert liegt bei heutigen Computern nahe, weil deren Taktfrequenz im Bereich von Giga-Hertz liegt. Weiterhin betrage die Anzahl n zu verarbeitender Punkte bzw. die Mächtigkeit der Punktwolke fünfhundert Millionen.

Die approximierte Laufzeit des Beispielalgorithmus errechnet sich nun wie folgt:[Abbildung in dieser Leseprobe nicht enthalten]

2.1.2 typische Laufzeitkomplexitäten

Entsprechend der Beschreibung im Beispiel die Einträge der folgenden Tabelle berechnet worden:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1: Tabelle typischer Laufzeitkomplexitäten

Die Tabelle legt nahe, dass lediglich Algorithmen, die ähnlich rapide wie c oder schneller arbeiten, für große Punktwolken geeignet sind. Demgemäß werden in dieser Arbeit nur Vorge- hensweisen vorgestellt, die mit einer von Laufzeit n × log (n) umgesetzt oder noch zeitsparender ausgeführt werden können. Diese werden im weiteren Verlauf als effiziente Algorithmen bezeich net.

2.2 Die Punktwolke

Entsprechend der Einleitung besteht die Eingabe der vorgestellten Algorithmus in Punktwol- ken. In diesem Abschnitt wird eine präzise Definition dieser dargelegt sowie die individuellen Eigenschaften, die durch das praktische physische Erfassen bedingt sind, beleuchtet. Insbeson- dere werden in den folgenden Analysen und Sektionen der Algorithmen die hier genannten Begriffe vorausgesetzt.

2.2.1 Definition

Eine Punktwolke besteht aus einer gewissen Menge von Punkten. Bei dem Punkt wiederum handelt es sich um einen 3D-Vektor, der also eine x, y und z Koordinate besitzt: P = { (x, y, z) T | x, y, z ϵ R }

Diese 3D-Position charakterisiert eine gemessene Stelle auf der Oberfläche des zugehörigen realen 3D-Objekts. Weiterhin wird sie zumeist mit Farb- oder Texturinformationen angerei- chert.

In der Regel ermöglichen die Verfahren zur physischen Erfassung der Punktwolke zusätz- lich das Registrieren einer weiteren Eigenschaft dieser 3D-Positionen: Ein sogenannter 3D- Normalenvektor besitzt ebenfalls drei Koordinaten. Er beschreibt eine nach außen zeigende Or- thogonale der Oberfläche an der zugehörigen 3D-Position. Diese Normalen besitzen stets eine euklidische Einheitslänge. Viele moderne Algorithmen nutzen diese Zusatzinformation hinsicht- lich der Orientierung der Punkte bezüglich der Originaloberfläche und erfordern Punkte mit Normalen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: 3D-Punktwolke mit Normalen

2.2.2 Eigenschaften einer Punktwolke

In Abhängigkeit des gewählten Verfahrens zur physischen Erfassung des realen Objekts entstehen in der Praxis unerwünschte Abweichungen der Punktwolke.

Weiterhin lassen sich meistens bestimmte Regionen des Objekts nur aufwändig beziehungs- weise spärlich erschließen. Die so entstehenden Punktwolken besitzen dann Ausschnitte, die pro Originaloberfläche des entsprechenden Teil-Areals über deutlich weniger Punkte verfügen. Dies betrifft beim praktischen Registrieren vor allem konkave bzw. nach innen geneigte Teilflächen.

Zu diesen Begebenheiten werden in dieser Sektion Begriffe definiert, welche anhand zweidimensionaler Punktwolken veranschaulicht sind. Zweidimensionale Punktwolken besitzen keine z-Koordinate, jedoch ansonsten analoge Eigenschaften zu dreidimensionalen. Der gelbfarbige Rand soll im 2D-Beispiel die Oberfläche verkörpern.

Uniforme Punktwolken stellen den optimalen Fall dar. Pro Originaloberfläche sind näherungsweise gleich viele Punkte vorhanden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Originalobjekt (a), nahezu uniforme Punktwolke (b), nicht-uniforme Punktwolke (c) und Punktwolke mit Messfehlern (d).

Bei nicht-uniformen Punktwolken dagegen liegen Teilregionen vor, die durch weniger Punkte beschrieben sind. Hierbei wird vom verarbeitenden Algorithmus gewünscht, dass er die Ober- fläche dieser unzureichend charakterisierten Regionen dennoch möglichst originalgetreu rekon- struieren kann.

Jedes physikalische Messgerät hat eine nur begrenzte Genauigkeit, weshalb alle daraus erhaltenen Daten mit einer Messungenauigkeit (Messfehler) behaftet sind. Die bei der physischen Erfassung entstehenden Abweichungen werden hier als überlagerte Störung der Punktwolke bezeichnet. So liegen die betroffenen Punkte nicht mehr auf der Oberfläche, sondern sind jeweils bis zu einem gewissen Abstand verschoben.

Idealerweise haben Punkte, die von der realen Oberfläche vollkommen exponiert sind, kei- nen Einfluss auf das Ergebnis des Algorithmus. Außerdem sollten die Messfehler der Punkte das Verfahren möglichst nicht daran hindern, die virtuelle Oberfläche originalgetreu zu rekon- struieren.

Bezüglich dieser beiden praktisch entstehenden Komplikationen werden die vorgestellten Algorithmen analysiert. Da diese Erschwernisse mit der Qualität der Anlage zur physischen Erfassung gekoppelt sind, legt die entsprechende Vorrichtung auch den einzusetzenden Algo- rithmus nahe.

Weiterhin wird von diversen Quellen empfohlen, die Punktwolke noch vor dem Einsatz der eigentlichen Rekonstruktionsalgorithmen, die in dieser Arbeit beschrieben werden, zu glätten.

Dies kann im Falle detailreicher Punktwolken, die beispielsweise von zuverlässigen Apparaten gescannt worden sind, im Gegenzug aber auch den Verlust feiner Kanten bedeuten.

Kapitel 3 Typen von Algorithmen

Die bestehenden praktisch einsetzbaren bzw. effizienten Algorithmen zur Oberflächenrekonstruktion von Punktwolken lassen sich in drei Kategorien einteilen, zu denen dieser Abschnitt einen Überblick geben soll. Dabei arbeiten diese drei Vorgehensweisen weitgehend divergent. Sie besitzen kaum Gemeinsamkeiten, die übergreifend erklärt werden könnten.

Eine Ausnahme hierzu bildet ihr Resultat, welche aus einem Dreiecksnetz besteht. Die Al- gorithmen verbinden jeweils drei 3D-Punkte zu einem Dreieck, welches bei einer erfolgreichen Ausführung mit anderen derartigen Dreiecken gemeinsame Kanten besitzt. Die so entstehenden Dreiecke dürfen sich hierbei nicht schneiden. In den detaillierteren Erläuterungen der folgen- den Algorithmen können Dreiecksnetze per Definition aber auch lediglich ein einziges Dreieck besitzen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Punktwolke und eine Beispieltriangulation

Verfahren A und B spannen das Dreiecksnetz über die übergebene Punktwolke. Die drei Vertices eines jeden solchen Dreiecks liegen also jeweils auf einem Punkt dieser. Dagegen erzeugt Typ C eine neue verhältnismäßig uniforme Punktwolke, die das reale Ursprungsobjekt repräsentieren soll und ebenfalls durch Dreiecke vernetzt wird.

Die Algorithmen B und C arbeiten global, d. h. sie analysieren zunächst die gesamte Punkt- wolke, bevor sie mit dem Erstellen der einzelnen Dreiecke beginnen. Verfahren A hingegen betreibt die Rekonstruktion lokal und beginnt unmittelbar mit dem erzeugen der Dreiecke.

In den detaillierteren Beschreibungen der Algorithmen gilt folgendes Farbschema: Die einzelnen Punkte der Eingabepunktwolke sind blau gefärbt, Zwischenergebnisse des jeweiligen Algorithmus violett und die Ausgabe-Dreiecke rot. Weiterhin werden aus Übersichtsgründen häufig 2D-Analogien der Punktwolken und der virtuellen Ausgabeoberfläche genutzt. Dabei beträgt die z-Koordinate der 2D-Punkte null und statt der Dreiecke im 3D-Fall werden Kanten als Resultat erzeugt.

3.1 Typ A: Algorithmen mit inkrementeller Oberflächenrekonstruktion basierend auf einem Initial-Dreieck

Hierbei handelt es sich um Verfahren, die zunächst ein anfängliches Dreieck auswählen, das die Initial-Dreiecks-Oberfläche der Rekonstruktion bildet. Ein Dreieck besteht hierbei aus drei Punkten mit Normalen, wobei diese Algorithmen in ihrem Wesen Punkte mit Normalen erfor- dern.

Diese initiale Oberfläche wird im weiteren Verlauf des Algorithmus wiederholt um adjazente Dreiecke erweitert, die stets mindestens eine gemeinsame Kante mit dem bisherigen Dreiecknetz haben. Vereinfacht ausgedrückt wird von jeder äußeren Kante des bisherigen rekonstruierten Dreiecksnetzes einen passenden Punkt gesucht, sodass jene Kante mit diesem Punkt zu einem neuen adäquaten Dreieck verbunden werden kann. Die Kriterien des auszuwählenden Punktes sind seine Position und seine Normale [BERN 1999].

Da es sich im um ein lokales Verfahren handelt, verarbeitet es die Punktwolke rapide. Im Allgemeinen haben Vertreter dieses Typs eine lineare Laufzeitkomplexität. Allerdings reagieren sie sensibel auf nicht-uniforme Punktwolken. Es liegen jedoch propagierte Ansätze vor, diese Erschwernis zu verringern.

Der Ball-Pivoting-Algorithmus, welcher einer Detektionskugel zum Erweitern des Dreiecksnetzes nutzt, besteht als die am präziseste beschriebene sowie öffentlich zugängliche Umsetzung dieser Gruppe und wird in der weiteren Ausarbeitung als Vertreter untersucht.

Weiterhin existieren verwandte moderne Ansätze, die bei der Wahl erweiternder Punkte neben der Position und der Normale ebenfalls die minimale Seitenlänge sowie den maximalen Winkel des so entstehenden Dreiecks miteinbeziehen [LONG 2011].

3.2 Typ B: Skulpturierende Algorithmen

Die skulpturierenden Algorithmen beruhen auf der Vorgehensweise, aus einer bestehenden Dreiecksstruktur bestimmte Dreiecke auszuwählen.

Aufgrund theoretischer Garantien wird oft eine Delaunay-Tetraedisierung als Ausgangs- Dreieckstruktur genutzt [HRAD 2003]. Hierbei wird die konvexe Hülle der Punktwolke nach dem sogenannten Delaunay-Kriterium so in Tetraeder unterteilt, dass jeder 3D-Punkt Eckpunkt eines oder mehrerer Tetraeder ist und sich die Tetraeder lediglich berühren aber nicht schneiden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Ein Ausschnitt einer Delaunay-Tetraedisierung. Hier sind die Tetraeder hell- violett gefärbt, wobei die Dreiecke der Tetraeder, die als Ausgabe-Dreiecksnetz dienen, rot sind. Quelle: http://wias-berlin.de/software/tetgen/examples.html.

Das Delaunay-Prinzip wird im weiteren Verlauf der Ausarbeitung genauer beleuchtet. Bis auf die Tetraeder die an der konvexen Hülle der Punktwolke liegen, hat jeder dieser Tetraeder vier Nachbarn, die jeweils genau eine Dreiecksfläche mit dem jeweiligen Tetraeder teilen.

Da so zunächst die gesamte Punktwolke strukturiert werden muss, stellt dies ein globales Verfahren dar. Dies zeigt sich auch in der Laufzeit, die bei den effizientesten DelaunayTetraedisierungsverfahren in der Größenordnung n × log (n) von der Mächtigkeit der Punktwolke abhängt [MAUR 2002].

In dem diesem Typ gewidmeten Kapitel wird neben der Tetraedisierung erläutert, wie aus dieser jene Dreiecke effizient herausgearbeitet werden können, die eine adäquate Oberflächenrekonstruktion des Originalobjekts bilden.

3.3 Typ C: Implizite Algorithmen

Vertreter dieser Gruppe zeichnen sich durch das Konzept aus, mithilfe der Punktwolke zunächst eine implizite Repräsentation zu erzeugen. Sie besteht meist aus einem Verbund mathematischer Funktionen, die die Oberfläche bzw. das Volumen des Originalobjekts indirekt widerspiegeln.

Nachdem das jeweilige Verfahren diese Repräsentation bestimmt hat, kann das Dreiecks- Netz der Oberfläche mithilfe eines Verfahrens zur Extraktion von Isoflächen bestimmt werden [HRAD 2003]. So bestimmt der Isoflächen-Extraktor nahe der Oberfläche der impliziten Ap- proximation befindliche topologisch benachbarte Vektoren. Diese Positionen mit dem verfah- rensabhängigen Merkmal der Oberflächennähe können dann zu Dreiecken verbunden werden.

Hierbei hat die so angenäherte Oberfläche stets die Eigenschaft, „wasserdicht“ zu seinsie unterteilt den Raum in zwei disjunkte Bereiche.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3: Bei den impliziten Algorithmen wird aus der Punktwolke (a) zunächst eine implizite Repräsentation (b) erzeugt, aus der dann eine Isofläche (c) extrahiert wird.

Bezüglich der impliziten Repräsentation kann zwischen der Vorzeichen-basierten und Konstanten- basierten Unterkategorie unterschieden werden, wobei sich die Bearbeitungsdauer bei den effizi- entesten Ausprägungen proportional zur Anzahl an Punkten verhält [KAZH 2006]. Die Grund- prinzipien etablierter Vorgehensweisen dieses Typs werden in dem entsprechenden Kapitel be- handelt.

Kapitel 4 Ball-Pivoting (Typ A)

In diesem Kapitel wird der bekannteste und am meisten untersuchte Vertreter des Typ A be- schrieben. Es handelt sich um ein inkrementell vorgehendes lokales Verfahren, das aus einer mit Normalen angereicherten Punktwolke eine virtuelle Oberfläche aus Dreiecken generieren kann. Zu Beginn des Algorithmus wird zunächst ein erstes Dreieck gesucht, das das Anfangsdreiecks- netz verkörpert.

Abbildung in dieser Leseprobe nicht enthalten

(a) Beispiel für bestehendes Dreiecksnetz

Abbildung in dieser Leseprobe nicht enthalten

(b) Platzieren der Detektionskugel

Abbildung in dieser Leseprobe nicht enthalten

(c) Rotation um linke Kante

Abbildung in dieser Leseprobe nicht enthalten

(d) Kollision mit Punkt außerhalb des bisherigen Dreiecksnetzes

Abbildung in dieser Leseprobe nicht enthalten

(e) erweitertes Dreiecksnetz

Abbildung 4.1: Dreidimensionales Beispielschema zur Erweiterung eines bestehenden Dreiecksnetzes mit dem Ball-Pivoting-Algorithmus.

4.1 Grundprinzip

Das Grundprinzip des Ball-Pivoting-Algorithmus besteht darin, das in der jeweiligen Iteration bestehende Dreiecksnetz am Rand um adjazente Dreiecke zu erweitern. Dazu wird auf einem zu prüfenden Dreieck, welches mindestens eine Kante am Rand des Netzes besitzt, eine virtuelle Detektionskugel mit einem bestimmten Radius ρ platziert. Diese Kugel wird so positioniert, dass sie die drei Vertices des jeweiligen Dreiecks berührt. Die Nor-malen der Eckpunkte des Dreiecks bestimmen hierbei die Seite. Nun wird die Kugel um eine der Kanten am Rand des Dreiecksnetzes rotiert. Falls sie dabei mit einen passenden Punkt kollidiert, der nicht zum aktuellen Dreiecksnetz gehört, bildet dieser mit der Kante ein neues Dreieck. Hierbei wird der potentiell erweiterbare bzw. zu prüfende Rand mithilfe einer Menge „aktiver“ Kanten verwaltet [BERN 1999].

Abbildung in dieser Leseprobe nicht enthalten

(a) 2D-Punktwolke mit Normalen

Abbildung in dieser Leseprobe nicht enthalten

(b) wählen eines Initial-Dreiecks

Abbildung in dieser Leseprobe nicht enthalten

(c) positionieren der Detek-

Abbildung in dieser Leseprobe nicht enthalten

(d) erweiternde Rotation

Abbildung 4.2: Das Konzept der zweidimensionalen Rotation um einen Punkt wird anhand einer Punktwolke mit Normalen erläutert.

4.2 2D-Analogie zur Veranschaulichung

Aus Übersichtsgründen wird in den folgenden Veranschaulichungen zur Vorgehensweise dieses Algorithmus eine 2D-Punktwolke genutzt, deren Rand rekonstruiert wird. Im Unterschied zur 3D-Ausprägung wird zunächst eine Startkante gesucht, die dem Anfangs-dreieck entspricht. Statt eine Detektionskugel auf einem Dreieck zu platzieren, positioniert das 2D-Verfahren einen Kreis auf einer Kante.

Der Kreis rotiert dann um einen der Punkte dieser. Wenn der Kreis mit einem passenden Punkt kollidiert, so bildet dieser mit dem Rotationsbezugspunkt eine neue Kante. Davon abgesehen arbeitet das Verfahren weitgehend analog zum 3D-Verfahren.

Abbildung in dieser Leseprobe nicht enthalten

(a) Beispielablauf bei uniformer Punktwolke

Abbildung in dieser Leseprobe nicht enthalten

(b) Beispielablauf bei Punktwolke mit lokaler

Punktdichtedifferenz

Abbildung 4.3: (a) Die Kugel startet rechts oben am Objekt, rollt es entlang und nimmt die detektierten Punkte auf. (b) Beispiel des Verhaltens des Algorithmus, falls die Kugel sich als zu groß für bestimmte Details der Punktwolke entpuppt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.4: (a) Das nahegelegte Vorgehen zur Triangulation nicht-uniformer Punktwolken: Zunächst (1) werden feinere Details mit einem kleineren Radius ρ festgehalten. Dann wird der Algorithmus ein weiteres Mal mit einem vergrößerten Radius durchgeführt (2). Würde die nicht uniforme Punktwolke unmittelbar mit dem größeren Radius trianguliert, so gingen Details zwischen dem Absatz und der Front des Schuhs verloren.

4.3 Größe der Detektionskugel

Zunächst wird ein Radius ρ für die sogenannte Detektionskugel des Ball-Pivoting-Algorithmus gewählt, welcher während eines Durchlaufs des Verfahrens konstant bleibt. Dieser Radius hängt primär von zwei Faktoren ab [BERN 1999]: Das erste Kriterium besteht in der mittleren Dichte der Punktwolke und das zweite in dem kleinsten Detail, das der Algorithmus erfassen soll. Beispielsweise kann für nahezu uniforme Punktwolken das Anderthalbfache des mittleren Abstands topologisch benachbarter Punkte gewählt werden.

4.4 Suche nach Initialdreieck

Zu Beginn des Algorithmus oder auch falls das Dreiecksnetz bzw. die bisherig erstellten Teilnetze keinen geeigneten Punkt zum erweitern des Netzes finden und es noch Punkte gibt, die zu keinem Teilnetz gehören, wird ein Initial-Dreieck gesucht. Eine simple Methode zum Finden dieses Start-Dreiecks wird beschrieben [BERN 1999]:

Man bestimme zunächst einen Punkt σ i, der noch kein Teil des bereits erstellten Triangulations- Netzes ist. Dann werden alle Paare von Punkten σ a, σ b in einem definierten Nachbarschaftsra- dius aufsteigend nach ihrem Abstand zu σ i sortiert nacheinander betrachtet. Nun wird geprüft, ob die Normalen dieser drei Punkte konsistent sind, das Skalar-Produkt ihrer Normalen also einen nutzerdefinierten positiven Schwellwert nicht unterschreitet. Dieser Schwellwert hängt von der Dichte der Punktwolke und der Kurvigkeit des 3D-Objekts ab. Dann wird kontrolliert, dass die Detektions-Kugel des Radius ρ, die die Punkte σ i, σ a und σ b berührt, keine Punkte enthält.

Wenn ein Dreieck gefunden worden ist, das diese Bedingungen erfüllt, wird gestoppt. Die Kanten dieses Dreiecks bilden die ersten Elemente einer Menge „aktiv“ markierter, die noch nicht durch eine Rotation einer Detektionskugel auf Erweiterbarkeit geprüft worden sind. In den folgenden Iterationsschritten werden diese aktiven Kanten untersucht und darauf aus jener Menge entfernt [BERN 1999].

4.5 Erweiterung des Dreiecksnetzes

Die iterative Kern-Methode besteht darin, eine Detektions-Kugel mit dem Radius ρ so auf einem der unverarbeiteten Dreiecke am Rand des jeweiligen Dreiecksnetzes zu platzieren, dass sie die drei Vertices berührt. Diese Kugel enthält zunächst keinen Punkt, da es sich bei dem Dreieck entweder um ein Initialdreieck handelt oder sie durch die Rotation der Detektionskugel entstanden ist.

Die Normalen der drei Vertices bestimmen hierbei auf welcher Seite des Dreiecks die Kugel sich zu Beginn befindet. Dann rotiert die Kugel um die aktive Kante bzw. eine der aktiven Kanten, die am Rand des zu erweiternden zusammenhängenden Dreiecksnetzes liegen, wobei sie dabei ständig in Berührung mit den Vertices der jeweiligen Kante bleibt. Während dieses Umlaufs werden diejenigen Punkte mit Normale geprüft, die mit dem Umlauf der Kugel kollidieren. Falls die Kugel auf keinen solchen Punkt trifft, markiert der Algorithmus die jeweilige Kante als Außengrenze.

Wenn die Kugel mit einem Punkt kollidiert, der nicht bereits Teil des Dreiecksnetzes ist, bildet dieser mit der entsprechenden aktiven Kante ein neues Dreieck. Diese Rotationskante wird aus der Menge aktiver Kanten entfernt, während die anderen beiden Kanten des neuen Dreiecks zu den aktiven Kanten hinzugefügt werden. Eine Kugel mit dem Radius ρ, die auf den drei Vertices des so entstandenen Dreiecks liegt, enthält keinen Punkt. Denn die Rotationskugel auf den drei Vertices des benachbarten Dreieck, dessen Kantenrotation das neue Dreieck erzeugt hat, hat ebenfalls keinen Punkt enthalten [BERN 1999]. Zudem wird bei der Rotation um die Kante unmittelbar mit dem ersten Kollisionspunkt ein neues Dreieck gebildet.

4.6 Ausgabegarantien

Das Verfahren garantiert ein Ausgabe-Dreiecksnetz, das topologisch äquivalent zum Original 3D-Objekt ist, sofern folgende Bedingungen erfüllt sind: a) Der Schnitt einer jeglichen Kugel des Radius ρ mit der Punktwolke bildet topologisch eine Scheibe - d. h. alle Punkte innerhalb dieser Kugel liegen auf einer Ebene. b) Jegliche Kugel mit einem Radius ρ, dessen Zentrum auf der topologischen Oberfläche der Punktwolke liegt, enthält mindestens einen Punkt.

Hierbei sagt a) aus, dass die Kugel auch durch Krümmungen des Objekts wandern kann, ohne die Oberfläche der Punktwolke mehrfach zu berühren - die Punkte in konkaven Regionen also undicht genug für die Detektionskugel sind. b) hingegen erfordert, dass die Dichte der Punkte stets so groß ist, dass eine Kugel nicht ins Innere des 3D-Objekts gelangen kann, ohne vorher mit einem Punkt zu kollidieren. Zusammenfassend erfordert der Ball-Pivoting- Algorithmus also gleichmäßig-dichte Punkte pro Originaloberfläche bzw. eine relativ uniforme Punktwolke [BERN 1999].

Wenn es sich jedoch um eine nicht-uniforme Punktwolke handelt, wird nahegelegt, zunächst den Algorithmus mit einem geringerem Radius ρ die Feinheiten der Punktwolke erfassen zu lassen. Darauf kann nochmals das Verfahren mit einem größeren Radius angewendet werden, um entstandene Lücken zu schließen. Bei solchen Punktwolken mit großer Varianz der Dichte von Punkten pro Originaloberfläche sind auch nach mehrmaliger Anwendung häufig Zwischenräume zu sehen.

4.7 Evaluation

Der Algorithmus ist mit verschiedenen Punktwolken unterschiedlicher Größe und Grad an Uniformität getestet worden. Hierbei kann die konkrete Laufzeit kaum bewertet werden, da sie eine sehr große Varianz in Abhängigkeit der Eingabe-Punktwolke und den genutzten Detektionsradien aufweist. Selbstverständlich besteht ebenfalls eine zeitliche Komponente in der Qualität des genutzten Quellcodes.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.5: Nicht-uniforme Punktwolke mit 76.268 Einträgen (a) und das Ergebnis der Ball-Pivoting-Rekonstruktion mit (b) bzw. ohne betonte Dreiecksränder (c).

Das Füllen der erwähnten Zwischenräume mit einer kontinuierlichen Oberfläche wird als nicht-triviale Aufgabe angesehen, weil hierzu die sonstige Oberfläche des Objekts global geprüft werden muss. Zwar nimmt der Algorithmus stark exponierte Punkte, die durch die Wahl der Detektionsradien bedingt unerreichbar sind, nicht in die Triangulation auf, jedoch besitzt er keinen Mechanismus, sonstige Störungen zu erkennen.

Andererseits wird somit dafür gesorgt, dass der Algorithmus möglichst wenig eigene Interpretation in die Rekonstruktion der Punktwolke miteinfließen lässt. Sofern beispielsweise bei der Rekonstruktion von Kulturgut lediglich objektiv erfasste Punkte in das Dreiecksnetz aufgenommen werden sollen, kann diese Eigenschaft durchaus wünschenswert sein.

Ein Nachteil dieses Verfahrens besteht darin, dass die Detektionsradien in der Praxis meist manuell gewählt bzw. erprobt werden müssen. Alternativ kann auch eine große Menge verschiedenartiger Radien genutzt werden, wobei dies die Laufzeit um ein Vielfaches verlängert. Zudem führen sehr große Detektionsradien nicht selten zu Artefakten.

Dagegen arbeitet der Ball-Pivoting-Algorithmus bei nahezu uniformen Punktwolken, bei denen die Wahl adäquater Detektionsradien sehr viel leichter fällt, in der Regel zuverlässig.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.6: Fein abgestufte Detektionsradien mit oberer Grenze (a) im Vergleich zum Erstversuch mit gröberen Abständen (b) bei nicht-uniformer Punktwolke.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.7: Ausgabedreiecksnetz (209.851 Dreiecke) des Ball-Pivoting Algorithmus bei einer Punktwolke mit 108.706 Punkten (a) aus verschiedenen Perspektiven (b, c).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.8: Ausgabedreiecksnetz (1.913.313 Dreiecke) des Ball-Pivoting Algorithmus bei einer Punktwolke mit 1.180.497 Punkten (bitte zoomen).

Kapitel 5 Voronoi-Delaunay-basierte skulpturierende Algorithmen (Typ B)

In diesem Kapitel werden Methoden vorgestellt, welche die virtuelle Oberflächenrekonstruktion der Punktwolke durch Filtern der Delaunay-Kriterien genügender Dreiecke betreiben. Dazu wird über die Punkte zunächst eine Delaunay-Tetraedisierung gespannt, wobei jeder Tetraeder vier Vertices aus der Punktwolke besitzt. Bis auf die am Rand liegenden berühren alle so entstehenden Tetraeder vier Nachbarn, mit denen sie jeweils ein Dreieck als Seitenflä-che teilen. Eine solche Delaunay-Tetraedisierung enthält als Untermenge Dreiecke sich topolo-gisch angrenzender Punkte, die bezüglich der Originaloberfläche Nachbarpositionen zueinander darstellen. So bildet diese beschränkte Triangulation eine vollständige virtuelle Oberflächenre-konstruktion der Punktwolke. Das Delaunay-Kriterium sorgt hierbei dafür, dass diese Dreiecke grafisch vorteilhafte Eigenschaften besitzen.

Allerdings enthält die Tetraedisierung zusätzlich unerwünschte Dreiecke, welche von denen der zur Originaloberfläche korrespondierenden getrennt werden müssen. Zu deren nicht trivialer Erkennung kommt das zur Delaunay-Diagramm duale Voronoi-Diagramm zum Einsatz, das weitere Information über die Struktur der Punktwolke bietet.

Im weiteren Verlauf dieses Kapitels werden zunächst das Delaunay-Kriterium für Dreiecke und die Dualität zum Voronoi-Diagramm beleuchtet. Zudem wird ein moderner Algorithmus gezeigt, der eine Delaunay-Tetraedisierung robust und effizient erzeugen kann. Daraufhin besteht der Fokus darin, zu zeigen, wie mithilfe des Voronoi-Diagramms auf den Verlauf der zu rekonstruierenden Oberflächen geschlossen werden kann.

5.1 2D-Analogie

Da sich die Delaunay-Triangulation im zweidimensionalen Raum bis auf bestimmte Umset- zungsdetails analoge Eigenschaften zur 3D-Delaunay-Tetraedisierung besitzt, wird hier aus Übersichtsgründen zunächst die 2D-Triangulation beschrieben. Die Dreiecke in der 2D-Delaunay- Triangulation entsprechen dabei den Tetraedern der 3D-Delaunay-Tetraedisierung und die Kanten in der 2D-Triangulation den Dreiecken der 3D-Tetraedisierung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.1: Eine zweidimensionale Punktwolke (a) und deren Delaunay-Triangulation (b).

Dementsprechend enthält das 2D-Delaunay-Diagramm der Punktwolke neben den Kanten, die eine adäquate Rand-Rekonstruktion bilden, weitere, die erkannt und entfernt werden müs- sen.

5.2 Das Delaunay-Diagramm

Bei dem 2D-Delaunay-Diagramm handelt es sich um eine Vernetzung von 2D-Dreiecken zu einer 2D-Punktwolke, sodass der Kreis, der auf den 2D-Vertices des Dreiecks liegt, keinen 2D-Punkt verinnerlicht [DELA 1934]. Dieser jeweils eindeutige Kreis wird im Folgenden als Umkreis des Dreiecks bezeichnet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.2: Zusammenhänge einer zweidimensionalen Punktwolke (a), den Umkreisen der Dreiecke (b) und der resultierenden Triangulation (c).

Diese Umkreisbedingung führt dazu, dass der kleinste Innenwinkel des jeweiligen Dreiecks maximiert wird, da so der Umkreis besonders klein ausfällt. Die Innenwinkel des Dreiecks sind also gleichmäßiger in der Größe. Denn bei sehr ungleichmäßigen Innenwinkeln bzw. sehr spitzen Dreiecken nimmt der Umkreis deutlich größere Maße an, sodass er tendenziell andere 2D-Punkte der 2D-Punktwolke enthält.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.3: Vergleich der Umkreise eines Dreiecks mit ähnlich großen Innenwinkeln und eines mit ungleichmäßigen.

Falls sich weniger als vier Punkte auf einem solchen Umkreis befinden, handelt es sich um eine eindeutige Delaunay-Triangulation. Andernfalls können beliebige Konstellationen zwischen den vier oder mehr Punkten zur Bildung eines Dreiecks gewählt werden, solange die sonstigen Dreiecke der Triangulation entsprechend angepasst werden [MAUR 2002].

Bei der 3D-Delaunay-Tetraedisierung liegt nicht eine Umkreisbedingung der Dreiecke vor, sondern ein Umkugel-Kriterium bezüglich der einzelnen Tetraeder. Dementsprechend darf die Umkugel eines Tetraeders keinen anderen Punkt der Punktwolke enthalten.

Dies schließt das zirkuläre Kriterium im Bezug auf die Seitenflächen des jeweiligen Tetraeders mit ein, da dessen Umkreise im dreidimensionalen Raum die Kugel berühren.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.4: Ein Tetraeder mit Umkugel.

5.3 Vorteilhafte Eigenschaften der Delaunay-Triangulation

Die Maximierung des minimalen Innenwinkels eines jeden Dreiecks führt zu computergrafisch gewünschten Eigenschaften. So werden spitze Dreiecke vermieden, die zu Rundungsfehlern in der grafischen Anzeige führen bzw. die Rechenzeit verlängern können. Zur Veranschaulichung wird eine Beispiel-Punktwolke auf zwei Weisen trianguliert. Hierbei berücksichtigt nur eine das Delaunay-Kriterium, während die andere die Punkte willkürlich durch sich berührende Dreiecke verbindet. Es befinde sich weiterhin ein zusätzliches Dreieck topologisch unter dem Dreiecksnetz. Der anzeigende Computer hat nun zur Aufgabe, zu bestimmen, welche Regionen des unten liegenden Dreiecks verdeckt werden und welche im Vordergrund anzuzeigen sind.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.5: Vergleich einer willkürlichen Triangulation (a) mit einer Delaunay-basierten (b).

Offensichtlich muss der verarbeitende Algorithmus im Fall der willkürlichen Triangulation zumeist eine größere Anzahl unmittelbar über dem halbverdeckten Dreieck liegender Dreiecke prüfen. Weiterhin wird das Dreieck unter der willkürlich triangulierten Punktwolke von mehr Kanten und schmalen Dreiecken bedeckt, welche leichter zu Fehlberechnungen führen.

5.4 Ein Inkrementeller Flipping-Algorithmus

Im folgenden Abschnitt wird ein detailreicher Algorithmus beschrieben, der eine Delaunay- Triangulation bezüglich einer 3D-Punktwolke erstellen kann. Für das Grundverständnis der skulpturierenden Algorithmen ist diese konkrete Umsetzung entbehrlich, aber sie zeigt, dass die zu Beginn des Kapitels beschriebene Triangulation basierend auf einer beliebigen Punktwolke erzeugt werden kann.

Bei dem hier beschriebenen Verfahren handelt es sich um einen inkrementellen Flipping- Algorithmus. Dieser basiert darauf, zunächst ein künstliches Dreieck im zweidimensionalen Raum bzw. einen Tetraeder im dreidimensionalen Raum zu erstellen, der die gesamte Punkt- wolke umspannt. Die Punkte der Punktwolke werden dann inkrementell hinzugefügt und ver- arbeitet [MAUR 2002]. Das Prinzip dieser Vorgehensweise wird zur Übersicht zunächst im zweidimensionalem Raum erläutert, verhält sich aber im dreidimensionalen aber weitgehend analog.

5.4.1 2D-Flipping-Algorithmus

Zunächst wird ein beliebiges Dreieck über die 2D-Punktwolke gespannt, das sämtliche Punkte verinnerlicht. Danach werden die Punkte inkrementell in das im jeweiligen Schritt bestehende Dreiecksnetz eingearbeitet. In jedem solchen Schritt erfüllen alle Dreiecke des Dreiecksnetzes das Delaunay-Kriterium bezüglich der bisher hinzugefügten Punkte. Am Ende des Algorithmus werden die zusätzlichen umspannenden Punkte sowie alle Dreiecke, die diese Punkte als Vertices besitzen, entfernt [MAUR 2002].

Dasjenige Dreieck, das im jeweiligen Verarbeitungsschritt den inkrementell hinzugefügten

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.6: Schema des Flipping-Prinzips: In die bestehende Triangulation (a) wird ein Punkt eingefügt (b). Das zentrale Dreieck, in dem sich der Punkt befindet, wird unterteilt (c). Darauf führt das Verfahren an den Kanten der drei zentralen Dreiecke, deren Umkreise andere Punkte enthalten, eine Flip-Operation durch (d).

2D-Punkte verinnerlicht, wird in drei neue Dreiecke zerlegt. Dazu verbindet die Flipping- Methode die Kanten dieses Dreiecks mit dem jeweiligen 2D-Punkt. Darauf prüft die Vorge- hensweise die so entstehenden Dreiecke lokal bezüglich des Delaunay-Kriteriums. Dementspre- chend werden die Nachbardreiecke des jeweiligen neuen Dreiecks untersucht, die mit dem neuen Dreieck eine gemeinsame Kanten haben. Bei diesen Nachbardreiecken wird ermittelt, ob der Umkreis des jeweiligen neuen Dreiecks den nicht-gemeinsamen Vertex verinnerlicht.

Falls dem so ist, wird das Delaunay-Kriterium verletzt und es findet zwischen diesen beiden Dreiecken eine sogenannte Flip-Operation statt: Sie entfernt die gemeinsame Kante der beiden Dreiecke und bildet stattdessen eine neue Kante zwischen den Vertices, die nicht Teil der eliminierten Kante sind.

Wenn eine Flip-Operation stattfindet, müssen alle Dreiecke, die mit den beiden betroffenen Dreiecken eine gemeinsame Kante besitzen, hinsichtlich des Delaunay-Kriteriums lokal geprüft werden. Eine Flipping-Operation kann also viele weitere zufolge haben, jedoch ist bewiesen, dass dies keine Endlosschleife zur Folge haben kann [MAUR 2002].

Falls sich ein zu verarbeitender 2D-Punkt auf einer Kante befindet, werden beide Dreiecke, die diese Kante umfassen, in zwei statt in drei Dreiecke geteilt. Der weitere Ablauf erfolgt jedoch analog.

Das Verfahren endet erst, nachdem alle Punkte der 2D-Punktwolke verarbeitet worden sind.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.7: Lokales Flipping am Beispiel zweier Dreiecke. Der Umkreis des linken Dreiecks enthält den Punkt p. Daher wird auf die gemeinsame Kante eine Flip-Operation durchgeführt..

Alle Dreiecke, die einen künstlichen Hilfsvektor als Vertex haben, werden dann entfernt.

5.4.2 3D-Flipping-Algorithmus

Analog zum 2D-Flipping-Algorithmus wird zuerst nach dem Tetraeder gesucht, der den zu verarbeitenden Punkt enthält oder schneidet. Falls der betroffene Tetraeder den Punkt verinnerlicht, wird er in vier kleinere Tetraeder geteilt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.8: Zerlegung eines Tetraeders, der den inkrementell hinzugefügten Punkt enthält, in vier kleinere. Zur Übersicht wird pro Bild einer der neuen Tetraeder hinzugefügt.

Wenn der Punkt dagegen auf einer Dreiecksfläche liegt, werden beide Tetraeder, die dieses Dreieck gemeinsam haben, in drei Tetraeder zerlegt. Sofern der Punkt auf einer Kante liegt, werden alle der tangierten Tetraeder in zwei Tetraeder unterteilt. Hierbei handelt es sich um den schlimmsten Fall des Algorithmus: Es kann theoretisch n-viele Tetraeder geben, die diese Kante gemeinsam haben. Wenn dieser Fall in Abhängigkeit zu n sehr häufig eintritt, kann das Verfahren theoretisch eine Laufzeit von O(n ³ ) besitzen. Weil dies aber auch bei großen realen Punktwolken überaus unwahrscheinlich ist, wird dieser schlimmste Fall vernachlässigt. Lediglich ein einziger Punkt, der genau auf einer Kante eines Tetraeders liegt, stellt bei der praktischen Anwendung eine Seltenheit dar.

Die durch die Teilung entstandenen Tetraeder werden ebenfalls auf das Delaunay-Umkugel- Kriterium bezüglich der Nachbar-Tetraeder geprüft. Falls die Umkugel eines solchen Tetraeders den nicht-gemeinsamen Vertex eines Nachbar-Tetraeders enthält, wird versucht, eine Flip-Operation durchzuführen.

Diese verhält sich allerdings im dreidimensionalen Raum wesentlich komplexer: Dort liegen dann drei Konstellationen mit verschiedenen Umkugeln vor, die unter bestimmten Bedingungen umgewandelt werden können. Es sei A der betrachtete Tetraeder, in dessen Umkugel sich ein nicht-gemeinsamer Vertex des Nachbar-Tetraeders B befindet [MAUR 2002].

Konstellation 1: Die Tetraeder A und B bilden gemeinsam eine Pyramide, deren Grundfläche

ein ebenes konvexes Viereck verkörpert. Hierbei kann mit der gemeinsamen Kante, die innerhalb des Vierecks diagonal verläuft, wie im 2D-Verfahren eine Flip-Operation durchgeführt werden. Sämtliche Tetraeder, die diese Kante gemeinsam haben, müssen entsprechend der Operation abgeändert werden.

Konstellation 2: Die Tetraeder A und B bilden einen Doppel-Tetraeder, wobei die Kante zwischen den beiden nicht gemeinsamen Vertices innerhalb des Doppel-Tetraeders verläuft und keine der Flächen schneidet. Es bezeichne a den nicht-gemeinsamen Vertex von A, b den nicht gemeinsamen Vertex von B und c, d, e die gemeinsamen Vertices. Die Tetraeder A und B können dann in die Tetraeder C, D, E geteilt werden: C umfasst so die Vertices a-b-c-d, D die Vertices a-b-c-e und E die Vertices a-b-d-e.

Konstellation 3: Diese drückt die Inversion der Konstellation 2 aus. Falls Tetraeder A, B und ein gemeinsamer Nachbar-Tetraeder X die Vertices a-b-c-d-e so umfassen, dass aus ihnen ein Doppel-Tetraeder entsprechend der Ausgangs-Konstellation 2 gebildet werden kann, werden sie umgewandelt. Alle mithilfe dieser Operationen modifizierten Tetraeder werden in eine Warteschlange eingefügt, die sequentiell jeden der Tetraeder auf das lokale Delaunay-Umkugel- Kriterium, welches sich auf Nachbar-Tetraeder beschränkt, prüft.

Zusammenfassend besitzt diese Delaunay-Tetraedisierung eine praktische Laufzeitkomplexität von O(n × log (n)) [MAUR 2002].

5.5 Dualität zum Voronoi-Diagramm

Die Delaunay-Triangulation verkörpert einen dualen Graphen zum Voronoi-Diagramm. Dieses kann ohne ins Gewicht fallende Laufzeit aus der Triangulation gewonnen werden. Hierbei bestehen die Ecken der einzelnen Voronoi-Zellen aus den Umkreismittelpunkten der Dreiecke der 2D-Delaunay-Triangulation bzw. den Zentren der Umkugeln der 3D-Delaunay- Tetraedisierung [AURE 1991].

Zur Bildung der 2D-Voronoi-Kanten werden die Umkreismittelpunkte benachbarter 2D- Dreiecke, die eine gemeinsame Seite besitzen, verbunden. Im 3D-Falle ergeben sich die 3D- Voronoi-Kanten entsprechend durch Verknüpfen der Zentren der Umkugeln benachbarter Tetraeder, die eine gemeinsame Seitenfläche besitzen. Eine 2D-Voronoi-Kante steht stets senkrecht zu ihrer dualen Dreiecksseite, während eine 3D-Voronoi-Kante orthogonal zu ihrem dualen Tetraeder-Seitenfläche orientiert ist.

Bei dem Voronoi-Diagramm handelt es sich um eine mathematische Struktur. Die Kanten der Voronoi-Zelle markieren dabei eine euklidische Entfernungs-Begrenzung: So besitzt jede Zelle ein Zentrum und umfasst alle Positionen, die dem jeweiligen Zentrum näher sind als sämtlichen sonstigen Zentren [AURE 1991].

Äußere Kanten des Diagramms, die entlang der einen Richtung keine weiteren schneiden, besitzen eine unendliche Länge. Im 2D-Falle liegt der Winkel solcher Voronoi-Kanten jeweils

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.9: Aus einer zweidimensionalen Delaunay-Triangulation (a) und den Zentren der Umkreise (b) wird ein Voronoi-Diagramm (c) erstellt. Eine einzelne Voronoi-Zelle (d) besteht hierbei aus den Verbindungen der Umkreiszentren benachbarter Dreiecke, die zum zentralen Punkt der Zelle adjazent sind.

orthogonal zur Randkante des Dreiecks, dessen Umkreismittelpunkt den Ursprung der VoronoiKante bildet. Dementsprechend erstrecken sich die äußersten 3D-Voronoi-Kanten orthogonal zur außen liegenden Seitenfläche des Tetraeders, der das entsprechende Umkugel-Zentrum am inneren Ende der Kante definiert.

5.6 Voronoi-Filtern basierend auf der medialen Achse

Bei hinreichend dichten Punktwolken ist die eingeschränkte Delaunay-Triangulation dieser homöomorph zur Originaloberfläche. Das heißt, dass die Menge der Dreiecke, welche dual zu den Voronoi-Kanten sind, die die Originaloberfläche schneiden, eine topologisch äquivalente Rekonstruktion der Originaloberfläche bilden [Dey 2001].

In der folgenden Sektion wird eine effizientes Verfahren erläutert, das diese beschränkte Delaunay-Triangulation aus dem Voronoi-Delaunay-Diagramm herausfiltert. Das Grundprinzip der Methode zur Identifikation der Voronoi-Kanten, die die Oberfläche

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.10: Eine zu rekonstruierende zweidimensionale Punktwolke (a) und deren Delaunay-Voronoi-Diagramm (b). Die Voronoi-Kanten sind grau gefärbt.

der Punktwolke schneiden, beruht auf der Approximation der medialen Achse des zu rekonstruierenden Objekts.

Hierbei wird die mediale Achse als Schließung aller Positionen des Raums definiert, die mehr als einen nächsten Punkt auf der Oberfläche haben. Bei hinreichend dichten Punktwolken kann diese durch die jeweils kürzeren Kanten länglicher Voronoi-Zellen angenähert werden [DEY 2001].

Abgesehen von den Spitzen dieser medialen Achse verläuft die Originaloberfläche nähe- rungsweise parallel zu den entsprechenden Abschnitten der medialen Achse. Diese Methode zur Identifikation der Voronoi-Kanten, die die Oberfläche schneiden, nutzt diesen Zusammenhang. So geht sie davon aus, dass bei besonders länglichen Voronoi-Zellen die kürzeren Kanten an der medialen Achse liegen, während die längeren Kanten entsprechend die Oberfläche kreuzen.

Zur Extraktion der Dreiecke, die zu den die Originaloberfläche schneidenden Voronoi-Kanten

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.11: Die geschätzte mediale Achse des Ursprungsobjekts (a) und die der medialen Achse entsprechenden Voronoi-Kanten in violetter Färbung.

dual sind, wird für jeden kontinuierlichen Abschnitt der angenäherten medialen Achse zunächst ein geeignetes Start-Dreieck gewählt. Ausgehend von diesem wird nach Nachbar-Dreiecken gesucht, deren duale Voronoi-Zellen ähnlich orientiert sind. Entsprechend werden entlang des jeweiligen stumpfen Teilabschnitts der medialen Achse zur Originaloberfläche äquivalente Dreiecke extrahiert. Im Idealfall treffen sich diese bei den Spitzen der medialen Achse adäquat mit denen benachbarter flacherer Teilabschnitte [DEY 2001].

Hierbei verhält sich diese Vorgehensweise weitgehend unempfindlich gegenüber einer varia- blen Punktedichte pro Originaloberfläche. Für eine erfolgreiche Rekonstruktion einer Punktwol- ke ist für dieses Verfahren vielmehr entscheidend, dass pro Oberflächenkrümmung ausreichend Punkte vorhanden sind. Denn nur so kommt es auch in detailreichen Regionen zu den weitge- hend erforderlichen länglichen Voronoi-Zellen, die den Verlauf der Oberfläche vermitteln.

5.7 Der Cocone-Algorithmus

Bei dem Cocone-Algorithmus [DEY 2001] handelt es sich um ein einzigartiges effizientes Ver- fahren, das mithilfe des Delaunay-Voronoi-Diagramms und der approximierten medialen Achse zu einer praktikablen Oberflächenrekonstruktion von Punktwolken fähig ist. Um die höheren Voronoi-Zellen zu identifizieren, deren längere Kanten die Oberfläche schneiden, werden diese charakterisiert.

Der eindeutige Punkt innerhalb der Voronoi-Zelle wird im Folgenden als Voronoi-Punkt p bezeichnet. Beim sogenannten Pluspol handelt es sich um den am weitesten entfernten Vertex der jeweiligen Voronoi-Zelle im Bezug zum Voronoi-Punkt p. Falls die Zelle unbegrenzt ist, wird die Richtung des Pluspols als Durchschnitt aller Kanten unendlicher Länge festgelegt. Der Minuspol ist der am weitesten entfernte Vertex der jeweiligen Voronoi-Zelle der entgegengesetz- ten Seite des Pluspols zu p. Weiterhin verkörpert der Polvektor die Strecke vom Punkt p zum Pluspol. Bei der Höhe der Voronoi-Zelle handelt es sich um die Distanz zwischen Minuspol und

p.

Der sogenannte Cocone stellt das Komplement eines Doppelkegels innerhalb der jeweiligen Zelle dar, dessen Spitzen sich bei p treffen. Es sei y eine Position innerhalb der Voronoi-Zelle, dann ist der Cocone: ∠ (y e Voronoi-Zelle: (y − p), Polvektor) ≥ 3/8 π. Der Radius der Zelle wird als Maximum der Entfernung einer beliebigen Position innerhalb dieses Cocones zum Voronoi-Punkt p definiert [DEY 2001].

(a) (b)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.12: Visualisierung einer zweidimensionalen (a) und einer dreidimensionalen

Voronoi-Zelle (b). Der sogenannte Cocone ist grün eingefärbt.

Basierend auf den obigen Definitionen identifiziert der Algorithmus zunächst längliche Voronoi- Zellen, die sich durch eine große Höhe in Relation zum Cocone-Radius auszeichnen. So wird bei diesen davon ausgegangen, dass die längeren Kanten dieser Zellen die zu rekonstruierende

Oberfläche schneiden. Zudem wird geprüft, ob die benachbarten Voronoi-Zellen, die den Cocone

der betrachteten Zelle berühren, einen ähnlich gerichteten Pol-Vektor besitzen. Wenn dem so ist, werden jeweils zu jenen Voronoi-Kanten, die den Cocone schneiden, die dualen Dreiecke ermittelt und zu einer Menge von Kandidatendreiecken hinzugefügt.

Bei der eigentlichen Rekonstruktion läuft der Algorithmus dann über diese Kandidaten- dreiecke und wählt dann solche aus, die zum Rand des bisherigen Dreiecksnetzes passen. Zu stumpfen Abschnitten der medialen Achse entsprechende Teilregionen werden so jeweils ver- bunden und treffen sich an gegebenenfalls vorhandenen Kanten der Originaloberfläche [DEY 2001].

In der Praxis unterteilt das Verfahren die Punktwolke zunächst räumlich in überlappende Unter-Punktwolken, auf die jeweils das Verfahren angewendet wird. So muss kein globales Delaunay-Diagramm gebildet werden, womit sich die Laufzeit verringert und weniger Rundungsfehler vorkommen.

5.8 Evaluation

Auch der präsentierte Cocone-Algorithmus ist mit Punktwolken unterschiedlicher Dichte getestet worden. Aufgrund des Delaunay-Prinzips werden auch stark exponierte bzw. fehlerhafte Punkte in die Triangulation aufgenommen. Weiterhin sind keine adäquaten Mechanismen beteiligt, fehlende Bereiche der Punktwolke zu approximieren.

Dementsprechend entstehen bei diesem Verfahren zwar keine Lücken bei der Rekonstruktion einer Oberfläche, jedoch werden Bereiche mit geringer Punktedichte durch auffallend große Dreiecke verbunden. Diesbezüglich wäre eine Nachbearbeitung durch einen Algorithmus denkbar, der eine implizite Repräsentation aus dem resultierenden Dreiecksnetz bildet und dabei die Flächeninhalte der einzelnen Dreiecke als Gewichte berücksichtigt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.13: Nicht-uniforme Punktwolke mit 76.268 Einträgen (a) und das Ergebnis der Cocone-Rekonstruktion mit (b) bzw. ohne betonte Dreiecksränder (c). Laufzeit: 119,44 Sekun- den.

Davon abgesehen besitzt er jedoch verhältnismäßig starke mathematische Garantien bezüglich der Qualität des Ausgabe-Dreiecksnetzes, sofern die Punktwolke durchgängig dicht genug beschaffen ist, um längliche Voronoi-Zellen hervorzurufen. Außerdem kann die Eigenschaft, dass dieser Algorithmus keine Normalen beansprucht, von hohem Wert sein.

Da die zugrundeliegende Delaunay-Triangulation, sofern nicht mehr als vier Punkte auf der Umkugel eines Tetraeders liegen, eindeutig ist und sich die Laufzeitkomplexität dieses Verfahrens nicht linear verhält, sind für die dargelegten Tests Zeitmessungen vorgenommen worden (2.30GHz duo, 16 GB RAM).

Falls lokal pro Oberflächenkrümmung nicht genug Punkte vorhanden sind, um die längli- chen Voronoi-Zellen zu erzeugen, werden innere Punkte konkaver Regionen eventuell nicht in das Ausgangsdreiecksnetz aufgenommen (siehe Abbildung 5.15). Es wird jedoch betont, dass die eigentliche Dreiecksextraktion bei nicht-uniformen Punktwolken durchaus eine hohe imple- mentierungsabhängige Varianz zwischen den verschiedenen Umsetzungen aufweist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.14: Ausgabedreiecksnetz (177.934 Dreiecke) des Cocone Algorithmus bei einer Punktwolke mit 108.706 Punkten (a) aus verschiedenen Perspektiven (b, c). Laufzeit: 75,12 Sekunden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.15: Lokaler Vergleich zwischen Cocone Algorithmus (a) und Ball-Pivoting Algorithmus (b) bei Punktwolkenbereich mit hoher Oberflächenkrümmung pro Punktdichte.

Bei hinreichend dichten Punktwolken erzeugt dieser Algorithmus aber in der Regel hochwertige und objektive Resultate.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5.16: Ausgabedreiecksnetz (2.198.804 Dreiecke) des Cocone Algorithmus bei einer Punktwolke mit 1.180.497 Punkten (bitte zoomen). Laufzeit: 938,11 Sekunden.

Kapitel 6 Implizite Algorithmen (Typ C)

In diesem Kapitel werden Algorithmen vorgestellt, die aus der Punktwolke des zu rekonstruierenden Objekts zunächst eine implizite Repräsentation erzeugen, welche das Volumen bzw. die Oberfläche indirekt beschreibt. Im Gegensatz zu den im vorherigen Teil der Arbeit vorgestellten Kategorien sind zahlreiche effiziente Ausprägungen dieses Typs vorhanden, die eine adäquate Rekonstruktion ermöglichen.

Hierbei besteht die implizite Repräsentation meist aus einem Verbund mathematischer Funktionen. In Abhängigkeit eines beliebigen Positionsvektors lässt sich nun mithilfe der Funktionen approximieren, ob sich dieser innerhalb oder außerhalb des so approximierten 3D-Objekts befindet. Aus der so geschaffenen Annäherung kann mithilfe eines Verfahrens zur IsoflächenExtraktion ein Dreiecksnetz generiert werden [HRAD 2003]. Der Iso-Flächen-Extraktor sucht hierbei nach topologisch benachbarten Positionen auf der approximierten Oberfläche der impliziten Repräsentation und bildet daraus Dreiecke.

Ein Vorteil dieses Typs liegt darin, dass ohne zusätzliche Verarbeitungsschritte analog zu einer Vektorgrafik die Feinheit des Dreiecksnetzes, das die extrahierte Oberfläche als Ausgabe verkörpert, beliebig modifiziert werden kann. Wird also eine detailreichere Darstellung verlangt, können durch das Verändern der Parameter des Isoflächen-Extraktors schlicht mehr Dreiecke pro Originaloberfläche extrahiert werden.

Vor allem für die Entwicklung und das Ausdrücken der impliziten Repräsentation liegen zahlreiche Umsetzungen vor.

Es bestehen auch solche, die durch Betrachtung jeweils benachbarter Punkte die Norma- len an einer bestimmten Position dynamisch approximieren. Solche Ansätze führen aber nur bei uniformen Punktwolken zu akzeptablen Rekonstruktionen. Eine entsprechende Randgruppe dieser Algorithmen nutzt das sogenannte Splatting [KOOB 2004]: Hierbei werden Kugeln bzw. Ellipsen an den Positionen der Punkte platziert und solange vergrößert, bis sie mit benach- barten Punkten kollidieren. Diese Vorgehensweise wird hier nicht weiter beschrieben, da sie so gleichmäßig dichte Punktwolken erfordert, dass die simpleren expliziten Verfahren bereits nahezu optimale Resultate erzeugen würden. Zudem kann dieses Verfahren als vereinfachte Form der vorzeichenbasierten impliziten Repräsentation betrachtet werden, welche im weiteren

Verlauf der Arbeit genauer analysiert wird.

Die moderneren Ansätze, welche auch durch erhöhte Robustheit geprägt sind, nutzen jedoch in der Regel Punkte mit vorab bekannten Normalen.

Zur Isoflächen-Extraktion liegen ebenfalls verschiedene Methoden vor, die sich in Ausgabequalität und Laufkomplexität unterscheiden. Weil sich jedoch der Detailgrad des so generierten Dreiecksnetzes beliebig erhöhen lässt, kann das menschliche Auge bei entsprechender Feinheit ohnehin kaum einen Unterschied mehr erkennen, der auf das gewählte Verfahren der Extraktion zurückzuführen ist. Daher spielt der Isoflächen-Extraktor für die eigentliche Qualität der Rekonstruktion eine untergeordnete Rolle.

Dieser Typ von Verfahren erzielt besonders bei regional sehr undichten Punktwolken vergleichsweise hochwertige Ergebnisse, weil die approximierten Funktionen diese Ausschnitte relativ originalgetreu füllen können.

Im weiteren Verlauf dieses Kapitels wird zunächst die implizite Repräsentation erläutert. Diese beschreibt das approximierte Objekt vollständig, kann allerdings in dieser Form grafisch nicht unmittelbar angezeigt werden.

Daraufhin liegen Vorgehensweisen zur Isoflächen-Extraktion im Vordergrund, die diese Re- präsentation triangulieren, wodurch eine effiziente Ausgabe der angenäherten Oberfläche er- möglicht wird.

6.1 Implizite Repräsentation eines 3D-Objekts

Damit der Iso-Flächen-Extraktor eine originalgetreue Triangulation durchführen kann, muss die implizite Repräsentation den Verlauf der Oberfläche des jeweiligen 3D-Objekts kennzeichnen. Es sei v = { (x, y, z)T | x, y, z ϵ R } ein Vektor mit drei Koordinaten und F (v) eine Funk-tion, die Positionen innerhalb des approximierten Objekts von denen außerhalb differenziert. Somit kann der Isoflächen-Extraktor für beliebige Positionen feststellen, ob sich diese gemäß der impliziten Repräsentation innerhalb oder außerhalb des zu triangulierenden Objekts befinden. Diesbezüglich dominieren zwei Ausprägungen:

Einerseits existieren solche, die mathematische Funktionen nutzen, die mithilfe von Vor- zeichen zwischen innerhalb und außerhalb differenzieren. Dementsprechend bilden Positionen innerhalb der approximierten Oberfläche mit negative Werte, während aus Vektoren außer- halb der Oberfläche positive Werte resultieren. Bei dieser Darstellung verläuft die angenäherte Oberfläche dort, wo die Werte dieses Verbunds von Funktionen den Schwellwert null ergeben. Außerhalb bzw. innerhalb des Objekts wächst der Betrag dieses Werts mit wachsender Entfer- nung zur Oberfläche.

Entsprechende effiziente Verfahren, die diese Repräsentation aus einer Punktwolke erzeu- gen, versuchen gemeinhin jeweils für Unterbereiche des Raums den Verlauf der dort vorhan- denen Teiloberfläche zu charakterisieren. Zwischen den diese Teiloberflächen beschreibenden Funktionen jener Bereiche kann mittels einer zentrischen und nach außen hin schrumpfenden

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.1: Vergleich der vorzeichenbasierten (a) und der konstantenbasierten (b) impliziten Repräsentation eines gegebenen zweidimensionalen Objekts.

Gewichtungsfunktion ein kontinuierlicher Übergang erzeugt werden [OTHA 2003].

Eine weitere Form einer adäquaten impliziten Darstellung besteht darin, Funktionen zu nutzen, die für Positionen innerhalb des approximierten Objekts eins ergeben, während den Vektoren außerhalb der Wert null zugeordnet wird. Somit verläuft die approximierte Oberfläche genau zwischen diesen beiden Konstanten. Algorithmen, die zu dieser Repräsentation führen, approximieren die entsprechende Funktion F (v) durch Bildung eines oberflächenbezogenen Integrals über die mit normalen angereicherte Punktwolke.

6.1.1 Vorzeichenbasierte implizite Repräsentation

Bei der vorzeichenbasierten impliziten Repräsentation wird eine Funktion F (v) erzeugt, die für innere Vektoren des zu rekonstruierenden Objekts einen negativen ergibt und für äußere einen positiven. Der Betrag dieser Abbildung ist umso kleiner, je näher sich die jeweilige Position an der so angenäherten Oberfläche befindet. Zur Erzeugung der vorzeichenbasierten impliziten Repräsentation wird ein Verbund primitiver Funktionen genutzt, die jeweils einen Teilbereich der äußeren geometrischen Form des Objekts beschreiben. Jede einzelne solche Funktion gi (v) erfüllt das Kriterium, dass innerhalb des von ihr approximierten Bereichs innere Positionen ne- gativen Werten bzw. äußere Positionen positive Werte zugeordnet werden. Hierbei sind zahlrei- che anzupassende Basisfunktionen möglich, wobei vorwiegend quadratische Polynome genutzt werden.

Um die jeweilige gewählte Basisfunktion den von ihr approximierten Bereich möglichst originalgetreu widerspiegeln zu lassen, sind die Koeffizienten jener anzupassen. Im Falle von Polynomen können beispielsweise entsprechend die Multiplikatoren der einzelnen Monome adaptiert werden. Diese Anpassung wird in der Regel mithilfe der Normalen der einzelnen Punkte und der Methode der kleinsten Quadrate durchgeführt [OTHA 2003].

Vereinfacht ausgedrückt berücksichtigt der Algorithmus entlang der Ausrichtung der Nor- male den Abstand der Punkte des zu approximierenden Teilbereichs von der geometrischen Form der anzupassenden Funktion gi (v). Die Summe dieser Abstände wird dann minimiert,

wobei sie häufig mit Gewichtungen in Abhängigkeit der Position des jeweiligen Punktes be-

legt werden. Falls es sich um ein Verfahren handelt, das sich überlappende Bereiche getrennt annähert, kann so Punkten nahe dem jeweiligen Zentrum des Teilbereichs mehr Bedeutung beigemessen werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.2: Zweidimensionales Beispielschema zur Erzeugung einer vorzeichenbasierten impliziten Repräsentation.

In der Abbildung wird eine primitive Funktion g (v) - hier durch eine Ellipse symbolisiert (a)

so über eine 2D-Punktwolke gespannt, sodass die Abweichungen entlang der Normalen möglichst gering ausfallen (b). Der gestrichelte Kreis markiert hierbei den Bereich von Punkten, der berücksichtigt wird. Die 2D-Punktwolke wird im nächsten Schritt in vier Kreise unterteilt, wobei für jeden Teilbereich eine Funktion gi (v) angepasst wird (c). Aus den Teilbereichs-Funktionen wird durch Gewichtung ein Verbund F (v) erstellt (d), der die Punktwolke präziser beschreibt als in den oberen beiden Zeichnungen.

Auch bei der Wahl einzelnen Teilbereiche bestehen verschiedene Varianten: Einerseits sind Ausprägungen vorhanden, die die Punktwolke in sich überlappende Kugeln aufteilen, deren verinnerlichte Punkte jeweils durch eine primitive Funktion g (v) berücksichtigt werden.

Entsprechend beschreibt jede einzelne Funktion gi (v) die geometrische Form der von der jeweiligen Kugel verinnerlichten Teiloberfläche. Bei dieser Methode steigt die Präzision in Ab- hängigkeit der Anzahl der Kugeln, in die die Punktwolke unterteilt wird. Dieses Verfahren ermöglicht eine adaptive Vorgehensweise [OTHA 2003]: Zunächst wird die Punktwolke mittels einer Kugel approximiert. Darauf können iterativ solche Kugeln, bei denen die Abweichung zwischen der zu beschreibenden Oberfläche und der Funktion einen bestimmten Schwellwert überschreiten, nochmals unterteilt werden. Dadurch kann in Abhängigkeit der gewünschten Feinheit des Ausgabe-Dreiecksnetzes eine besonders geringe Laufzeit erreicht werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.3: Beispiel für adaptive Approximation einer Punktwolke (a) mithilfe verschiedener Octree-Tiefen (b).

Demgegenüber definieren bestimmte Varianten für jeden einzelnen Punkt und dessen Nor- male eine mathematische Abbildung g (v). Somit beschreibt hier jede einzelne Funktion gi (v) ein Teilstück der Gesamtoberfläche durch die näherungsweise tangentiale Umgebung eines Punktes [KOLL 2008].

Um einen kontinuierlichen Übergang F (v) zwischen diesen jeweils einen Teilbereich des Objekts beschreibenden Funktionen zu schaffen, wird jeweils eine Gewichtungsfunktion wi (v) genutzt [GUEN 2007]. Ihre Aufgabe besteht darin, für die Approximation eines bestimmten

Vektors zwischen den verschiedenen geometriebezogenen Funktionen zu priorisieren. Zumeist

werden sogenannte Gaußglocken oder ähnliche radiale Basisfunktionen [BELY 2003] für diese Gewichtung verwendet. Diese besitzen einen symmetrischen kurvenförmigen Graphen, der im Zentrum sein Maximum besitzt und nach außen hin stetig abfällt. Der Wert wi (v) hängt hierbei lediglich vom Abstand zum Teilbereichsursprung ab.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.4: Eine einsetzbare Gewichtungsfunktion. Hierbei beschreibt ||v|| den euklidischen Abstand eines Vektors zum Bezugszentrum. U steht für die Höhe des Gewichtungswerts.

In der Regel approximiert eine geometriebezogene Funktion gi (v) zentrale Punkte ihres zugeordneten Teilbereichs präziser als äußere. Dies deckt sich mit dem Verlauf der Gewich- tungsfunktion wi (v), deren Ursprung im Zentrum des Teilbereichs von gi liegt: Sie kann so eine Funktion gi (v), deren Teilbereichs-Zentrum näher an dem zu approximierenden Vektor liegt, stärker berücksichtigen als solche mit weiter entfernten Kernbereichen. Durch die Gewichtungen w aller eine Teiloberfläche beschreibenden Funktionen g kann somit die gewünschte Repräsen- tation F (v) approximiert werden.

6.1.2 Konstantenbasierte implizite Repräsentation

Formal differenziert die konstantenbasierte Repräsentation mit zwei verschiedenen Werten zwischen vom Objekt verinnerlichten und außenliegenden Positionen. Algorithmen, die zu dieser Repräsentation führen, erfordern Normalen, die sie für die weitere Verarbeitung umgekehrt bzw. nach innen gerichtet betrachten.

Bei der Unterteilung der Punktwolke in Einsen innerhalb des zu rekonstruierenden Objekts und Nullen außerhalb handelt es sich um ein Skalarfeld, das jeder Position im Raum einen Wert zuordnet:

F (v) = 1, falls v innerhalb des Objekts F (v) = 0, falls v außerhalb

Der sogenannte Gradient charakterisiert die Steigung dieses Skalarfelds an einer bestimmten Position:

Abbildung in dieser Leseprobe nicht enthalten

Dieser Gradient beträgt abgesehen von der Oberfläche des Objekts überall null, da F (v) für Positionen innerhalb konstant eins und außerhalb null als Funktionswert hat. Die invertierten Normalen können als Messwerte dieses Gradienten gesehen werden: Sie besitzen eine Einheitslänge und zeigen von außen nach innen, also vom null-Niveau auf das eins-Niveau. Durch das Umkehren des Gradienten-Operators, welches mithilfe von Integralen angenähert wird, kann also aus den Normalen an den Positionen der einzelnen Punkte die gewünschte Funktion F gewonnen werden [KAZH 2006].

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.5: Schema zur Erzeugung einer konstantenbasierten impliziten Repräsentation. Mithilfe der Punktwolke und deren umgekehrten Normalen (a) wird das Gradienten-Feld ap- proximiert (b). Aus diesem wird mithilfe von Integralen das gewünschte Skalarfeld gebildet (c).

Existierende Verfahren, die diese Methode verwenden, approximieren dieses Skalarfeld unter Verwendung von Basisfunktionen mit unterschiedlichen Koeffizienten, etwa durch Fourierreihen [KAZH 2005] oder Wavelets [MANS 2008]. Zudem besteht der Ansatz, das Integral über die Gradienten mithilfe einer Poisson-Gleichung zu ermitteln.

Um einen möglichst präzisen Schwellwert zu erhalten, der Positionen innerhalb von denen außerhalb des Objekts differenziert, wird im praktischen Einsatz der Durchschnitt der Funktion F (v) an den Punkten ermittelt [KAZH 2005]. Somit nimmt der Isoflächen-Extraktor Positionen, die als Argument für F einen größeren Wert als diesen Durchschnitt ergeben, als innerhalb des Objekts befindliche wahr. Analog ordnet er kleinere Werte Positionen außerhalb des zu rekonstruierenden Objekts zu.

6.2 Isoflächen-Extraktion

In den vorherigen drei Sektionen ist die implizite Repräsentation eines Objekts erläutert worden und wie sie aus einer Punktwolke approximiert werden kann. Diese umfasst zwar eine vollstän- dige Rekonstruktion eines Objekts, kann aber in dieser Form nicht unmittelbar visualisiert werden.

Deshalb wird gemeinhin aus jener Repräsentation durch die sogenannte Isoflächen-Extraktion eine Triangulation erstellt, deren Dreiecke topologisch benachbarte Positionen auf der implizit ausgedrückten Oberfläche adäquat verbindet. Die Auflösung des entstehenden Dreiecksnetzes kann beliebig erhöht werden, sodass sich die Feinheit der ausgegebenen Triangulation unabhängig von der Dichte der ursprünglichen Punktwolke verhält.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.6: Beispieltriangulation eines Torus in verschiedenen Auflösungen bezüglich der vorzeichenbasierten impliziten Repräsentation[Abbildung in dieser Leseprobe nicht enthalten] mit680 Dreiecken (a),4.316 Dreiecken (b) bzw.253.168 Dreiecken (c).

Der extrahierende Algorithmus sucht für die Eckpunkte der einzelnen Dreiecke nach Positionen auf der Oberfläche der impliziten Repräsentation, welche in möglichst ähnlicher Distanz zueinander stehen.

Hierbei wird die Oberflächennähe eines Vektors häufig dadurch approximiert, dass in der Nähe befindliche Positionen auf der jeweiligen Gegenseite vorhanden sind. Stellt das Verfahren bezüglich eines Testvektors v beispielsweise fest, dass sich dieser innerhalb der Oberfläche befindet, so prüft es, ob in der Nähe zu ihm Positionen außerhalb existieren. Weiterhin kann die Differenz zwischen dem Ausgabewert der impliziten Abbildung F an der Position v und dem oberflächenbezogenen Schwellwert herangezogen werden. Je kleiner der Betrag ausfällt, desto näher liegt der Vektor an der approximierten Oberfläche.

Auch zur Isoflächen-Extraktion einer gegebenen impliziten Repräsentation bestehen verschiedene Algorithmen, die sich in Bearbeitungszeit und Ausgabequalität unterscheiden.

Die primitiveren rasterbasierten Varianten [LORE 1987] erstellen Dreiecke, die nur teilweise dem vorteilhaften Delaunay-Kriterium genügen und deren Eckpunkte verhältnismäßig weit von der implizit angenäherten Oberfläche entfernt sein können. Ein Vorzug der Rasterung besteht darin, dass der Algorithmus leicht parallelisiert implementiert werden kann.

Weiterhin sind solche vorhanden, die inkrementell arbeiten und das Delaunay-Kriterium bei der Wahl der erweiternden Dreiecke berücksichtigen [HILT 1997].

Im Allgemeinen besteht eine lineare Laufzeitkomplexität in Abhängigkeit der Anzahl der Dreiecke der resultierenden Triangulation.

6.2.1 Marching Cubes

Hierbei handelt es sich um ein primitives Verfahren, implizite Repräsentationen von 3D-Objekten zu triangulieren. Zur Einfachheit wird zunächst ein analoges 2D-Verfahren erklärt, welches sich Marching Squares nennt.

Es sei v ein beliebiger 2D-Vektor und F (v) eine Funktion, welche kennzeichnet, ob sich die Position v innerhalb oder außerhalb der impliziten Repräsentation eines 2D-Objekts befindet. Der Raum, in dem sich das 2D-Objekt wird in Quadrate einer bestimmten Größe unterteilt. Nun wird für jedes der Quadrate geprüft, ob sich Eckpunkte innerhalb des implizit repräsentierten 2D-Objekts befinden oder nicht. Dabei ergeben sich folgende 2D-Konstellationen:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.7: Die 2⁴ möglichen Konstellationen eines Marching-Square Algorithmus. Die magentafarbenen Kugeln markieren die Eckpunkte eines Quadrats, welche innerhalb der impli- ziten Repräsentation liegen. Bei den roten Geraden innerhalb der Quadrate handelt es sich um Kanten, die das Verfahren zur Randrekonstruktion ausgibt. Jene Quadrate, die Spiegelungen oder Drehungen einer vorherigen Konstellation verkörpern, besitzen einen grauen Rand.

In Abhängigkeit der jeweiligen Konstellation werden der 2D-Randrekonstruktion die Kanten hinzugefügt, die innerhalb des jeweiligen Konstellations-Quadrats liegen. Je kleiner die Seitenlänge des Quadrats gewählt wird, desto präziser und feiner wird die Oberfläche der impliziten Repräsentation angenähert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.8: Vergleich der Annäherung eines Randes einer impliziten Repräsentation durch einen Marching-Square-Algorithmus mit unterschiedlichen Quadratseitenlängen.

Die 3D-Methode „Marching Cubes“ erfolgt analog, mit dem Unterschied, dass der Raum, in dem sich die implizite Repräsentation des 3D-Objekts befindet, in Würfel einer bestimmten Größe unterteilt wird. Dann werden die acht Eckpunkte eines jeden Würfels geprüft, wobei sich 28= 256 verschiedene Konstellationen ergeben. Diese Konstellationen verinnerlichen bis zu vier Dreiecke, die dann jeweils der Ausgabe-Triangulation hinzugefügt werden [LORE 1987].

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.9: Aus Übersichtsgründen werden hier lediglich die 15 Konstellationen des Marching-Cubes-Algorithmus dargestellt, die keine Spiegelung oder Drehungen einer vorhe- rigen verkörpern. Die magentafarbenen Kugeln markieren die Eckpunkte eines Würfels, welche innerhalb der impliziten Repräsentation liegen. Bei den roten Flächen innerhalb der Quadrate handelt es sich um Dreiecke, die das Verfahren zur Oberflächenrekonstruktion ausgibt.

Neben diesem würfelbasierten Verfahren existieren ähnliche Variationen, die nach demselben Grundprinzip beispielsweise Tetraeder als Unterteilungsbasis verwenden [BLOO 1994]. Weiterhin bestehen zusätzliche Ansätze, die so generierten Dreiecksnetze zu optimieren.

Hierbei wird versucht, die bestehenden Dreiecke so anzupassen, dass sie tangential an der impliziten Repräsentation liegen [OTHA 2002].

6.2.2 Marching-Triangles

Dieses inkrementelle Verfahren trianguliert eine gegebene implizite Repräsentation gemäß dem lokalen Delaunay-Kriterium. Zunächst wird in Abhängigkeit der gewünschten Feinheit ein Start- Dreieck einer bestimmten Größe gewählt, dessen Eckpunkte auf dem Schwellwert der Reprä- sentation F (v) liegen. Dabei wird jeder Eckpunkt mit approximierten Normalen versehen.

Um das Delaunay-Kriterium lokal zu prüfen, wird eine Kugel in dem jeweiligen erweiternden Dreieck platziert. Sie besitzt ihr Zentrum am geometrischen Schwerpunkt des Dreiecks und berührt dessen drei Eckpunkte. Dabei prüft der Algorithmus das lokale Delaunay-Kriterium bezüglich Eckpunkten des bisherigen Netzes, deren Normalen mit der des Dreiecks einen kleineren Winkel als neunzig Grad bilden. Falls sich ein solcher innerhalb dieser Kugel befindet, wird das Delaunay-Kriterium verletzt.

Bei jeder Iteration werden alle Kanten am Rand des Netzes auf Erweiterbarkeit geprüft. Dazu projiziert das Verfahren zu der jeweiligen Randkante mit den Vertices vi und vj einen senkrecht im Raum stehenden Punkt p in den Raum. Sein Abstand zur Ausgangskante hängt von einer Konstante ab, die sich durch die gewünschte Auflösung der Triangulation ergibt. Für diesen Projektionspunkt wird nach der nächsten Position vk auf der Oberfläche der impliziten Repräsentation gesucht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.10: Ausgehend von der Kante vi - vj wird ein Punkt p projiziert.

Wenn die Vektoren vi, vj und vk ein Dreieck bilden, das das lokale Delaunay-Kriterium erfüllt, wird es zum bestehenden Dreiecksnetz hinzugefügt. Falls es das Kriterium verletzt, prüft der Algorithmus die am Rand befindlichen und zu der jeweiligen Kante adjazenten Vertices vn und vp. Bezüglich dieser wird ermittelt, ob sie mit den Vertices vi und vj der Ausgangskante ein adäquates Dreieck bilden.

Falls diese ebenfalls nicht das Delaunay-Kriterium einhalten, sucht das Verfahren nach einem Randdreieck, das die Kugel des Dreiecks mit den Vertices vi, vj und vk schneidet. Außerdem wird verlangt, dass das Skalarprodukt der Normalen der beiden Dreiecke einen positiven Wert hat. Wenn ein solches existiert, wird dessen Eckpunkt vo mit der kürzesten Distanz zu vi und vj

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.11: Im Beispiel führt der projizierte Punkt p zu einer Verletzung des DelaunayKriteriums.

bestimmt. Darauf prüft der Algorithmus entsprechend, ob die Vertices vi, vj und vo ein Dreieck bilden, das das Delaunay Kriterium lokal erfüllt und fügt es gegebenenfalls zum Dreiecksnetz hinzu.

Wenn keine neuen Dreiecke mehr am Rand der Triangulation angegliedert werden können, endet das Verfahren [HILT 1997].

6.3 Evaluation

Ein Vorteil dieses Typs besteht darin, dass mithilfe der impliziten Approximation eine hohe Flexibilität ermöglicht wird: So kann nicht nur die Feinheit des auszugebenden Dreiecksnetzes bestimmt, sondern auch die Menge der verwendeten mathematischen Funktionen und deren Präzision beeinflusst werden.

Eine weniger genauer mathematische Annäherung führt hierbei zu geglätteteren Dreiecksnetzen und erheblich verringerter Laufzeit, welche durch rein explizite Verfahren nicht erreichbar sind. Weil der konkrete Zeitaufwand drastisch von der Anzahl der zu extrahierenden Dreiecke und der anzugebenden Toleranz, mit der die Gleichungen zum Erhalt der impliziten Repräsentation gelöst werden, abhängt, lässt sich dieser nicht allgemeingültig bewerten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.12: Rekonstruktion einer nahezu uniformen Punktwolke (a) mit unterschiedlich genauen impliziten Repräsentationen (MPU).

Die oben genannte Anpassungsmöglichkeit geht jedoch auf Kosten der Garantie, dass die Ausgabedreiecke die Einträge der Punktwolke berühren.

Weiterhin besteht bei der vorzeichenbasierten impliziten Repräsentation die Option, die Dreiecks-Extraktion mit von null verschiedenen Werten vorzunehmen, um so ein verbreitertes oder ausgedünntes 3D-Modell des Ursprungsobjekts zu erhalten. Diese können gegebenenfalls das Erkennen von Spalten bzw. Spitzen erleichtern, um beispielsweise einen interaktiven Scan-

vorgang zu unterstützen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.13: Eine nahezu uniforme Punktwolke (a), die vorzeichenbasierte Standard- Rekonstruktion (d), Rekonstruktionen mit negativen Iso-Werten (b, c) sowie solche mit po- sitiven (d, e).

Bei den folgenden Testresultaten sind das Verfahren „Multi-levelParitition of Unity Implicits“ [OTHA 2003] als Vertreter für die vorzeichenbasierte implizite Repräsentation (adaptiv) und die Umsetzung „Poisson Surface Reconstruction“ [KAZH 2006] für die konstantenbasierte implizite Repräsentation gewählt worden.

Im Gegensatz zu den expliziten Verfahren sind sie in der Lage Bereiche, die durch Punktwolke nicht beschrieben sind, authentisch wirkend zu approximieren. Algorithmen mit konstantenbasierter impliziter Repräsentation verhalten sich bei der Wahl laufzeitrelevanter Parameter in der Regel etwas weniger flexibel als solche mit vorzeichenba-sierter. Zudem besitzen bei der konstantenbasierten Variante Operationen, die mit der Wahl verschiedener Iso-Werte zusammenhängen, keine brauchbare Wirkung.

(Dass die konstantenbasierte Version in den Abbildungen unten einen verlängerten Stumpf besitzt und die vorzeichenbasierte nicht hängt nicht dem Wesen der Verfahren zusammen. Vielmehr kann der Entwickler bei der Umsetzung des jeweiligen Algorithmus wählen, in welcher

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.14: Nicht-uniforme Punktwolke (b) und die vorzeichenbasierte (a) bzw. konstantenbasierte Rekonstruktion (c).

Reichweite die implizite Repräsentation bei geöffneten Punktwolken außerhalb der Bounding Box der Punkte approximiert.)

Allerdings verhält sich die konstantenbasierte implizite Repräsentation bei messfehlerbehafteten Punktwolken deutlich robuster als die vorzeichenbasierte.

Dies rührt vor allem daher, dass die konstantenbasierte implizite Rekonstruktion globaler arbeitet, d. h. die gesamte Punktwolke auf einmal in die Annäherung ihres Integrals miteinfließen lässt [KAZH 2006]. Dagegen werden bei der vorzeichenbasierten Variante lediglich Funktionen für einzelne lokal begrenzte Teilbereiche gebildet, die dann durch Gewichtungen zusammengefügt („Blending“) werden.

So entstehen bei vorzeichenbasierten Umsetzungen oftmals zapfenförmige Artefakte, die durch fehlerhafte Normalen begünstigt verursacht werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.15: Ausgabedreiecksnetze der vorzeichenbasierten (a, 693.516 Dreiecke) bzw. kon- stantenbasierten (b, 782.936 Dreiecke) Repräsentation bei einer Punktwolke mit 108.706 Punk- ten (b).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.16: Lokaler Vergleich zwischen adaptiver vorzeichenbasierter (a) und konstantenbasierter (b) impliziter Repräsentation bei Punktwolkenbereich mit hoher Oberflächenkrümmung pro Punktdichte.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6.17: Ausgabedreiecksnetze der vorzeichenbasierten (a, 4.154.096 Dreiecke) bzw. konstantenbasierten (b, 3.892.612 Dreiecke) Repräsentation bei einer Punktwolke mit 1.180.497 Punkten (bitte zoomen).

Kapitel 7 Fazit

Alle vorgestellten Verfahren sind dazu fähig bei sehr dichten Punktwolken, die jede Teilregion des Ursprungsobjekts beschreiben, eine originalgetreue Rekonstruktion durchzuführen. Vielmehr sollte daher von Interesse sein, wie sich die verschiedenen Algorithmen bei Störungen oder fehlenden Teilbereichen verhalten.

Falls keine Interpretation bzw. Verfälschung der gemessenen Punktwolke gewünscht wird, lie- fert Typ B die objektivste Rekonstruktion. Denn die Delaunay-Tetraedisierung für eine Punkt- wolke ist meistens eindeutig. Somit besteht das einzige subjektive Element in den Schwellwerten, mit denen die Dreiecke aus der Tetraedisierung ausgewählt werden, die dann das Ursprungsob- jekt repräsentieren.

Bei Typ A hingegen kann bereits die Wahl des Anfangsdreiecks einen maßgeblichen Einfluss für die inkrementell fortsetzende Rekonstruktion bedeuten. Somit sind besonders bei variierender Punktdichte durch Ausführung desselben Algorithmus bei minimaler Veränderung der Punktwolke sehr unterschiedliche Rekonstruktionsergebnisse möglich. Andererseits arbeiten die modernsten Umsetzungen dieses Typs wohl durchschnittlich am schnellsten. Nur die impliziten Algorithmen können die Punktwolke noch rapider verarbeiten, wenn ein weniger präzises Dreiecksnetz als Resultat akzeptiert wird.

Sofern bei nicht-uniformen Punktwolken verlangt wird, dass fehlende Bereiche möglichst au- thentisch wirkend rekonstruiert werden sollen, sind die impliziten Ansätze klar überlegen. Zu- dem erhalten hier im Gegensatz zu den expliziten Typen durch Messfehler verschobene Punkte, die mit den benachbarten Punkten keine kontinuierliche Form bilden, bei der Rekonstruktion verringerten Einfluss.

Außerdem lassen sich die Ausgabe-Dreiecksnetze bei impliziten Methoden besser in ihrer Feinheit verändern oder optimieren, wenn die Punktwolke einen anderen Detailgrad besitzt als die gewünschte rekonstruierte Oberfläche haben soll. Es kann zwar auch aus den Ausgabe- Dreiecksnetzen der ersteren beiden Typen eine implizite Repräsentation ermittelt werden, die dann wiederum trianguliert wird, jedoch erfordert dies einen noch höheren Zeitaufwand und dürfte nur im Falle mangelhafter oder nicht vorhandener Normalen qualitativ sinnvoll sein.

Die mit dem Typ C verbundene Glättung kann jedoch auch auf Kosten sehr feiner Kanten gehen, die so in Abhängigkeit der gewählten Genauigkeit der impliziten Repräsentation reduziert werden. Falls die erhöhte Flexibilität der vorzeichenbasierten Variante nicht benötigt wird, sollte eine konstantenbasierte eingesetzt werden, weil diese in der Regel originalgetreuere Resul- tate erzielt. Demgegenüber sind die konstantenbasierten Vorgehensweisen mit den komplexesten Umsetzungsdetails behaftet und benötigen bei der Verwirklichung deutlich mehr Quellcode.

Abbildung in dieser Leseprobe nicht enthalten

(a) Punktwolke

Abbildung in dieser Leseprobe nicht enthalten

(b) Typ A

Abbildung in dieser Leseprobe nicht enthalten

(c) Typ B

Abbildung in dieser Leseprobe nicht enthalten

(d) Typ C1

Abbildung in dieser Leseprobe nicht enthalten

(e) Typ C2

Abbildung 7.1: Nicht-uniforme Punktwolke (a) sowie Ball-Pivoting (b), Cocone (c), MPU (d, vorzeichenbasiert) und Poisson (e, konstantenbasiert) im Vergleich.

7.1 Ausblick

In der Zukunft sind weitere spezialisierte Algorithmen zu erwarten, die unter bestimmten Bedingungen schneller arbeiten oder hochwertigere Ergebnisse erzeugen.

So sind beispielsweise verhältnismäßig neue Verfahren darauf ausgelegt, Objekte zu rekonstruieren, die sich aus geschlängelten Elementen zusammensetzen (z. B. ein klassischer Schaukelstuhl) [LI 2010]. Vor allem die wachsende Vielseitigkeit zur Bildung der impliziten Darstellungen lässt sich zunehmend schwer in einem einzelnen Schriftstück abhandeln.

Weiterhin bestehen solche, die sich ausschließlich mit der interaktiven Rekonstruktion befassen [SHAR 2007].

Die Unterteilung zwischen inkrementellen bzw. Delaunay-basierten expliziten Verfahren einerseits und impliziten Vorgehensweisen andererseits wird aber wohl bestehen bleiben.

Abbildung in dieser Leseprobe nicht enthalten

(a) Punktwolke

Abbildung in dieser Leseprobe nicht enthalten

(b) Typ A

Abbildung in dieser Leseprobe nicht enthalten

(c) Typ B

Abbildung in dieser Leseprobe nicht enthalten

(d) Typ C1

Abbildung in dieser Leseprobe nicht enthalten

(e) Typ C2

Abbildung 7.2: Punktwolke (a) sowie Ball-Pivoting (b), Cocone (c), MPU (d, vorzeichenbasiert) und Poisson (e, konstantenbasiert) bei Skulptur im Vergleich.

Abbildung in dieser Leseprobe nicht enthalten

(a) Typ A

Abbildung in dieser Leseprobe nicht enthalten

(b) Typ B

Abbildung in dieser Leseprobe nicht enthalten

(c) Typ C1

Abbildung in dieser Leseprobe nicht enthalten

(d) Typ C2

Abbildung 7.3: Ball-Pivoting (a), Cocone (b), MPU (c, vorzeichenbasiert) und Poisson (d, konstantenbasiert) bei Kopf im Vergleich.

Literaturverzeichnis

[AURE 1991] AURENHAMMER, Franz. Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR), 1991, 23. Jg., Nr. 3, S. 345-405.

[BELY 2003] OHTAKE, Yutaka; BELYAEV, Alexander; SEIDEL, H.-P. A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions. In: Shape Modeling International, 2003. IEEE, 2003. S. 153-161.

[BERN 1999] BERNARDINI, Fausto, et al. The ball-pivoting algorithm for surface reconstruction. Visualization and Computer Graphics, IEEE Transactions on, 1999, 5. Jg., Nr. 4, S. 349-359.

[BLOO 1994] BLOOMENTHAL, Jules. OlV. 8. Graphics gems IV, 1994, 4. Jg., S. 324.

[DELA 1934] DELAUNAY, Boris. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 1934, 7. Jg., Nr. 793-800, S. 1-2.

[DEY 2001] DEY, Tamal K.; GIESEN, Joachim; HUDSON, James. Delaunay based shape reconstruction from large data. In: Parallel and Large-Data Visualization and Graphics, 2001. Proceedings. IEEE 2001 Symposium on. IEEE, 2001. S. 19-146.

[GUEN 2007] GUENNEBAUD, Gaël; GROSS, Markus. Algebraic point set surfaces. In: ACM Transactions on Graphics (TOG). ACM, 2007. S. 23.

[HRAD 2003] HRÁDEK, Jan. Methods of surface reconstruction from scattered data. Technical Report. Department of Computer Science and Engineering University of West Bohemia in Pilsen. 2003.

[HILT 1997] HILTON, Adrian, et al. Marching triangles: Delaunay implicit surface triangulation. University of Surrey, 1997.

[KAZH 2005] KAZHDAN, Michael. Reconstruction of solid models from oriented point sets. In: Proceedings of the third Eurographics symposium on Geometry processing. Eurographics Association, 2005. S. 73.

[KAZH 2006] KAZHDAN, Michael; BOLITHO, Matthew; HOPPE, Hugues. Poisson surface reconstruction. In: Proceedings of the fourth Eurographics symposium on Geometry processing. 2006.

[KOBB 2004] WU, Jainhua; KOBBELT, Leif. Optimized SubǦSampling of Point Sets for Surface Splatting. In: Computer Graphics Forum. Blackwell Publishing, Inc, 2004. S. 643-652.

[KOLL 2008] KOLLURI, Ravikrishna. Provably good moving least squares. ACM Transactions on Algorithms (TALG), 2008, 4. Jg., Nr. 2, S. 18.

[LI 2010] LI, Guo, et al. Analysis, reconstruction and manipulation using arterial snakes. ACM Transactions on Graphics-TOG, 2010, 29. Jg., Nr. 6, S. 152.

[LONG 2011] LONG, Chengjiang, et al. A new region growing algorithm for triangular mesh recovery from scattered 3d points. In: Transactions on edutainment VI. Springer Berlin Heidelberg, 2011. S. 237-246.

[LORE 1987] LORENSEN, William E.; CLINE, Harvey E. Marching cubes: A high resolution 3D surface construction algorithm. In: ACM Siggraph Computer Graphics. ACM, 1987. S. 163- 169.

[MANS 2008] MANSON, Josiah; PETROVA, Guergana; SCHAEFER, Scott. Streaming surface reconstruction using wavelets. In: Computer Graphics Forum. Blackwell Publishing Ltd, 2008. S. 1411-1420.

[MAUR 2002] MAUR, Pavel. Delaunay triangulation in 3D. Technical Report, Departmen. of Computer Science and Engineering, University of West Bohemia, Pilsen, Czech Republic, 2002.

[OTHA 2002] OHTAKE, Yutaka; BELYAEV, Alexander G. Dual/primal mesh optimization for polygonized implicit surfaces. In: Proceedings of the seventh ACM symposium on Solid modeling and applications. ACM, 2002. S. 171-178.

[OTHA 2003] OHTAKE, Yutaka, et al. Multi-level partition of unity implicits. In: ACM SIGGRAPH 2005 Courses. ACM, 2005. S. 173.

[SHAR 2007] SHARF, Andrei, et al. Interactive topology-aware surface reconstruction. In: ACM Transactions on Graphics (TOG). ACM, 2007. S. 43.

• Veranstaltung: Visual Computing
• Note: 1.7
• Autor: Philipp Eisele (Autor:in)
• Erscheinungsjahr: 2015
• Seiten: 64
• Katalognummer: V298800
• ISBN (eBook): 9783656951445
• ISBN (Buch): 9783656951452
• Sprache: Deutsch
• Schlagworte: analyse, algorithmen, oberflächenrekonstruktion, punktwolken