Die Eigenschaft abwickelbarer Flächen, verzerrungsfrei über planaren Gebieten parametrisiert werden zu können, ist für viele Anwendungsfelder der Computergrafik von großem Nutzen. Aus diesem Grund ist es wünschenswert, in der Lage zu sein, abwickelbare Annäherungen an beliebige Dreiecksnetze zu erzeugen.

In dieser Arbeit wird ein Verfahren vorgestellt, mit dem gegebene Dreiecksnetze durch stückweise abwickelbare Dreiecksnetze approximiert werden können. Im Zuge dessen wurde eine Erweiterung des von Cohen-Steiner et al. vorgestellten L^2,1-Abstands entworfen, die es erlaubt den L^2,1-Abstand zu beliebigen zwei-mannigfaltigen Dreicksnetzen zu berechnen.

Zuerst wurde ein Algorithmus entwickelt, der zu gegeben berandeten, quasi-abwickelbaren Dreiecksnetzen abwickelbare Approximanten erzeugt, die den Rand des gegebenen Netzes interpolieren. In einem zweiten Schritt wurde dieser Algorithmus in Verbindung mit einem iterativen Optimierungsalgorithmus dazu verwende in gegebenen Dreiecksnetzen quasi-abwickelbare Teilstücke zu identifizieren und mit abwickelbaren Flächen zu approximieren. Wie die vorhergehenden Arbeiten vorgestellten Verfahren, auf denen diese Diplomarbeit aufbaut, baut auch der in dieser Arbeit entwickelte Algorithmus auf einer Lloyd-Iteration auf, mit dem Ziel, den entstehenden Approximationsfehler durch iterative Anpassung der Segmentkonfigurationen zu minimieren. Hierfür wurden sowohl verschiedene Abstandsmetriken als auch verschiedene Verfahren zur Anpassung der Segmentkonfigurationen implementiert und auf ihre Eignung, den Approximationsfehler zu minimieren, hin überprüft. Von beiden Algorithmen wurden einige Varianten entworfen und umgesetzt die durch die Anwendung auf einige Beispielnetze auf ihre Eignung zur Lösung des Problems hin untersucht wurden. Dabei hat sich herausgestellt, dass die Richtungen der minimalen Krümmungen ein gute Handhabe bieten um abwickelbare Approximanten zu erzeugen. Durch die Verwendung eines genaueren Verfahrens zur Annäherung der Krümmungsrichtungen in den Eckpunkten eines Dreiecksnetzes ist eine weitere Verbesserung der Güte der gefundenenen Approximanten zu erwarten.

Um die Eignung verschiedener Varianten des Verfahrens zur Approximation eines beliebigen, berandeten Dreiecksnetzes durch ein abwickelbares Dreiecksnetz, zu überprüfen, wurden diese auf verschiedene Referenznetze angewendet, und die erzeugen Approximanten mittles verschiener Abstandsmetriken bewertet.

Einige Referenznetze

 

Ergebnisse bei Approximation unter Zuhilfenahme der Richtungen der minimalen Krümmung, sowie des L2,1-Abstands zur Steuerung der Approximation.

Um die Eignung verschiedener Varianten des Verfahrens zur Unterteilung eines beliebigen beliebigen gegebenen Dreiecksnetzes in quasi-abwickelbare Teilsegmente zu überprüfen, wurden diese auf ebenfalls verschiedene Referenznetze angewendet. Die gefundenen Segmente wurden mithilfe des oben gezeigten Algorithmus approximiert, und das mittles verschiener Abstandsmetriken bewertet.

Ergebnisse bei Segmentierung und Approximation des Standford Bunny bei unterschiedlicher Art der Neuwahl der Startdreiecke zwischen zwei aufeinanderfolgenden Iterationen.

Die für das Gesamtverfahren ermittelten Ergebnisse legen den Schluss nahe, dass keines der in dieser Arbeit entworfenen Verfahren zur Anpassung der Segmentkonfigurationen zwischen zwei aufeinanderfolgenden Schritten der Lloyd-Iteration eine erkennbare Konvergenz des Approximationsfehlers gegen ein Minimum erreichen kann. Für dieses Verhalten sind zwei ursächliche Faktoren auszumachen. Einerseits ist dieses Verhalten darin begründet, dass die Neuwahl der Startfacette eines jeden Segments, von denen aus die Segmente durch schrittweise Erweiterung um angrenzende Facetten bestimmt werden, bei dem in dieser Arbeit verwendeten Erweiterungskriterium kein Garant für eine Reduzierung des Approximationsfehlers ist. Für die Anwendbarkeit der Lloyd-Iteration zur Minimierung eine Kostenfunktion ist es jedoch von essentieller Bedeutung, dass die Neuwahl der Stellvertreter zwischen zwei Iterationsschritten die Kosten der im vorhergehenden Schritt ermittelten Konfiguration senkt. Da in dieser Arbeit keine Möglichkeit gefunden werden konnte, diese Prämisse durch eine Neuwahl der Startdreiecke zu erfüllen, sollte die Anwendbarkeit dieses Verfahrens auf das vorliegende Optimierungsproblem in Frage gestellt werden. Unter Umständen gelangen andere Verfahren aus dem Bereich der heuristischen Optimierung nichtlinearer Probleme, wie z. B. das simulierte Tempern oder das Schwellwertakzeptanz-Verfahren im vorliegenden Fall zu besseren Lösungen. Zwar profitieren auch diese Verfahren von einer kostenminimierenden Neuwahl der Stellvertreter, also in diesem Fall der Startfacetten, sind zur Minimierung der Kostenfunktion jedoch nicht zwingend auf eine solche angewiesen.

Ebenfalls fraglich ist die Anwendbarkeit der Approximationsfunktion zur Bewertung angrenzender Dreiecke, um durch iterative Erweiterung zu quasi abwickelbaren Segmenten zu gelangen. Denn im Gegensatz zu den in den in den vorhergehenden Arbeiten verwendeten Kostenfunktionen wächst der Approximationsfehler durch die Erweiterung eines Segments um angrenzende Dreiecke bei der in dieser Arbeit verwendeten Bewertung nicht monoton und weist stattdessen eine Vielzahl lokaler Maxima auf. Dies wiederum führt dazu, dass sich die erzeugten Segmente nicht auf natürliche Weise den geometrischen Eigenschaften der Fläche anpassen und global günstige Konfigurationen i. Allg. nicht erreicht werden können. Da jedoch deutlich wurde, dass der in dieser Arbeit entwickelte Approximationsalgorithmus durchaus das Potential aufweist, visuell ansprechende abwickelbare Approximanten zu gegebenen, berandeten, quasi-abwickelbaren Dreiecksnetzen zu erzeugen, erscheint die Kombination mit einer anderen Heuristik zur Aufteilung eines gegebenen Dreiecksnetzes in quasi-abwickelbare Segmente vielversprechend. Ein geigneter Kandidat hierfür könnte die Heuristik von Yamauchi et al. sein, da diese Heuristik einerseits in der Lage ist, allgemeine abwickelbare Teilstücke einer Fläche zu identifizieren und die Suche nicht auf bestimmte Klassen abwickelbarer Flächen beschränkt. Andererseits wurde diese Heuristik dahingehend optimiert, Segmente zu erzeugen, deren Topologie möglichst der einer Scheibe entspricht. Von solchen Randkurven ist zu erwarten, dass der in dieser Arbeit entworfene Approximationsalgorithmus sein Potential voll ausschöpfen kann.