Arvutigraafika
Arvutigraafika mängib suurt rolli filmi- ja mängutööstuses, CAD-programmides, pildi ja videotöötluses, robootikas (arvutinägemine) jne.
Objektide geomeetriline modelleerimine
Geomeetrilisi objekte kuvatakse ekraanile lähtuvalt nende kujundite kolmemõõtmelisest mudelist arvuti mälus. Enamkasutatavad mudelid moodustatakse hulknurkade ühendina, s.t modelleeritavate objektide pind konstrueeritakse hulknurkade võrena, kusjuures modelleeritav objekt on seda tõetruum, mida rohkemate hulknurkade abil on tema pind võrendatud.
Skalaarkorrutis
\[ \vec{a} \cdot \vec{b} := |\vec{a}||\vec{b}| \cos(\theta) = a_1 b_1 + a_2 b_2 \]
\[ \vec{a} \cdot \vec{b} := |\vec{a}||\vec{b}| \cos(\theta) = a_1 b_1 + a_2 b_2 \]
Nurk vektorite vahel
\[ \cos(\alpha) = \frac{\vec{x} \cdot \vec{y}}{|\vec{x}||\vec{y}|} = \frac{x_1 y_1 + x_2 y_2}{\sqrt{x_1^2 + x_2^2} \cdot \sqrt{y_1^2 + y_2^2}} \]
\[ \cos(\alpha) = \frac{\vec{x} \cdot \vec{y}}{|\vec{x}||\vec{y}|} = \frac{x_1 y_1 + x_2 y_2}{\sqrt{x_1^2 + x_2^2} \cdot \sqrt{y_1^2 + y_2^2}} \]
Vektorkorrutis
\[ \vec{a} \times \vec{b} := |\vec{a}||\vec{b}| \sin(\theta) =
\begin{vmatrix}
\vec{i} & \vec{j} & \vec{k} \\
a_1 & a_2 & a_3 \\
b_2 & b_2 & b_3
\end{vmatrix} \]
\[ \vec{a} \times \vec{b} := |\vec{a}||\vec{b}| \sin(\theta) =
\begin{vmatrix}
\vec{i} & \vec{j} & \vec{k} \\
a_1 & a_2 & a_3 \\
b_2 & b_2 & b_3
\end{vmatrix} \]
Hulknurga keskpunkt
\[ C_x = \frac{1}{6A} \sum_{i=0}^{n-1} (x_i + x_{i+1})(x_i y_{i+1} - x_{i+1}y_i) \]
\[ C_y = \frac{1}{6A} \sum_{i=0}^{n-1} (y_i + y_{i+1})(x_i y_{i+1} - x_{i+1}y_i) \]
\[ A = \frac{1}{2} \sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1}y_i) \]
Punkti kaugus sirgeni
Punkti $P=(a_0,b_0)$ kaugus punktidega $P_1 = (a_1,b_1)$ ja $P_2 = (a_2,b_2)$ antud sirgeni $s$: \[ d(P,s) = \frac{|(y_2 - y_1)x_0 - (x_2 - x_1)y_0 + x_2 y_1 - y_2 x_1|}{\sqrt{(y_2 - y_1)^2} + (x_2 - x_1)^2} \]Kokkupõrke arvutamine
\[ j_r = \frac{-(1+e)\vec{v}_r \cdot \hat{\mathbf{n}}}{m_1^{-1} + m_2^{-1} + (\mathbf{I}_1^{-1}(\mathbf{r}_1 \times \hat{\mathbf{n}}) \times \mathbf{r}_1 + \mathbf{I}_2^{-1}(\mathbf{r}_2 \times \hat{\mathbf{n}}) \times \mathbf{r}_2) \cdot \hat{\mathbf{n}}} \]
\[ \mathbf{v}_1^{'} = \mathbf{v}_1 - \frac{j_r}{m_1} \hat{\mathbf{n}}, \; \; \; \mathbf{v}_2^{'} = \mathbf{v}_2 - \frac{j_r}{m_2} \hat{\mathbf{n}} \]
\[ \omega_1^{'} = \omega_1 - j_r \mathbf{I}_1^{-1} (\mathbf{r}_1 \times \hat{\mathbf{n}}), \; \; \; \omega_2^{'} = \omega_2 + j_r \mathbf{I}_2^{-1} (\mathbf{r}_2 \times \hat{\mathbf{n}}) \]
Geomeetrilised teisendused
Et geomeetrilisi objekte ekraanil liikuma panna, on vaja teisendada selle kujundi punkte, s.t tuleb ette anda eeskiri, mille alusel arvutatakse vaadeldava objekti punktidele uued koordinaadid. Ühed lihtsamad teisendused on lineaarteisendused, mille hulka kuuluvad objekti nihutamine, pööramine, peegeldamine, skaleerimine jne... Vektorruumide $U$ ja $W$(üle korpuse $\mathbb{K}$) vahelist kujutust $f: U \rightarrow W$ nimetatakse lineaarkujutuseks, kui \[ f(\mathbf{u} + \mathbf{v}) = f(\mathbf{u}) + f(\mathbf{v}) \text{ iga } \mathbf{u,v} \in U \text{ korral ja }\] \[ f(c\mathbf{u}) = c f(\mathbf{u}) \text{ iga } c \in \mathbb{K}, \mathbf{u} \in U \text{ korral} \] Lineaarkujutus säilitab vektorite liitmise ja skalaariga korrutamise. $\mathbf{A} = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}, \mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \Rightarrow \mathbf{Ax} = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} a_{11} x_1 + a_{12} x_2 \\ a_{21} x_2 + a_{22} x_2 \end{pmatrix} = \mathbf{x'}$ $\mathbf{A} = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}, \mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} \Rightarrow \mathbf{Ax} = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} a_{11} x_1 + a_{12} x_2 + a_{13} x_3 \\ a_{21} x_1 + a_{22} x_2 + a_{23} x_3 \\ a_{31} x_1 + a_{22} x_2 + a_{23} x_3 \end{pmatrix} = \mathbf{x'}$
Pööre
$\mathbf{A} =
\begin{pmatrix}
\cos{\theta} & -\sin(\theta) \\
\sin(\theta) & \cos(\theta)
\end{pmatrix}$
Kitsendamine $\mathbf{A} =
\begin{pmatrix}
k & 0 \\
0 & \frac{1}{k}
\end{pmatrix}$
Skaleerimine $\mathbf{A} =
\begin{pmatrix}
k & 0 \\
0 & k
\end{pmatrix}$
Horisontaalne nihutamine $\mathbf{A} =
\begin{pmatrix}
1 & k \\
0 & 1
\end{pmatrix}$
Peegeldamine x ja y telje suhtes $\mathbf{A} =
\begin{pmatrix}
1 & 0 \\
0 & -1
\end{pmatrix},
\mathbf{A} =
\begin{pmatrix}
-1 & 0 \\
0 & 1
\end{pmatrix}$
Projektsioon x ja y teljele $\mathbf{A} =
\begin{pmatrix}
1 & 0 \\
0 & 0
\end{pmatrix},
\mathbf{A} = \begin{pmatrix}
0 & 0 \\
0 & 1
\end{pmatrix}
$
Projektiivne geomeetria
Kolmemõõtmeliste objektide kahemõõtmelisel arvutiekraanil kuvamiseks on vaja rakendada projektiivset geomeetriat, mille põhjal on võimalik arvutada, milliseid objekti külgi mis määras ja millises perspektiivis vaatetasandile (arvutiekraan) kuvada. Fikseerime ruumis $\mathbb{R}^3$ fookuse ehk kaamera asukoha $C \in \mathbb{R}^3$. Fikseerime kaamera asukohast lähtuvalt kaamera vaate suunavektori ning selle suunavektoriga kaugusel $f$ ristuva kaamera vaatetasandi $\pi$. Siis mistahes punkti $X$ korral leidub sirge, mis läbib punkte $X$ ja $C$, kusjuures see sirge lõikab vaatetasandit $\pi$ punktis $X'$. Projektsioonsirged punktidest $X$ läbi fikseeritud punkti $X$ on üksüheses vastavuses vaatetasandi $\pi$ punktidega $X$', mis on vastava projektsioonsirge ja vaatetasandi lõikepunkt. Punkti $X$ homogeenseteks koordinaatideks nimetatakse mistahes punkte $\lambda AX$, kus $\lambda \in \mathbb{R}$. Ruumipunkti $(x_1,x_2,x_3)$ projektsiooni koordinaadid vaatetasandil saab leida tekkinud kolmnurkade sarnasusest, mille tulemusel \[ \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} = \frac{f}{x_3} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \] Homogeensetes koordinaatides saame eelnevale võrdusele kuju \[ \begin{pmatrix} y_1 \\ y_2 \\ 1 \end{pmatrix} = \frac{f}{x_3} \begin{pmatrix} x_1 \\ x_2 \\ \frac{x_3}{f} \end{pmatrix} \sim \begin{pmatrix} x_1 \\ x_2 \\ \frac{x_3}{f} \end{pmatrix} \] Esitades punkti $(x_1,x_2,x_3)$ homogeensetes koordinaatides, saame eelnevale võrdusele kuju \[ \begin{pmatrix} y_1 \\ y_2 \\ 1 \end{pmatrix} \sim \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{f} & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ 1 \end{pmatrix}, \] kus \[ \mathbf{C} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{f} & 0 \end{pmatrix} \sim \begin{pmatrix} f & 0 & 0 & 0 \\ 0 & f & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} \] on kaamera maatriks Esialgse koordinaatsüsteemi pöörde maatriks on $ \Big( \begin{array}{c|c} \mathbf{R} & \mathbf{0} \\ \hline \mathbf{0} & 1 \end{array} \Big) $ ja nihke maatriks on $ \Big( \begin{array}{c|c} \mathbf{I} & \mathbf{t} \\ \hline \mathbf{0} & 1 \end{array} \Big) $, kus $\mathbf{R} = R(\theta) = R_z(\alpha) \cdot R_y (\beta) \cdot R_y (\gamma)$, kus \[ R_x(\theta) = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \cos \theta & - \sin \theta \\ 0 & \sin \theta & \cos \theta \end{pmatrix}, \; \; R_y(\theta) = \begin{pmatrix} \cos \theta & 0 & \sin \theta \\ 0 & 1 & 0 \\ - \sin \theta & 0 & \cos \theta \end{pmatrix} , \; \; R_z(\theta) = \begin{pmatrix} \cos \theta & - \sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{pmatrix} \] ning $\mathbf{t} = (p_x,p_y,p_z)^T$ on nihkevektor. Kokkuvõteks saab punkti $(x_1,x_2,x_3)$ projektiivset teisendust vaatetasandile $\pi$ kirjeldada maatrikskujul \[ \mathbf{y} \sim \mathbf{C} \mathbf{x} = \begin{pmatrix} f & 0 & 0 & 0 \\ 0 & f & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} \cdot \Big( \begin{array}{c|c} \mathbf{R} & \mathbf{0} \\ \hline \mathbf{0} & 1 \end{array} \Big) \cdot \Big( \begin{array}{c|c} \mathbf{I} & \mathbf{t} \\ \hline \mathbf{0} & 1 \end{array} \Big) \mathbf{x} \]Renderdamine
Kiirtejälitus (ray tracing)
Kiirte arvutamine ristküliku vaateväljast.
Asetame ruumi $\mathbb{R}^3$ kaamera kohavektoriga $\vec{e}$. Fikseerime selle kaamera asukohast lähtuvalt normeeritud ristkoordinaatsüsteemi $(\vec{s}, \vec{v}, \vec{b})$, kus
$\vec{s}$ on kaamera vaate suunavektor;
$\vec{v}$ on suunavektoriga $\vec{s}$ ristuv kaamera vaate orientatsioonivektor;
$\vec{b} := \vec{s} \times \vec{b}$ on mõlema eelneva vektoriga ristuv vektor, mis määrab parema käe koordinaadistiku.
Konstrueerime kaamera jaoks tema vaate suunavektoriga ristuva ja vektoriga $\vec{v}$ orienteeritud ristkülikukujulise vaateekraani,
mille laius on $h_x$, kõrgus on $h_y$ ja mille keskpunkti kaugus kaamerast on $t$. Siis selle vaateekraani keskpunkti kohavektor on
$\vec{c} = \vec{e} + t \vec{s}$. Jaotame vaateekraani vastavalt $k \times m$ piksliks. Siis piksite mõõtmed on vastavalt $\frac{h_x}{k} \times \frac{h_y}{m}$.
Siis $i$-ndas reas ja $j$-ndas veerus paikneva piksli keskpunkti kohavektor on $\vec{p}_{ij} = \vec{p}_{11} + \frac{h_x}{k} \vec{b} - \frac{h_y}{m} \vec{v}$,
kus $\vec{p}_{11} = ...$.
Kaamerast lähtuva ja vaateekraani $i$-ndas reas ja $j$-ndas veerus paikneva piksli keskpunkti läbiva kiire parameetriline võrrand on
$\vec{e} + d \vec{p}_{ij}$, kus $d \ge 0$ on selle kiire parameeter. Vaateekraani igat pikslit läbiva ja kaamerast lähtuva kiire korral
leiami need kujundid ruumis $\mathbb{R}^3$, mida antud kiir lõikab. Kui kujund on antud võrrandiga ilmutamata kujul $f(\vec{p}) = 0$,
siis selle kujundi ja parameetriliselt antud kiire $\vec{e} + d \vec{p}_{ij}$ lõikepunktide leidmiseks tuleb lahendada võrrand
$f(\vec{e} + d \vec{p}_{ij}) = 0$.
- silma asukoht
$T \in \mathbb{R}^3$ - sihtmärgi asukoht
$\theta in [0,\pi]$ - nägemisulatus, inimese silma korral $\approx \pi 2 \rad = 90^{\circ} $
$m,k \in \mathbb{N}$ ruutpiksleid ristküliku vaateväljas vertikaal- ja horisontaalsihil
$i,j \in \mathbb{N}, \; 1 \leq i \leq k \land 1 \leq j \leq m$ tegelik pikslite arv
$\vec{w} \in \mathbb{R}^3$ - vertikaalne vektor, mis määrab orientatsiooni, tavaliselt $\vec{w} = [0,1,1]$ - pöördekomponent, mis määrab vaatevälja pöörde punkti
$C$ ümber.
Leiame ja normaliseerime vektori $\vec{t}$ ja vektorid $\vec{b}, \vec{v}$, mis on paralleelsed vaateväljaga.
\[ \vec{t} = T - E, \; \; \vec{b} = \vec{w} \times \vec{t} \]
\[ \vec{t}_n = \frac{\vec{t}}{||\vec{t}||}, \; \; \vec{b}_n = \frac{\vec{b}}{||\vec{b}||}, \; \; \vec{v}_n = \vec{t}_n \times \vec{b}_n \]
Vaatevälja keskpunkt $C = E + \vec{t}_n \times \vec{b}_n$. Järmiseks arvutame vaateväljade suurused $h_x$ ja $h_y$ jagatud 2-ga, sisaldades suhet $\frac{m}{k}$:
\[ g_x = \frac{h_x}{2} = d \tan \frac{\theta}{2}, \; \; g_y = \frac{h_y}{2} = g_x \frac{m}{k} \]
ja siis ma arvutame järgmise piksli nihkevektorid $q_x, q_y$ suunal, mis on paralleelne vaateväljaga $\vec{b},\vec{v}$, ja alumise vasaku piksli keskpunkti $p_{1m}$
\[ \vec{q}_x = \frac{2 g_x}{k-1} \vec{b}_n, \; \; \vec{q}_y = \frac{2 g_y}{m-1} \vec{v}_n, \; \; \vec{p}_{1m} = \vec{t}_n d - g_x \vec{b}_n - g_y \vec{v}_n \]
Märkuseks, et $P_{ij} = E + \vec{p}_{ij}$ ja kiir $\vec{R}_{ij} = P_{ij} - E = \vec{p}_{ij}$, seega
\[ \vec{p}_{ij} = \vec{p}_{im} + \vec{q}_x (i-1) + \vec{q}_y (j-1), \; \; \vec{r}_{ij} = \frac{\vec{R}_{ij}}{||\vec{R}_{ij}||} = \frac{\vec{p}_{ij}}{||\vec{p}_{ij}||} \]