Iscrtavanje metodom praćenja zrake (Ray tracing)

U 3D računalnoj grafici, praćenje zrake (Ray tracing) je metoda iscrtavanja koja generira sliku praćenjem puta zrake svjetlosti od kamere do izvora svjetlosti i simuliranjem optičkih efekata koji nastaju prilikom njenih susreta s virtualnim objektima. Budući da metoda poštuje zakone fizike, sposobna je proizvesti visoki stupanj vizualnog realizma, ali uz veće računske i vremenske troškove.

Virtualni objekti u 3D sceni su zapravo skup međusobno povezanih trokuta, pa se zato susret zrake svjetlosti i objekta može poistovjetiti sa presjekom pravca i nekog trokuta na tom objektu. Još preciznije, to je presjek pravca i ravnine zadane s tri nekolinearne točke (vrhovima trokuta), no treba pripaziti da je taj presjek untar tog trokuta.

Vektorski oblik jednadžbe pravca $$\overrightarrow {{r_p}} = \overrightarrow {{r_1}} + t\overrightarrow s ,{\rm{t}} \in R,t \ge 0$$ Vektorski oblik jednadžbe ravnine $$\overrightarrow {{r_\pi }} = \overrightarrow {{r_2}} + \lambda \overrightarrow a + \mu \overrightarrow b ,{\rm{ }}\lambda ,\mu \in R$$

Presjek pravca i ravnine je sustav jednadžbi s tri nepoznanice $$\overrightarrow {{r_p}} = \overrightarrow {{r_\pi }} $$ $$\overrightarrow {{r_1}} + t\overrightarrow s = \overrightarrow {{r_2}} + \lambda \overrightarrow a + \mu \overrightarrow b $$ Presjek se može pronaći na jedan elegantniji način, pomoću implicitnog (općeg) oblika jednadžbe ravnine i parametarskih jednadžbi pravca.

Implicitni (opći) oblik jednadžbe ravnine $$Ax + By + Cz + D = 0,{A^2} + {B^2} + {C^2} \ne 0$$ Parametarske jednadžbe pravca $$\left\{ \matrix{ x = {x_1} + t\alpha \hfill \cr y = {y_1} + t\beta \hfill \cr z = {z_1} + t\gamma \hfill \cr} \right.,t \in R,t \ge 0$$

Kako doći do implicitnog oblika jednadžbe ravnine?

Ravninu u prostoru možemo zadati preko jedne točke T0(x0, y0, z0) i normale n=(A, B, C).
Ako vrhove trokuta definiramo kao EFG, onda normalu možemo dobiti kao vektorski produt vektora EF i EG.
Sad su nam poznati A,B,C, preostaje nam još odrediti koeficijent D.
S obzirom da točka T0 leži u ravnini, njezine koordinate moraju zadovoljavati jednadžbu te ravnine. Stoga vrijedi $$A{x_0} + B{y_0} + C{z_0} + D = 0$$ iz čega se dobiva $$D = - A{x_0} - B{y_0} - C{z_0}$$ Konačno dobivamo $$Ax + By + Cz + D = 0$$ $$Ax + By + Cz - A{x_0} - B{y_0} - C{z_0} = 0$$ $$A(x - {x_0}) + B(y - {y_0}) + C(z - {z_0}) = 0$$ jednadžbu ravnine zadanu s točkom i normalom.

Položaj pravca i ravnine

Pravac i ravnina u prostoru mogu biti u sljedećim položajima:
- pravac i ravnina se sijeku
- pravac i ravnina su paralelni
- pravac leži u ravnini.

U nastavku bit će razmotreni svi slučajevi na jednom primjeru. U svakom primjeru će biti korištena ista ravnina, a pravac će se mijenjati. Za prijmer može se uzeti ravnina razapeta trokutom ABC čije su koordinate vrhova A(1, 2, -3), B(1, 2, 3) i C(-1, -2, 1).
Sada možemo izračunati implicitni oblik jednadžbe ravnine na temelju jedne točke i normale. Kao točku ravnine možemo uzeti npr. točku A(1, 2, -3), a za računanje normale vektore AB i AC. $$\eqalign{ & A(1,2, - 3),\overrightarrow {AB} = (0,0,6),\overrightarrow {AC} = ( - 2, - 4,4) \cr & \overrightarrow {AB} \times \overrightarrow {AC} = (24, - 12,0) \cr & {1 \over {12}}(24, - 12,0) = (2, - 1,0) = \overrightarrow n \cr & Ax + By + Cz + D = 0 \cr & 2 \cdot 1 + ( - 1) \cdot 2 + 0 \cdot - 3 + D = 0 \cr & 0 + D = 0 \cr & D = 0 \cr & \pi ...2x - y = 0 \cr} $$ Implicitni oblik jednadžbe ravnine razapete trokutom ABC: 2x - y = 0

Ovo je zapravo specijalni položaj ravnine s obzirom na koordinatni sustav, jer su koeficijenti C i D iz implicitnog oblika jednadžbe ravnine jednaki 0. Ovo je ravnina koja sadrži z-os - paralelna je sa z-osi odnosno okomita je na xy-ravninu, i prolazi kroz ishodište koordinatnog sustava.

Pravac i ravnina se sijeku

Da bismo pokazali ovaj slučaj, možemo uzeti vrlo jednostavan primjer: neka točka A trokuta ABC bude neka točka na pravcu, a vektor smjera neka bude normala ravnine 2x - y = 0. Odmah možemo zaključiti da je u tom slučaju A(1, 2, -3) točka presjeka pravca i ravnine. $$\eqalign{ & A(1,2, - 3),\overrightarrow s = \overrightarrow {{n_\pi }} = (2, - 1,0) \cr & \overrightarrow r = \overrightarrow {{r_0}} + t\overrightarrow s \cr & \overrightarrow r = (1,2, - 3) + t(2, - 1,0) \cr & p...\left\{ \matrix{ x = 1 + 2t \hfill \cr y = 2 - t \hfill \cr z = - 3 \hfill \cr} \right. \cr & \pi ...2x - y = 0 \cr & 2(1 + 2t) - (2 - t) = 0 \cr & 2 + 2t - 2 + t = 0 \cr & 3t = 0 \cr & t = 0 \cr} $$ Dobili smo da za t=0 pravac p siječe ravninu π, odnosno kad t=0 uvrstimo u parametarske jednadžbe pravca dobivamo da je točka presjeka T(1,2,-3). To je zapravo točka A trokuta ABC, što je bilo očekivano.
Dakle, ovo je slučaj kad pravac i ravnina nisu paralelni te se sijeku u jedinstvenoj točki.

Pravac i ravnina su paralelni

Ovo je slučaj kad je pravac paralelan s ravninom i ne leži u njoj. Možemo odmah zaključiti da u tom slučaju točka presjeka ne postoji, no u nastavku ćemo vidjeti što se događa kod rješavanja jednadžbe u takvom slučaju.
Za radijvektor neke točke (r0) na pravcu možemo uzeti zbroj radijvektora točke A trokuta ABC i normale ravnine π, tako da točka r0 sigurno bude odmaknuta od ravnine odnosno da ne leži u njoj.
Za vektor smjera pravca možemo uzeti neki vektor λAB+μAC (iako možemo jednostavno uzeti samo npr. vektor AB) tako da imamo vektor smjera koji je paralelan s ravninom π. $$\eqalign{ & \overrightarrow {{r_A}} = (1,2 - 3),\overrightarrow {{n_\pi }} = (2, - 1,0) \cr & \overrightarrow {{r_0}} = \overrightarrow {{r_A}} + \overrightarrow {{n_\pi }} = (1,2, - 3) + (2, - 1,0) = (3,1, - 3) \cr & \overrightarrow {AB} + \overrightarrow {AC} = (0,0,6) + ( - 2, - 4,4) = ( - 2, - 4,10) \cr & \overrightarrow s = {1 \over 2}\left( {\overrightarrow {AB} + \overrightarrow {AC} } \right) = ( - 1, - 2,5) \cr & \overrightarrow r = \overrightarrow {{r_0}} + t\overrightarrow s \cr & \overrightarrow r = (3,1, - 3) + t( - 1, - 2,5) \cr & p...\left\{ \matrix{ x = 3 - t \hfill \cr y = 1 - 2t \hfill \cr z = - 3 + 5t \hfill \cr} \right. \cr & \pi ...2x - y = 0 \cr & 2(3 - t) - (1 - 2t) = 0 \cr & 6 - 2t - 1 + 2t = 0 \cr & 0 = - 5 \cr} $$ Kod rješavanja jednadžbe dobili smo 0 = -5 što samo po sebi govori da rješenje ne postoji odnosno da pravac i ravnina nemaju točku presjeka.

Pravac leži u ravnini

Ovo je slučaj kad je pravac paralelan s ravninom i leži u njoj. Možemo odmah zaključiti da u tom slučaju pravac siječe ravninu u beskonačno mnogo točaka. U nastavku ćemo vidjeti što se događa kod rješavanja jednadžbe u takvom slučaju. Za radijvektor neke točke (r0) na pravcu možemo uzeti npr. radijvektor točke A (ra) trokuta ABC, tako da je točka r0 sigurno dio ravnine π odnosno da leži u njoj (iako možemo uzeti bilo koju točku rt = ra + λAB + μAC).
Za vektor smjera pravca možemo uzeti neki vektor λAB+μAC (iako možemo jednostavno uzeti samo npr. vektor AB) tako da imamo vektor smjera koji je paralelan s ravninom π. $$\eqalign{ & \overrightarrow {{r_0}} = \overrightarrow {{r_A}} = (1,2 - 3) \cr & \overrightarrow {AB} + \overrightarrow {AC} = (0,0,6) + ( - 2, - 4,4) = ( - 2, - 4,10) \cr & \overrightarrow s = {1 \over 2}\left( {\overrightarrow {AB} + \overrightarrow {AC} } \right) = ( - 1, - 2,5) \cr & \overrightarrow r = \overrightarrow {{r_0}} + t\overrightarrow s \cr & \overrightarrow r = (1,2, - 3) + t( - 1, - 2,5) \cr & p...\left\{ \matrix{ x = 1 - t \hfill \cr y = 2 - 2t \hfill \cr z = - 3 + 5t \hfill \cr} \right. \cr & \pi ...2x - y = 0 \cr & 2(1 - t) - (2 - 2t) = 0 \cr & 2 - 2t - 2 + 2t = 0 \cr & 0 = 0 \cr} $$ Kod rješavanja jednadžbe dobili smo 0 = 0 što znači da rješenje nije jedinstveno odnosno da pravac siječe ravninu u beskonačno mnogo točaka. Zapravo, to znači da je pravac paralelan s ravninom i leži u njoj.

Naime, nakon razmotrena sva tri slučaja u kojima se mogu zateći pravac i ravnina možemo zaključiti da se u Ray tracing-u uzima u obzir samo slučaj kad je presjek pravca i ravnine jednoznačno definiran odnosno kad postoji samo jedna točka u kojoj pravac siječe ravninu (slučaj kad pravac nije paralelan s ravninom), jer u ostalim slučajevima ili presjek ne postoji ili nije jednoznačno definiran.

Provjera je li presjek unutar trokuta

Provjeru je li presjek unutar trokuta možemo provesti na više načina: računanjem baricentričnih koordinata, površine trokuta, ili linearne kombinacije dvaju vektora.

Linearna kombinacija dvaju vektora

Ako su vrhovi trokuta ABC, možemo uzeti npr. vektor AB i AC, i njihovom linearnom kombinacijom dobiti vektor AT, gdje je T točka presjeka pravca i ravnine zadanom vrhovima tog trokuta. Pridružimo vektorima AB i AC skalare λ i μ. Da bi točka bila unutar trokuta mora vrijediti 0 <= λ,μ <= 1; λ + μ <= 1.
Dokaz: $$\eqalign{ & \lambda \overrightarrow {AB} + (1 - \lambda )\overrightarrow {AC} \cr & = \overrightarrow {AC} + \lambda \overrightarrow {CB} \cr & = \overrightarrow {AC} + \lambda (\overrightarrow {CA} + \overrightarrow {AB} ) \cr & = \overrightarrow {AC} + \lambda ( - \overrightarrow {AC} + \overrightarrow {AB} ) \cr & = \overrightarrow {AC} - \lambda \overrightarrow {AC} + \lambda \overrightarrow {AB} \cr & = (1 - \lambda )\overrightarrow {AC} + \lambda \overrightarrow {AB} \cr & = \lambda \overrightarrow {AB} + (1 - \lambda )\overrightarrow {AC} \cr} $$

Površine trokuta

Neka je zadan trokut ABC i točka T. Neka je T točka presjeka pravca i ravnine zadane vrhovima trokuta ABC. Tokča T je unutar trokuta ako je suma površina trokuta ABT, BCT i CAT jednaka površini trokuta ABC.
Dokaz:

Ishodište i vektor smjera zrake

Ako virtualna kamera stoji u ishodištu koordinatnog sustava, a transformacije nad kamerom su zapravo transformacije nad objektima, onda je ishodište svake zrake točka T(0, 0, 0), a vektor smjera sljedeći: $$f\left( {{p_x},{p_y}} \right) = \left( {{x_{\min }} + {{{x_{\max }} - {x_{\min }}} \over w}{p_x}, {y_{\max }} - {{{y_{\max }} - {y_{\min }}} \over h}{p_y}, - d} \right)$$ gdje je px zaslonska koordinata piksela na platnu (canvasu) s obzirom na x os; py zaslonska koordinata piksela na platnu s obzirom na y os; xmin najmanja, a xmax najveća x koordinata koju vidi kamera; ymin najmanja, a ymax najveća y koordinata koju vidi kamera; w (width) širina platna u pikselima; h (height) visina platna u pikselima; d (distance) udaljenost ravnine projiciranja zraka od kamere.

Optimizacije ray tracing algoritma

U svom najjednostavnijem obliku, ray tracer treba za svaki piksel za svaki trokut u sceni testirati presjek zrake i trokuta, i onda samo uzeti u obzir najbliži presjek. To je dosta neefikasno, jer većina testova prolazi neuspješno (ne postoji presjek zrake i trokuta) i testiranje takvih slučajeva je gubitak vremena. Kao posljedica toga, nastale su razne optimizacijske metode koje pomažu ubrzati rad ray tracing algoritma. Neke od njih se svode na smanjenje broja primarnih zraka, dok druge na brže pronalaženje presjeka zrake i trokuta.

Metode koje ubrzavaju ray tracing algoritam smanjenjem broja primarnih zraka narušavaju kvalitetu iscrtane slike jer njihova osnovna ideja je da se ne računaju zrake za svaki piksel, pa se oni neizračunati pikseli interpoliraju sa pikselima koji ga okružuju. Takve metode daju brz, ali ne i precizan rezultat.

Metode koje se svode na brže pronalaženje presjeka zrake i trokuta ubrzavaju ray tracing algoritam bez narušavanja kvalitete iscrtane slike. Jedna od metoda je korištenje jednostavnih objekata kao graničnih volumena (eng. bounding volumes; BV's), npr. kuboida paralelnih s koordinatnim osima. Kako granični volumen u potpunosti ograđuje objekt, najprije možemo izračunati presjek zrake s jednostavnijim graničnim volumenom (BV-om) i samo ako zraka presijeca BV nastaviti traženje presejka s originalnim objektom.
Druga metoda za ograničavanje skupa objekata za koje se treba računati presjek s danom zrakom jest podijeliti prostor na jednake segmente i unaprijed odrediti koji se objekti nalaze u svakom od segmenata. Kod praćenja zrake treba odrediti kroz koje segmente prostora zraka prolazi i tražiti presjek zrake samo s onim objektima koji se nalaze unutar odgovarajućih segmenata.

Osim spomenutih, postoji još mnogo drugih metoda za optimizaciju ray tracing algoritma. Spomenute metode se ne moraju koristiti isključivo, već se mogu kombinirati i na taj način ubrzati ray tracing algoritam kroz više različitih aspekata.

Literatura

[1] M. Pintera, „Iscrtavanje metodom praćenja zrake korištenjem paralelne obrade kod suvremenih grafičkih procesora“, Fakultet organizacije i informatike, Varaždin, 2011.
[2] I. Hip, „Geometrijsko modeliranje, Metode iscrtavanja“. Pristupljeno: pros. 30, 2019. [Na internetu]. Dostupno na: https://elf.foi.hr/pluginfile.php/15241/mod_resource/content/4/RG-P05-modeliranje-iscrtavanje.pdf.
[3] B. Divjak, „Klasična algebra vektora“. Pristupljeno: pros. 30, 2019. [Na internetu]. Dostupno na: https://elfarchive1718.foi.hr/pluginfile.php/5115/mod_page/content/43/OPM1.pdf.
[4] B. Divjak, „Analitička geometrija prostora“. Pristupljeno: pros. 30, 2019. [Na internetu]. Dostupno na: https://elfarchive1718.foi.hr/pluginfile.php/5110/mod_page/content/39/OPM2.pdf.
[5] „Two Optimization Methods for Raytracing“. Pristupljeno: pros. 30, 2019. [Na internetu]. Dostupno na: https://ws.iat.sfu.ca/papers/rtopt.pdf.