Tomuto článku alebo sekcii chýbajú odkazy na spoľahlivé zdroje, môže preto obsahovať informácie, ktoré je potrebné ešte overiť. Pomôžte Wikipédii a doplňte do článku citácie, odkazy na spoľahlivé zdroje.

Path tracing je fotorealistický 3D vykresľovací algoritmus, ktorý využíva integrovanie metódou Monte Carlo na výpočet intenzity svetla, ktoré sa odrazí od jednotlivých bodov na povrchu objektu scény a dopadá do virtuálnej kamery. Algoritmus jednotlivo simuluje tok svetla na scéne, ktoré sa pohybujú smerom od svetla do kamery. Medzi jeho hlavné výhody patrí jeho fyzikálna vernosť, ktorá umožňuje zachytávať javy ako nepriame osvetlenie, mäkké tiene alebo kaustiky pod vodnou hladinou.

Práve pre jeho presnosť a nestrannosť sa dnes využíva ako referenčný algoritmus pri testovaní iných, rýchlejších algoritmov. Vykresľovanie kvalitných obrázkov pomocou path tracingu môže trvať niekoľko desiatok až stoviek hodín.

História

V roku 1986 James Kajiya predstavil zobrazovaciu rovnicu, popri ktorej zároveň publikoval aj algoritmus, ktorý odhaduje jej numerickú aproximáciu. O desať rokov neskôr Eric P. Lafortune priniesol niekoľko vylepšení, medzi ktoré patril aj algoritmus bidirectional path tracing.

V roku 2009 Austin Robinson z Nvidia prezentoval prvú komerčnú implementáciu algoritmu path tracing, ktorý beží na grafickej karte. Tá vo veľkej miere ovplyvnila ďalšie implementácie, ktorým pomohlo aj vyzretie technológií pre programovanie na GPU ako sú CUDA alebo OpenCL.

Opis

Zobrazovacia rovnica, ktorú publikoval Kajiya sa zdží troch zásad optiky: Princíp globálneho osvetlenia, Princíp ekvivalencie (odrazené svetlo je ekvivalentné vyžarovanému svetlu) a Princíp smerov (odrazené aj refraktované svetlo majú svoj smer).

V svete okolo nás, objekty sú viditeľné pre ich odrazivosť svetla. Z tohto hľadiska možno pozorovať, že sa objekty (aj odrazeným) svetlom osvetľujú navzájom. Z tohto jednoduchého pozorovania vychádzajú ďalšie dva princípy:

I. Pre danú uzavretú scénu, každý objekt na scéne musí vyžarovať svetlo na každý objekt.

II. Nie je žiadny rozdiel v správaní svetla, ktoré prichádza priamo od svetelného zdroja a svetla, ktoré je odrazené.

Teoretické pozadie

Algoritmus aproximuje radianciu, ktorá zo scény prichádza do kamery zo scény, teda tú ktorá je vyžarovaná priamo, aj tú, ktorú odrážajú osvetlené objekty v scéne. Pri odrazenom svetle z objektov na scéne do kamery je nutné uvažovať nielen svetlo, ktoré dopadá na ne priamo zo svetelného zdroja, ale aj to, ktoré ich osvetľuje po odraze zo scény. Preto je nutné najprv poznať zobrazovaciu rovnicu:

${\displaystyle L(\mathbf {x} ,\omega _{o})=L_{e}(\mathbf {x} ,\omega _{o})+\int _{H}L(r(\mathbf {x} ,\omega _{i}),-\omega _{i})\cdot f_{r}(\mathbf {x} ,\omega _{i}\rightarrow \omega _{o})\cdot cos(\theta _{i})\mathrm {d} \omega _{i}.}$

Ktorá hovorí o tom, že pre daný bod x na scéne v smere ${\displaystyle \omega _{o}}$ je súčet radiance, ktorá je z bodu x vyžarovaná priamo (v prípade svetelného) zdroja a integrálu prichádzajúcej radiancie z celej hemisféry funkcie BRDF doplnenú o faktor ${\displaystyle frac{cos(\theta _{i})}{\pi }}$. Výraz ${\displaystyle r(x,\omega _{i})}$ vyjadruje presečník z bodu x v smere ${\displaystyle \omega _{i}}$ so scénou a ${\displaystyle L(r(x,\omega _{i}),-\omega _{i})}$ je prichádzajúca radiancia z bodu ${\displaystyle r(x,\omega _{i})}$ do bodu x.

V komplikovanejších scénach však nie je možné v krátkom čase vypočítať priestorový integrál analyticky. V tomto prípade je nutné použiť numerickú metódu pre výpočet integrálu. V prípade algoritmu path tracing sa využíva metóda Monte Carlo, pre ktorý príslušný estimátor bude mať tvar:

${\displaystyle {\hat {L}}(\mathbf {x} ,\omega _{o})=L_{e}(\mathbf {x} ,\omega _{o})+{\frac {L(r(\mathbf {x} ,\omega _{i}),-\omega _{i})\cdot f_{r}(\mathbf {x} ,\omega _{i}\rightarrow \omega _{o})\cdot cos(\theta _{i})}{p(\omega _{i})}},}$

Kde ${\displaystyle \omega _{i}}$ je náhodne vygenerovaný smer a ${\displaystyle p(\omega _{i})}$ je pravdepodobnosť, s akou bol smer ${\displaystyle \omega _{i}}$ vygenerovaný.

Popis algoritmu

Pre jednoduchosť algoritmus počíta s kamerou ako s bodom. Odtiaľ cez jednotlivé pixely vedie lúče a skúša, či sa od scény neodrazí do svetla. Ak áno, vypočíta príspevok v danom bode a vráti sa naspäť cez odrazené miesta postupne až ku kamere, pričom v odrazených miestach eliminuje intenzitu svetla v závislosti na odrazivosti konkrétneho bodu na scéne.

Prvý krok algoritmu, pri ktorom vedie lúč smerom od kamery na scénu

1. Na začiatku nech x je pozícia kamery
2. Zvolí sa smer ω cez pixel na obrazovke smerom od kamery do scény
3. Nájde sa priesečník y smeru ω so scénou

Ak je y súčasť svetla, k medzivýsledku pripočíta intenzitu svetla, ktoré je z bodu y vyžarované v smere -ω (z bodu y do x)

Ak y neexistuje (nenájde priesečník), vráti sa a pripočíta sa farba okolia

Ak y je bod na scéne s nenulovou odrazivosťou, pokračuje s bodom y ako s bodom x, odtiaľ sa vygeneruje nový smer ω (na základe distribučnej funkcie) a pokračuje sa v bode 3 (rekurzívne), kde sa hľadá nový priesečník. Vypočítaný príspevok po odraze pripočíta k medzivýsledku.

Uvedený úsek algoritmu je pre 1 pixel. Výsledná scéna vznikne, ak sa spustí niekoľkokrát pre každý pixel a v rámci jedného pixelu sa hodnoty spriemerujú. Kvalita obrázku priamo závisí na počte opakovaní algoritmu na jednom pixeli.

Pseudokód

function renderImage() 
{
   for all pixels
   {
      Color pixelCol = (0,0,0);
      for k = 1 to N
      {
         wk := náhodný smer cez k-tý pixel
         pixelCol += getLi(camPos,wk)
      }
   }
}

getLi(x, w)
{
   Color thrput = (1,1,1)
   Color accum  = (0,0,0)
   while(1)
   {
      hit = NearestIntersect(x, w)
      if no intersection
         return accum + thrput * bgRadiance(x, w)
      if isOnLightSource(hit)
         accum += thrput * Le(hit.pos, -w)
      ρ = reflectance(hit.pos, -w)
      if rand() < ρ // ruská ruleta - pravdepodobnosť prežitia
      {
         wi := SampleDir(hit)
         thrput *= fr(hit.pos, wi, -w) * dot(hit.n, wi) / (ρ*pdf(wi))
         x := hit.pos
         w := wi
      }
      else // absorb
         break;
   }
return accum;
}

Výber náhodného smeru

Algoritmus ako je uvedený vyššie používa metódu SampleDir() o ktorej vieme len to, že vygeneruje nejaký smer ${\displaystyle \omega _{i}}$ s nejakou pravdepodobnosťou ${\displaystyle p(\omega _{i})}$. Jedno z možných riešení je, že metóda bude vyberať smery uniformne z celej hemisféry, ktorá sa však ukazuje ako korektná, ale z výsledných obrázkov šum mizne veľmi pomaly. V praxi je výhodnejšie vyberať prednostne tie smery, kde očakávame vyšší príspevok svetla.

Vzorkovanie podľa BRDF

V závislosti na charakteristike materiálu a vstupnom smere, vygenerujeme nový smer s hustotou podľa funkcie odrazivosti. Napríklad v prípade zrkadlovehó povrchu bude výsledný smer zakaždým odrazený v smere od kolmice, v prípade ideálne Lambertovského povrchu, bude vzorkovanie prebiehať s hustotou ${\displaystyle {\frac {cos(\theta )}{\pi }}}$(tzv. cosínové vzorkovanie), kde ${\displaystyle \theta }$ je uhol medzi vygenerovaným smerom a normálou plochy v bode x.

Vzorkovanie svetla

Ak sú svetelné zdroje príliš malé, alebo dokonca sú v scéne vyjadrené ako matematický bod (nemajú nikdy priesečník s náhodne vygenerovaným smerom), môže trvať veľmi dlho, kým algoritmus vygeneruje taký smer, že bude mať s nimi priesečník. V tomto prípade je výhodné odhadovať zvlášť priame a zvlášť nepriame osvetlenie. Kým stratégia pre odhad nepriameho osvetlenia môže ostať napr. vzorkovaním podľa BRDF, priame osvetlenie algoritmus odhadne zvlášť vygenerovaným smerom zo svetelného zdroja.

Kombinované vzorkovanie

Predstavme si prípad, kde materiál je „takmer zrkadlový“ a svetlo s veľmi veľkou plochou. Ak budeme vzorkovať z plochy svetla, je veľmi nízka pravepodobnosť, že sa trafíme práve do úzkeho intervalu smerov ${\displaystyle U(\omega _{i})}$, ktorý je materiál schopný odraziť v smere ${\displaystyle \omega _{o}}$ s nejakou nezanedbateľnou radian- ciou. Ak budeme mať ešte silnejší predpoklad, a to že materiál je „dokonale zrkadlový“, budeme mať len jeden prípustný smer ${\displaystyle \omega _{o}}$. Ten však nami zvolená technika nikdy nevygeneruje. V týchto prípadoch bude lepšie použiť vzorkovanie podľa BRDF.

Naopak, predpokladajme, že materiál je „dokonale difúzny“ a svetlo s veľmi malou plochou. Ak budeme vzorkovať náhodne smery z celej hemisféry, opäť dostávame veľmi nízku pravdepodobnosť, že trafíme zdroj svetla. Aj v tomto prípade môžeme mať silnejší predpoklad, a to keď svetelný zdroj bude zanedbateľne malý – môžeme ho zjednodušit’ až na bodový svetelný zdroj. V tomto prípade technika vzorkovania nikdy nevygeneruje smer, kde sa trafí práve do bodu, kde je umiestnené svetlo, preto bude lepšie použiť techniku z prvého prípadu.

Oba prípady môžu nastať dokonca v rámci jednej scény. Metóda vyrovnanej heuristiky využíva obe metódy vzorkovania naraz a do výsledku dáva ich súčet upravený o váhu s akou pravdepodobnosťou by boli vygenerované tou druhou metódou.

Majme smer ${\displaystyle \omega _{l}}$ ktorý bol vygenerovaný metódou vzorkovania svetla, smer ${\displaystyle \omega _{f}}$, ktorý bol vygenerovaný metódou vzorkovania podľa BRDF. Pravdepodobnosť ${\displaystyle p_{l}(\omega _{l})}$ bude príslušná pravdepodobnosť z prvej metódy, ${\displaystyle p_{f}(\omega _{f})}$ príslušná pravdepodobnosť pre metódu vzorkovania podľa BRDF. Pri tejto metóde vzorkovania potrebujeme ďalšie dve hodnoty a to, aká by bola pravdepodobnosť, keby sme smery ${\displaystyle \omega _{l}}$ a ${\displaystyle \omega _{f}}$ vygenerovali v druhej stratégií. Formálne ${\displaystyle p_f}$Zdroj:
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.