Der "Marching Cubes" Algorithmus

Entwickelt wurde der Marching Cubes Algorithmus 1987 von William E. Lorensen und Harvey E. Cline für das Unternehmens General Electric als Hilfsmittel zur Visualisierung von Daten aus bildgebenden Verfahren wie z.B. der Computertomographie. Der Algorithmus berechnet für ein dreidimensionales skalares Feld und einen gegebenen Cut-Off-Wert eine Einhüllende, d.h. ein Polygon-Mesh, dass zusammenhängende Punkte mit einem skalaren Wert grösser oder gleich dem Cut-Off Wert von solchen mit einem niedrigeren Wert trennt.

Damit lassen sich etwa bei Messdaten einer CT einzelne Knochenpartien, Organe o.Ä. mit einem bestimmten Dichtewert einzeln visualisieren.

Seinen Namen verdankt der Algorithmus der Tatsache, dass die Daten dabei Würfel-weise in die Berechnung einbezogen werden. Jeweils acht Punkte mit Skalarwert, die im dreidimensionalen Feld einen Würfel bilden werden ausgewählt, wobei von links nach rechts, von oben nach unten und von vorne nach hinten iteriert wird. Da der Würfel aus acht Eckpunkten besteht, deren Skalarwert jeweils entweder kleiner oder grösser/gleich dem Cut-Off-Wert ist, ergeben sich 256 mögliche Konfigurationen. Durch Drehungen und Inversionen lassen sich diese aber auf 15 Grundfälle zurückführen, für die Lorensen und Cline jeweils die entsprechenden Einhüllenden-Polygone angaben:

Auf diese Polygone werden dann die Überführungs-Operationen (Drehungen, etc.) - durch welche die Konfiguration des Würfels in den Grundfall überführt wurde - in umgekehrter Reihenfolge angewandt. Anschliessend werden sie in einer Liste gespeichert die nach Ausführung des Algorithmus die Einhüllende enthält.

Mit diesem Verfahren ergaben sich allerdings bald Probleme für gewisse Datensätze, bei denen der Algorithmus Einhüllende mit "Löchern" lieferte. Zurückzuführen war dieses Problem auf angrenzende Würfel, deren gemeinsame Seite von der rechts dargestellten Diagonalform war. In diesen Fällen ist es möglich die Einhüllende so zu erzeugen, dass die "schwarzen" Eckpunkte auf der gemeinsamen Seite verbunden werden, oder aber auch die "Weissen". Wird diese Wahl bei den beiden angrenzenden Würfeln jeweils unterschiedlich getroffen, passen die Polygone der Einhüllenden nicht mehr aneinander, wie in folgendem Beispiel:

Zur Behebung des Problems entwickelten Nielson und Hamann 1991 das Verfahren des "Asymptotic Decider". Dabei fügten Sie zunächst für alle Grundfälle die mindestens eine Seite von der besagten Diagonalform hatten, Komplementärfälle hinzu, die alle Möglichkeiten schwarz von weiss zu trennen abdecken, wie im Bild dargestellt.

Um bei beiden angrenzenden Würfeln konsistent eine Möglichkeit der Abtrennung zu wählen kommt nun das "asymptotic decider"-Verfahren zum Einsatz. Dabei wird den vier Eckpunkten der Grenzfläche ihr ursprünglicher Skalarwert als Funktionswert zugewiesen und zwischen den Punkten bilinear interpoliert.

Da die Skalarwerte zweier gegenüberliegender Punkte dabei grösser/gleich und die der beiden Anderen kleiner dem Cut-Off-Wert sind bildet auf der interpolierten Fläche die Grenze zwischen Funktionswerten die über und solchen die unter dem Cut-Off-Wert liegen eine Hyperbel die im Bild rot gestrichelt eingezeichnet ist. Nun wird der Ursprung dieser Hyperbel berechnet. Je nachdem ob der interpolierte Funktionswert im Ursprung grösser/gleich oder kleiner dem Cut-Off-Wert ist werden die Fälle so gewählt dass durch die Einhüllende die entsprechenden Eckpunkte auf der Grenzfläche verbunden werden.