Die Mathematik hinter Computergrafik

Sowohl in der zwei- als auch in der dreidimensionalen Computergrafik steht man vor der immer wiederkehrenden Frage, an welcher Stelle des Computerbildschirms ein grafisches Element der Anwendung, z.B. eines Spiels, angezeigt werden soll. Im folgenden soll es darum gehen, anhand einfacher Beispiele einen möglichst allgemeingültigen und universellen Lösungsweg für dieses Problem zu finden.

Einführungsbeispiel

Wir nehmen für ein erstes Beispiel einmal ein, dass ein Grafiker folgende Spielgrafik erstellt hat (Bildquelle: siehe unten):

baum-im-koordinatensystem

Diese Grafik soll im fertigen Spiel allerdings unter Umständen in verschiedenen Größen dargestellt werden, also muss man einen Weg finden, die Eckpunkte der Grafik derart neu anzuordnen, dass die Grafik dabei vergrößert oder verkleinert (skaliert) werden kann. Dass das Zentrum der Grafik im Ursprung des eingezeichneten Koordinatensystems liegt, ist hierbei von großer Bedeutung, denn so handelt es sich beim Vergrößerungsvorgang um eine zentrische Streckung der gesamten Figur. Das Koordinatensystem, in welchem die Grafik angelegt wurde, nennt man Modellkoordinatensystem und das Koordinatensystem, in das es überführt werden soll, nennt man Weltkoordinatensystem. Eine zentrische Streckung, beispielsweise mit Faktor \(k = 1,2\), würde folgendermaßen aussehen:

baum-zentrisch-gestreckt

Die Eckpunkte der Grafik wandern dabei gleichmäßig vom Ursprung weg. Um diesen Vorgang rechnerisch umzusetzen, betrachtet man die Ortsvektoren der vier Eckpunkte der Grafik.

Für eine Streckung in Richtung der x-Achse um einen Faktor \(k_x\), muss lediglich die x-Koordinate eines jeden Ortsvektors mit diesem Faktor multipliziert werden. Analog dazu ergibt sich eine Streckung mit Faktor \(k_y\) entlang der y-Achse. Es gilt also:

\(x’={k_x} \cdot {x} \\ y’={k_y} \cdot {y} \)

In Vektorschreibweise:

\( \begin{pmatrix} x‘ \\ y‘ \end{pmatrix} = \begin{pmatrix} k_x \\ k_y \end{pmatrix} \cdot \begin{pmatrix} x \\ y \end{pmatrix} \)

In der folgenden, detaillierteren Schreibweise kann man gut erkennen, dass die Koordinaten des Bildpunktes, also des neu entstehenden Punktes, als eine Linearkombination der Koordinaten des ursprünglichen Punktes darstellbar sind:

\( \begin{pmatrix} x‘ \\ y‘ \end{pmatrix} = \begin{pmatrix} k_x \cdot {x} + 0 \cdot {y} \\ 0 \cdot {x} + k_y \cdot {y} \end{pmatrix} \)

Eine derartige Abbildung, die einem Vektor eine Linearkombination desselben Vektors zuordnet, nennt man lineare Abbildung. Alle linearen Abbildungen erfüllen die folgenden Bedingungen:

\( \begin{matrix} {f(a \cdot {\vec{x}}) = a \cdot {f(\vec{x})}} & \text{(1)} \\ \\ f(\vec{x}+\vec{y}) = f(\vec{x})+f(\vec{y}) & \text{(2)} \end{matrix} \)

Aus (1) folgt, dass für lineare Abbildungen immer gilt, dass der Nullvektor seinerseits immer wiederum dem Nullvektor zugeordnet wird.

Punkte, deren Ortsvektoren von einer Abbildung auf sich selbst abgebildet werden, nennt man Fixpunkte dieser Abbildung. Der Koordinatenursprung ist somit ein Fixpunkt jeder linearen Abbildung. Als Kern einer Abbildung bezeichnet man dagegen diejenigen Punkte, deren Ortsvektoren durch die Abbildung auf den Nullvektor abgebildet werden. Bei unserem Beispiel der zentrischen Streckung ist der Ursprung der einzige Fixpunkt und ebenfalls das einzige Element des Kerns der Abbildung.

Matrix-Schreibweise

Die zu linearen Abbildungen gehörenden Gleichungssysteme lassen sich durch sog. Matrizen übersichtlicher darstellen. So kann unser Beispiel folgendermaßen umgeschrieben werden:

\( \begin{pmatrix} x‘ \\ y‘ \end{pmatrix} = \begin{pmatrix} k_x \cdot {x} + 0 \cdot {y} \\ 0 \cdot {x} + k_y \cdot {y} \end{pmatrix} = \underbrace{\begin{pmatrix} k_x & 0 \\ 0 & k_y \end{pmatrix}}_{M} \cdot \begin{pmatrix} x \\ y \end{pmatrix} \)

Eine Matrix ist also eine tabellarische Darstellung der Koeffizienten (Vorfaktoren) der zur Abbildung gehörenden Linearkombinationen. Die als \(M\) gekennzeichnete Matrix nennt man Abbildungsmatrix. Zu jeder linearen Abbildung lässt sich eine solche Matrix finden, sodass gilt:

\( \vec{x‘} = M \cdot {\vec{x}} \)

Für alle Fixpunkte einer linearen Abbildung gilt somit \( M \cdot \vec{x} = \vec{x}\) und für jedes Element des Kerns einer linearen Abbildung gilt \(M \cdot \vec{x} = \vec{0}\).

Bestimmen einer Abbildungsmatrix

Nicht bei jeder linearen Abbildung lässt sich die zugehörige Abbildungsmatrix so einfach bestimmen wie im Beispiel. Durch den folgenden Zusammenhang lässt sich dieser Vorgang unter Benutzung der obigen Gleichungen (1) und (2) allerdings vereinfachen:

\(f \begin{pmatrix} x \\ y \end{pmatrix} = f \left( x \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} + y \cdot \begin{pmatrix}0 \\ 1\end{pmatrix} \right) \\ \\ \underbrace{=}_{\text{nach (2)}} f \left( x \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} \right) + f \left( y \cdot \begin{pmatrix} 0 \\ 1 \end{pmatrix} \right) \\ \\ \underbrace{=}_{\text{nach (1)}} x \cdot f \begin{pmatrix} 1 \\ 0 \end{pmatrix} + y \cdot f \begin{pmatrix}0 \\ 1 \end{pmatrix} \hspace{80px} \text{(3)} \)

Jeder beliebige Vektor lässt sich durch eine Linearkombination der Vektoren \(\begin{pmatrix} 1 \\ 0 \end{pmatrix} \) und \(\begin{pmatrix} 0 \\ 1 \end{pmatrix}\) (die sog. Standardbasis des \(\mathbb{R}^2\)) darstellen. Obiger Zusammenhang besagt nun, dass man lediglich die Bilder dieser Vektoren kennen muss, um das Bild eines beliebigen Vektors zu bestimmen.

Beispiel: Rotationsmatrix

Das genannte Vorgehen wird nun benutzt, um die Abbildungsmatrix einer Rotation um den Koordinatenursprung zu bestimmen. Die Skizze verdeutlicht das Vorgehen:

rotation

Der Vektor \(\begin{pmatrix} 1 \\ 0 \end{pmatrix}\) wird um den Winkel Alpha um den Koordinatenursprung gedreht. Es gilt \(\sin( \alpha ) = y‘\) und \(\cos( \alpha ) = x‘\), da der Vektor \(\begin{pmatrix} 1 \\ 0 \end{pmatrix}\) die Länge 1 hat. Somit gilt \(f \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} \cos \alpha \\ \sin \alpha \end{pmatrix}\).

Analog dazu gilt nach folgender Skizze \(f \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} – \sin \alpha \\ \cos \alpha \end{pmatrix}\):

rotation2

Nach eben gezeigter Gleichung (3) ergibt sich die folgende Abbildungsmatrix für die Rotation um den Koordinatenursprung:

\(R(\alpha ) = \begin{pmatrix} \cos \alpha & -\sin \alpha \\ \sin \alpha & \cos \alpha \end{pmatrix}\)

Wählt man nun einen Winkel Alpha und multipliziert jeden Eckpunkt aus unserem ersten Beispiel mit dieser Matrix, entsteht beispielsweise folgendes Bild:

baum-rotiert

Verschiebung (Translation)

Da die Grafiken in Spielen nicht nur im Bildschirmmittelpunkt, sondern i.d.R. über den ganzen Bildschirm verteilt angezeigt werden sollen, ist es nötig, sie an die richtige Position zu verschieben. Man benötigt also eine Abbildung, die zu einem jedem Vektor \(\vec{x}\) einen konstanten Vektor \(\vec{v}\) addiert, also:

homogene-koordinaten_neu_neu4

\(\vec{x‘}=\vec{x}+\vec{v}=\begin{pmatrix}x_1 + v_1 \\ x_2 + v_2 \end{pmatrix}\)

Man sieht leicht, dass eine solche Abbildung den Nullvektor nicht wieder auf den Nullvektor abbildet. Damit ist eine solche Abbildung nicht linear und somit nicht durch eine Abbildungsmatrix darstellbar. Da das Rechnen mit Matrizen allerdings sehr übersichtlich ist, wendet man einen Trick an, um eine derartige Verschiebung dennoch als lineare Abbildung darstellen zu können.

Homogene Koordinaten

Die sogenannten homogenen Koordinaten, die zum Punkt \(P(x|y)\) gehören, lauten \(P_{w}(x|y|w), w \neq 0\), wobei üblicherweise der Einfachheit halber \(w=1\) gewählt wird. Bevor also die eigentlich gewünschte Verschiebung stattfindet, wird der Punkt zuerst sozusagen „aus der x-y-Ebene gehoben“.

homogene-koordinaten-neu-neu-2

Der neu entstandene Punkt wird nun verschoben:

homogene-koordinaten-neu-neu-3

Was eine Verschiebung in der Ebene darstellt, entspricht einer sog. Scherung im Raum. Dabei handelt es sich wiederum um eine lineare Abbildung. Die zugehörige Abbildungsmatrix wird wie folgt bestimmt (zur Abgrenzung werden für homogene Koordinaten eckige Klammern benutzt):

\( \vec{x_h‘} = \begin{bmatrix} x_1′ \\ x_2′ \\ 1 \end{bmatrix}=\begin{bmatrix} x_1 + v_1 \\ x_2 + v_2 \\ 1 \end{bmatrix}=\begin{bmatrix} 1 \cdot {x_1} + 0 \cdot {x_2} + v_1 \cdot {1} \\ 0 \cdot {x_1} + 1 \cdot {x_2} + v_2 \cdot {1} \\ 0 \cdot {x_1} + 0 \cdot {x_2} + 1 \cdot {1} \end{bmatrix}=\begin{bmatrix} 1 & 0 & v_1 \\ 0 & 1 & v_2 \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \\ 1 \end{bmatrix} \)

Die Abbildungsmatrix für eine Verschiebung eines Punktes in homogenen Koordinaten um den Vektor v lautet also:

\(T_h=\begin{bmatrix} 1 & 0 & v_1 \\ 0 & 1 & v_2 \\ 0 & 0 & 1 \end{bmatrix}\)

Die Koordinaten des verschobenen Punkts erhält man dann durch einfaches Ignorieren der dritten Koordinate:

homogene-koordinaten-neu-neu-4

Auch die Skalierung und die Rotation lassen sich mit homogenen Koordinaten durchführen. Die entsprechenden Matrizen lauten dann:

\(S_h=\begin{bmatrix}k_x & 0 & 0 \\ 0 & k_y & 0 \\ 0 & 0 & 1 \end{bmatrix}\)

\(R_h(\alpha )=\begin{bmatrix} \cos \alpha & -\sin \alpha & 0 \\ \sin \alpha & \cos \alpha & 0 \\ 0 & 0 & 1 \end{bmatrix}\)

Verkettung von Abbildungen

Mehrere lineare Abbildungen lassen sich nacheinander durchführen, indem man alle Punkte nacheinander mit den entsprechenden Abbildungsmatrizen multipliziert. Die Reihenfolge ist dabei von Bedeutung, d.h. die Matrizenmultiplikation ist nicht kommutativ. Die folgenden Bilder verdeutlichen das:

baum-reihenfolge-1 baum-reihenfolge-2

Im linken Bild wurde die Grafik zuerst gedreht, danach verschoben; im rechten genau andersherum.

3D-Computergrafik

Sämtliche bisher gezeigten Konzepte, einschließlich das der homogenen Koordinaten, lassen sich analog zur Ebene auch im Raum umsetzen. Um ein dreidimensional modelliertes Objekt auf dem Bildschirm anzeigen zu können, werden folgende Schritte durchgeführt:

Modellkoordinaten -> Weltkoordinaten (Skalierung, Rotation, Translation); Weltkoordinaten -> Kamerakoordinaten; Kamerakoordinaten -> Bildschirmkoordinaten (Projektion)

Von Modellkoordinaten zu Weltkoordinaten

Analog zum Einführungsbeispiel werden alle Punkte (in homogenen Koordinaten, also mit Vektoren mit vier Koordinaten) des Modells mit den entsprechenden Abbildungsmatrizen multipliziert. Im folgenden sind diese für den dreidimensionalen Raum aufgeführt:

Skalierung mit Faktoren \(k_1, k_2, k_3\) (wahlweise für jede Achse separat):
\(S_h=\begin{bmatrix}k_1 & 0 & 0 & 0 \\ 0 & k_2 & 0 & 0 \\ 0 & 0 & k_3 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

Rotation um eine Koordinatenachse um den Winkel \(\alpha\):
\(\text{x-Achse: } \hspace{10px} R_{h_x}(\alpha)=\begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & \cos \alpha & -\sin \alpha & 0 \\ 0 & \sin \alpha & \cos \alpha & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

\(\text{y-Achse: } \hspace{10px} R_{h_y}(\alpha)=\begin{bmatrix}\cos \alpha & 0 & \sin \alpha & 0 \\ 0 & 1 & 0 & 0 \\ -\sin \alpha & 0 & \cos \alpha & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

\(\text{z-Achse: } \hspace{10px} R _{h_z}(\alpha)=\begin{bmatrix} \cos \alpha & -\sin \alpha & 0 & 0 \\ \sin \alpha & \cos \alpha & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

Abhängig davon, um welche Koordinatenachse rotiert werden soll, ergeben sich verschiedene Rotationsmatrizen. Die Herleitung dieser funktioniert jedoch völlig analog zur zweidimensionalen Rotation.

Verschiebung (Translation):
\(T_h=\begin{bmatrix}1 & 0 & 0 & v_1 \\ 0 & 1 & 0 & v_2 \\ 0 & 0 & 1 & v_3 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

Der Ortsvektor \(\vec{x}\) eines jeden Punktes des 3D-Modells wird also zusammenfassend folgendermaßen abgebildet:

\(\vec{x‘}=T_h \cdot {R_{h_z}}(\alpha_z) \cdot {R_{h_y}}(\alpha_y) \cdot {R_{h_x}}(\alpha_x) \cdot {S_h} \cdot \vec{x}\)

Die Multiplikationen müssen von rechts nach links gelesen werden, also zuerst Skalierung, dann Rotation, dann Verschiebung.

Diese Rechenoperation platziert das Modell im Weltkoordinatensystem. Die Reihenfolge der Rotationen kann von der hier genannten abweichen. Die gesamte Kette von Abbildungen lässt sich durch Matrizenmultiplikation auch zu einer einzigen Matrix zusammenfassen, welche dann für das gesamte Modell identisch ist.

Von Weltkoordinaten zu Kamerakoordinaten

handUm die später folgende Projektion des Bildes auf die Bildschirmkoordinaten zu vereinfachen, werden sämtliche Modelle im Weltkoordinatensystem nun so abgebildet, als befände sich die (virtuelle) Kamera im Koordinatenursprung mit Blick in negative z-Richtung. Die y-Achse zeigt im „Kamerabild“ nach oben. Um die Abbildungsmatrix für diesen Schritt zu erhalten, benötigt man zunächst drei Hilfsvektoren mit der Länge Eins, die aus Sicht der Kamera ein entsprechendes, rechtshändiges Koordinatensystem (siehe Bild, Bildquelle: siehe unten) aufspannen. Für diese Vektoren gilt:

\(\vec{z}=\frac{1}{|\vec{k}-\vec{t}|} \cdot \left( \vec{k}-\vec{t} \right)\)

\(\vec{x}=\begin{pmatrix}0 \\ 0 \\ 1 \end{pmatrix} \times \vec{z}\)

\(\vec{y}=\vec{z} \times \vec{x}\)

Dabei steht \(\times\) für das Kreuzprodukt, \(\vec{t}\) für den Ortsvektor des Punktes, auf den die Kamera gerichtet ist und \(\vec{k}\) für den Ortsvektor der Kameraposition (beides in Weltkoordinaten).

Die Abbildungsmatrix, welche die Weltkoordinaten in Kamerakoordinaten überführt (auch View-Matrix genannt), lautet dann:

\(V_h=\begin{bmatrix} x_1 & x_2 & x_3 & -\vec{k} \cdot \vec{x} \\ y_1 & y_2 & y_3 & -\vec{k} \cdot \vec{y} \\ z_1 & z_2 & z_3 & -\vec{k} \cdot \vec{z} \\ 0 & 0 & 0 & 1\end{bmatrix} \)

Von Kamerakoordinaten zu Bildschirmkoordinaten (Projektion)

Im letzten Schritt werden die dreidimensionalen Koordinaten auf die x-y-Ebene projiziert, d.h. sie verlieren ihre Tiefeninformation. Dies geschieht auf eine von zwei Arten:

Orthogonal-/Parallelprojektion

orthogonalprojektion

Zentralprojektion

zentralprojektion

Bei der Orthogonal- oder auch Parallelprojektion wird die z-Koordinate einfach ignoriert. In der entstehenden Projektion sind alle Kanten, die im 3D-Modell parallel zueinander waren, immer noch parallel. Anwendungsgebiete hierfür sind z.B. technische Zeichnungen oder das Anlegen eines Schrägbildes im Schulunterricht. Nachteilig ist, dass Tiefeninformationen nicht ersichtlich sind, d.h. weiter entfernte Objekte verlieren nicht an Größe.

Bei der Zentralprojektion werden alle Punkte in Richtung des Augpunktes, also des Punktes, an dem sich der Betrachter befindet (hier im Ursprung), auf eine zur x-y-Ebene parallelen Ebene projiziert. Das resultierende Bild entspricht dem natürlichen, perspektivischen Eindruck, den wir aus der eigenen Erfahrung kennen. Anwendung findet dieses Verfahren in allen Bereichen, in denen annähernd realistische Darstellungen verlangt werden, z.B. in Computerspielen oder Animationsfilmen.

Die Abbildungsmatrizen für die Projektionen sehen wie folgt aus:

\(\text{Orthogonal-/Parallelprojektion:} \hspace{10px} P_h=\begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)

\(\text{Zentralprojektion:} \hspace{10px} P_h=-\frac{d}{p_3} \cdot \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -\frac{1}{d} & 0 \end{bmatrix}\)

Hierbei steht \(d\) für den Abstand von Augpunkt zur Projektionsebene und \(p_3\) für die z-Koordinate des zu projizierenden Punktes. Das bedeutet, dass die Projektionsmatrix bei Zentralprojektion in der Regel für jeden Punkt verschieden ist. In der Praxis wird allerdings die Multiplikation der Matrix mit \(-\frac{d}{p_3}\) automatisch von der Grafikkarte übernommen, sodass sich der Programmierer darum nicht selbst kümmern muss.

Abschließendes Beispiel

Der kennengelernte Gesamtvorgang wird nun an einem Beispiel illustriert. Betrachtet wird ein Würfel mit Kantenlänge \(a=1\) im Modellkoordinatensystem:

wuerfel_01

Die Koordinaten des Würfels werden dann mittels Rotationsmatrizen und Translationsmatrix in Weltkoordinaten gebracht:

wuerfel_02

Nun bestimmt man den Standort der virtuellen Kamera K und den Punkt T, auf den diese gerichtet ist:

wuerfel_03

Durch Anwendung der View- und Projektionsmatrizen ergibt sich folgendes Resultat:

Orthogonal-/Parallelprojektion
wuerfel_ortho
Zentralprojektion
wuerfel_zp

Quellen

Bildnachweise

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.