Geometrie/Raytracing

Z Wikiknih
Skočit na navigaci Skočit na vyhledávání

Ray-tracing[editovat]

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[editovat]

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í:

  • – průsečík
  • – další průsečík odraženého paprsku
  • – další průsečík propuštěného paprsku
  • – globální koeficient odrazivosti (reflexe)
  • – 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í

,

kde a jsou body ležící na této přímce a je parametr. Trojúhelník určený body , a můžeme také popsat parametrickou rovnicí. Stačí si uvědomit, že nedegerovaný trojúhelník (pro nedegerovaný trojúhelník musí platit, že body , , 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ů , a

.

S tímto tvarem by se nám ale špatně počítalo, proto si z podmínky vyjádříme např. . Pro bod trojúhelníku pak musí platit

Označíme-li navíc a , můžeme psát

,

kde , .

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 a normálovým vektorem . Pro libovolný bod () platí, že vektory a jsou kolmé. Platí tedy

.

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

,

odtud

.

Průsečík paprsku s rovinou je proto roven

.

Je-li trojúhelník určen body , a , můžeme normálový vektor roviny zapsat ve tvaru

.

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 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ěmito souřadnicemi jsou parametry a v rovnici (\ref{param_rce_troj})), pak jsou-li splněny podmínky

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

Dále pro libovolný vektor roviny s normálovým vektorem definujeme operátor jako vektorový součin vektorů a . Platí tedy . Tento operátor je zřejmě lineární, tzn., že platí

pro všechny skaláry , a vektory , . Z vlastností vektorového součinu navíc plyne, že , neboli

.

Identity a využijeme k výpočtu rovnice , kde , která vznikla z rovnice (\ref{param_rce_troj}) dosazením za . Vynásobíme-li ji skalárně vektorem dostaneme , tzn. . Odtud můžeme vyjádřit . Analogicky získáme skalárním vynásobením rovnice vektorem parametr . Dostaneme tedy

Algoritmizace[editovat]

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 (, ).
    2. Lomený paprsek Sleduj_paprsek (, ).
  6. Paprsek má barvu danou součtem barvy od osvětlení, odraženého paprsku a lomeného paprsku .

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[editovat]

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.