Zobrazení zdroje stránky Obousměrné sledování cest

'''Obousměrné sledování cest''' ([[Angličtina|anglicky]]: ''Bidirectional path tracing'') je vylepšení a zobecnění [[Algoritmus|algoritmu]] [[sledování cest]] a používá se ve [[3D grafika|3D grafice]] pro [[Syntéza|syntézu]] ([[render]]ování) 3D scén. Jeho principem je sledování cest fotonů oběma směry, jak od kamery ke světlům, tak od světel ke kameře.

==Historie==
Algoritmus BPT na sobě nezávisle objevili Eric Lafortune v roce 1993 a Yves D. Willems v roce 1994. Tento algoritmus má mnohem lepší výsledky než klasický "path tracing" a stal se základem pro kombinované techniky a další vývoj v této oblasti. 

==Motivace==
Klasický "path tracing" je fyzikálně správný a funkční, avšak v některých případech vyžaduje příliš dlouhé výpočty, aby vrátil věrný výsledek. Příklad: mějme ve scéně nějaký průhledný kulatý objekt, který funguje jako čočka a vytváří tzv. [[kaustika|kaustiku]]. Při path tracingu vrháme paprsek směrem od kamery, při každém průsečíku ho odrazíme náhodným směrem a sledujeme, kdy narazí na nějaké světlo. Paprsky směřující do kaustiky se náhodně rozptýlí, a pokud projdou kulatým objektem, rozptýlí se ještě více. Je velmi malá šance, že zasáhnou světlo, a proto v oblasti kaustiky bude velký šum.

Pokud bychom vrhali paprsky směrem od světla, většina z těch, kteří projdou kulatým objektem, se soustředí v kaustice a tím rychle vytvoří věrný obrázek. Je však malá šance, že by při dalším pohybu zasáhly kameru, jelikož její plocha bývá většinou velmi malá. Této technice se také říka '''light tracing''' (sledování světla). Jsou však příklady, např. spekulární složka lesklých povrchů, u které light tracing nemá dobré výsledky.

Dva výše zmíněné postupy mají své výhody i nevýhody. Obousměrné sledování cest kombinuje výhody obou způsobů ("směrů").

==Teoretické pozadí==
===Základní rovnice===
Při formulaci teorie path tracingu se příspěvek místa definuje jako integrál [[Zář|radiance]] v tomto místě, která pochází od světelného zdroje.
:<math>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, \omega_o) \cdot cos(\theta_i)\mathrm d \omega_i.</math>

Pro light tracing zkusme "otočit směr". Zaveďme si tzv. důležitost <math>W</math>, která bude pocházet od kamery a pro dané místo a směr bude určovat důležitost (příspěvek, váhu) daného místa pro konečnou barvu pixelu na kameře.
:<math>W(\mathbf x,\omega_o) = W_e(\mathbf x,\omega_o) + \int_H W(r(\mathbf x, \omega_i), -\omega_i) \cdot f_r(\mathbf x, \omega_o, \omega_i) \cdot cos(\theta_i)\mathrm d \omega_i.</math>

Vidíme, že obě rovnice si jsou podobné, popisují stejnou věc. Jsou definovány rekurzivně a obě mluví o cestách paprsků, tvořených body <math>\mathbf x</math>. První se stala motivací pro path gracing, ta druhá pro light tracing.

===Od směrů k cestám===
Nejdříve se pokusme dostat od rovnic výše k rovnicím, které počítají s cestami a s body na nich.
Místo bodu a směru zkusme uvažovat bod a k němu další bod scény, který je v daném směru nejblíže.
Při této úvaze můžeme přeformulovat značení radiance a [[BRDF]]:

:<math> L(x, x') \equiv L(x, \omega) </math>

:<math> f_r(x, x', x'') \equiv f_r(x', \omega_i, \omega_o) </math>

Stejným způsobem můžeme přeznačit i zobrazovací rovnici:

:<math> L(x', x'') =  L_e(x', x'') + \int_M L(x, x') \cdot f_r(x, x', x'') \cdot G(x, x') dM_x </math>

Kde ''M'' jsou všechny povrchy scény a <math>G(x, x') </math> zastupuje kosínové faktory z původní rovnice a zároveň viditelnost bodů:

:<math> G(x \leftrightarrow x') = V(x \leftrightarrow x') \cdot \frac{|\cos \theta_0 \cos \theta_i'|}{||x - x'||^2} </math>

Nyní můžeme pro nějakou cestu <math>x_0 \dots x_k</math> můžeme definovat funkci příspěvku k pixelu ''j'':

:<math> 
f_j(\bar x) = L_e(x_0, x_1) \cdot G(x_0, x_1) \cdot
 \prod_{i=1}^{k-1} f_r(x_{i-1}, x_i, x_{i+1}) \cdot G(x_i, x_{i+1})   \cdot W_{e}^{(j)} (x_{k-1}, x_k) 
</math>

Vidíme, že funkce zohledňuje počáteční radianci na světle, hodnoty BRDF, viditelnost a úhly dopadu (vše součástí ''G'') na každém bodě cesty a také jakousi důležitost ''W'' u samotného pixelu. Vidíme tedy, že čím více bodů cesta obsahuje, čím jsou od sebe body dál a čím "nižší" jsou úhly dopadů, tím menší má příspěvek.

==Provedení==
V praxi bychom rádi vybrali cesty paprsků mezi světlem a kamerou takové, aby šance, že se světlo vydá právě touto cestou, byla co nejvyšší (cesty s největším tokem světla, které mají velký vliv na barvu pixelu). Vygenerujeme náhodnou cestu směrem od kamery (děláme to chytře, např. s použitím BRDF importance samplingu, nejspíše netrefí světelný zdroj) a stejně tak druhou náhodnou cestu od zdroje světla. Spojením libovolného bodu z první cesty s libovolným bodem z druhé cesty dostaneme několik "úplných cest" mezi kamerou a zdrojem a právě na těchto cestách spočítáme barevný příspěvek.

== Související články ==

* [[Sledování cest]]
* [[Globální osvětlení]]
* [[Zobrazovací rovnice]]
* [[Radiometrické veličiny]]
* [[BRDF]]
* [[Monte Carlo integrování]]


[[Kategorie:Počítačová 3D grafika]]