2011-07-09

Macierz rozszerzona

Macierz rozszerzona to macierz o jeden wymiar wyższa niż liczba wymiarów przestrzennych. Czyli dla 3D będzie to macierz 4x4. Operacje typu: translacja, rotacja, skalowanie, pochylenie oraz ich dowolne złożenia można przedstawić za pomocą takiej macierzy.

Właśnie uniwersalność, przewidywalny czas obliczeń, łatwość przechowywania zdecydowała o jej powszechności w grafice komputerowej.

Macierz transformacji

Macierze transformacji to z reguły macierze skalowania, rotacji wokół środka układu współrzędnych i translacji. Do tego dochodzą różnego rodzaje projekcje, pochylenia.

Macierze te są o jeden wymiar większe niż przestrzeń na której operują. Czyli każde takie powyższe przekształcenie w 3D to macierz 4x4.

Trzy pierwsze kolumny w takiej macierzy reprezentują osie układu współrzędnych nowego układu współrzędnych do jakiego dokonujemy transformacji.

Weźmy macierz jednostkową 4x4:

$\mathbf{I}=\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}$
Dowolny punkt albo macierz wymnożoną przez macierz jednostkową nie zmienia swojej postaci.

Ogólna postać macierzy transformacji:

$\mathbf{I}=\begin{bmatrix}
right_x & up_x & forward_x & t_x \\
right_y & up_y & forward_y & t_y \\
right_z & up_z & forward_z & t_z \\
0 & 0 & 0 & 1 \\
\end{bmatrix}$
Mnożąc przez siebie dowolną ilość macierzy rotacji i translacji 4x4 otrzymujemy macierz 4x4, która te wszystkie przekształcenia przedstawia jako jedną rotację i jedną translację. Macierz rotacji $\mathbf{R}$ wyciągamy wprost z macierzy 4x4. Translacja nie jest dana wprost z takiej macierzy. Dla macierzy $\mathbf{M}$:

$IT=T$
$R^{-1}R=I$
$R^{-1}RT=T$
$R^{-1}M=T$
$R^{T}M=T$

Zamiast $\mathbf{T=R^{T}M}$ możemy użyć $\mathbf{T=R^{-1}Tr}$ dzięki czemu uwzględnimy przypadki, gdzie R będąca fragmentem macierzy Tr nie spełnia wszystkich warunków macierzy rotacji, a zwłaszcza $\mathbf{R^{T}=R^{-1}}$.

Podobnie możemy pokazać dla macierzy $\mathbf{M=TR}$.

Wektory $\mathbf{\overrightarrow{right}}$, $\mathbf{\overrightarrow{up}}$, $\mathbf{\overrightarrow{forward}}$ to osie układu współrzędnego lokalnego. Mnożąc dowolny punkt przez macierz translacji transformowany jest on do układu współrzędnych wyznaczonego przez te wektory. Np: punkty leżące na osi OX będą leżały na nowej osi OX, której wersorem będzie $\mathbf{\overrightarrow{right}}$.

Macierz odwrotna lub transponowana będzie dokonywać przekształcenia odwrotnego.

Jeśli chodzi o odwrotność rotacji to z faktu że: $R^T=R^{-1}$ wynika, że osie układ
współrzędnych rotacji odwrotnej wyznaczają wiersze macierze rotacji.

Macierz skalowania

Macierz skalowania definiujemy dla 3D jako:

$S=\begin{bmatrix}
s_x & 0 & 0 & 0 \\
0 & s_y & 0 & 0 \\
0 & 0 & s_z & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}$

Łatwo sprawdzić, że dla wektora $\vec v=\begin{bmatrix} v_x & v_y & v_z \\\end{bmatrix}$:

$\begin{bmatrix}
s_x & 0 & 0 & 0 \\
0 & s_y & 0 & 0 \\
0 & 0 & s_z & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}
\;\;\;
\begin{bmatrix} v_x \\ v_y \\ v_z \\ 1 \\\end{bmatrix}
=
\begin{bmatrix} s_x v_x \\ s_y v_y \\ s_z v_z \\ 1 \\\end{bmatrix}
$

Jeśli trójka $\mathbf{\vec v}$ jest punktem, to jest traktowana jako wektor względem początku układu współrzędnych. Czyli jeśli punkt należy do obiektu to jego środek powinien leżeć w środku układu współrzędnych, żeby całą operacja miała sens.

Chcąc przeskalować obiekt nie leżący w środku układu współrzędnych musimy złożyć macierz transformacji z macierzy transpozycji do środka układu współrzędnych, macierzy do niej odwrotnej i samej macierzy skalowania.

Transpozycja macierzy skalowania jest równa jej samej.

Składanie macierzy

Mamy macierz transformacji przekształcającą układ współrzędnych $M_1\rightarrow 2$ oraz $M_2\rightarrow 3$. Macierz przekształcająca nam układ współrzędnych 1 w 3 ma postać:

$M_{1\rightarrow 3}=M_{2\rightarrow 3} \cdot M_{1\rightarrow 2}$

Kolejność ma znaczenie.

Przykład:

Rotacja obiektu wokół swojego środka składa się z 3 transformacji i tym samym trzech macierzy:

$M_1$ - sprowadzenie obiektu do początku układu współrzędnych
$M_2$ - rotacja wokół środka układu współrzędnych
$M_3$ - macierz odwrotna do $M_1$

Złożeniem tych trzech macierzy jest macierz:

$M_{321} = M_3 \cdot M_2 \cdot M_1$

Wynikowa macierz to macierz rotacji dla tego konkretnego położenia obiektu wokół jego środka.

Składając ze sobą macierz rotacji i translacji z reguły najpierw dokonujemy rotacji (wokół środka układu współrzędnych), a później translacji.

Wybór sposobu mnożenia macierz razy wektor ma wpływ na to jak składane są macierze. W przypadku traktowania wektora jako wiersz, transformacje są nakładane od lewej do prawej. Jeśli wektor jest traktowany jako kolumna to od prawej do lewej, czyli pierwsza transformacja jest ostatnią w iloczynie.

2011-07-08

Macierz transponowana

Macierz transponowana $\mathbf{M^{T}}$ macierzy $\mathbf{M} $to taka macierz w której elementy o współrzędnych $\mathbf{(i,j)}$ zostały umieszczone pod współrzędnymi $\mathbf{(j,i)}$. Przy czym pierwsza współrzędna to wiersz, druga to kolumna.

Szczególna właściwość macierzy kwadratowej:

$\det M=\det M^T$

Właściwości:

$(A^{-T})^T=A$
$(A+B)^T=A^T+B^T$
$(AB)^T=A^{T}B^{T}$
$(cA)^T=c(A)^T$
$(A^{T})^{-1}=(A^{-1})^{T}$

Przykłady:

$\begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \\ \end{bmatrix}^T=\;\begin{bmatrix} 1 & 3 & 5 \\ 2 & 4 & 6 \\ \end{bmatrix}$

$\begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix}^T=\;\begin{bmatrix} 1 & 3 \\ 2 & 4 \\ \end{bmatrix}$

Dla macierzy kwadratowych elementy po przekątnej zostają na swoim miejscu, zaś pozostałe są symetrycznie odbijane względem tej przekątnej.

Dopełnienie algebraiczne macierzy

Dopełnienie algebraiczne i-tego wiersza, j-tej kolumny macierzy $\mathbf{M}$ to:

$C_{ij}=(-1)^{i+j}\cdot \det M_{ij}$

Macierz $\mathbf{M_{ij}}$ to macierz powstała z $\mathbf{M}$ poprzez wykreślenie i-tego wiersza i j-tej kolumny.

Dopełnienie algebraiczne istnieje tylko dla macierzy kwadratowych.

Przykład:

$M=\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9 \\
\end{bmatrix}$

$M_{22}=\begin{bmatrix}
1 & 3 \\
7 & 9 \\
\end{bmatrix}$

$\det M_{22}=1\cdot 9 - 3\cdot 7=9-21=(-12)$

$C_{11}=(-1)^{1+1}\cdot (-12)=(-12)$

Macierz odwrotna

Macierz $\mathbf{A}$ nazywamy macierzą odwrotną do $\mathbf{B}$ jeśli:

$A \cdot B=B \cdot A=I$
Gdzie $\mathbf{I}$ to macierz jednostkowa. $\mathbf{A}$ i $\mathbf{B}$ to macierze kwadratowe. Macierz odwrotną do macierzy $\mathbf{A}$ oznaczamy jako $\mathbf{A^{-1}}$.

Własności macierzy odwrotnej

$(A^{-1})^{-1}=A$
$(A^T)^{-1}=(A^{-1})^T$
$(k\cdot A)^{-1}=\frac{1}{k}\cdot A^{-1}$
$(A\cdot B)^{-1}=B^{-1}\cdot A^{-1}$
$(A_{1}A_{2}...A_{N})^{-1}=A_N^{-1}...A_2^{-1}A_1^{-1}$
$\det {A^{-1}}=\displaystyle\frac{1}{\det A}$

Wyznaczanie macierzy odwrotnej

$A^{-1}=\displaystyle{1 \over \det A}\left(C^{\mathrm{T}}\right)_{ij}=\displaystyle{1 \over \det A}\left(C_{ji}\right)=\displaystyle{1 \over \det A}\begin{bmatrix}C_{11} & C_{21} & \cdots & C_{n1} \\C_{12} & C_{22} & \cdots & C_{n2} \\\vdots & \vdots & \ddots & \vdots \\C_{1n} & C_{2n} & \cdots & C_{nn} \\\end{bmatrix}$

Macierz $\mathbf{C_{ji}}$ to transponowana macierz dopełnień algebraicznych macierzy $\mathbf{A}$.

Zauważmy, że jeśli $\mathbf{\det A=0}$ macierz odwrotna do $\mathbf{A}$ nie istnieje.

Zastosowanie w grafice 3D

Wymnażając punkt $\mathbf{P}$ przez macierz $\mathbf{M}$ otrzymujemy nowy punkt $\mathbf{P'}$. Mnożąc punkt $\mathbf{P'}$ przez macierz $\mathbf{M^{-1}}$ otrzymujemy spowrotem punkt $\mathbf{P}$. Punkt $\mathbf{P}$ może być tutaj równie dobrze macierzą. Macierz $\mathbf{M}$ to z reguły transformacja układu współrzędnych np: świat-kamera, lokalny układ obiektu-świat albo dowolny inny. Macierz M jest najczęściej złożeniem macierzy rotacji, transpozycji, skalowania.

Przykład wyznaczenia macierzy odwrotnej 3x3 w C#:

public Matrix3 Inverted
{
    get
    {
        double det = Determinant;

        Debug.Assert(det != 0);

        return new Matrix3(

            (M22 * M33 - M23 * M32) / det, 
            -(M12 * M33 - M13 * M32) / det, 
            (M12 * M23 - M13 * M22) / det, 

            -(M21 * M33 - M23 * M31) / det, 
            (M11 * M33 - M13 * M31) / det, 
            -(M11 * M23 - M13 * M21) / det, 

            (M21 * M32 - M22 * M31) / det, 
            -(M11 * M32 - M12 * M31) / det, 
            (M11 * M22 - M12 * M21) / det
        );
    }
}

Przykład szybkiego wyznaczenia macierzy odwrotnej 4x4 w C#:

public Matrix4 Inverted
{
    get
    {
        var d01 = M31 * M42 - M41 * M32;
        var d02 = M31 * M43 - M41 * M33;
        var d12 = M32 * M43 - M42 * M33;
        var d13 = M32 * M44 - M42 * M34;
        var d23 = M33 * M44 - M43 * M34;
        var d30 = M34 * M41 - M44 * M31;

        double r_11 = M22 * d23 - M23 * d13 + M24 * d12;
        double r_21 = -(M21 * d23 + M23 * d30 + M24 * d02);
        double r_31 = M21 * d13 + M22 * d30 + M24 * d01;
        double r_41 = -(M21 * d12 - M22 * d02 + M23 * d01);

        var s = 1 / (M11 * r_11 + M12 * r_21 + M13 * r_31 + M14 * r_41);

        double r_12 = -(M12 * d23 - M13 * d13 + M14 * d12) * s;
        double r_22 = (M11 * d23 + M13 * d30 + M14 * d02) * s;
        double r_32 = -(M11 * d13 + M12 * d30 + M14 * d01) * s;
        double r_42 = (M11 * d12 - M12 * d02 + M13 * d01) * s;

        d01 = M11 * M22 - M21 * M12;
        d02 = M11 * M23 - M21 * M13;
        d12 = M12 * M23 - M22 * M13;
        d13 = M12 * M24 - M22 * M14;
        d23 = M13 * M24 - M23 * M14;
        d30 = M14 * M21 - M24 * M11;

        return new Matrix4(
            r_11 * s, 
            r_12, 
            (M42 * d23 - M43 * d13 + M44 * d12) * s, 
            -(M32 * d23 - M33 * d13 + M34 * d12) * s,

            r_21 * s, 
            r_22, 
            -(M41 * d23 + M43 * d30 + M44 * d02) * s, 
            (M31 * d23 + M33 * d30 + M34 * d02) * s,

            r_31 * s, 
            r_32, 
            (M41 * d13 + M42 * d30 + M44 * d01) * s, 
            -(M31 * d13 + M32 * d30 + M34 * d01) * s,

            r_41 * s, 
            r_42, 
            -(M41 * d12 - M42 * d02 + M43 * d01) * s, 
            (M31 * d12 - M32 * d02 + M33 * d01) * s
        );
    }
}

Macierz jednostkowa

To taka macierz, że po jej przekątnej mamy jedynki, zaś wszędzie indziej zera. Macierz jednostkowa jest macierzą kwadratową.

Przykład macierzy jednostkowej 4x4:

$\mathbf{I}=\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}$

Wymnożenie dowolnej macierzy $\mathbf{A}$ przez macierz jednostkową daje $\mathbf{A}$.

$\mathbf{A}\cdot \mathbf{I}=\mathbf{A}$
$\mathbf{I}\cdot \mathbf{B}=\mathbf{B}$

Przy czym jeśli wymiary macierzy $\mathbf{A}$ i $\mathbf{B}$ powinny być tak dobrane by mnożenie było możliwe.

Jeśli istnieją takie macierze $\mathbf{A}$ i $\mathbf{B}$, że:

$\mathbf{A}\cdot \mathbf{B}=\mathbf{B}\cdot \mathbf{A}=\mathbf{I}$

To mówimy, że macierz $\mathbf{A}$ jest odwrotna do macierzy $\mathbf{B}$, a $\mathbf{B}$ odwrotna do macierzy $\mathbf{A}$.

2011-07-07

Równanie parametryczne linii

Równanie parametryczne linii przechodzącej przez punkt P o kierunku $\mathbf{\vec{d}}$ dla parametru $\mathbf{t\in\mathbb{R}}$ wyznacza nam zbiór wszystkich punktów linii:

$P=P+\vec{d}\cdot t$
Traktując linie jako promień biegnący od P w kierunku $\vec{d}$ jeśli $\mathbf{t<0}$ to punkt leży przed promieniem. Jeśli $\mathbf{t>0}$ to punkt leży na drodze promienia.

2011-07-04

Prawo odbicia

Promień światła o kierunku $\mathbf{\vec{R}_{IN}}$ pada na powierzchnię w punkcie o normalnej $\mathbf{\vec{N}}$ odbija się w kierunku $\mathbf{\vec{R}_{OUT}}$. Kąt padania względem $\mathbf{\vec{N}}$ jest równy kątowi odbicia względem $\mathbf{\vec{N}}$.

Zakładamy, że wektor $\mathbf{\vec{N}}$ jest znormalizowany.
image/svg+xml Master slide R R d d R N N OUT IN
Rzut wektora $\mathbf{\vec{R}_{IN}}$ na $\mathbf{\vec{N}}$:

$\vec{R}_{N}=-(\vec{R}_{IN}\cdot\vec{N})*\vec{N}$(1)

Wektor $\mathbf{\vec{d}}$ możemy wyliczyć na dwa sposoby:

$\vec{d}=\vec{R}_{N}+\vec{R}_{IN}$
$\vec{d}=\vec{R}_{OUT}-\vec{R}_{N}$

Z porównania:

$\vec{R}_{N}+\vec{R}_{IN}=\vec{R}_{OUT}-\vec{R}_{N}$

Stąd:

$\vec{R}_{OUT}=2*\vec{R}_{N}+\vec{R}_{IN}$

Podstawiając $\mathbf{\vec{R}_{N}}$ z (1) otrzymujemy:

$\vec{R}_{OUT}=-2*(\vec{R}_{IN}\cdot\vec{N})*\vec{N}+\vec{R}_{IN}$

Jeśli dodatkowo wektor $\mathbf{\vec{R}_{IN}}$ jest znormalizowany to wtedy wektor $\mathbf{\vec{R}_{OUT}}$ też jest znormalizowany:

$\left|\vec{R}_{OUT}\right|^2=\left|\vec{R}_{N}\right|^2+\left|\vec{d}\right|^2=\left|\vec{R}_{IN}\right|^2=1$

Przykład:

Vector3 reflected_dir = 
    Ray.Dir - ShadeNormal * (2 * ShadeNormal * Ray.Dir);

Wektory ShadeNormal i Ray.Dir sa znormalizowane.