WikiDer > Marschwürfel
Marschwürfel ist ein Algorithmus für Volumen-Rendering Biene Computergrafik. Der Algorithmus stellt ein dreidimensionales Objekt als eine Sammlung verbundener Polygone (normalerweise Dreiecke) Der Algorithmus wurde erstmals veröffentlicht in 1987 von William E. Lorensen und Harvey E. Cline.
Algorithmus
Operation
Man sollte davon ausgehen, dass ein 3D-Objekt in ein dreidimensionales Gitter mit vielen Zellen unterteilt ist. Der Algorithmus baut nun a Gittergewebe des 3D-Objekts bestehend aus einer Vielzahl von Dreiecken. Dazu werden zunächst alle Zellen markiert, die sich außerhalb des Objekts befinden. Für jede "äußere Zelle" werden nun ein oder mehrere Dreiecke gezeichnet.
Die Hauptarbeit des Algorithmus besteht darin, zu bestimmen, wie viele Dreiecke pro Zelle gezeichnet werden sollen, welche Form und Ausrichtung die Dreiecke in Bezug auf den Betrachter haben werden. Dazu wird eine Zelle als Würfel (Marschwürfel) dargestellt. Dieser Würfel wird von einem Teil des 3D-Objekts geschnitten. Die Schnittebene, die das 3D-Objekt im Marschwürfel erzeugt, besteht aus wenigen Dreiecken. Einfach ausgedrückt bildet der Algorithmus den Schnittpunkt, indem er die Schnittpunkte des Schnittpunkts mit dem Würfel entlang der Seiten des Würfels verschiebt, sodass die Dreiecke, aus denen der Schnittpunkt besteht, die richtige Form erhalten. Die Form der Schnittebene wird als eine Ansammlung von Punkten definiert. Die Ausrichtung der Schnittebene wird durch die normaler Vektor. Die Kreuzungen und die Orientierung werden gespeichert, bevor zum nächsten Marschwürfel gewechselt wird.
Da einfache Polygone verwendet werden, kann die Grafikhardware diese problemlos verarbeiten und das 3D-Objekt kann schnell angezeigt werden.
Würfel schneiden Cutting
Ebenen, die einen Würfel schneiden, können auf viele Arten angezeigt werden, wobei bestimmte Ecken des Würfels auf der "Innenseite" oder "Außenseite" des Querschnitts liegen. Wenn bekannt ist, wie viele und welche Ecken eines Würfels darin liegen, d.h. außerhalb eines Würfelquerschnitts liegen, lässt sich leicht feststellen, welche Schnittpunkte dafür verantwortlich sind. Es kann berechnet werden, dass es 256 Möglichkeiten gibt, Querschnitte eines Würfels zu erstellen, wobei eine bestimmte Anzahl von Ecken auf der "Innenseite" oder auf der "Außenseite" des Querschnitts liegt. Tatsächlich können durch die Symmetrie des Würfels 15 Fälle unterschieden werden, die alle 256 Schnittpunkte bilden können. Diese Fälle können in einer sogenannten "Triangle Lookup Table" (TLT) gespeichert werden. Wenn nun bekannt ist, wie viele und welche Knoten sich nun an der Außenseite eines Würfels befinden, kann über das TLT schnell der entsprechende Querschnittsfall ermittelt werden.
Prozess
Für jede Zelle im 3D-Objekt wird Folgendes getan:
- Würfel bauen: Stellen Sie einen imaginären Würfel aus 4 Datenpunkten von Layer k und 4 Datenpunkten von Layer k 1 des 3D-Objekts zusammen. Die 8 Datenpunkte fungieren als die 8 Knoten eines Würfels (v1...v8).
- Scheitelpunkte klassifizieren: Das 3D-Objekt schneidet diesen imaginären Würfel. Bestimmen Sie, welche Scheitelpunkte des imaginären Würfels innerhalb oder außerhalb des 3D-Objekts liegen.
- Index berechnen: Erstellen Sie einen Index zwischen 0 und 255 (1 Byte). Jedes Bit im Byte repräsentiert einen Scheitelpunkt. Wenn ein Scheitelpunkt außerhalb des 3D-Objekts liegt, wie in Schritt 2 bestimmt, wird das betreffende Bit '1', andernfalls '0'.
- Seiten bestimmen: Über den Index kann eine Schnittebene aus dem TLT ausgewählt werden. Jeder Schnittpunkt besteht aus einem oder mehreren Dreiecken.
- Schnittpunkte der Schnittebene durch Interpolation ermitteln: Die genauen Schnittpunkte des Querschnitts mit dem imaginären Würfel werden durch Interpolation mit den Scheitelpunkten des imaginären Würfels bestimmt.
- Berechnen und Interpolieren von Normalenvektoren: Für jede Seite des imaginären Würfels wird ein Normalenvektor berechnet. Interpolieren Sie nun die Normalenvektoren der Schnittpunkte durch lineare Interpolation zwischen den Normalenvektoren der Würfelecken.