Rasterung

Berechnungen

Um herauszufinden, ob ein Pixel der Bildebene von einem Dreieck bedeckt wird, reicht es, zu prüfen, ob der Projektionsstrahl (siehe Zentralprojektion), der durch das Pixel verläuft, das Dreieck schneidet.

Nimmt man an, dass das Projektionszentrum ${\displaystyle {\vec {e}}}$ der Koordinatenursprung des dreidimensionalen kartesischen Koordinatensystems ist, und bezeichnet die Ecken des projizierten Dreiecks mit ${\displaystyle {\vec {p_{0}}}}$, ${\displaystyle {\vec {p_{1}}}}$, ${\displaystyle {\vec {p_{2}}}}$ (Bild 1), dann ergibt sich folgende Bedingungen dafür, dass das Pixel ${\displaystyle {\vec {d}}}$ im projizierten Dreieck liegt (Bild 2):

• Die Ebene, die durch das Dreieck ${\displaystyle ({\vec {e}},{\vec {p_{1}}},{\vec {p_{0}}})}$ verläuft, teilt den dreidimensionalen Raum in zwei Halbräume. Das Pixel der Bildebene muss in dem Halbraum liegen, in dem sich der Punkt ${\displaystyle {\vec {p_{2}}}}$ befindet. Außerdem muss das Pixel
• in dem durch das Dreieck ${\displaystyle ({\vec {e}},{\vec {p_{2}}},{\vec {p_{1}}})}$ definierten Halbraum liegen, in dem sich der Punkt ${\displaystyle {\vec {p_{0}}}}$ befindet und
• in dem durch das Dreieck ${\displaystyle ({\vec {e}},{\vec {p_{0}}},{\vec {p_{2}}})}$ definierten Halbraum liegen, in dem sich der Punkt ${\displaystyle {\vec {p_{1}}}}$ befindet.

Um zu prüfen, ob sich ein Punkt ${\displaystyle {\vec {d}}}$ in einem durch die Punkte ${\displaystyle {\vec {e}}}$, ${\displaystyle {\vec {p_{1}}}}$ und ${\displaystyle {\vec {p_{0}}}}$ definierten Halbraum befindet, kann man folgende Funktion verwenden (Bild 3):

${\displaystyle V({\vec {d}}):={\vec {n_{2}}}\cdot {\vec {d}}=(({\vec {p_{1}}}-{\vec {e}})\times ({\vec {p_{0}}}-{\vec {p_{1}}}))\cdot {\vec {d}}}$

wobei ${\displaystyle {\vec {n_{2}}}\cdot {\vec {d}}}$ das Skalarprodukt der Vektoren ${\displaystyle {\vec {n_{2}}}}$ und ${\displaystyle {\vec {d}}}$ ist. Der Normalenvektor ${\displaystyle {\vec {n_{2}}}}$ ist durch das Kreuzprodukt

${\displaystyle {\vec {n_{2}}}:=({\vec {p_{1}}}-{\vec {e}})\times ({\vec {p_{0}}}-{\vec {p_{1}}})}$

definiert und ist orthogonal zum Dreieck ${\displaystyle ({\vec {e}},{\vec {p_{1}}},{\vec {p_{0}}})}$. Diese Funktion berechnet das 6-fache vom Volumen des Tetraders mit den Ecken ${\displaystyle {\vec {e}}}$, ${\displaystyle {\vec {p_{1}}}}$, ${\displaystyle {\vec {p_{0}}}}$, ${\displaystyle {\vec {d}}}$. Wenn der Punkt ${\displaystyle {\vec {d}}}$ oberhalb des Dreiecks ${\displaystyle ({\vec {e}},{\vec {p_{1}}},{\vec {p_{0}}})}$ liegt, ist das Vorzeichen positiv, wenn ${\displaystyle {\vec {d}}}$ unterhalb liegt, ist das Vorzeichen negativ. Wenn ${\displaystyle {\vec {d}}}$ in der Ebene des Dreiecks ${\displaystyle ({\vec {e}},{\vec {p_{1}}},{\vec {p_{0}}})}$ liegt, ist das Volumen gleich 0. Der Skalierungsfaktor für das Volumen kann hier weggelassen werden, weil bei diesen Betrachtungen nur das Vorzeichen der Funktion wichtig ist.

Entsprechendes gilt für die Dreiecke ${\displaystyle ({\vec {e}},{\vec {p_{2}}},{\vec {p_{1}}})}$ und ${\displaystyle ({\vec {e}},{\vec {p_{0}}},{\vec {p_{2}}})}$.

Mit den Funktionen

${\displaystyle V_{0}({\vec {d}}):=({\vec {p_{2}}}-{\vec {e}})\times ({\vec {p_{1}}}-{\vec {p_{2}}})}$

${\displaystyle V_{1}({\vec {d}}):=({\vec {p_{0}}}-{\vec {e}})\times ({\vec {p_{2}}}-{\vec {p_{0}}})}$

${\displaystyle V_{2}({\vec {d}}):=({\vec {p_{1}}}-{\vec {e}})\times ({\vec {p_{0}}}-{\vec {p_{1}}})}$

kann folgende Aussage formuliert werden:

• Das Pixel ${\displaystyle {\vec {d}}}$ liegt genau dann im projizierten Dreieck, wenn ${\displaystyle V_{0}({\vec {d}})>0}$ und ${\displaystyle V_{1}({\vec {d}})>0}$ und ${\displaystyle V_{2}({\vec {d}})>0}$ ist.

Der Schnittpunkt ${\displaystyle {\vec {e}}+t\cdot {\vec {d}}}$ des Pixels ${\displaystyle {\vec {d}}}$ mit dem ursprünglichen Dreieck ${\displaystyle ({\vec {p_{0}}},{\vec {p_{1}}},{\vec {p_{2}}})}$ kann auch mit baryzentrischen Koordinaten der Punkte ${\displaystyle {\vec {p_{0}}}}$, ${\displaystyle {\vec {p_{1}}}}$, ${\displaystyle {\vec {p_{2}}}}$ ausgedrückt werden (Bild 4). Dann gilt:

${\displaystyle {\vec {e}}+t\cdot {\vec {d}}=t\cdot {\vec {d}}=\lambda _{0}\cdot {\vec {p_{0}}}+\lambda _{1}\cdot {\vec {p_{1}}}+\lambda _{2}\cdot {\vec {p_{2}}}}$ mit ${\displaystyle \lambda _{i}={\frac {V_{i}({\vec {d}})}{V_{0}({\vec {d}})+V_{1}({\vec {d}})+V_{2}({\vec {d}})}}}$

wobei ${\displaystyle t}$ und die ${\displaystyle \lambda _{i}}$ reelle Zahlen sind. Die baryzentrischen Koordinaten werden mit ${\displaystyle {\vec {e}}+t\cdot {\vec {d}}=(\lambda _{0}:\lambda _{1}:\lambda _{2})}$ bezeichnet.

Algorithmen

Sobald ein Dreieck zum Rendern ausgewählt wurde, müssen die Strahlen, die es abdeckt, effizient identifiziert werden. Bei der herkömmlichen Strahlverfolgung werden nur Dreiecke, die wahrscheinlich geschnitten werden, durch die Durchquerung aufgelistet. Bei größeren Bildausschnitten kann ein Dreieck jedoch nur einen kleinen Teil der Pixel bedecken, und es kann vorteilhaft sein, Binning zu verwenden, um das Auffinden der bedeckten Pixel zu beschleunigen. Aus dem gleichen Grund wurde bei der Rasterung immer das Binning verwendet, um die abgedeckten Pixel schnell auf dem Bildschirm zu lokalisieren.

Eine generische Formulierung von kombiniertem Durchlaufen und Binning zeigt folgende rekursive Funktion, die in Pseudocode dargestellt ist:

funktion durchlaufen(bildausschnitt F, knoten N)
    falls istVerdeckt oder istAuszerhalb dann stop
    falls bildausschnittTeilen dann
        teile F in teilausschnitte F[i]
        für jeden teilausschnitt F[i]
            durchlaufen(F[i], N)
    ende
    sonst falls pixelErzeugen dann rastern(N, binning)
        sonst
            für jeden nachfolger_von_N
                durchlaufen(F, nachfolger_von_N)
    ende
ende
                durchlaufen(F, nachfolger_von_N)

Hier ist F ein Bildausschnitt und N ist ein Knoten der räumlichen Indexstruktur, der typischerweise mit dem gesamten Ansichtsfenster bzw. dem Wurzelknoten beginnt. Die kursiven Wörter istVerdeckt, istAuszerhalb, bildausschnittTeilen, pixelErzeugen, istAuszerhalb und binning bezeichnen Testfunktionen, die das Verhalten des Algorithmus steuern und es uns ermöglichen, die oben genannten Rendering-Algorithmen zu produzieren und neue Wege zu erkunden.