Raycasting

Raycasting

Tekintsünk minden pixelre úgy, mint egy kis ablakra a világra.

Milyen színértéket vegyen fel ez a pixel? $\to$ Nézzük meg, mi látszik onnan a világból és az alapján rendeljünk hozzá a pixelhez egy színt!

Az algoritmus

	for each pixel:
		cast a ray into the scene

		for each object in scene:
			check if the ray intersects the object

		set pixel to the color of the closest object

Sugár

A sugárnak van

egy $p_{0}$ kiindulási pontja
egy $v$ iránya

A parametrikus sugár: $p (t) = p_{0} + t v,$ ahol $t > 0$ (félegyenes).

$t = 0$ ?, $t < 0$ ? sugár kezdőpontja, sugár mögötti részek.

Sugarak indítása

A szempozcióból indítunk sugarakat minden pixel középpontján keresztül

Most: középpontosan szeretnénk vetíteni egy kamerába, a vetítési sík egy négyszögletes részét megfeleltetve a képernyőnek.

Kamera tulajdonságok

Szempozíció (eye),
Egy pont amire néz (center),
Felfele irányt megadó vektor a világban (up),
Nyílásszög, amekkora szögtartományt lát (fov),
Vetítővászon mérete. Most legyen adott: $2 tan (\frac{fov _{x}}{2}) \times 2 tan (\frac{fov _{y}}{2}) na g ys \overset{a}{ˊ} g \overset{u}{ˊ} .$

Ezek segítségével fogjuk megadni $(i, j)$ pixel világbeli koordinátáit.

Keressük a kamera saját $u, v, w$ (jobbkezes) koordináta-rendszerét.

Nézzen a kamera $- Z$ irányba! $w = \frac{eye - center}{∣ eye - center ∣}$
Az $X$ tengely legyen merőleges mind $w$ -re, mind az $up$ irányra! $u = \frac{up \times w}{∣ up \times w ∣}$
Az $Y$ tengely merőleges $u$ -ra és $w$ -re is: $v = w \times u$

Pixel koordináták

Legyen $p$ az $i, j$ pixel középpontja, a vetítősík egységnyi távolságra a nézőponttól!
Ekkor: $p (i, j) = eye + (αu + β v - w)$ Ahol

$α = tan (\frac{fov _{x}}{2}) \cdot \frac{i - width /2}{width /2}$
$β = tan (\frac{fov _{y}}{2}) \cdot \frac{height /2 - j}{height /2}$

A sugár egyenlete

A sugár egy félegyenes, amit kezdőpontjával és irányvektorával adhatunk meg.

Legyen $p_{0}$ a sugár kezdőpontja, $v$ pedig az irányvektora, ekkor $p (t) = p_{0} + t v, t \geq 0$ megadja a sugár összes pontját.

Most a sugarak kezdőpontját az előbbieknek megfelelően számolhatjuk, azaz $p_{0} = p (i, j)$

A sugár irányvektora pedig $v = \frac{p ( i , j ) - eye}{∣ p ( i , j ) - eye ∣}$

Metszések

A sugárkövető programok futásidejük döntő részében metszéseket fognak végezni.

Nézzük meg néhány egyszerű geometriai elemmel vett metszetét a sugárnak.

A sugarak mindig a korábban is látott $p (t) = p_{0} + t v$ alakú, ahol feltesszük a továbbiakban, hogy $∣ v ∣ = 1$ .

Ekkor a $t$ sugárparaméter éppen a $p (t)$ pont távolsága $p_{0}$ -tól.

Parametrikus sugár és implicit felület metszéspontja

Legyen adva egy $f (x) = f (x, y, z) = 0$ implicit egyenlet, ami meghatározza a metszeni kívánt felületet. ( $x \in R^{3}$ )

A sugarunk egyenlete $\forall t \in [0, \infty)$ -re meghatározott egy pontot a térben $\to$ helyettesítsük be ezt a képletet az implicit egyenletbe!

Tehát a következő egyenletet kell megadnunk $t$ -re:

$f (p (t)) = 0$

A kapott $t$ -től függően a következő esetek állhatnank fenn:

Ha $t > 0$ , akkor a sugarunk előtt van a felület és metszi
Ha $t = 0$ , akkor a sugár kezdőpontja a felületen van
Ha $t < 0$ , akkor a sugár "mögött" van a felület és metszi a sugár egyenese a felületet (de nekünk $t > 0$ kell!)

Parametrikus sugár és parametrikus felület metszéspontja

Legyen adva egy $r (u, v) = [x (u, v), y (u, v), z (u, v)]^{T}$ parametrikus felület.

Kell találni egy olyan $t$ sugárparamétert, amihez létezik $(u, v)$ , hogy $p (t) = r (u, v)$

Ez három ismeretlenes ( $t, u, v$ ), három egyenletes ( $x, y, z$ koordinátáként egy) egyenletrendszer.

A $t$ ugyanúgy ellenőrizhető, mint előbb, de most az $(u, v)$ -re is figyeljünk, hogy a felületünk paramétertartományának megengedett részén van-e (általában $(u, v) \in [0, 1]^{2}$ kell)!

Sugár és implicit sík metszéspontja

Síkot megadhatunk implicit alakban: $A x + B y + C z + D = 0$

$p (t) = p_{0} + t v = x_{0} y_{0} z_{0} + t x y z$

A fenti sugár egyenese metszi a síkot, ha

$A (x_{0} + t x) + B (y_{0} + t y) + C (z_{0} + t z) + D = 0$

Ezt $t$ -re átrendezve adódik

$t (A x + B y + C z) + x_{0} + y_{0} + z_{0} + D = 0$

$t = - \frac{x _{0} + y _{0} + z _{0} + D}{A x + B x + C z}$

Látható a sík a nézőpontunkból, ha $t > 0$

Sugár és normálvektoros sík metszéspontja

Legyen $q_{0}$ a sík egy pontja, $n$ a normálvektora.

Legyen $p_{0}$ ez egyenes egy pontja, $v$ az irányvektora.

Az egyenes egyenlete: $p (t) = p_{0} + t v$

A sík egyenlete: $⟨ n, q - q_{0} ⟩ = 0$ minden $q$ pontja a síknak kielégíti ezt az egyenletet.

Behelyettesítve $p (t)$ -t a $q$ helyére:

$⟨ n, p_{0} + t v - q_{0} ⟩ = 0,$ $⟨ n, p_{0} ⟩ + t ⟨ n, v ⟩ - ⟨ n, q_{0} ⟩ = 0,$ $t = \frac{⟨ n , q _{0} ⟩ - ⟨ n , p _{0} ⟩}{⟨ n , v ⟩} = \frac{⟨ n , q _{0} - p _{0} ⟩}{⟨ n , v ⟩}$ ha $⟨ n, v ⟩ \neq = 0$

A sugár metszi a síkot, ha $t > 0$ .

Ha $⟨ n, v ⟩ = 0$ , akkor az egyenes párhizamos a síkkal, és így vagy nincs metszéspontjuk, vagy az egyenes a síkon fut.

Sugár és parametrikus sík metszéspontja

Síkot megadhatunk egy $q$ pontjával és $i, j$ kifeszítő vektorokkal is: $s (u, v) = q + u i + v j$

Metszéspont a $p (t) = p_{0} + t v$ sugár egyenesével: keressük $t$ és $u, v$ -t úgy, hogy $p (t) = s (u, v)$

Beírva a képletet adódik $p_{0} + t v = q + u i + v j$

Átrendezve kapjuk, hogy $p_{0} - q = - t v + u i + v j$

Ez három ismeretlenes, három lineáris egyenletből álló egyenletrendszer, ami megoldható, ha $v, i, j$ lineárisan nem összefüggő.

Mátrix alakban: $p_{0_{x}} - q_{x} p_{0_{y}} - q_{y} p_{0_{z}} - q_{z} = - v_{x} - v_{y} - v_{z} i_{x} i_{y} i_{z} j_{x} j_{y} j_{z} t u v$

Látjuk a síkot, ha $t > 0$ (most $u, v \in R$ a felület paramétertartománya, ez teljesülni fog)

Sugár és háromszög metszéspontja I.

A háromszög egyértelműen megadható három csúcsával.

Ha $a, b, c$ a háromszög csúcsai, akkor a hozzátartozó sík egy parametrikus megadésa $s (u, v) = a + u (b - a) + v (c - a)$

A korábbi jelölésekkel: $q = a, i = b - a$ és $j = c - a$

Ez egyben egy baricentrikus megadása is, hiszen átrendezve kapjuk, hogy

$s (u, v) = (1 - u - v) a + u b + v c,$ ahol az együtthatók $1$ -re összegződnek.

Elvégezve tehát a parametrikus síkkal a metszést, megkapjuk a baricentriukus koordinátáit a sugár síkkal való metszéspontjának. A sugárparamétert ne felejtsük el ellenőrizni!

Utolsó lépésként ellenőriznünk kell, hogy a metszéspont a háromszögön belül van-e. Ez pontosan akkor teljesül, ha

$0 \leq u, 0 \leq v \overset{e}{ˊ} s 0 \leq 1 - u - v$

Sugár és háromszög metszéspontja II.

A háromszög egyértelműen megadható három csúcsával.

Ha $a, b, c$ a háromszög csúcsai, akkor a hozzátartozó sík pont-normálvektoros implicit megadásához a sík

egy pontja $a, b, c$ bármelyike
normálvektora

$n = \frac{( c - a ) \times ( b - a )}{∥ ( c - a ) \times ( b - a ) ∥}$ ahol $\times$ a vektorális szorzatot jelöli, és ekkor $n$ egységnyi hosszúságú.

Először számítsuk ki az egyenes és a háromszög síkjának metszéspontját, ez legyen $p$ (már ha létezik).

Legyenek $λ_{1}, λ_{2}, λ_{3}$ a $p$ pont $a, b, c$ -re vonatkoztatott baricentrikus koordinátái, úgy hogy $p = λ_{1} a + λ_{2} b + λ_{3} c$

$p$ akkor, és csak akkor van a háromszögön belül, ha $0 \leq λ_{1}, λ_{2}, λ_{3} \leq 1$

Pont a háromszögön vizsgálat

Tudjuk, hogy $p = [x, y, z]^{T} = λ_{1} a + λ_{2} b + λ_{3} c$ . Ekkor $x = λ_{1} a_{x} + λ_{2} b_{x} + λ_{3} c_{x} y = λ_{1} a_{y} + λ_{2} b_{y} + λ_{3} c_{y} z = λ_{1} a_{z} + λ_{2} b_{z} + λ_{3} c_{z}$ ill $λ_{1} + λ_{2} + λ_{3} = 1 ⟹ λ_{3} = 1 - λ_{1} - λ_{2}$

A gyorsabb számolásértvegyük a fentiek egy síkra vett vetületét.

A koordinátasíkok közül ( $X Y$ , $XZ$ vagy $Y Z$ ) arra vegyük a háromszög 2D vetületét, amelyre a háromszög vetületének területe a legnagyobb! $\to$ a héromszög és sík normálisa leginkább "egyálású".

A vetülethez egyszerűen elhagyjuk $z, y$ vagy $x$ egyenletét, megfelelően.

Azt a tengelyt kell választani, amelyik mentén a legnagyobb a háromszög normálvektorának abszolút értéke, így biztos nem fordulhat elő, hogy a háromszög merőleges a síkra, és csak egy szakasz marad belőle.

Pl. legyen a $z$ a választott tengely. Ekkor $x = λ_{1} a_{x} + λ_{2} b_{x} + λ_{3} c_{x} y = λ_{1} a_{y} + λ_{2} b_{y} + λ_{3} c_{y}$

Behelyettesítve $λ_{3} = 1 - λ_{1} - λ_{2}$ -t, és rendezve:

$x = λ_{1} (a_{x} - c_{x}) + λ_{2} (b_{x} - c_{x}) + c_{x} y = λ_{1} (a_{y} - c_{y}) + λ_{2} (b_{y} - c_{y}) + c_{y}$

Rendezve $λ_{1}, λ_{2}$ -re kapjuk:

$λ_{1} = \frac{( b _{y} - c _{y} ) ( x - c _{x} ) - ( b _{x} - c _{x} ) ( y - c _{y} )}{( a _{x} - c _{x} ) ( b _{y} - c _{y} ) - ( b _{x} - c _{x} ) ( a _{y} - c _{y} )}$

$λ_{2} = \frac{- ( a _{y} - c _{y} ) ( x - c _{x} ) - ( a _{x} - c _{x} ) ( y - c _{y} )}{( a _{x} - c _{x} ) ( b _{y} - c _{y} ) - ( b _{x} - c _{x} ) ( a _{y} - c _{y} )}$

A nevező csak degenerált háromszög esetén lehet nulla.

$p$ akkor, és csak akkor van a háromszögön belül, ha $0 \leq λ_{1}, λ_{2}, λ_{3} \leq 1$

Sugár metszése poligonnal

Tegyük fel, hogy a poligonunk csúcsai egy síkban vannak, ekkor a metszés két lépésben történik

A sugarat metsszük el a poligon síkjával
Döntsük el, hogy a metszőpont a poligonon belül van-e

A másodikat egy síkban érdemes csinálni (vagy a poligon síkjában, vagy a poligon valamely koordinátatengelyre vett vetületének síkjában)

Pont-poligon tartalmazás teszt síkban

A pont a poligonon belül van, ha tetszőleges irányú, belőle indított sugárnak páratlan számú metszéspontja van a poligon oldalaival. (azaz a sugarat a poligon összes oldalszakaszával el kell metszeni)

Konkáv és csillag alakú poligonra is működik.

Sugár metszése szakasszal

A poligon $d_{i} = [x_{i}, y_{i}]^{T}, d_{i + 1} = [x_{i + 1}, y_{i + 1}]^{T}$ csúcspontjai közötti szakasz parametrikus alakja: $d_{i, i + 1} (s) = (1 - s) d_{i} + s d_{i + 1} = d_{i} + s (d_{i + 1} - d_{i}), s \in [0, 1]$

Ezt kell metszeni a $p (t) = p_{0} + t v$ alakú sugárral

Most: a $p_{0} = (x_{0}, y_{0})$ pont az a pont, amiről el akarjuk dönteni, hogy a poligonon belül van-e, $v$ tetszőleges.

Legyen $v = (1, 0)$ !

Így a $p (t) = d_{i, i + 1} (s)$ egyenletet csak $y$ koordinátára kell megoldani.

Keressük meg, hogy hol metszi a $d_{i, i + 1} (s)$ oldal egyenese a sugarat ( $=$ melyik $s$ -re lesz $d_{i, i + 1} (s)_{y} = y_{0}$ ?)

Azaz $y_{0} = y_{i} + s (y_{i + 1} - y_{i})$

$s$ -t kifejezve: $s = \frac{y _{0} - y _{i}}{y _{i + 1} - y _{i}}$

Innen megkapjuk azt az $x$ koordinátát $d_{i, i + 1} (s)$ -be behelyettesítve, ahol a sugér metszi a szakaszt.

Ha $s \neq \in [0, 1]$ : a sugár nem metszi a szakaszt (csak az egyenesét).

Ha $t \leq 0$ : a sugár egybeesik a szakasszal, vagy mögötte van a metszéspont.

Sugár és gömb metszéspontja

Az $r$ sugarú, $c = (c_{x}, c_{y}, c_{z})$ középpontú gömb implicit egyenlete: $(x - c_{x})^{2} + (y - c_{y})^{2} + (z - c_{z})^{2} - r^{2} = 0$

Ugyanez skalárszorzattal felírva: $⟨ p - c, p - c ⟩ - r^{2} = 0,$ ahol $p = [x, y, z]^{T}$

Legyen $p_{0}$ az egyenes egy pontja, $v$ az irányvektora.

Ekkor az egyenes egyenlete: $p (t) = p_{0} + t v$

Behelyettesítve a gömb egyenletébe ezt kapjuk: $⟨ p_{0} + t v - c, p_{0} + t v - c ⟩ - r^{2} = 0$

Kifejtve: $t^{2} ⟨ v, v ⟩ + 2 t ⟨ v, p_{0} - c ⟩ + ⟨ p_{0} - c, p_{0} - c ⟩ - r^{2} = 0$

Ez másodfokú egyenlet $t$ -re (minden más ismert).

Legyen $D = (2 ⟨ v, p_{0} - c ⟩)^{2} - 4 ⟨ v, v ⟩ (⟨ p_{0} - c, p_{0} - c ⟩ - r^{2})$

Ha $D > 0$ , két megoldás van, az egyenes metszi a gömböt.
Ha $D = 0$ , egy megoldás van, az egyenes érinti a gömböt.
Ha $D < 0$ , nincs valós megoldás, az egyenes nem metszi a gömböt.

Sugárparamétert ezután ellenőrizni kell ( $t > 0$ ).

Másodfokú egyenlet megoldása

Elméletileg a megoldás megkapható $a \neq = 0$ esetben: $x_{1, 2} = \frac{- b \pm b ^{2} - 4 a c}{2 a}$

Gyakorlatilag baj van, ha $a \approx 0$

Átalakítással megkapjuk, hogy $x_{1, 2} = \frac{2 c}{- b \mp b ^{2} - 4 a c}$ formában felírható a két gyök (Citardauq Formula)

Gyakorlatilag akkor is baj van, ha $b >> 4 a c$

Ekkor $b^{2} - 4 a c \approx b^{2}$ , vagyis $b$ előjelétől függően vagy $- b + b^{2} - 4 a c$ vagy pedig $. b - b^{2} - 4 a c$ elveszít az értékes tizedesjegyeket.
Számítsuk ki az egyik gyököt azon az ágon, amelyiken nem vonunk ki egymásból két közrl azonos pozitív számot, a másik gyököt pedig a Viète-formulákból
Azaz például ha $b > 0$ , akkor $x_{1} = \frac{- b - b ^{2} - 4 a c}{2 a}$ és $x_{2} = \frac{c}{a x _{1}}$

Sugár és transzformált objektumok metszése

Legyen $M$ egy adott objektum transzformációs mátrixa.

Feladat: Keressük $r$ sugár és az $M$ -mel transzformált objektum metszéspontját!

Probléma: Hogyan transzformálunk egy gömböt? Pontonként? Képletet írjuk át? $\dots$

Megoldás: transzformáljuk inkább a sugarat!

Tétel: Az $r$ sugér és az $M$ -mel transzformált objektum metszéspontja $\equiv$ az $M^{- 1}$ -el transzformált $r$ sugár és az objektum metszéspontja.

$M \in R^{4 \times 4}$ , homogén transzformáció
Sugár kezdőpontja: $p_{0} = (p_{x}, p_{y}, p_{z}) \to [p_{x}, p_{y}, p_{z}, 1]^{T}$
Sugár iránya: $v = (v_{x}, v_{y}, v_{z}) \to [v_{x}, v_{y}, v_{z}]^{T}$ . Így nem hat ré az eltolás.
Transzformált sugár: $\overset{r}{^} (t) = M^{- 1} p + t \cdot M^{- 1} v$

Metszetvizsgálat: használjuk $\overset{r}{^}$ -t!

Metszéspont: $q$ , akkor az eredeti térben $M \cdot q$

Távolságokaz újra kell számolni az eredeti térben!

Normálvektorok: $n$ helyett $M^{- T} \cdot n$ (inverz-transzponált)

Sugér metszése AAB-vel

AAB $=$ axis aligned box, olyan téglatest, aminek az oldallapjai a koordinátasíkjainkkal párhuzamosak.

Legyen a sugarunk $p (t) = p_{0} + t v$ alakú, ahol
$p_{0} = [x_{0}, y_{0}, z_{0}]^{T}, v = [v_{x}, v_{y}, v_{z}]^{T}$ a téglatestet pedig adjuk meg átlójának két pontjával, $a$ és $b$ segítségével ( $a < b$ )!

Tegyük fel, hogy a sugár kiindulópontja a doboztól balra helyezkedik el.

Legyen $t_{near} : = - \infty, t_{far} : = + \infty$

Ha $v_{x} = 0$ : merőleges az $x$ -tengelyre (pl. 2D-ben függőleges). Ekkor nincs metszéspont, ha $x_{0} \neq \in [a_{x}, b_{x}]$ , különben az $x$ -koordinátás számításokat kihagyhatjuk.

Ha $v_{x} \neq = 0$ , akkor legyen $t_{1} : = \frac{a _{x} - x _{0}}{v _{x}}, t_{2} : = \frac{b _{x} - x _{0}}{v _{x}}$

Ha $t_{1} > t_{2}$ : cseréljük meg $t_{1}, t_{2}$ -t!

Ha $t_{near} < t_{1}$ : $t_{near} : = t_{1}$

Ha $t_{far} < t_{2}$ : $t_{far} : = t_{2}$

A fentit végezzük el az $y$ és $z$ koordinátákra is.

Ha $t_{near} > t_{far}$ : nem találtuk el a dobozt.

Ha $t_{far} < 0$ : a doboz mögöttünk van.

Minden más esetben a sugarunk metszéspontjai a dobozzal $t_{near}$ és $t_{far}$ -ban lesznek (sorban a közelebbi és távolabbi metszéspontok)

4. félévi jegyzetek