Geometrie/Raytracing

Ray-tracing

Jedná se o vysoce výpočetně náročnou metodu počítačové vizualizace, pomocí které lze dosáhnout velmi realistického zobrazení modelu. Spočívá v postupném stopování paprsků odrážených modelem směrem k uživateli. Umožňuje zobrazení jevů, pomocí jiných technik vůbec, či jen stěží dosažitelných, jako jsou např. odrazy a odlesky objektů, lom světla v objektech, atd.

Na začátku máme:

• Popis 3D scény skládající se z
  1. objektů (pozice, tvar, barva a další vlastnosti materiálu)
  2. světelných zdrojů (pozice, barva)
  3. (případně: barva pozadí scény, vlastnosti prostředí)
• Pozici pozorovatele

Sledujeme paprsky, které se šíří od světelných zdrojů do scény. Některé paprsky zasáhnou objekty, kde se podle jejich vlastností lomí, odrážejí a rozptylují. Obraz scény tvoří paprsky dopadlé na projekční plochu.

Tato metoda zahrnuje efekty vznikající vzájemnou interakcí objektů ve scéně (tj. například odrazy ostatních těles na povrchu lesklého objektu a lom světla při průchodu průhledným tělesem). Dokáže určit stíny vržené různými tělesy (tyto stíny jsou však ostře ohraničeny). Protože je nereálné sledovat všechny paprsky ze zdrojů světla, postupujeme v praxi naopak. Paprsek je sledován zpětně, tzn. ve směru od pozorovatele. Projekční paprsky vysíláme přes pixely obrazu scény. Hledáme, co je vidět v daném pixelu, jakou světelnou energii paprsek přináší.

Typy paprsků:

• Primární paprsek – vyslaný od pozorovatele scény.
• Sekundární paprsek – vzniká odrazem nebo lomem paprsku.
• Stínový paprsek – vyslaný z místa dopadu paprsku na objekt ke zdrojům světla pro zjištění, leží-li ve stínu. Není-li objekt ve stínu, je pro něj vyhodnocen osvětlovací model. Zanedbává se jejich lom.

Popis

Diagram ilustruje algoritmus ray tracingu pro renderování obrázku.

Při sledování paprsků musíme vlastně hledat jejich průsečíky s objekty scény. Naivní algoritmus testuje navzájem každý paprsek s každým objektem scény (a se všemi polygony v každém objektu), což vede ke značně časově náročnému výpočtu. Každý průsečík paprsku s objektem generuje další dva paprsky + stínový paprsek. V každém takovém průsečíku je zapotřebí provést ty samé výpočty, je tedy vhodné využít pro implementaci ray-tracingu rekurzi.

Pro ukončení rekurze je možné použít následující kritéria:

1. paprsek narazí na difúzní povrch
2. je dosažena předem stanovená maximální hloubka rekurze
3. energie paprsku klesne pod určitý práh

V každém průsečíku P paprsku a objektu platí:

${\mathcal {I}}(P)=I_{local}(P)+I_{global}(P)=I_{local}(P)+k_{rg}I(P_{r})+k_{tg}I(P_{t})$

• $P$ – průsečík
• $P_{r}$ – další průsečík odraženého paprsku
• $P_{t}$ – další průsečík propuštěného paprsku
• $k_{rg}$ – globální koeficient odrazivosti (reflexe)
• $k_{tg}$ – globální koeficient propouštění (lomu, transmise, refrakce)

Rekurzivní charakter této rovnice potvrzuje vhodnost tohoto přístupu pro implementaci ray-tracingu. Pro reprezentaci hierarchie paprsků a průsečíků bývá použita stromová struktura.

Nevýhody ray-tracingu

• ostré stíny
• bodové zdroje světla
• zrcadla (lesklé plochy) sice odrážejí okolí, ale neodrážejí světlo do okolí, nejsou sekundárními zdroji světla
• při změně ve scéně (místo pozorovatele, nové světlo, nový objekt, odebrání něčeho, …) se musí vyhodnotit celá scéna
• není adaptivní, zobrazení probíhá se stejným vzorkováním, nezávisle na situaci ve scéně (velké monotónní plochy)

Urychlování ray-tracingu

Prostý ray-tracing je velmi náročný na čas, urychlovací metody ho mohou urychlit o jeden až dva řády.

Nejčastější urychlovací metody:

• Urychlení výpočtu průsečíků
  1. speciální funkce na výpočet průsečíků s každým typem objektu (pre testy potenciálních průsečíků před vlastními výpočty s tělesem)
  2. snížení počtu výpočtů průsečíků – obálky, hierarchie obálek – dělení scény (BSP, Octal-tree) – paměť překážek – koherence paprsků (válcové nebo kuželové obálky paprsků)
• Snížení počtu paprsků
  1. adaptivní antialiasing (zředěné vysílání paprsků, interpolace při malé změně)
  2. řízení hloubky rekurze (útlum intenzity paprsků při odrazech a lomech -> stupeň rekurze při útlumu pod daný limit)
• Svazky paprsků (svazek paprsků se vysílá jako jeden – kvalita)
• Distribuce výpočtů na dvě části (procesů, procesorů)

Reprezentace objektů

Objekty jsou v počítačové grafice zpravidla reprezentovány pomocí "množiny trojúhelníčků", které se snaží vystihnout jejich tvar. Pro metodu raytracing je proto mimo jiné potřeba vyřešit problém, jak získat průsečík paprsku s určitým trojúhelníkem.

Paprsek je zřejmě přímkou a trojúhelník chápeme jako množinu bodů v rovině, které leží uvnitř nebo na trojúhelníku v běžném smyslu.

Paprsek ${\mathcal {R}}$ je možno popsat (například) parametrickou rovnicí

${\mathcal {R}}:R(t)=R_{0}+t(R_{1}-R_{0})$,

kde $R_{0}$ a $R_{1}$ jsou body ležící na této přímce a $t\in \mathbb {R}$ je parametr. Trojúhelník ${\mathcal {T}}$ určený body $T_{0}$, $T_{1}$ a $T_{2}$ můžeme také popsat parametrickou rovnicí. Stačí si uvědomit, že nedegerovaný trojúhelník (pro nedegerovaný trojúhelník musí platit, že body $T_{0}$, $T_{1}$, $T_{2}$ jsou v obecné poloze; trojúhelník tedy nezdegeneruje do bodu nebo úsečky) je dvourozměrným simplexem, tzn., že body trojúhelníku leží v konvexním obalu bodů $T_{0}$, $T_{1}$ a $T_{2}$

${\mathcal {T}}(T_{0},T_{1},T_{2})=\left\{t_{0}T_{0}+t_{1}T_{1}+t_{2}T_{2};\sum _{i=0}^{2}t_{i}=1,t_{i}\geq 0\right\}$.

S tímto tvarem by se nám ale špatně počítalo, proto si z podmínky $\sum _{i=0}^{2}t_{i}=1$ vyjádříme např. $t_{0}$. Pro bod $T$ trojúhelníku pak musí platit

${\mathcal {T}}(t_{1},t_{2})=(1-t_{1}-t_{2})T_{0}+t_{1}T_{1}+t_{2}T_{2}=T_{0}+(T_{1}-T_{0})t_{1}+(T_{2}-T_{0})t_{2}.$

Označíme-li navíc ${\vec {u}}=T_{1}-T_{0}$ a ${\vec {v}}=T_{2}-T_{0}$, můžeme psát

${\mathcal {T}}(t_{1},t_{2})=T_{0}+t_{1}{\vec {u}}+t_{2}{\vec {v}}$,

kde $t_{1}+t_{2}\leq 1$, $t_{1},t_{2}\geq 0$.

Průnik paprsku a plochy

Nejprve si rozebereme obecnější úlohu, tzn. průnik paprsku s plochou. Nechť trojúhelník ${\mathcal {T}}$ leží v rovině $\varrho$, která je určená bodem $T_{0}$ a normálovým vektorem ${\vec {n}}$. Pro libovolný bod $X\in \varrho$ ($X\neq T_{0}$) platí, že vektory ${\overrightarrow {XT_{0}}}$ a ${\vec {n}}$ jsou kolmé. Platí tedy

$(X-T_{0})\cdot {\vec {n}}=0$.

Dosazením parametrické rovnice paprsku (\ref{param_rce_primky}) do rovnice (\ref{norm_rce_roviny}) získáme

$\left(R_{0}+t(R_{1}-R_{0})-T_{0}\right)\cdot {\vec {n}}=0$,

odtud

$t={\frac {(T_{0}-R_{0})\cdot {\vec {n}}}{(R_{1}-R_{0})\cdot {\vec {n}}}}$.

Průsečík $I$ paprsku s rovinou $\varrho$ je proto roven

$I=R\left({\frac {(T_{0}-R_{0})\cdot {\vec {n}}}{(R_{1}-R_{0})\cdot {\vec {n}}}}\right)$.

Je-li trojúhelník určen body $T_{0}$, $T_{1}$ a $T_{2}$, můžeme normálový vektor ${\vec {n}}$ roviny $\varrho$ zapsat ve tvaru

${\vec {n}}=(T_{1}-T_{0})\times (T_{2}-T_{0})={\vec {u}}\times {\vec {v}}$.

Průnik paprsku a trojúhelníku

Pro výpočet průsečíku paprsku s trojúhelníkem nejprve pomocí (\ref{I}) zjistíme průsečík $I$ tohoto paprsku s rovinou, ve které daný trojúhelník leží. Protne-li paprsek rovinu, pak zbývá určit, jestli průsečík leží v daném trojúhelníku či nikoliv. Pokud vyjádříme souřadnice tohoto průsečíku vzhledem k bodu $T_{0}$ (těmito souřadnicemi jsou parametry $t_{1}$ a $t_{2}$ v rovnici (\ref{param_rce_troj})), pak jsou-li splněny podmínky

$t_{1}+t_{2}\leq 1,t_{1}\geq 0,t_{2}\geq 0,$

průsečík leží v trojúhelníku.

Dále pro libovolný vektor ${\vec {u}}$ roviny $\varrho$ s normálovým vektorem ${\vec {n}}$ definujeme operátor $*$ jako vektorový součin vektorů ${\vec {n}}$ a ${\vec {u}}$. Platí tedy ${\vec {u}}^{*}={\vec {n}}\times {\vec {u}}$. Tento operátor je zřejmě lineární, tzn., že platí

$\left(a{\vec {u}}+b{\vec {v}}\right)^{*}=a{\vec {u}}^{*}+b{\vec {v}}^{*}$

pro všechny skaláry $a$, $b$ a vektory ${\vec {u}}$, ${\vec {v}}$. Z vlastností vektorového součinu navíc plyne, že ${\vec {a}}^{**}{\vec {a}}$, neboli

${\vec {a}}^{*}\cdot {\vec {a}}=0$.

Identity a využijeme k výpočtu rovnice ${\vec {w}}=t_{1}{\vec {u}}+t_{2}{\vec {v}}$, kde ${\vec {w}}=I-T_{0}$, která vznikla z rovnice (\ref{param_rce_troj}) dosazením $I$ za $T(t_{1},t_{2})$. Vynásobíme-li ji skalárně vektorem ${\vec {v}}^{*}$ dostaneme ${\vec {w}}\cdot {\vec {v}}^{*}=t_{1}{\vec {u}}\cdot {\vec {v}}^{*}+t_{2}{\vec {v}}\cdot {\vec {v}}^{*}$, tzn. ${\vec {w}}\cdot {\vec {v}}^{*}=t_{1}{\vec {u}}\cdot {\vec {v}}^{*}$. Odtud můžeme vyjádřit $t_{1}$. Analogicky získáme skalárním vynásobením rovnice vektorem ${\vec {u}}^{*}$ parametr $t_{2}$. Dostaneme tedy

$t_{1}={\frac {{\vec {w}}\cdot {\vec {v}}^{*}}{{\vec {u}}\cdot {\vec {v}}^{*}}}={\frac {{\vec {w}}\cdot \left({\vec {n}}\times {\vec {v}}\right)}{{\vec {u}}\cdot \left({\vec {n}}\times {\vec {v}}\right)}},$

$t_{2}={\frac {{\vec {w}}\cdot {\vec {u}}^{*}}{{\vec {v}}\cdot {\vec {u}}^{*}}}={\frac {{\vec {w}}\cdot \left({\vec {n}}\times {\vec {u}}\right)}{{\vec {v}}\cdot \left({\vec {n}}\times {\vec {u}}\right)}}.$

Algoritmizace

Rekurzivní funkce Sleduj_paprsek (R, H – hloubka rekurze):

1. Najdi průsečík P mezi R a objektem.
2. Jestliže P neexistuje – R jde mimo scénu – pixel má barvu pozadí.
3. Z P pošli ke zdrojům světla stínové paprsky.
4. Vyhodnoť součet osvětlovacích modelů v P pro nezakryté zdroje světla.
5. Pokud není překročena hloubka rekurse H, vyšli z P:
   1. Odražený sekundární paprsek voláním Sleduj_paprsek ($R_{r}$, $H+1$).
   2. Lomený paprsek Sleduj_paprsek ($R_{t}$, $H+1$).
6. Paprsek má barvu danou součtem barvy od osvětlení, odraženého paprsku $R_{r}$ a lomeného paprsku $R_{t}$.

Počet rekurzivních volání procedury Sleduj_paprsek je řízen parametrem H. Je-li roven 1, jedná se o tzv. ray-casting – vyhodnocují se pouze primární paprsky a jejich dopady na nejbližší objekt, při použití stínových paprsků jsou vyhodnoceny stíny. Pro zobrazení odrazů musí mít hodnotu minimálně 2 a pro řešení průhledných těles je minimum 3.

Autoři

Tento text vypracovali studenti Univerzity Palackého v Olomouci katedry Matematické informatiky jako součást zápočtového úkolu do předmětu Počítačová geometrie.