Der Marching Cube Algorithmus

In seiner ursprünglichen Variante wird dieser Algorithmus zur Berechnung von Isoflächen skalarer Werte verwendet, die auf einem regelmäßigen Gitter bekannt sind. Im Dreidimensionalen werden alle ,,Würfel (Cubes) benachbarter Knoten`` (siehe Abb. 4.1) durchlaufen.

Abbildung: Marching Cube auf einem regelmäßigen Skalarfeld mit Knoten unterhalb eines Isowertes (rot), dadurch resultierenden Punkten auf den Kanten (blau) und der mit Hilfe einer Tabelle erzeugten zugehörigen Triangulierung (grün).

Für jeden Würfel werden die Ecken bestimmt, die einen festen Isowert überschreiten. Auf Kanten, die die Isofläche durchdringen, da die beteiligten Ecken nicht beide ober- bzw. unterhalb des Isowertes liegen, wird mittels Interpolation bestimmt, an welcher Stelle der Isowert angenommen wird. Nun werden auf Grund der Eck-Konfiguration (einfacher Tabellenaufruf, siehe [3]) die ermittelten Punkte auf den Kanten zu einer Isofläche des einzelnen Würfels verbunden. Beim Durchlaufen des Skalarfeldes können die Daten des vorangegangenen Würfels, also Skalarwerte an schon ausgewerteten Ecken und Kanten wiederverwendet werden. So marschiert also der Würfel durch das Skalarfeld und erzeugt, unter der Annahme von Randpunkten des Skalarfeldes, die alle unterhalb des Isowertes liegen, eine geschlossene Hülle um alle Knoten, die oberhalb liegen. Die Vorschrift für die Triangulierung eines Würfels ist damit noch nicht eindeutig. Siehe dazu Abb. 4.2.

Abbildung 4.2: Wahlfreiheit der Triangulierung

Auf der Website [3] fand ich die Liste einer Beispielimplementierung des MCA. Diese habe ich, leicht abgewandelt, in meiner Arbeit verwendet. So stellte ich sicher, dass in Situationen wie in Abb. 4.2 stets Fall (a) gewählt wird, da ohnehin eines der störendsten Artefakte des Algorithmus instabile, durch Flackern auffallende Verbindungen zwischen einzelnen Tropfen oder Flüssigkeitsansammlungen sind.

Je näher sich Partikel kommen müssen, um als eine Zusammenhangskomponente dargestellt zu werden, desto größer ist auch die Wahrscheinlichkeit, dass die Physik eine parallele Bewegung auf einer kritischen Distanz verhindert, welche besonders zu derartigen Artefakten führen dürfte.