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

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:

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

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

$ℐ (P) = I_{l o c a l} (P) + I_{g l o b a l} (P) = I_{l o c a l} (P) + k_{r g} I (P_{r}) + k_{t g} 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_{r g}$ – globální koeficient odrazivosti (reflexe)
$k_{t g}$ – 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 $ℛ$ je možno popsat (například) parametrickou rovnicí

$ℛ : 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 ℝ$ je parametr. Trojúhelník $𝒯$ 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}$

$𝒯 (T_{0}, T_{1}, T_{2}) = {t_{0} T_{0} + t_{1} T_{1} + t_{2} T_{2}; \sum_{i = 0}^{2} t_{i} = 1, t_{i} \geq 0}$ .

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

$𝒯 (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

$𝒯 (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 $𝒯$ leží v rovině $ϱ$ , která je určená bodem $T_{0}$ a normálovým vektorem $\vec{n}$ . Pro libovolný bod $X \in ϱ$ ( $X \neq T_{0}$ ) platí, že vektory $\vec{X T_{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

$(R_{0} + t (R_{1} - R_{0}) - T_{0}) \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 $ϱ$ je proto roven

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

Je-li trojúhelník určen body $T_{0}$ , $T_{1}$ a $T_{2}$ , můžeme normálový vektor $\vec{n}$ roviny $ϱ$ 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 $ϱ$ 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í

${(a \vec{u} + b \vec{v})}^{*} = 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 (\vec{n} \times \vec{v})}{\vec{u} \cdot (\vec{n} \times \vec{v})},$

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

Algoritmizace

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

Najdi průsečík P mezi R a objektem.
Jestliže P neexistuje – R jde mimo scénu – pixel má barvu pozadí.
Z P pošli ke zdrojům světla stínové paprsky.
Vyhodnoť součet osvětlovacích modelů v P pro nezakryté zdroje světla.
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$ ).
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.

Geometrie/Raytracing

Obsah

Ray-tracing

Popis

Algoritmizace

Autoři

Navigační menu

Geometrie/Raytracing

Ray-tracing

Popis

Algoritmizace

Autoři

Navigační menu

Hledat