Scienceworld.cz
PRO MOBIL
PRO MOBIL


KLASICKY
KLASICKY


Jak se algoritmy učí kreslit: Počítačový obraz reálného světa (3)

Rozměrová exploze

Všechny postupy k řešení zobrazovací rovnice uvedené v předcházejícím díku našeho seriálu používají tím či oním způsobem metodu konečných prvků. Postupy běžné numerické matematiky se ze zkoumané funkce rovnoměrně odeberou vzorky a vhodným průměrováním jejich hodnot se odhadne výsledná hodnota. Výpočetní náročnost této metody bohužel exponenciálně roste s dimenzí prostoru, v němž výpočet probíhá. Naneštěstí právě zobrazovací rovnici je třeba řešit v mnohorozměrném prostoru, takže pravidelné vzorkování takřka nepřipadá v úvahu. Tento problém se někdy označuje pojmem rozměrová exploze (dimensional explosion).

Obdobně jako v případě výše zmíněné otázky úplné simulace fotonů ve scéně navíc představuje výpočet s pravidelným vzorkováním nezměrné plýtvání výpočetním výkonem. Věnuje totiž prakticky stejnou energii výpočtu důležitých i naprosto zanedbatelných nebo zastíněných oblastí scény.
Matematická analýza naštěstí nabízí aparát umožňující zaútočit na oba tyto problémy (rozměrovou explozi i zbytečně důkladný výpočet nepodstatných částí scény): Řešením jsou tzv. stochastické výpočetní metody, při nichž se do výpočtu vnese náhodný prvek. Konkrétně se v tomto případě jedná zejména o integraci metodou Monte Carlo, kdy se hodnota integrálu odhaduje z vzorků funkce odebraných v náhodných místech.

Výpočet Monte Carlo ovšem vyžaduje velmi pečlivé zacházení s náhodným výběrem vzorků. Tvar náhodného rozdělení používaného pro jejich výběr musí pokud možno odrážet jejich důležitost pro výsledný obraz (v jasně osvětlených a dobře viditelných oblastech je třeba odebírat více vzorků než v oblastech slabě osvětlených nebo zastíněných).
Zásadní výsledný rozdíl oproti metodám konečných prvků (sledování paprsků, radiozita) spočívá v tom, že zatímco tyto metody počítají obraz scény s pevně danou přesností a zvýšení složitosti scény nebo nároků na přesnost způsobí jen odpovídající prodloužení výpočtu, náhodné metody typicky umožňují obraz scény spočítat ve víceméně libovolně krátkém čase. Snížení výpočetního času ovšem přitom samozřejmě způsobí vyšší zašumění výsledného obrazu. Se zvyšováním dostupného výpočetního času úroveň šumu postupně klesá, obraz jakoby vystupuje z mlhy.
Mezi metody tohoto typu patří například stochastické sledování paprsku (stochastic ray tracing), metoda fotonových map (photon mapping) nebo obousměrné sledování [světelných] cest (bidirectional path tracing).

S trochou nadsázky lze říci, že náhodné procházení světelných cest lépe kopíruje fyzikální realitu náhodného rozptylování fotonů ve scéně; výsledkem je mimo jiné schopnost těchto algoritmů simulovat pokročilejší optické jevy, jako jsou kaustiky (čočkové efekty, například kroužek jasnějšího světla na stole pod sklenkou nebo mihotání světla na dně bazénu), rozlévání barev (bílá zeď sousedící s červenou zdí získá načervenalý nádech nepřímým osvětlením světlem odraženým od červené zdi), podpovrchové rozptylování (u materiálů jako např. mramor nebo porcelán, kdy světlo prochází a lomí se i uvnitř materiálu) nebo prostorové rozptylování (například mihotání ohřátého vzduchu za turbínami letadel či nad pouští nebo světelné efekty hudebních show vznikající rozptylem laserového světla v dýmu nebo mlze).


Fotonové mapy: skleněná koule zaostřuje světlo ze světelného zdroje a vrhá na podstavu prasátko (kaustiku).
Výpočet obrázku byl proveden pomocí programu POV-Ray verze 3.5 (http://www.povray.org).

Doplňující postupy

Zobrazovací metody s náhodným výběrem vzorků lze rozvíjet řadou dalších směrů; jedná se většinou o postupy a principy velmi mladé, podléhající překotnému teoretickému i praktickému vývoji, takže je nyní velmi obtížné předvídat, zda a které z nich naleznou postupem času uplatnění v komerční počítačové grafice (např. při tvorbě filmových efektů).
Jedním z doplňujících je např. metoda Metropolis, vycházející z teorie tzv. Markovových procesů, kdy jednotlivé vzorky světelných cest nejsou při výpočtu vybírány zcela náhodně, ale na základě principů vzdáleně podobných genovým mutacím. To umožňuje například syntézu obrazu u scén s velmi slabým nebo nepřímým osvětlením s příspěvky z komplikovaných světelných cest, kdy zobrazovaný prostor osvětlí pouze zanedbatelná část výkonu vyzářeného ze světelných zdrojů.
Další možný směr vývoje těchto metod vede cestou snižování jejich výpočetní náročnosti tím, že se sice provádí náhodné vzorkování, ale v každém kroku se najednou zpracovávají celé svazky namísto jednotlivých světelných cest. Cílem této metody je snížit časovou náročnost geometrických výpočtů – tím, že viditelnost a průsečíky paprsků s objekty scény se určují pro celé svazky paprsků najednou namísto pro každou jednotlivou zkoumanou světelnou cestu samostatně. V případě takových technik se dokonce opět rýsuje možnost část algoritmu převést do specializovaných grafických procesorů, což umožní lépe distribuovat potřebný výpočetní výkon mezi jednotlivé komponenty počítače, a tím tvorbu obrazu zrychlit.

Budoucnost filmového průmyslu

Moderní počítačová grafika díky prudkému nárůstu dostupného výpočetního výkonu prodělává v posledních letech bouřlivý vývoj a odhaluje stále nové, nedávno netušené možnosti tvůrcům umělecky i vědecky zaměřených počítačových audiovizuálních děl. Zřejmě ovšem ještě nenastala doba, kdy filmová díla budou vznikat čistě prostřednictvím počítače s pouze okrajovým nebo žádným využitím herců a klasických filmařských metod; počítačem vytvořené filmy, ač stále populárnější, dosud spíše volí stylizaci, než snahu o plnou nápodobu reálného světa (např. Hledá se Nemo, Doba ledová, Shrek, Příšerky s.r.o.).
Na druhé straně v hraných velkofilmech se počítačová grafika již dobře zabydlela a otevřela jejich tvůrcům takřka Pandořinu skříňku dříve nemyslitelných postupů (např. Titanic, Matrix, Mumie, nové díly Hvězdných válek nebo Jacksonovo opus magnum Pán prstenů).

Co číst dál

Internet doslova přetéká odkazy na technologie typu Z-buffer. Následuje proto přehled adres mapujících nejmodernější a nejdokonalejší metody počítačové syntézy obrazu.
http://www.iit.bme.hu/~szirmay/puba.html
http://graphics.stanford.edu/papers/veach_thesis/
http://www.cs.princeton.edu/courses/archive/fall02/cs526/lectures/global.pdf
http://www.lems.brown.edu/vision/people/leymarie/Refs/CompGraphics/Render/General.html
http://graphics.cs.uni-sb.de/Courses/ws0203/cg/Literatur/Dutre_GlobalIlluminationCompendium.pdf
http://www.cs.utah.edu/~bes/papers/scenes/

Shrnutí: Hlavní metody pro syntézu obrazu

– drátový model (wireframe)
– model se skrytím neviditelných hran (hidden edge).
– malířův algoritmus (painter’s algorithm)
– paměť hloubky (Z-buffer)
– radiozita (radiosity)
– stochastické sledování paprsku (stochastic ray tracing)
– metoda fotonových map (photon mapping)
– obousměrné sledování [světelných] cest (bidirectional path tracing).

1. díl seriálu
http://www.scienceworld.cz/sw.nsf/ID/B0B2D892E4624EA2C1256EAE00473337?OpenDocument&cast=1

2. díl seriálu
http://www.scienceworld.cz/sw.nsf/ID/F5D83D770A4C4D53C1256EAE00476723?OpenDocument&cast=1

autor Tomáš Rylek


 
 
Nahoru
 
Nahoru