Das Kefk Network Wiki befindet sich im Testbetrieb.

Aus Kefk.

Marching Cubes ist ein Algorithmus zur Berechnung von Isoflächen in der 3D-Computergrafik. Er nähert eine Voxelgrafik durch eine Polygongrafik an.

Entwicklung des Algorithmus

[[Hilfe:Cache|Fehler beim Thumbnail-Erstellen]]: convert: unable to open image `/var/www/kefk/w/images/3/36/MRI_head_side.jpg': No such file or directory.

Eine Scheibe aus einer Aufnahme eines Magnetresonanztomografen. Die Helligkeit eines Bildpunktes gibt den Wasser- oder Fettgehalt des Gewebes an dieser Stelle wieder.

Marching Cubes wurde 1987 von William E. Lorensen und Harvey E. Cline als Ergebnis einer Forschungsarbeit für die Forschungsabteilung des Unternehmens General Electric in der Zeitschrift Computer Graphics vorgestellt. Lorensen und Cline beschäftigten sich mit der effizienten Visualisierung von Bilddaten bildgebender Verfahren wie Computertomografie, Magnetresonanztomografie und Single Photon Emission Tomography ^[1].

Bedeutung des Algorithmus

Für die Erläuterung unklarer Begriffe siehe die Artikel 3D-Computergrafik und Volumengrafik.

In der 3D-Computergrafik gibt es verschiedene Methoden, dreidimensionale Objekte zu modellieren. Eine davon ist die Modellierung als polygonale Oberfläche: Man fügt eckige Flächen - in der Regel Dreiecke - so aneinander, dass sie die Oberfläche des Objektes nachbilden. Diese Modelle können sehr schnell und einfach in Bilder umgesetzt werden, der Speicherbedarf eines Modells ist relativ gering und durch zahlreiche Raffinessen kann man dafür sorgen, dass die Bilder sehr realistisch wirken. Andererseits ist es fast unmöglich, auf diese Weise Objekte wie Nebel oder Wasser zu modellieren, die keine klar umrissene Oberfläche aufweisen.

Eine andere Methode ist die Modellierung als Voxel-Datenmenge: In regelmäßigen Abständen pickt man einen einzelnen Punkt aus dem Objekt heraus und liest dort die Dichte des Materials ab; das Ergebnis ist ein würfelförmiges dreidimensionales Gitter aus Voxeln. Bildgebende Systeme wie die Computertomografie erzeugen von Natur aus solche Modelle. Diese Voxel-Modelle können recht einfach in Bilder umgesetzt werden, die zudem sehr realistisch und detailgetreu wirken. Allerdings benötigt das Modell sehr viel Speicherplatz - in Größenordnungen von mehreren hundert Megabyte bis einigen Gigabyte - und die Visualisierung dauert erheblich länger als bei einem polygonalen Oberflächenmodell vergleichbarer Größe.

Marching Cubes ermöglichte es erstmals, unpraktikable Volumen-Modelle durch praktikable polygonale Oberflächen-Modelle anzunähern, um sie anschließend effizient zu visualisieren. Der Algorithmus befriedigte damit den Wunsch der Radiologie nach einem Verfahren, Daten bildgebender Systeme wie der Computertomografie schnell und aussagekräftig bildlich darzustellen. Auch heute noch ist Marching Cubes als effizienter Transformationsalgorithmus im Einsatz. Zwar hat die Volumengrafik in der Zwischenzeit Fortschritte gemacht und durch 3D-Texturen Eingang in die Computergrafik-Praxis gefunden, jedoch gibt es bisher keine Hardware, die die Volumengrafik auf ähnliche Weise beschleunigt, wie dies Grafikprozessoren mit polygonalen Oberflächen-Modellen tun.

Der Algorithmus

Die Idee von Marching Cubes ist es, das gegebene Voxelmodell eines Objekts zunächst in kleine Würfel zu zerlegen und anschließend von einem Würfel zum nächsten zu „marschieren“ und zu bestimmen, wie die Oberfläche des Objekts den jeweiligen Würfel durchschneidet. Dazu wird ein vom Benutzer gewählter Grenzwert verwendet, um zu bestimmen, welche Teile der einzelnen Würfel innerhalb und welche außerhalb des letztendlichen Objekts liegen. Durch Veränderung dieses als „Dichte“ interpretierten Grenzwerts kann der Benutzer bestimmen, welche Bereiche des Objekts dargestellt werden und welche nicht.

Eingabe

Der Algorithmus verarbeitet folgende Eingabeparameter:

• Voxelgrafik. Das Volumen-Modell des Objekts.

Format: Für gewöhnlich liegt eine Voxelgrafik als Liste L zweidimensionaler Arrays A_i - genannt „Scheiben“ - vor. Es gilt: L(i) = A_i, ferner ist A_z[x,y] = ρ_x,y,z ∈ [0,1] der Dichtewert des modellierten Objektes an der Stelle (x,y,z).

• Dichtewert ρ. Über diesen Parameter wird gesteuert, welche Bereiche des Modells als solide und welche als transparent interpretiert werden.

Format: ρ ∈ [0,1].

Datenstrukturen

Die folgenden Datenstrukturen werden vom Algorithmus verwendet oder erzeugt, aber nicht als Eingabeparameter übergeben:

• Triangle Lookup Table (TLT). Es gibt 256 Möglichkeiten, wie eine beliebig geformte Oberfläche einen Marching-Cubes-Würfel in Innen- und Außenbereiche aufteilen kann; denn laut Kombinatorik gibt es 2⁸ = 256 Möglichkeiten, die 8 Ecken eines Marching-Cubes-Würfels in 2 Mengen „innerhalb“ und „außerhalb“ aufzuteilen. Die Triangle Lookup Table enthält alle diese Möglichkeiten; dabei gibt es aufgrund der Symmetrie der Fälle tatsächlich nur 15 voneinander verschiedene Einträge.

Format: TLT(i) = {{v₁, v₂, v₃}, ... }, d. h. für den Fall i liefert TLT(i) eine Liste aller benötigten Dreiecke bestehend aus je drei Knoten.

• D. Der Algorithmus erstellt hier eine Liste aller Dreiecke, die benötigt werden, um die eingegebene Voxelgrafik durch eine Polygongrafik anzunähern.
• N. Zusätzlich zu der Dreiecksliste erstellt der Algorithmus hier eine Liste aller Einheitsnormalen der Knoten der Dreiecke.

Verarbeitung

1. Daten einlesen. Der Algorithmus wählt zunächst zwei direkt aufeinanderfolgende Scheiben A_i und A_i+1 aus dem eingegebenen Voxelmodell aus.
2. Kubus bilden. Dann bildet der Algorithmus aus vier benachbarten, ein Quadrat bildenden Knoten der Scheibe A_i und den vier direkt gegenüberliegenden Knoten der Scheibe A_i+1 einen Kubus. Die acht Ecken des Kubus werden als v₁, ..., v₈, die zwölf Kanten als e₁, ..., e₁₂ durchnummeriert; v steht dabei für vertex, „Knoten“, e für edge, „Kante“ (siehe Abbildung).
   Bild:Marching Cubes Kubus.png
3. Index des Kubus berechnen. Nun wird aus den Voxelwerten der acht Knoten ein Index zwischen 0 und 255 wie folgt gebildet: Ist v_i > ρ, so ist die i-te Ziffer eine 1, ansonsten eine 0. Man erhält also eine achtstellige Zahl, deren Ziffern jeweils 0 oder 1 sind; betrachtet man diese als Binärzahl und wandelt sie in eine Dezimalzahl um, so erhält man den gewünschten Index i ∈ {0, 1, ..., 255}.
4. Benötigte Kanten erzeugen. Schlage den Eintrag i in der Triangle Lookup Table nach, also TLT(i). Erzeuge alle dort angegebenen Dreiecke.
5. Oberflächenschnittpunkte interpolieren. Bestimme die Position jedes Knotens der eben erzeugten Dreiecke auf den Kanten des Würfels durch lineare Interpolation der anliegenden Ecken.
6. Einheitsnormalen berechnen und interpolieren. Berechne für jede Ecke des Kubus die Einheitsnormale und interpoliere die Einheitsnormalen der Knoten der eben erzeugten Dreiecke durch lineare Interpolation zwischen den Einheitsnormalen der anliegenden Kubus-Ecken.
7. Daten ausgeben. Füge die erzeugten Dreiecke und die dazugehörigen Einheitsnormalen der Liste aller bisher gefundenen Dreiecke und Einheitsnormalen hinzu und marschiere weiter zum nächsten Kubus.

Ausgabe

• Liste aller erzeugten Dreiecksknoten.
• Liste aller Einheitsnormalen in den Dreiecksknoten.

Verbesserungen

Der oben dargestellte Algorithmus für Marching Cubes ist sehr rudimentär. Er nutzt beispielsweise nicht aus, dass man bereits berechnete Informationen wieder verwenden kann: Teilen sich zwei benachbarte Kuben eine Kante, so müssen darauf liegende Knoten nur einmal interpoliert werden; der Nachbar kann die bereits gefundenen Knoten einfach übernehmen.

Da die Laufzeit des Algorithmus nur von der Anzahl der betrachteten Kuben abhängig ist, liegt in der Verminderung dieser Anzahl das größte Einsparpotenzial. Weitere Optimierungsansätze versuchen daher, vor dem Marching Cubes-Durchlauf diejenigen Würfel aus der Datenmenge herauszufiltern, die ohnehin nicht mit der Isooberfläche in Berührung kommen. Dies sind diejenigen Kuben, die vollständig innerhalb oder vollständig außerhalb des Objektes liegen.

Octree

Der erste Ansatz besteht darin, das Volumen in einem Octree abzulegen. In einem Octree wird jeder Würfel von Voxeln in acht Unterwürfel zerlegt. Zu jedem Würfel wird nun der niedrigste und der höchste Wert abgespeichert, der darin zu finden ist. Sind bei einem Würfel beide Werte gleich, so wird er nicht mehr weiter unterteilt. Das Ergebnis ist eine Hierarchie von kleiner werdenden Würfeln, für die jeweils ihr Werteintervall bekannt ist. Durch eine Travesierung dieser Hierarchie lassen sich nun diejenigen Würfel aussortieren, deren Minimum über oder deren Maximum unter dem Iso-Schwellwert liegt. Das Verfahren hat die Nachteile, dass bei jeder Änderung des Isowertes die Hierarchie komplett neu durchlaufen werden muss und dass in realistischen Datensätzen meist erst auf unteren Hierarchieebenen Würfel ignoriert werden können.

Quellen

1. ↑ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, Juli 1987

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Marching_Cubes, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.