Reply to comment

Matrixrechnung

Submitted by Stefan on 3. June 2008 - 20:59

Matrizen sind Zahlenschemata die in Reihen und Spalten angeordnet sind. Für grafische Anwendungen sind vor allem quadratische Matrizen mit der gleichen Anzahl von Reihen wie Spalten interessant. Mit diesen ist es nämlich möglich lineare Abbildungen dazustellen.

Das alleine macht aber noch nicht ihre Bedeutung für die Computergrafik aus. Es ist die Tatsache, dass man Abbildungsmatrizen miteinander multiplizieren kann und dadurch eine einzelne Matrix erhält, die alle in sie hineinmultiplizierten Abbildungen auf einmal ausführt. Dies bietet einen enormen Performancegewinn wenn viele Abbildungen auf viele Punkte angewendet werden müssen und dazu dann nur eine Matrix verwendet werden muss.

Skalare Multiplikation

Die skalare Multiplikation bei Matrizen entspricht der bei Vektoren: Eine Matrix wird mit einer Zahl (=Skalar) multipliziert, indem alle ihre Elemente mit dieser Zahl multipliziert werden:

$\left( \begin{array}{cccc} m_{11} & m_{12} & m_{13} & m_{14} \\ m_{21} & m_{22} & m_{23} & m_{24} \\ m_{31} & m_{32} & m_{33} & m_{34} \\ m_{41} & m_{42} & m_{43} & m_{44} \end{array} \right) = \left( \begin{array}{cccc} f m_{11} & f m_{12} & f m_{13} & f m_{14} \\ f m_{21} & f m_{22} & f m_{23} & f m_{24} \\ f m_{31} & f m_{32} & f m_{33} & f m_{34} \\ f m_{41} & f m_{42} & f m_{43} & f m_{44} \end{array} \right)$

Matrixmultiplikation

Wie oben bereits erwähnt kann man Abbildungen von mehrere Matrizen auch zusammenfassen und damit mit einer einzigen Matrix darstellen. Hierfür wird die Matrixmultiplikation benutzt. Werden zwei Matrizen A und B miteinander multipliziert, so erhält man eine Matrix C=A*B die beide Abbildungen in dieser Reihenfolge in einem Schritt ausführt:

$\left( \begin{array}{cccc} m_{11} & m_{12} & m_{13} & m_{14} \\ m_{21} & m_{22} & m_{23} & m_{24} \\ m_{31} & m_{32} & m_{33} & m_{34} \\ m_{41} & m_{42} & m_{43} & m_{44} \end{array} \right) \left( \begin{array}{cccc} r_{11} & r_{12} & r_{13} & r_{14} \\ r_{21} & r_{22} & r_{23} & r_{24} \\ r_{31} & r_{32} & r_{33} & r_{34} \\ r_{41} & r_{42} & r_{43} & r_{44} \end{array} \right) = \left( \begin{array}{cccc} e_{11} & e_{12} & e_{13} & e_{14} \\ e_{21} & e_{22} & e_{23} & e_{24} \\ e_{31} & e_{32} & e_{33} & e_{34} \\ e_{41} & e_{42} & e_{43} & e_{44} \end{array} \right)$

mit

$e_{11} = m_{11} r_{11} + m_{12} r_{21} + m_{13} r_{31} + m_{14} r_{41}$
$e_{12} = m_{11} r_{12} + m_{12} r_{22} + m_{13} r_{32} + m_{14} r_{42}$
$e_{13} = m_{11} r_{13} + m_{12} r_{23} + m_{13} r_{33} + m_{14} r_{43}$
$e_{14} = m_{11} r_{14} + m_{12} r_{24} + m_{13} r_{34} + m_{14} r_{44}$
$e_{21} = m_{21} r_{11} + m_{22} r_{21} + m_{23} r_{31} + m_{24} r_{41}$
$e_{22} = m_{21} r_{12} + m_{22} r_{22} + m_{23} r_{32} + m_{24} r_{42}$
$e_{23} = m_{21} r_{13} + m_{22} r_{23} + m_{23} r_{33} + m_{24} r_{43}$
$e_{24} = m_{21} r_{14} + m_{22} r_{24} + m_{23} r_{34} + m_{24} r_{44}$
$e_{31} = m_{31} r_{11} + m_{32} r_{21} + m_{33} r_{31} + m_{34} r_{41}$
$e_{32} = m_{31} r_{12} + m_{32} r_{22} + m_{33} r_{32} + m_{34} r_{42}$
$e_{33} = m_{31} r_{13} + m_{32} r_{23} + m_{33} r_{33} + m_{34} r_{43}$
$e_{34} = m_{31} r_{14} + m_{32} r_{24} + m_{33} r_{34} + m_{34} r_{44}$
$e_{41} = m_{41} r_{11} + m_{42} r_{21} + m_{43} r_{31} + m_{44} r_{41}$
$e_{42} = m_{41} r_{12} + m_{42} r_{22} + m_{43} r_{32} + m_{44} r_{42}$
$e_{43} = m_{41} r_{13} + m_{42} r_{23} + m_{43} r_{33} + m_{44} r_{43}$
$e_{44} = m_{41} r_{14} + m_{42} r_{24} + m_{43} r_{34} + m_{44} r_{44}$

Wenn man sich die Formeln genauer ansieht dann sieht man, dass die Elemente e der Ergebnismatrix durch ein Skalarprodukt der Zeile der ersten Matrix mit der Spalte der zweiten Matrix entstehen. Die Zeile, die aus der ersten Matrix genommen werden muss ist auch die Zeile in die das Ergebnis eingetragen wird. Ebenso muss die Spalte der zweiten Matrix gewählt werden die identisch mit der Spalte in der Ergebnismatrix ist. Mein Merksatz lautet "Zeile mal Spalte" - auf diese Weise merke ich mir wie die Matrizen miteinander multipliziert werden.

Die Reihenfolge in der die Multiplikation durchgeführt wird ist nicht egal: Auf den beiden Abbildungen kann man sehen was die Ergebnisse sind wenn man eine Verschiebung und eine Drehung auf die beiden möglichen Arten kombiniert:

Erst eine Verschiebung, dann eine Drehung
Erst eine Drehung, dann eine Verschiebung

Man sieht anhand der Koordinaten im jeweils ganz rechten Bild, dass eine Umkehrung der Abbildungen nicht zum gleichen Ergebnis führt. In hellgrün sind in den Abbildungen die durch die Abbildung veränderten Koordinatensysteme eingezeichnet. An diesen erkennt man sehr viel deutlicher warum die Reihenfolge wichtig ist: Im ersten Bild sieht man, dass die Drehung das verschobene Koordinatensystem dreht und damit die Drehung nicht mehr um den Ursprung erfolgt - der Ursprung wurde ja verschoben. Dies geschieht in Bild 2 jedoch nicht.

Vielleicht stellt ihr euch nun die Frage, dass wenn doch durch die erste Abbildung das Koordinatensystem verändert wurde, die zweite Abbildung dann nicht innerhalb dieses veränderten Systems erfolgt und dann beide Reihenfolgen egal wären?! Dies ist richtig, wären die Abbildungen für ein bereits verändertes System formuliert würde das funktionieren. Die Verschiebung ist aber

$\left( \begin{array}{ccc} 1 & 0 & 1,5 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right)$

und die Drehmatrix ist:

$\left( \begin{array}{ccc} \cos 26 & \sin 26 & 0 \\ -\sin 26 & \cos 26 & 0 \\ 0 & 0 & 1 \\ \end{array} \right)$

Wie man sieht sind beide Matrizen die "normale" Translations- und Drehmatrix. Und diese beziehen sich nun auf das Ursprungssystem. Daher wird auch jede Abbildung in einer Kette von Abbildungen immer in Bezug zum Ursprungssystem durchgeführt. Dies ist der Grund, warum Abbildungen in der Regel nicht vertauschbar sind.

Invertieren von Matrizen

Da eine Matrix eine Abbildung darstellt, muss es demnach auch eine Matrix geben die diese Abbildung in umgekehrter Richtung durchführt. Dies sind dann die inversen Matrizen. Es ist nicht jede Matrix invertierbar - für unsere Zwecke aber schon da sich schließlich jede Abbildung auch rückwärts durchführen lässt. Das Berechnen einer inversen Matrix ist nicht einfach. In meinen Klassen verwende ich die Formeln die auf Wikipedia beschrieben sind:

Wir brauchen die inverse Matrix als erstes im Kapitel zum Thema "Frustum" (die Sichtpyramide). Dort wird über die inverse Matrix eine Abbildung erstellt die das Kamerasystem zurück in das Ursprungssystem bringt.

Im Detail sieht die Berechnung der Inversen Matrix wie folgt aus: Die Inverse ist

$A^{-1} = \frac{\operatorname{adj} (A)}{\det(A)}$

mit

$\operatorname{adj}(A) = \tilde A^T = \begin{pmatrix} \tilde a_{11} & \tilde a_{21} & \cdots & \tilde a_{n1}\\ \tilde a_{12} & \tilde a_{22} & & \tilde a_{n2}\\ \vdots & & \ddots & \vdots\\ \tilde a_{1n} & \tilde a_{2n} & \cdots & \tilde a_{nn}\end{pmatrix} $

Man sollte hierbei beachten, dass dem Indexpaar (i,j) der Cofaktor $\tilde a_{ji}$ zugeordnet wird. Die Cofaktoren $\tilde a_{ji}$ berechnen sich zu

$ \tilde a_{ji} = (-1)^{j+i}\cdot M_{ji} = (-1)^{j+i}\cdot \begin{vmatrix} a_{1,1} & \cdots & a_{1,i-1} & a_{1,i+1} & \cdots & a_{1,n} \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{j-1,1} & \cdots & a_{j-1,i-1} & a_{j-1,i+1} & \cdots & a_{j-1,n} \\ a_{j+1,1} & \cdots & a_{j+1,i-1} & a_{j+1,i+1} & \cdots & a_{j+1,n} \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,i-1} & a_{n,i+1} & \cdots & a_{n,n}\end{vmatrix} $

Die Minoren $M_{ji}$ sind die Werte der Unterdeterminanten der transponierten Matrix $A^T$ , die durch Streichen der j-ten Zeile und der i-ten Spalte entstehen.

Mit dem laplaceschen Entwicklungssatz kann man die Determinante einer $n \times n$ -Matrix "nach einer Zeile oder Spalte entwickeln". Die beiden Formeln lauten

$\det A = \sum_{i=1}^n (-1)^{i+j} \cdot a_{ij} \cdot \det A_{ij}$ (Entwicklung nach der j-ten Spalte)
$\det A = \sum_{j=1}^n (-1)^{i+j} \cdot a_{ij} \cdot \det A_{ij}$ (Entwicklung nach der i-ten Zeile)
wobei $A_{ij}$ die $(n-1) \times (n-1)$ -Untermatrix von A ist, die durch Streichen der i-ten Zeile und j-ten Spalte entsteht. Das Produkt $(-1)^{i+j}\det A_{ij}$ wird Minore $\tilde a_{ij}$ genannt.

Hier der Java-Source für die Berechnung der inversen Matrix:

/**
* Returns a subdeterminant of the matrix.
*
* Calculates the determinant of the matrix reduced by the given column and row.
*
* @param remRow the row to omit
* @param remCol the column to omit
* @return the subdeterminant
*/
public double getSubDeterminant(int remRow, int remCol) {
double[] m = new double[9];

int idx=0;
for ( int row=0 ; row<4 ; row++ ) {
for ( int col=0 ; col<4 ; col++) {
if ( row!=remRow && col!=remCol ) {
m[idx++] = mat[row][col];
}
}
}

double det = m[0]*m[4]*m[8] + m[1]*m[5]*m[6] + m[2]*m[3]*m[7] -
m[2]*m[4]*m[6] - m[1]*m[3]*m[8] - m[0]*m[5]*m[7];

return det;
}

/**
* Returns the determinant of the matrix.
*
* @return the determinant
*/
public double getDeterminant() {
double det = 0.0;
double faktor=1;

for ( int i=0 ; i<4 ; i++ ) {
if ( i % 2 == 1 ) {
faktor=-1;
} else {
faktor=1;
}

det += mat[0][i] * faktor * getSubDeterminant(0, i);
}

return det;
}

/**
* Inverts the matrix.
*/
public void invert() {
Matrix m = new Matrix(this);
double faktor=1;

double det = getDeterminant();

for ( int row=0 ; row<4 ; row++ ) {
for ( int col=0 ; col<4 ; col++ ) {
if ( (row+col) % 2 == 1 ) {
faktor=-1;
} else {
faktor=1;
}

m.mat[col][row] = getSubDeterminant(row, col);
m.mat[col][row] *= faktor;
m.mat[col][row] /= det;
}
}

mat = m.mat;
}

Abbildungen mit Matrizen

Um eine Matrixabbildung auf Punkte und Vektoren anzuwenden und damit die Abbildung durchzuführen ist es nötig die Matrix mit dem Vektor zu multiplizieren. Diese Operation ist die gleiche wie die Matrixmultiplikation mit der Ausnahme, dass der zweite Multiplikator nur eine Spalte besitzt und wir daher als Ergebnis wieder einen Spaltenvektor erhalten werden:

$\left( \begin{array}{cccc} m_{11} & m_{12} & m_{13} & m_{14} \\ m_{21} & m_{22} & m_{23} & m_{24} \\ m_{31} & m_{32} & m_{33} & m_{34} \\ m_{41} & m_{42} & m_{43} & m_{44} \end{array} \right) \left( \begin{array}{c} v_x \\ v_y \\ v_z \\ v_t \end{array} \right) = \left( \begin{array}{c} m_{11} v_x + m_{12} v_y + m_{13} v_z + m_{14} v_t \\ m_{21} v_x + m_{22} v_y + m_{23} v_z + m_{24} v_t \\ m_{31} v_x + m_{32} y_y + m_{33} v_z + m_{34} v_t \\ m_{41} v_x + m_{42} y_y + m_{43} v_z + m_{44} v_t \end{array} \right)$

Die Einheitsmatrix

Die Einheitsmatrix bewirkt keine Veränderung wenn sie mit einem Vektor oder einer anderen Matrix multipliziert wird.

$\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right)$

Drehung

Um Drehungen mit Matrizen abzubilden gibt es mehrere Möglichkeiten. Man kann die Matrizen die Vektoren um die X-, Y- und Z-Achse drehen miteinander geschickt kombinieren um die gewünschte Enddrehung zu erhalten. Es gibt auch die Möglichkeit über Quaternionen eine Drehung um eine beliebige Achse direkt als Matrix anzugeben. Die Formel hierzu findet ihr wieder auf Wikipedia.

Die drei Matrizen für die Drehungen um die einzelnen Achsen sehen wie folgt aus:

Die Drehmatrix um die X-Achse:

$\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \cos \alpha & -\sin \alpha & 0 \\ 0 & \sin \alpha & \cos \alpha & 0 \\ 0 & 0 & 0 & 1 \end{array} \right)$

Die Drehmatrix um die Y-Achse:

$\left( \begin{array}{cccc} \cos \alpha & 0 & \sin \alpha & 0 \\ 0 & 1 & 0 & 0 \\ -\sin \alpha & 0 & \cos \alpha & 0 \\ 0 & 0 & 0 & 1 \end{array} \right)$

Die Drehmatrix um die Z-Achse:

$\left( \begin{array}{cccc} \cos \alpha & \sin \alpha & 0 & 0 \\ -\sin \alpha & \cos \alpha & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right)$

Die Matrix die Quaternionen verwendet um eine Drehung darzustellen sieht wie folgt aus:

Ist a die Drehachse und $\alpha$ der Drehwinkel und gilt $|\vec{a}|=1$ dann erhält man mit

$x = a_x \sin \frac{\alpha}{2}$
$y = a_y \sin \frac{\alpha}{2}$
$z = a_z \sin \frac{\alpha}{2}$
$w = \cos \frac{\alpha}{2}$

die Drehmatrix um die Achse $\vec{a}$ und den Winkel $\alpha$ mit

$\left( \begin{array}{cccc} 1-2(y^2 + z^2) & 2(xy-zw) & 2(xz + yw) & 0 \\ 2(xy+zw) & 1-2(x^2+z^2) & 2(yz-xw) & 0 \\ 2(xz-yw) & 2(yz+xw) & 1-2(x^2+y^2) & 0 \\ 0 & 0 & 0 & 1 \end{array} \right)$

Verschiebung

Die Matrix für eine Verschiebung sieht folgendermaßen aus:

$\left( \begin{array}{cccc} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{array} \right)$

Homogene Koordinate

An dieser Stelle kommen wir um die homogenen Koordinaten nicht mehr herum - denn ohne diese ist eine Verschiebung nicht mit einer Matrix durchführbar. Wird die oben genannte Verschiebungsmatrix auf einen Vektor angewendet, so ergibt sich folgende Rechnung:

$\left( \begin{array}{cccc} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{array} \right) \left( \begin{array}{cc} x \\ y \\ z \\ w \end{array} \right) = \left( \begin{array}{cc} x + w t_x \\ y + w t_y \\ z + w t_z \\ w \end{array} \right)$

Wie man sieht werden die Translationskoordinaten elementweise auf den Vektor aufaddiert falls die homogene Koordinate 1 ist.

Matrizen und Koordinatensysteme

Die Koordinatenachsen in einer Matrix

Auf der obigen Abbildung habe ich mal dargestellt was die Werte in einer Matrix in Wirklichkeit sind. Eine Matrix ist also eine klare und ablesbare Definition eines Koordinatensystems. Die einzelnen Spalten die ich oben hervorgehoben habe stellen nämlich die drei Koordinatenachsen des durch die Matrix definierten Systems dar - die vierte Spalte definiert den Ursprung des Koordinatensystems.

Und wenn man diese Tatsache kennt, dann kann man sich anschließend auch die Verschiebungen, Drehungen und Skalierungen durch Matrizen direkt besser vorstellen. Schaut noch mal oben nach ob die verschiedenen Standard-Matrixabbildungen nun direkt einleuchtender erscheinen.

Eine Spiegelung an der X-Achse kann man nun zum Beispiel direkt angeben: Indem einfach der Vektor (-1,0,0,0) in die erste Spalte der Matrix gesetzt wird.

Reply

Subject:

Comment: *

Input format

Filtered HTML

LaTex commands embedded in text will be interpreted and rendered. Additional information can be found at DruTex Documentation Pages
- Assists automatic numbering of tex, equation, and equations environments.
- Provides different environments to create rendered images (especially maths).
- Line and paragraphs break automatically.
- Lines and paragraphs break automatically.
- Web page addresses and e-mail addresses turn into links automatically.
- You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>, <cpp>, <java>, <python>, <xml>. The supported tag styles are: <foo>, [foo].

Full HTML

Images can be added to this post.
Web page addresses and e-mail addresses turn into links automatically.
LaTex commands embedded in text will be interpreted and rendered. Additional information can be found at DruTex Documentation Pages
- Assists automatic numbering of tex, equation, and equations environments.
- Provides different environments to create rendered images (especially maths).
- Line and paragraphs break automatically.
- You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>, <cpp>, <java>, <python>, <xml>. The supported tag styles are: <foo>, [foo].

More information about formatting options

CAPTCHA

Diese Frage hat den Zweck zu testen, ob man ein menschlicher Benutzer ist und um automatisierten Spam vorzubeugen.

What code is in the image?: *

Enter the characters shown in the image.