Implementierung
"Shelling"-Algorithmus
Unseren Algorithmus haben wir als Methode (applyNormalShift()) in der Mesh-Klasse implementiert.
Diese erhält dabei als Parameter den Offset-Wert, der
vom Benutzer über ein Dialogfenster eingegeben werde kann.
Innerhalb dieser Methode wurden zwei Detektionsalgorithmen implementiert. Diese
sind durch eine Precompilerabfrage getrennt, welche überprüft ob das Flag gesetzt wurde oder nicht.
Ist das
Flag gesetzt, wird die Normalen-basierte Detektion benutzt.
Ist dies nicht der Fall, wird auf die Winkel-basierte Detektion zurückgegriffen.
Des Weiteren gibt es noch eine Funktion die von den
Threads aufgerufen wird.
Diese hat die Aufgabe, alle kritischen Stellen im Mesh zu finden.
Sie übernimmt auch ein Teil des Clusteringverfahrens.
Hierfür kann die Funktion auf drei Parameter zurückgreifen, die in Form eines Datencontainers übergeben werden.
Dieser besteht neben dem Offset-Wert auch aus dem zu überprüfenden Bereich.
Die Funktion liefert dann die vorsortierten kritischen Vertices
als Rückgabewert zurück.
Original-Mesh mit Offset verbinden
Dieser Algorithmus wurde von uns in einer sog. Helper-Funktion (applyNormalShiftHelper) implementiert.
Diese nimmt drei verschiedene boolsche Parameter entgegen.
Der Erste initialisiert und speichert z.B. die die ggf. vorhanden Kanten des "Original"-Mesh.
Der Zweite entfernt das "Original"-Mesh, so dass nur das "Offset"-Mesh vorhanden ist.
Der Letzte und dritte Parameter verbindet die beiden, "Original"- mit "Offset"-Mesh, via den vorher gespeicherten Kanten.
In der Regel wird diese Funktion mehrfach (z.B. 2 mal) aufgerufen, z.B. am Anfang als Initialisierung und später,
je nachdem welche Aktion man starten möchte.
Die Funktion besteht aus verschiedenen Abschnitten, die je nach gesetzten Parametern aufgerufen werden.
Der interessanteste und letzte Abschnitt verbindet das "Original"- mit dem "Offset"-Mesh.
Hierzu wird auf die vorher gespeichert Kantenlinie zurückgegriffen. Auf dieser befinden sich alle Kanten-Vertices vom "Original"-Mesh.
Diese werden nacheinander abgearbeitet und so mit den passen Vertices des "Offset"-Mesh trianguliert.
Clean-Mesh
Dreieckdublikate entfernen
Diese Funktion kommt ohne Parameter aus. Im Prinzip wird das ganze Mesh durchsucht, ob zwei Dreiecke auf einer ähnlichen Position liegen. Ist dies der Fall wird geprüft, welches Dreieck entfernt werden soll. Haben beide die selbe Orientierung wird eines gelöscht. Ist die Orientierung unterschiedlich, wird via Voting-Zähler ermittelt, welches Orientierung hauptsächlich in der Nachbarschaft vorkommt. Daraufhin wird das Dreieck mit der "unwichtigeren" Orientierung gelöscht.
Dreiecksnormale überprüfen und ggf. drehen
Auch diese Funktion kommt ohne Parameter aus, das das ganze Mesh durchsucht wird.
Außerdem hat diese eine Sub-Funktion die aufgerufen wird, wenn ein Dreieck gedreht werden soll.
Dieser Algorithmus grift auf die Nachbardreiecke zu und vergleicht deren Kanten mit denen des zu prüfenden Dreiecks.
Sofern das Dreieck die selbe Orientierung wie die Nachbardreiecke hat, sind alle Kanten der Nachbarn gegenläufig.
Ist dies der Fall wird zum nächsten Dreieck gesprungen.
Ist jedoch das Dreieck anders orientiert, dann wird via Voting-Wert überprüft, wieviele Nachbarn anderes orientiert sind.
Sind mehr als 50% anders orientiert, wird das Dreieck gedreht.
Dies geschieht über eine Sub-Funktion, die vom Code aufgerufen wird.
Die Sub-Funktion hat einen einzigen Parameter, welcher den ID des Faces bzw. Triangles enthält. Durch diese ID kann auf das entsprechende Face zurückgegriffen werden. Der Algorithmus erzeugt nun aus den 3 Eck-Vertices des Faces zwei neue Faces. Beide jeweils anders orientiert (im UZS und gegen UZS). In einem weiteren Schritt wird nun geprüft, welches Face anders als das ursprüngliche Face orientiert ist. Das Face mit der größten Abweichung ersetzt nun das alte Face.
Selbst Durchdringungen erkennen und beheben
Auch diese Funktion verfügt über keine Parameter, da auch hier das ganze Mesh durchsucht wird.
Bevor jedoch diese Funktion aufgerufen wird, kommen zwei bereits implementierte Funktionen in GigaMesh zum Einsatz.
Zuerst wird ein Octree generiert woraufhin die Intersecetion-Detektion durchgeführt wird.
Anschließend sind alle Faces, die sich irgendwie schneiden in einer Liste verfügbar.
Unser Algorithmus kann auf diese Liste zugreifen und prüft nun welche Dreiecks-Paare sich schneiden.
Wurde ein Paar gefunden, dann werden die Schnittpunkte via Ray-Intersection-Verfahren berechnet.
Welches in einer einfacheren, jedoch etwas fehleranfälliger,
und einer komplexeren, mit mehreren Berechnungen und dafür wesentlich genaueren, Variante zur Verfügung stehen.
Beide sind über boolsche Variablen im Code aktivierbar.
Sind alle Schnittpunkte berechnet, werden diese via Delaunay Algorithmus neu trianguliert.
Daraufhin werden die neu triangulierten Dreiecke überprüft, so dass sich z.B. kein Dreieck außerhalb des "Original"-Faces befindet.