Marching Cube Ambiguities versus Marching Tetrahedron

Question

Ich habe den Marching Cubes Algorithmus erfolgreich implementiert. Ich habe die Standardmaterialien als Referenz verwendet, aber ich habe es komplett neu geschrieben. Es funktioniert, aber ich beobachte die Mehrdeutigkeiten, die zu Löchern im Netz führen.

Ich habe über den Marsch-Tetraeder-Algorithmus nachgedacht, der angeblich nicht unter Zweideutigkeiten leidet. Ich sehe nicht, wie das möglich ist.

Der marschierende Tetraeder-Algorithmus verwendet sechs Tetraeder anstelle eines Würfels mit Triangulationen für jedes Tetraeder. Aber angenommen, ich würde den Marsch-Würfel-Algorithmus implementieren, aber für jede der 256 Triangulierungen wähle einfach die, die die "Summe" (Vereinigung) der Triangulationen des Würfel-Tetraeders ist. Soweit ich weiß, ist dies, was marschierende Tetraeder tut - warum also mag das die Mehrdeutigkeiten magisch beheben?

Es gibt 16 einzigartige Fälle, denke ich, und die 240 anderen sind nur Reflexionen/Umdrehungen dieser 16. Ich erinnere mich, irgendwo in einer Zeitung gelesen zu haben, dass um Mehrdeutigkeiten aufzulösen, 33 Fälle benötigt werden. Könnte das damit zusammenhängen, dass marschierende Tetrahedons irgendwie nicht unter Problemen leiden?

Also, Fragen:

1. Warum Tetraedern nicht marschieren nicht von Mehrdeutigkeiten leiden?
2. Wenn nicht, warum benutzen die Leute nicht einfach den Marching Cubes Algorithmus, sondern stattdessen die Triangulierungen der Tetraeder?

Ich fühle mich wie etwas hier fehlt. Vielen Dank.

Answer 1

Okay, nun, ich habe gerade meine Version von marschierenden Tetraedern fertiggestellt, und während ich leicht Mehrdeutigkeiten sah, die zu Problemen im Netz der marschierenden Würfel führten, scheint das Netz des marschierenden Tetraeders durchwegs topologisch korrekt zu sein. Dort sind einige lästige Features entlang sehr dünner Punkte, wo einige Vertices nicht ganz entscheiden können, auf welcher Seite des Grabens sie sein wollen, aber das Mesh ist immer wasserdicht.

In Antwort auf meine Fragen:

1. Um Unklarheiten in der Marching Cubes Algorithmus zu beheben, soweit ich das beurteilen kann, wertet man die Funktion genauer in der Zelle. Im Tetraeder-Algorithmus wird explizit das Zentrum der Zelle abgetastet und zu ,, polygonalisiert. Ich vermute, dass, weil das Tetraedergitter insbesondere diesen Scheitelpunkt enthält, Zweideutigkeiten implizit behandelt werden. Die anderen zusätzlichen Ecken auf der Seite haben wahrscheinlich auch etwas damit zu tun. Als ein wichtiger Punkt wird die Funktion tatsächlich an mehr Orten gesampelt, wenn Sie sie verfeinern.
2. Ich bin mir ziemlich sicher, dass sie es tun. Mein Marsch-Tetraeder-Algorithmus macht genau das, und ich denke, dass er intern dasselbe tut wie der klassische Marsch-Tetraeder-Algorithmus. In meiner Implementierung werden die Dreiecke der Tetraeder für jeden möglichen Würfel aufgelistet, was vermutlich schneller ist, als das eine oder die zwei Dreiecke für jedes einzelne Tetraeder einzeln herauszufinden.

Wenn ich die Zeit und Aufmerksamkeitsspanne hatte (weder von denen ich zu tun), kann es vorteilhaft sein, die Innenseiten der einzelnen Würfel neu vernetzt weniger Dreiecke maximal zu nutzen, die ich denke, würde es nicht schaden.

Answer 2

Nehmen Sie das folgende 2d Beispiel (die Zweideutigkeiten führt):

Wenn wir diesen Platz in zwei Dreiecke teilen, werden wir unterschiedliche Ergebnisse in der Diagonale bekommen wir teilen wählte das Quadrat. Entlang der 0-0-Diagonalen erhalten wir Dreiecke (010,010), während wir für die 1-1-Diagonale Dreiecke (101,101) erhalten. Offensichtlich führt eine unterschiedliche Zerlegung des Quadrats zu unterschiedlichen Ergebnissen. Beides ist korrekt und das gilt auch für 3D-Würfel.

MT löst die Mehrdeutigkeiten nicht wirklich auf, aber es kann topologisch konsistentes Ergebnis erzeugen, indem die gleiche Zerlegungsstrategie für alle Würfel gewählt wird. So wie es von Unklarheiten befreit wird.

Answer 3

Um die Frage zu beantworten "Warum hat Marching Tetrahedrons Algo Unklarheiten?" Es ist notwendig zu verstehen, warum die Unklarheiten in erster Linie in Marching Cubes entstehen.

---

Mehrdeutigkeiten auftreten kann, wenn es zwei diagonal gegenüberliegende „positive“ Ecken und zwei diagonal gegenüberliegender „negativer“ Vertices in einem Würfel. Ich brauchte einige Zeit, um mich daran zu erinnern, aber das Problem mit Mehrdeutigkeiten besteht darin, dass sie theoretisch erlauben, Isoflächen-Patches für benachbarte Cubes zu erstellen, die miteinander inkompatibel sind. Das ist der offensichtliche Teil. Der interessante Teil ist, dass zwei benachbarte Isoflächenfelder aus zwei mehrdeutigen Konfigurationen inkompatibel sind, wenn (und nur wenn) eine von ihnen "negative" Scheitelpunkte trennt und die andere "positive" Scheitelpunkte trennt.

ist hier ein relevantes Zitat aus Rephael Wengers großes Buch „Isosurfaces Geometrie, Topologie & Algorithms“ (nicht mehr als 2 Links posten, also habe ich alle relevanten Bilder aus dem Buch in eine single one verschmolzen):

Rand eines dreidimensionalen Isooberfläche Patchs Würfels definiert eine Isokontur auf jedem der quadratischen Facetten des Würfels. Wenn der Isoflächen-Patch einer Konfiguration die negativen Scheitelpunkte auf der Facette trennt, während einbenachbarter Kon fi gurations-Isoflächen-Patch die positiven trennt, dann werden die Isoflächenkanten auf der gemeinsamen Facette nicht ausgerichtet. Die Isoflächen-Patches in Abbildung 2.16 trennen die positiven Scheitelpunkte auf keiner Facette. Darüber hinaus teilen die abgeleiteten Isoflächen-Flächen Patches in jeder Drehung oder Reflexion der Konfigurationen auch keine positiven Ecken auf jeder Facette . Somit sind die Isoflächenfelder in irgendwelchen zwei benachbarten Würfeln richtig an ihren Grenzen ausgerichtet. Eine gleichwertige, aber kombinatorisch unterschiedliche Isoflächen-Tabelle könnte erzeugt werden, indem Isosurface-Patches verwendet werden, die die negativen Scheitelpunkte auf jeder quadratischen Facette nicht trennen.

Was dies bedeutet ist, dass, wenn alle verwendet mehrdeutige Konfigurationen das gleiche Muster (das heißt immer getrennt „negative“ Eckpunkte) folgen, dann ist es unmöglich, eine topologisch falsche Oberfläche zu erzeugen. Und Probleme treten auf, wenn Sie Konfigurationen "aus beiden Welten" für eine einzelne Isofläche verwenden.

Die Oberfläche, die die gleiche Doppeldeutigkeit-Auflösungsmuster konstruiert wurde mit noch unerwünschte Fehler wie this enthalten (aus „Effiziente Umsetzung von Marching Cubes' Fälle mit topologischen Garantien“ Artikel von Thomas Lewiner Helio Lopes, Antonio Wilson Vieira und Geovan Tavares), aber es wird, wie Sie gesagt haben, wasserdicht.

Um dies zu erreichen, müssen Sie die Nachschlagetabelle basierend auf den 22 einzigartigen Konfigurationen verwenden (nicht den Standard 14 oder 15), die in Abbildung 2.16 gezeigt werden. Jetzt

---

, zurück auf die ursprüngliche Frage schließlich - warum Marschieren Tetraedern leidet nicht an Zweideutigkeiten? Aus dem gleichen Grund wird es in den Marching Cubes keine Unklarheiten geben, wenn sie wie oben beschrieben ausgeführt werden - weil Sie willkürlich eine der beiden verfügbaren Varianten einer mehrdeutigen Konfigurationsauflösung gewählt haben. In Marching Cubes ist es überhaupt nicht offensichtlich (zumindest für mich, musste viel graben), dass dies sogar eine Option ist, aber in Marching Tetrahedrons ist es für Sie durch den Algorithmus selbst getan. Hier ist ein weiteres Zitat aus Rephael Wenger Buch:

Die regelmäßigen Gitterwürfel haben mehrdeutige Konfigurationen, während die tetraedrischen Zersetzung nicht. Was ist mit den mehrdeutigen Konfigurationen passiert? Diese Konfigurationen werden durch die Wahl der Triangulation gelöst. In Abbildung 2.31 beispielsweise liefert die erste Triangulation ein Isoflächen-Patch mit zwei Komponenten, die in Abbildung 2.22 2B-II entsprechen, während die zweite ein Isoflächen-Patch mit einer Komponente entsprechend 2B-I ergibt.

Beachten Sie, wie Würfel in Abbildung 2.31 auf zwei verschiedene Arten in Tetraeder geschnitten werden. Die Wahl dieses Slicings oder des anderen ist die geheime Soße, die die Unklarheiten löst.

Man kann sich fragen: Wenn das Mehrdeutigkeitsproblem gelöst werden kann, indem man für alle Würfel dasselbe Muster anwendet, warum gibt es dann so viele Bücher und Papiere über kompliziertere Lösungen? Warum brauche ich Asymptotic Decider und all das Zeug? Soweit ich das beurteilen kann, kommt es darauf an, was Sie erreichen müssen. Wenn topologische Korrektheit (wie in, keine Löcher) für dich genug ist, dann brauchst du nicht alle fortgeschrittenen Dinge. Wenn Sie Probleme wie die in "Effiziente Implementierung von Marching Cubes" oben gezeigten Artikel lösen möchten, müssen Sie tiefer tauchen.

Ich empfehle den entsprechenden Kapiteln Rephael Wenger Buch zu lesen „Isosurfaces Geometrie, Topologie & Algorithms“ um besser auf die Natur dieser Algorithmen zu verstehen, was sind die Probleme, wo kommen die Probleme kommen und wie sie sein können gelöst.

Wie von Li Xiaosheng aufgezeigt wurde, können die Grundlagen besser verstanden werden, indem man die Marching Squares zuerst gründlich untersucht. Eigentlich wurde die ganze Antwort von Li Xiaosheng niedergelegt, ich habe die Erklärungen nur ein wenig erweitert.