Rekurzívny raytracing

Priesečník lúča s objektom nadobúda určitú farbu na základe vlastností daného povrchu alebo uhla pohľadu kamery a uhla dopadu lúča. K výslednej farbe prispieva aj osvetlenie alebo prenos farby z iného objektu, z ktorého sa lúč už predtým odrazil.

Raytracing pracuje rekurzívne, jeho fungovanie sme už opísali v predchádzajúcom článku (Raytracing – podstata a pipeline). Teraz sa pozrieme bližšie na rekurziu.

Prvý lúč sa vyšle z miesta pozorovateľa (kamery) cez pixel priemetne smerom do scény. tento lúč si zaznamenávame do dátovej štruktúry ako koreň stromu. Ďalej si zaznamenáme prvý prienik tohto lúča s objektom v scéne (identifikátor objektu). Na obrázku hore prvotný lúč pretne ako prvý kváder.

V mieste priesečníku vzniknú dva lúče, jeden odrazený lúč (reflected ray) a druhý lomený lúč, ktorý sa láme smerom do objektu (refracted ray). Rovnice týchto dvoch lúčov zaznamenáme do dátovej štruktúry. V mieste prieniku ešte vznikne tieňový lúč (shadow ray), ktorý smeruje priamo do svetelného zdroja. Ak tento lúč pretne nejaký objekt, znamená to, že daný prvý prienik je v tieni. Ak máme na scéne viacero svetelných zdrojov, máme aj viacero tieňových lúčov.

Odrazený a lomený lúč následne ďalej sledujeme a postupujeme presne tak isto ako pri prvotnom lúči. Tu teda máme rekurziu, ktorú opakujeme ľubovoľne veľakrát, resp. skončíme, ak je príspevok farby pre daný pixel po danej rekurzii už iba veľmi malý. Ak niektorý z lúčov už neprechádza iným objektom, pridáme pre neho farbu pozadia. Farba pre pixel sa teda skladá z viacerých zložiek, ktoré sa v rekurzii spätne poskladajú podľa vlastností všetkých povrchov, ktorými prešli všetky lúče v danej rekurzii.

Vstupom pri raytracingu je teda lúč a výstupom je farba pixla. Raytracing opakujeme pre každý pixel výsledného obrazu. Raytracing zabezpečuje ľahké odstránenie neviditeľných stien (v porovnaní s primitívnou metódou rasterizácie objektov), takisto vieme rátať tiene, lesklé materiály, odrazy,.. Avšak raytracing nezvláda dobre globálnu ilumináciu, pretože pre ňu by bolo potrebné veľké množstvo lúčov a odrazov.

Aproximácie raytracingu

Problém s globálnou ilumináciou riešime ambientným (konštantným) svetlom, ktoré bez ohľadu na iné svetlá a objekty v scéne, resp vlastnosti daného objektu, osvetlí každú plochu každého objektu rovnakým množstvom svetla.

Aproximuje sa taktiež počet svetiel. Tých máme konečný počet, zatiaľčo v porovnaní s realitou by napríklad aj už iba samotná jedna neónová lampa mala byť reprezentovaná v podstate nekonečným počtom bodových svetiel.

Prirodzene aproximujeme aj farbu. Zvyčajne používame tri farebné zložky červenú, zelenú a modrú (R,G,B) s konečným počtom možných hodnôt (napr. 0 až 255) namiesto celého reálneho farebného spektra.

Pri raytracingu chceme algoritmus čím viac zefektívniť, do úvahy prichádzajú nasledujúce možnosti:
– nemusíme rátať priesečník objektu a lúča, ktorý ide jasne mimo daného objektu (napr. úplne opačným smerom)
– lúč, ktorý sa iba málo odchyľuje od iného už vyrátaného lúča, môžeme aproximovať a tak urýchliť výpočet

Grid (mriežka)

Scénu si môžeme ľahko rozdeliť do trojrozmernej mriežky, ktorá nám umožní urýchlenie rátania, resp. vynechanie zbytočných výpočtov. Prienik lúča s objektom sa bude rátať iba ak lúč prechádza bunkou, v ktorej sa objekt nachádza. Pri masívnych scénach tak môžeme ušetriť aj 99 percent rátaní prienikov s objektami, ktoré by aj tak vyšli nulové. Bunky, cez ktoré lúč prechádza, nájdeme napríklad Bresenhamovým algoritmom, alebo 3D-DDA algoritmom. Objekty v každej bunke budú indexované, aby sme k nim mohli ľahšie pristupovať. Prienik tak budeme rátať iba s objektami, ktoré majú indexy buniek, cez ktoré lúč prechádza.

Pri tvorení tejto mriežky môžeme mať problém s určením jej rozlíšenia, tj. aký rozmer budú mať jednotlivé bunky. Ak je scéna jednotná, čo sa veľkosti objektov týka, tak nie je problém nejaký vhodný rozmer mriežky určiť. Avšak ak máme komplexnejšiu scénu, kde máme aj veľké, aj malé objekty, rádovo sa odlišujúce veľkosťou (napríklad prípad čajníka uprostred štadiónu), musíme tomu prispôsobiť aj mriežku. Napríklad môžeme mať novú mriežku vnútri jednej bunky prvej mriežky. Nová mriežka nemusí byť presne vnútri bunky, ale môže byť prispôsobená podmienkam konkrétnej scény. Pri tvorení mriežky môžeme využiť aj Octree, tj každá bunka sa podľa potreby delí na osem nových menších buniek.

Bounding volumes (ohraničujúce objemy)

Pre zjednodušenie rátania prienikov môžeme použiť aj ohraničujúce objemy, teda namiesto zložitého objektu s tisíckami trojuholníkov budeme uvažovať iba šesťstranný kváder, ktorý zložitejší objekt obsahuje celý vo svojom vnútri. Ako hraničný objem môžeme použiť napríklad aj kružnicu, guľu, kocku, prípadne iné primitívne objekty. Ak ako ohraničujúci objekt použijeme AABB box (axis-alligned bounding box), rátanie sa nám ešte viac zjednoduší, avšak tento AABB box nemusí vždy úplne vyhovovať pre daný objekt (napríklad ak je objekt úzky a dlhý a natočený mimo všetkých troch osí).

Ohraničujúcimi objemami môžeme scénu hierarchicky rozdeliť. Najprv všetky objekty v scéne obalíme do jedného veľkého objemu, následne objekty rozdelíme vhodne do dvoch skupín, ktoré obalíme do dvoch samostatných menších objemov, a tak ďalej, až bude každý objekt v samostatnom ohraničujúcom objeme. Na organizáciu týchto objemov môžeme využiť napríklad binárny strom. Pri zisťovaní prieniku stačí, ak najprv zistím, či lúč má prienik s koreňom stromu, ak nemá, nemusím ďalej rátať, ak má, rátam prienik dvoch synov daného rodiča, a takto postupujeme nižšie a nižšie v strome.

Problémy môžu nastať pri pridávaní nového objektu do scény, kedy musíme buď vybudovať celú štruktúru odznovu, alebo pridať objekt do štruktúry rozšírením niektorej obálky, resp. pridaním novej, resp. rozšírením stromu pridaním listu.

BSP a KD trees (BSP a KD stromy)

Priestor môžeme hierarchicky deliť aj vhodnými rovinami, tj každou rovinou sa daný priestor rozdelí na dva podpriestory. Takéto delenie sa nazýva Binary Space Partition. Roviny, ktorými priestor delíme sú často určené hraničnými rovinami objektov v scéne. Toto delenie sa často používa pri zisťovaní viditeľnosti, napríklad v hrách.

KD stromy sú zúžením metódy BSP. Pri KD stromoch (v skutočnosti k-D tree, ako skratka pre k-dimensional) sa priestor delí rovinami kolmými na osi x,y,z. Rátanie s nimi je tak omnoho jednoduchšie. Vyhľadávanie v nich je ekvivalentné vyhľadávaniu v hierarchických štruktúrach. Priestor delíme buď na polovicu, alebo ho delíme tak, aby v každej novej časti bol rovnaký počet objektov.

Directional Partitioning (delenie v smeroch)

Priestor si môžeme rozdeliť aj podľa smerov. Tento prístup použijeme v prípade, že máme mnoho lúčov vychádzajúcich z jedného miesta.