Algorithmus
Detektion
Für die Detektion der kritischen Stellen, wurden zwei verschiedene Algorithmen entwickelt.Winkel basierter Detektions Algorithmus
Dieser Algorithmus basiert auf der extremen Veränderung des Winkels beim Verschieben von kritischen Vertices. Diese extreme Veränderung wird durch eine, an konkaven Stellen auftretende, Schleife verursacht. Innerhalb dieser Schleife gibt es Vertices, deren Winkel zu den anderen Vertices kleiner als in der Ursprungsfläche ist. Dies lässt sich prüfen und dementsprechend erkennen. Da bei anderen Punkten auch eine Veränderung des Winkels während des Shelling passiert, wurde die Veränderung des Winkels als prozentuale Veränderung berechnet und mit einem Schwellwert verglichen. Ist die prozentuale Veränderung größer als der Schwellwert, so ist davon auszugehen, dass dieser Punkt ein kritischer Punkt ist.Normale basierter Detektions Algorithmus
Der Normale basierte Detektions Algorithmus prüft ob sich zwei Normalen schneiden. Dazu geht dieser Algorithmus in zwei Schritten vor. Im ersten Schritt extrahiert der Algorithmus nur die Vertices die innerhalb der Offset Distanz vom zu prüfenden Punkt liegen. Im nächsten Schritt werden die Normalen der Vertices mit der Normale des zu prüfenden Vertices auf Überschneidungen getestet. Hierzu wurden die Normalen der extrahierten Vertices durch eine Kugel verallgemeinert. Liegt der Punkt für die Offset-Fläche des zu prüfenden Vertices innerhalb der Kugel eines der extrahierten Vertices so ist der zu prüfende Vertice ein kritischer.Unterschiede
Der wesentliche Unterschied zwischen den beiden Verfahren ist die Anzahl der Vertices die als kritisch eingestuft werden. Beim ersten Verfahren werden nur die erkannt, die wirklich Probleme verursachen. Beim zweiten Algorithmus wird die gesamte konvexe Stelle als kritisch erkannt. Dieser Sachverhalt ist in den beiden Bildern gezeigt. Das Rechte ist dabei der Normale basierte Ansatz und das linke Bild zeigt den Winkel basierten Ansatz. Rot eingefärbte Vertices sind als kritisch erkannte Vertices.
Lösung des Problems
Für die Lösung des Problems gibt es zwei Wege. Der Erste versucht das Problem schon bei der Entstehung zu verhindern. Der Andere erkennt erst nach dem Shelling verdrehte oder sich schneidende Faces und korrigiert diesen Fehler. Der Vorteil des ersten Verfahrens ist die kurze Laufzeit und einfachere Lösung des Problems. Das andere Verfahren ist dafür gründlicher, da es nur problematische Stellen und nicht wie beim ersten Verfahren gelegentlich auch konvexe Stellen erkennt.Die Lösung, die hier verwendet wurde versucht beide Vorteile zu kombinieren. Für das erste Verfahren benötigt der Algorithmus mehrere Schritte. Der erste Schritt erstellt aus zusammenhängenden kritischen Punkten sog. Cluster. Dies ist ein sehr zeitintensiver Abschnitt des Algorithmus. Da dieser schwer zu parallelisieren ist, ist eine Vorsortierung in die Detektion integriert und parallelisiert. Der Teil, der ausgelagert wurde, sorgt für die Vorsortierung der Vertices um die eigentliche Sortierung zu beschleunigen. Damit kann nachher, im nicht parallelisierten Teil, schneller die restlichen Zuordnungen durchgeführt werden. Im nächsten Schritt werden die Randpunkte der Cluster identifiziert. Damit kann dann die Größe des Clusters bestimmt werden. Dies ist wichtig, da die Vertices im kritischen Bereich einfach in die Shellingfläche kopiert und mithilfe der Größe des Clusters passend skaliert werden kann. Das Kopieren erfolgt dabei durch Gewichte, die vorher aus der relativen Position des Vertices zu den Randpunkten berechnet wurden. Daraus kann dann die korrekte Normale berechnet werden. Da dies nicht ganz perfekt ausgeführt werden kann, gibt es noch eine Nachbearbeitung, die fehlerhafte Stellen zu beseitigen versucht.
Original-Mesh mit Offset verbinden
Sofern es sich nicht um ein geschlossenes Objekt handelt, kann es sinnvoll sein das neue Mesh mit dem Ausgangs-Mesh, zumindest an den Außenkanten, zu verbinden. Hierzu prüft der Algorithmus, ob überhaupt eine Außenkante bzw. mehrere (Kanten von Löchern) vorhanden sind. Sofern eine Außenkante bei Ausgangs-Mesh gefunden wurde, kann davon ausgegangen werden, dass es diese auch beim neuen Mesh gibt. Dementsprechend verbindet der Algorithmus beide Kanten via Triangulation.
Clean-Mesh
Wie bereits beschrieben, kann es beim "Shelling" zu fehlerhaften Stellen im Mesh kommen, die durch die nachfolgenden Algorithmen behoben werden können.
Dreieckdublikate entfernen
Eine Fehlerquelle können dupliziert Dreiecke sein. Diese "kleben" häufig auf derselben Position und erzeugen beim Betrachter einen unschönen Flimmer-Effekt. Der entwickelte Algorithmus behebt das Problem, in dem er alle Dreiecke anhand ihrer Position prüft und diese entfernt, sofern zwei dieselben Positionswerte haben. Da es gelegentlich vorkommen kann, dass doppelte Dreiecke nicht direkt auf derselben Position liegen, sondern ein wenig verschoben sind, haben wir einen Toleranzwert eingeführt. Dieser erlaubt es auch doppelte Dreiecke zu erkennen, selbst wenn diese nicht auf derselben Position liegen, aber trotzdem überlappend sind.
Dreiecksnormale überprüfen und ggf. drehen
Eine weitere Fehlerquellen sind falsch orientierte Dreiecke. Unser Algorithmus ist in der Lage, diese zu erkennen und zu korrigieren. Hierzu wird auf die Nachbardreiecke zugegriffen und deren Kanten mit denen, des zu prüfenden, Dreiecks verglichen. Sofern das Dreieck dieselbe Orientierung wie die Nachbardreiecke hat, sind alle Kanten der Nachbarn gegenläufig. Ein Beispiel: Verläuft die eine Kante des Dreiecks von Punkt A nach B und die des Nachbardreieck von B nach A. Dann haben beide Dreiecke dieselbe Orientierung. Verlaufen beide Kanten von A nach B, dann muss das Dreieck gedreht werden. Außerdem wurde ein Voting-Wert implementiert, dieser entscheidet, wie viel Nachbarn anderes orientiert sein müssen, damit das Dreieck gedreht wird. Dies kann schwierig sein, da es für Eckdreiecke auf einer Ebene nur zwei Nachbarn gibt. In diesem Fall müssen beide Nachbarn anders orientiert sein. Bei allen anderen Fällen reicht macht es Sinn, wenn mindestens 2/3 anderes orientiert sind, damit das Dreieck gedreht wird.
Selbst Durchdringungen erkennen und beheben
Der am häufigsten auftetende Fehler ist die sog. Selbst-Durchdringung. Dieser tritt auf, wenn zwei Dreiecke sich durchdringen. In unserem Algorithmus werden diese Durchdringungen erkannt und behoben. Bei der Detektion wird auf eine vorhanden Funktion innerhalb GigaMesh zurückgegriffen. Unser Algorithmus prüft nun um welche Dreiecks-Paare es sich handelt und bestimmt via Ray-Intersection-Verfahren[1] die Durchdringungspunkte der Kanten in den beiden sich druchdringenden Dreiecken. Sofern alle Durchdringungspunkte berechnet wurden, wird neu trianguliert. Hierzu verwenden wir den sog. Delaunay Algorithmus [2] . Wurden alle Durchdringungen behoben, werden die betroffenen Dreiecke durch die neu triangulierten Dreiecke ausgetauscht.