Einführung FaceCenterPoints Zyklenberechnung VESTA-Zyklen Triangulierung Abstandsgesetz Ergebnisse Ausblick Anwendung Quellennachweise
Ein VESTA-Zyklus ist in dieser Implementation nichts anderes als eine Folge von FCP-structs. Jedes dieser structs enthält ein Vertex-Handle. Sobald man drei dieser Handles hat, kann man sich von OpenMesh ein Dreieck zeichnen lassen. Sind die Zyklen nun länger als 3, dann müssen diese Polygone in Dreiecke zerlegt werden. Das Problem, das dabei auftritt, besteht darin, dass die Polygone im allgemeinen nicht-planar sind und in einer vernünftigen Weise zerlegt werden müssen. Schlei weist in seinem Paper darauf hin, dass es unterschiedliche Möglichkeiten gibt, diese Polygone zu zerlegen, und schlägt für die VESTA-Zyklen der Länge 3 bis 7 folgende Triangulierungen vor (Bildquelle: Schlei, S. 7 [1] ):
In dieser Implementierung wurde diesen Vorschlägen in den Fällen (b),(c),(d),(g) gefolgt, aber nicht in den Fällen (e), (f), (h) und (i). Diese wurden durch die Triangulierungen (e'), (f') und (h') ersetzt (bei (h) und (i) handelt es sich um denselben Fall):
Wie man sieht, wurde bei allen Triangulierungen dieser Implementation stets ein Punkt ausgewählt, den alle Dreiecke einer Triangulierung teilen. Das hat den Vorteil, dass in einem VESTA-Zyklus stets nur dieser eine Punkt ermittelt werden muss und dann vom Triangulierungs-Algorithmus alle weiteren Punkte im Zyklus nur sukzessive abgelaufen und dabei die Dreiecke gezeichnet werden müssen.
Wichtig ist nun, dass die Wahl dieses Startpunktes nicht dem Zufall überlassen werden darf und gut überlegt sein muss. Wenn man das nicht macht, dann kann zum Beispiel bei einem 6-Zyklus ein Fall wie in Abbildung 18 (a) eintreten:
Wir sehen in dieser Abbildung stets dieselben zwei aktiven Voxel, die diagonal benachbart und im connected mode miteinander verbunden worden sind. Dadurch entstehen jeweils zwei Zyklen der Länge 6, die diese beiden Voxel miteinander verbinden - es liegt also der Fall aus Abbildung 12 (b) vor. In Fall (a) wurde der Startpunkt ungünstig gewählt, so dass die Vorder- und die Rückseite des Verbindungsstückes zum Teil direkt aufeinanderliegen. OpenMesh generiert in diesem Fall eine Fehlermeldung und weigert sich die hellgrün gefärbten Flächen zu zeichnen. Abgesehen davon, dass OpenMesh hier Probleme hat, eine Fläche ohne Löcher zu generieren, ist natürlich diese Oberflächengestaltung äußerst unschön. Um eine vernünftige Isofläche zu erhalten, muss nun einfach der Startpunkt für die Triangulierung richtig gewählt werden: Und zwar links oben an der Spitze, wo der VESTA-Zyklus einen 60-Grad-Winkel bildet (oder - was denselben Effekt hätte - oben rechts an der Spitze; dort bildet der VESTA-Zyklus ebenfalls einen 60-Grad-Winkel). Diese Triangulierung entspricht genau der von Schlei in Abb. 16 (g) vorgeschlagenen Triangulierung.
Wie findet man nun den Startpunkt, von dem ausgehend alle Dreiecke der Triangulierung gebildet werden müssen? Dazu schaut man sich die Orientierungen der Face Center Points des VESTA-Zyklus an, die in dem Attribut ori abgespeichert sind. Bei dem 6-Zyklus aus Abbildung 16 (g) könnte die Abfolge dieser Orientierung zum Beispiel folgende sein:
4 2 6 4 5 1
oder - falls man an einem anderen Face Center Punkt gestartet ist -:
6 4 5 1 4 2
Der mögliche Startpunkt ist nun dadurch ausgezeichnet, dass er eine der Orientierungen besitzt, die genau zweimal und im Abstand von 3 auftauchen. Also wenn die Folge
F A B C A D
gegeben ist, dann ist damit klar, dass der Startpunkt der Triangulierung bei einem A liegt. Dann kann man die Folge umsortieren zu
A B C A' D F
und sukzessive die Dreiecke ABC, ACA', AA'D und ADF zeichnen:
Allerdings sind damit nicht alle Fälle des 6-Zyklus abgedeckt. Es gibt 6-Zyklen, wo die Face Center Points mit derselben Orientierung nicht im Abstand von 3 auftauchen - dann liegt nämlich der Fall aus Abbildung 16 (h) bzw. (i) vor. Hier muss dann der Startpunkt mit einem anderen Verfahren ermittelt werden. Ebenso sind für sämtliche Zyklen, die länger als 5 sind, derartige Überlegungen anzustellen. Alle diese Abfragen, die dazu erforderlich sind, werden in der Funktion createTriangles gemacht.
Für die Triangulierungen der 8-,9- und 12-Zyklen sind in dem Paper von Schlei keine Empfehlungen gemacht worden. Sie treten zwar relativ selten auf, aber natürlich darf man auch hier die Wahl des ausgezeichneten Punktes, der als Eckpunkt aller Dreiecke fungiert, nicht dem Zufall überlassen. Tatsächlich ist nicht von vorneherein klar gewesen, ob es bei den 9- und 12-Zyklen überhaupt einen derartigen ausgezeichneten Startpunkt gibt, der eine vernünftige Triangulierung ermöglicht, oder ob ein Triangulierungsverfahren wie in Abbildung 16 (f) verwendet werden muss. Wie sich aber gezeigt hat und auf folgender Abbildung zu sehen ist, gibt es einen derartigen Startpunkt:
Dass die Triangulierung für das nicht-planare 12-Eck tatsächlich sinnvoll ist, zeigt folgende Abbildung:
Wie so ein 12-Zyklus im mixed mode entsteht, sieht man sehr schön in Abbildung 21 (b): Man sieht 4 aktive Voxel, die allesamt diagonal benachbart sind. Der Voxel hinten rechts oben ist derjenige, mit dem die anderen drei Voxel verbunden sind. Da diese drei Voxel aber nicht direkt miteinander verbunden sind, sind jeweils zwei von ihnen immer disconnected, und dadurch entsteht der 12-Zyklus im Inneren dieses Gebildes. Der Startpunkt, der als Eckpunkt aller Dreiecke fungiert, wurde in 21 (a) mit der Ziffer 1 bezeichnet.
Obwohl die eben beschriebenen Triangulierungen für die allermeisten Fälle funktionieren und fehlerfreie Oberflächen liefern, können allerdings doch noch vereinzelt Fälle auftreten, wo diese versagen. Folgende Abbildung zeigt das bei zwei Zyklen der Länge 8:
Wenn zwei 8-Zyklen, wie in Abbildung 22 (b) gezeigt, zufällig direkt aneinandergrenzen, dann kommt es zur Überlappung der gelb eingezeichneten Dreiecke (Vorderseite: hellgelb, Rückseite: dunkelgelb). Es liegt also hier wieder ein Fall wie in Abbildung 18 (a) vor, wo zwei Dreiecke mit ihren Rückseiten direkt aufeinander liegen. Eine Möglichkeit, diesem Dilemma zu begegnen, besteht darin, den Startpunkt für die Triangulierung rechts außen zu wählen, wie in Abbildung 22 (c) gezeigt. Allerdings ist diese Lösung nicht wirklich schön, da dann die zwei aktiven Voxel, die sich an den Positionen R und S befinden, plötzlich miteinander verbunden sind - sie sollten aber in diesem Fall gerade eben nicht im connected mode gezeichnet werden (genau dieser Umstand ist ja Schuld daran, dass der 8-Zyklus generiert wurde). Zwar lassen sich 8-Zyklen so zeichnen - und in dieser Implementierung lässt dich diese Art der Triangulierung dadurch generieren, dass man mittels des Setters setSemiConnectedMode diese Art der Triangulierung festlegt -, doch gibt es eine bessere Art, diesem Problem zu begegnen, und zwar indem man bei der Triangulierung einen zusätzlichen Punkt einfügt.
Dieser Triangulierungsmodus wird von Schlei als High Resolution Mode bezeichnet und dem Low Resolution Mode gegenübergestellt. Dieser Modus hat nicht nur den Vorteil, dass der eben beschriebene Fall, in dem zwei Dreiecke mit ihren Rückseiten direkt aufeinanderliegen, nicht mehr eintritt, sondern auch, dass das Oberflächen-Mesh feingranularer unterteilt ist. Der Nachteil besteht darin, dass die Oberfläche aus mehr Faces und Vertices besteht.
Die Triangulierung funktioniert nun folgendermaßen: Man fügt einfach einen zusätzlichen Punkt in die Mesh ein, der genau im Schwerpunkt der anderen Punkte des Zyklus positioniert wird. Dieser Punkt ist der Startpunkt für die Triangulierung, also der Punkt, der als Eckpunkt aller Dreiecke fungiert. Die folgende Abbildung zeigt das Verfahren am Beispiel eines 6-Zyklus:
In Abbildung 23 (a) wird der noch nicht triangulierte Zyklus gezeigt: A B C A' D F. Nun wir der Punkt X im Schwerpunkt hinzugefügt (Abbildung 23 (b)) und ausgehend von diesem Punkt X sechs Dreiecke gezeichnet, nämlich XBC, XCA', XA'D, XDF, XFA und XAB. Im Ergebnis erhalten wir eine feiner unterteilte Oberfläche, und es gibt keine Dreiecke mehr, deren Rückseiten direkt aufeinanderliegen (wie zum Beispiel in Abbildung 18 (a)). Ein weitere Vorteil besteht darin, dass keine aufwändigen Überlegungen darüber anzustellen sind, welcher der Face Center Points als Startpunkt in Frage kommt, sondern der Startpunkt ist einfach gegeben als Schwerpunkt aller Face Center Points. Die Triangulierungen, die sich hier für alle Zyklen ergeben, sind auf folgender Abbildung darstellt. Die einzelnen Darstellungen stammen, abgesehen von 24 (m), wieder aus dem Paper von Schlei (Bildquelle: Schlei, S. 9 [1] ).
Anzumerken ist, dass ein Zyklus der Länge 3 natürlich nicht weiter zerlegt zu werden braucht. Und auch wenn bei den Zyklen der Länge 8, 9 und 12 die genaue Triangulierung in dieser Darstellung nicht gut auszumachen ist, so sind doch gerade diese Triangulierungen besonders wichtig, denn sie garantieren, dass keine Dreiecke mit Rückseiten aufeinander zu liegen kommen. Um die Vorteile des High Resolution Modes bei den Zyklen der Länge 8, 9 und 12 auskosten zu können, aber den Nachteil einer höheren Anzahl von Faces und Vertices in dem Mesh zu minimieren (bei den häufig auftretenden Zyklen der Länge 4 verdoppelt sich die Anzahl der Faces im High Resolution Mode!), wurde in dieser Implementierung ein Medium Resolution Mode eingeführt, der die Zyklen der Länge 3,4,5,6,7 im Low Resolution Mode zeichnet, während er bei Zyklen der Länge 8,9,12 in den High Resolution Mode springt. Dieser Mode wird mit dem Setter setMediumMode eingestellt.
Ein weiterer Mode lässt sich darüber hinaus mit setSpecialMode setzen. Dieser Mode versucht alle Zyklen, wie gewünscht, zu zeichnen, springt aber dann, wenn OpenMesh im Low Resolution Mode ein Dreieck nicht zeichnen kann, weil es sich mit einem anderen überlappt, in den High Resolution Mode.
Einführung FaceCenterPoints Zyklenberechnung Vesta-Zyklen Triangulierung Abstandsgesetz Ergebnisse Ausblick Anwendung Quellennachweise
1.8.6
