Sledování cest, anglicky Path tracing, je algoritmus používaný v počítačové 3D grafice k syntéze (renderování) obrazu virtuální trojrozměrné scény, v níž věrně simuluje globální osvětlení. Řeší zobrazovací rovnici za pomoci Monte Carlo integrování, kdy pro každý pixel výsledného obrázku opakovaně simuluje tok světla ve scéně formou náhodné procházky, neboli sleduje možné cesty paprsků světla, které vycházejí ze světelných zdrojů a po interakci se scénou dopadají do daného pixelu virtuální kamery (odtud název).

Sledování cest přirozeně a fyzikálně přesně simuluje mnoho efektů nepřímého osvětlení, které musí být při užití jiných metod (např. sledování paprsku) komplikovaně imitovány. Patří mezi ně zejména ideální odraz a lom světla, „půjčování barev“ (anglicky color bleeding), kaustiky, měkké stíny, zachycuje rovněž hloubku ostrosti či rozmazání pohybem. Při kombinaci s dostatečně přesnými modely povrchů objektů, světelných zdrojů a kamery pak produkuje obrázky nerozeznatelné od reálných fotografií. Pro získání takto kvalitních výstupů však musí být odsimulováno velké množství paprsků, jinak jsou výsledky zatíženy viditelným šumem.

Časová náročnost této metody dosud komplikuje nasazení v interaktivních aplikacích, díky své přesnosti a nestrannosti ale našla uplatnění například ve filmovém průmyslu a designu či je používána ke generování referenčních obrázků při testování kvality jiných renderovacích algoritmů.

Ukázka scény zobrazené pomocí algoritmu sledování cest.

Historie editovat

Když v roce 1986 James Kajiya publikoval zobrazovací rovnici a její využití v počítačové grafice, představil rovněž algoritmus pro nalezení jejího numerického řešení, jenž nazval sledováním cest.[1] O deset let později na něj navázal Lafortune a navrhl mnohá zlepšení včetně tzv. obousměrného sledování cest.[2]

V roce 1997 přispěli svou modifikací obousměrného sledování cest Eric Veach a Leonidas J. Guibas.[3] Nesla název Metropolis light transport a byla založena na znovu využívání již nalezených cest z kamery do světelných zdrojů za účelem zvýšení výkonu v náročných scénách.

Na počátku nového tisíciletí bylo směřování dalšího vývoje ovlivněno nástupem programovatelných GPU. V roce 2002 prezentoval Timothy Purcell první algoritmus globálního osvětlení běžící na GPU.[4] Následné zdokonalení technologií pro programování GPU (OpenCL, CUDA, ATI Stream) pak spolu s nárůstem výpočetní síly znovu podnítilo zájem o algoritmy založené na sledování cest. První komerční GPU implementaci sledování cest demonstroval Austin Robison ze společnosti NVIDIA v únoru 2009[5] a další následovaly. V současnosti jsou již některé schopny vykreslovat fotorealistické scény v reálném čase.

Existující implementace editovat

Základní verze algoritmu editovat

Teoretické pozadí editovat

Algoritmus chápe světlo jako spojitou nekonečně dělitelnou energii, která vychází ze světelných zdrojů a šíří se prostředím, kde interaguje s povrchy objektů, až se ustálí v rovnovážném stavu. Přitom předpokládá, že se světlo vzájemně neovlivňuje, tj. že energie přicházející do jednoho místa z více směrů se jednoduše sčítá. Tento model je zjednodušením reality, nepostihuje vlnový ani částicový charakter světla, odpovídá spíše geometrické optice. Sledování cest tudíž v této podobě nesimuluje jevy jako je difrakce, disperze, interference či polarizace.

Vyzařování a přenos světla jsou charakterizovány radiometrickými veličinami, zejména září   vyjadřující směrovou hustotu toku světla v bodě   ve směru  . Zář daným bodem emitovaná je typicky značena   a nabývá nenulových hodnot pro body na povrchu světelných zdrojů. Nelze ji však použít pro popis bodových zdrojů, k tomu slouží veličina zářivost.

Interakce světla s hmotou je vyjádřena pomocí BRDF, tj. funkce   udávající v zásadě hustotu pravděpodobnosti, s jakou se světlo dopadající ze směru   do bodu   odrazí do směru  . Tato funkce zachycuje odrazivé vlastnosti materiálů ve scéně, modeluje mikrostrukturu jejich povrchů.

Podmínku na rovnovážné rozložení světla ve scéně formuluje zobrazovací rovnice:

 

Ta říká, že odchozí zář v bodě   ve směru   je dána součtem záře tímto bodem do tohoto směru emitované a integrálu záře příchozí do   z libovolného směru hemisféry, která se s pravděpodobností danou BRDF do směru   odrazila.

Cílem algoritmu pak je pro daný popis světelných zdrojů pomocí emitované radiance a povrchů pomocí BRDF nalézt takové rozložení světla ve scéně, které splňuje zobrazovací rovnici, tzn. nalézt její řešení. Zobrazovací rovnici je však typicky nemožné vyřešit analyticky (scény mají složitou geometrii, integrand je tudíž nespojitý a nabývá takřka libovolných hodnot), sledování cest je proto řešením numerickým. Integrál v rovnici algoritmus odhadne metodou Monte Carlo pomocí jednoho náhodně vygenerovaného směru, neboli spočítá

 

kde   je směr náhodně vygenerovaný podle hustoty pravděpodobnosti  .

Algoritmus editovat

Vlastní renderování probíhá následovně. Pro daný pixel výstupního obrázku je náhodným směrem skrze něj z kamery do scény vržen paprsek. Jestliže žádný objekt scény netrefí, použije se zář pozadí a cesta končí. Jinak se nalezne nejbližší průsečík se scénou a spočítá se zde odhad odchozí záře podle vztahu výše. Tj. leží-li průsečík na zdroji, přičte se emitovaná zář zdroje, a zář odražená se odhadne rekurzivně opětovným vržením paprsku do scény v náhodném směru hemisféry. Aby nevznikaly nekonečné cesty a algoritmus skončil, nevrhá se další paprsek vždy, nýbrž pouze s pravděpodobností rovnou odrazivosti povrchu v místě průsečíku. Tento postup se pro každý pixel zopakuje mnohokrát a příspěvky jednotlivých cest se zprůměrují.

V této podobě lze celý algoritmus zapsat následujícím pseudokódem:

renderImage()
{
  for each pixel p
  {
    Color pixelColor = (0, 0, 0);
    for k = 1 to N
    {
      w = randomDirThroughPixel(cameraPosition, p);
      pixelColor += getL(cameraPosition, w);
    }
    setOutputPixel(p, pixelColor / N);
  }
}

getL(x, wo)
{
  Color L = (0, 0, 0);
  hit = nearestIntersection(x, wo);
  if isEmpty(hit)
    return backgroundRadiance(x, wo);
  if isOnLightSource(hit)
    L += Le(hit.pos, -wo);
  ρ = reflectance(hit.pos, -wo);
  if rand() < ρ
  {
    wi = randomDirOnHemisphere(hit);
    L += getL(hit.pos, wi) * fr(hit.pos, wi, -wo) * dot(hit.n, wi) * 2 * Pi / ρ;
  }
  return L;
}

Vylepšení editovat

Popsaná verze algoritmu je ryze základní, slouží především pro ilustraci. Ač je z teoretického hlediska korektní, v praxi velice špatně konverguje, pročež se typicky implementuje s celou řadou vylepšení. Mezi nejvýznamnější z nich patří:

Vzorkování podle BRDF editovat

Místo uniformního generování směrů (vzorkování) hemisféry se použije technika vzorkování podle důležitosti a hemisféra se vzorkuje podle BRDF. Tedy místo konstantní hustoty   jsou směry generovány podle hustoty co nejpodobnější BRDF. Například pro difúzní komponentu Phongovy BRDF se používá hustota  , kde   je úhel mezi vygenerovaným směrem a normálou plochy v místě průsečíku. Paprsky jsou tak vrhány ve směru pravděpodobnějšího odrazu.

Vzorkování světelných zdrojů editovat

V některých situacích samotné vzorkování podle BRDF selhává (zejména pro malé či bodové světelné zdroje). Kombinuje se proto se vzorkováním světelných zdrojů, kdy se v místě dopadu paprsku vrhá, vedle paprsku sloužícího pro rekurzivní výpočet odražené záře, ještě jeden speciální paprsek k náhodně vygenerovanému bodu na zdroji (ten ve zdroji končí, cesty se tedy exponenciálně nevětví). Příspěvky obou paprsků se poté sečtou s vhodnými vahami.

Složitější interakce světla se scénou editovat

BRDF popisuje pouze odraz světla, počítá se proto s komplikovanějšími distribucemi BTDF či BSDF modelujícími lom, resp. rozptyl světla, pro některé materiály se uvažují i odrazy pod povrchem (BSSRDF).

Osvětlení mapou prostředí editovat

Místo bodových a plošných světelných zdrojů scénu osvětluje myšlená nekonečná koule kolem ní, na níž byl namapován obraz reálného prostředí. Implementace tohoto vylepšení významně ovlivňuje uvěřitelnost výstupu.

Obousměrné sledování cest editovat

Sledování cest směrem z kamery do světelných zdrojů není v praxi pro vykreslení některých jevů použitelné, např. kaustiky konvergují jen velice pomalu. Obousměrné sledování cest proto tento směr kombinuje i se směrem opačným, tj. ze zdrojů do kamery.

Zkratky editovat

  • BSDF - Bidirectional scattering distribution function
  • BRDF - Bidirectional reflectance distribution function
  • BTDF - Bidirectional transmittance distribution function
  • BTF - Bidirectional texture function
  • BSSRDF - Bidirectional Surface Scattering Reflectance Distribution Function
  • SVBRDF - Spatially Varying Bidirectional Reflectance Distribution Function

Odkazy editovat

Reference editovat

V tomto článku byl použit překlad textu z článku Path tracing na anglické Wikipedii.

  1. KAJIYA, James T. The rendering equation. In: SIGGRAPH '86 Proceedings of the 13th annual conference on Computer graphics and interactive techniques. New York: ACM, 1986. Dostupné online. ISBN 0-89791-196-2. DOI 10.1145/15922.15902. S. 143–150. (anglicky)
  2. LAFORTUNE, Eric. Mathematical Models and Monte Carlo Algorithms for Physically Based Rendering. Ithaca, 1996. Disertační práce (PhD.). Cornell University, Program of Computer Graphics. Dostupné online. (anglicky)
  3. VEACH, Eric; GUIBAS, Leonidas J. Metropolis light transport. In: SIGGRAPH '97 Proceedings of the 24th annual conference on Computer graphics and interactive techniques. New York: ACM, 1997. Dostupné v archivu pořízeném dne 2012-04-21. ISBN 0-89791-896-7. DOI 10.1145/258734.258775. S. 65-76. (anglicky)
  4. PURCELL, Timothy J. Ray Tracing on Programmable Graphics Hardware. In: SIGGRAPH '02 Proceedings of the 29th annual conference on Computer graphics and interactive techniques. New York: ACM, 2002. Dostupné online. ISBN 1-58113-521-1. DOI 10.1145/566570.566640. S. 703–712. (anglicky)
  5. ROBISON, Austin. Interactive Ray Tracing on the GPU and NVIRT Overview. Prezentace na I3D 2009. Dostupné online. (anglicky)

Literatura editovat

KŘIVÁNEK, Jaroslav. Počítačová grafika III. Praha, 2012. Přednáška na Matematicko-fyzikální fakultě Univerzity Karlovy. Dostupné online.

PHARR, Matt; HUMPHREYS, Greg. Physically Based Rendering: From Theory to Implementation. 2. vyd. San Francisco: Morgan Kaufmann, 2010. Dostupné online. ISBN 0123750792. (anglicky) 

VEACH, Eric. Robust Monte Carlo Methods for Light Transport simulation. Stanford, 1998. Disertační práce (PhD.). Stanford University. Dostupné online. (anglicky)

DUTRÉ, Philip; BALA, Kavita; BEKAERT, Philippe. Advanced Global Illumination. 2. vyd. Natick: A. K. Peters, 2006. Dostupné online. ISBN 1568813074. (anglicky) 

Související články editovat

Externí odkazy editovat

  • Global Illumination Compendium - Souhrn matematických vztahů souvisejících nejen se sledováním cest ale s globálním osvětlením obecně (anglicky)