D y n a m i c k é s t í n y
DDDyynnaammiicckkéé sssttíínnyy
D y n a m i c k é s t í n y
Pokud alespoň trochu sledujete demoscénu, určitě vám
neuniklo, že se začínají rozmáhat všemožné simulace reálných
světelných efektů, povětšinou v podobě rychlého raytracingu bez
časově náročného osvětlovacího modelu. Programátoři těchto enginů
mají většinou v plánu co nejlepší emulaci reálných dynamických
stínů. Obecně existuje relativně mnoho způsobů, jak stíny
generovat. Mezi časově nejnáročnější a zároveň nejpřesnější patří
samozřejmě radiosita implementovaná metodou konečných elementů.
Pokud hrajete nějaké nejnovější 3D super hity, určitě jste její
výsledky viděli v praxi. Její přesnost je zejména patrná na
plynulých přechodech mezi světlem a stínem v závislosti na
vzdálenosti od světelného zdroje. Člověk má opravdu pocit, že to
světlo tam opravdu je. Ostatně není divu, radiosita spojená s
Monte Carlo raytracingem je v současné době asi to nejlepší,
čím můžeme výpočetní technikou simulovat realitu. Jenomže pro
takové hrátky v reálném čase nám většinou nestačí ani ty
nejrychlejší superpočítače dneška. Všechno se musí spočítat
dopředu, a pak staticky shadow-texturovat za běhu. Stíny jsou tím
pádem statické a hodí se pouze na poziční světelné zdroje.
Další možnost, co do reálnosti stínů velmi podobná
radiositě, je již zmiňovaný raytracing. S přechody světlo stín už
to není tak růžové, ale například pro tzv. spotlights (např.
baterka) nebo openlights (např. lucerna zavěšená relativně daleko
od stěn) je vizuální rozdíl takřka zanedbatelný. Navíc pokud
použijeme pouze geometrický model, tzn. nepočítáme žádné barevné
efekty, mnohonásobné odrazy a další vymoženosti raytracingu, lze
jej urychlit do takové míry, že dnešní P2 zobrazují jednodušší
scény v reálném čase. Je třeba podotknout, že mnoho enginů od
Transgression 2, přes Sink po Gateways používá mnohdy značně
redukované rozlišení, díky kterému snižují počet vystřelovaných
paprsků a výsledek interpolují do výsledného rozlišení videomódu.
Všechno je pak dosti zubaté a rozmazané.
Jak vidíte, ani tento způsob není úplně ideální. Dalo by se
říci, že je to taková honba s tankem na jelena, protože to, co za
takovýchto okolností oddře raytracing, lze velmi dobře
aproximovat analyticky. Získáme opravdu mnohonásobné urchylení
bez významných změn na přesnosti a vizuálním dojmu. Navíc si
můžeme dovolit vyšší rozlišení a rychlejší fps, což velmi
pozitivně působí na diváka. Lidské oko je k plynulým pohyblivým
světelným efektům mnohem shovívavější, a tak si můžeme dovolit i
menší nepřesnosti. Je tu ovšem jedna nevýhoda. Musíme se
orientovat pouze na spotlight. Hlavní finta, která nám umožní
velmi rychlou simulaci stínů, je rendering scény z pohledu
světla.
První demo, které toho využilo společně s texturováním, je,
pokud si dobře pamatuji, Magic View od Dubiusu (vzpomínám si, že
před Magic View bylo ještě jedno demo, které analytické stíny
mělo, ale pouze ve flat podobě na nikterak složité děravé
krychli). Tak jako tak lze říci, že Tremor je v tomto oboru v
mnoha směrech na demoscéně pionýrem. Pokud jste Magic View
viděli, určitě si pamatujete na scénu s děravou krychlí na
podstavci osvětleném dvěma kuželi světla. Nedám za to krk, ale
řekl bych, že Tremor používá právě analytickou metodu. Je to
totiž patrné ze všeobecně velké přesnosti a absence chyb, o
kterých se zmíním později. Také mírně hranatý kužel upozorňuje na
analytickém ořezávání. Prostě princip bude stejný. Scénu je
třeba přetransformovat pomocí matice světla, která je podobná
transformační maticí kamery (funkčně naprosto stejná), do
pohledu světla a jednoduše malířem (pokud je k dispozici BSP
strom, je situace mnohem jednodušší) "vykreslovat" jednotlivé
polygony. Nejde tak ani o to je vykreslit, ale zpracovávat je ve
správném pořadí, čímž se zajistí jejich korektní viditelnost,
která je pro vytvoření reálných stínů velmi podstatná. Při
"vykreslování" následujícího polygonu je třeba pomocí rovin,
které jsou definované hranou tohoto polygonu a bodem světla,
osekat polygony, které ten nový částečně překryje. Jedná se o
naprosto identické ořezávání jako v případě kamery. Může tak
například dojít k tomu, že původní vzdálenější polygon bude
postupně rozsekán na několik disjunktních částí. Je nutné tyto
části stále udržovat ve spojovém seznamu, na jehož kořen ukazuje
pointer z původního netransformovaného a neořezaného polygonu.
Každá tato část se ale stává pro další krok samostatným
polygonem. Ty polygony, které se nachází uvnitř ořezávací
"pyramidy", se logicky odhazují. Pokud znáte span buffery, tak
lze říci, že se jedná o velmi podobnou myšlenku, rozšířenou na
celé polygony. Následuje rendering z pohledu kamery. Kromě
stávajících polygonů je třeba do transformací zapojit i polygony
vzniklé při ořezávání z pohledu světla. Budou sloužit jako
indikátory světla a stínu. V praxi je třeba před texturováním
polygonu vykreslit jeho jakýsi 2D shadow buffer z pohledu
kamery, jenž je analyticky přesný, a z něho pak při samotném
texturování odečítat hodnotu světla a stínu. Je zřejmé, že
přechod světlo/stín je "hranatý", ale o tom pohovořím později.
Důležité je, že tuto metodu lze všelijak modifikovat a docilovat
velmi značného urychlení, zejména při použití BSP stromů. Na
scénu s malým počtem polygonů je opravdu velmi efektivní a dává
analyticky naprosto přesné výsledky. S rostoucím počtem polygonů
efektivita značně klesá a analytická přesnost a striktní ostrost
stínů lze v mnoha případech oželet. Jak jistě tušíte, přichází
další urychlení a zjednodušení problému.
Dostávám se tak, po poněkud delším úvodu do problematiky, k
jádru tohoto článku. V současné době asi nejrychlejší a
nejjednodušší algoritmus generující dynamické stíny v reálném
čase s dostatečnou "diváckou" přesností je technika, která se v
odborných kruzích nazývá Shadow map, případně Poly-Id Shadow
buffer. Poprvé s ní přišli pánové od SGI v podobě příspěvku do
SIGGRAPHu '87. Na poli demoscény se ale objevila až s příchodem
vynikajícího 64kB intra Spotlite od dnes již velmi populárního
Digisnapa. Spotlite využívá tuto techniku na plné obrátky a
zároveň ukazuje v plné kráse její efektivitu a rychlost (intro
běželo plynule i na 486 !). Díky simulaci plynulého přechodu
světlo/stín vypadá občas velmi podobně jako shadow mapy
vygenerované pomocí radiačních metod, což je opravdu velmi
pozitivní efekt. Digisnap jej s úspěchem použil i ve svém
posledním trháku Fulcrum. Ale nic není jednoduché, jak by se z
počátku mohlo zdát. Jak to tedy všechno vlastně funguje ?
Princip je podobný jako u analytických stínů. Scénu nejprve
vykreslíme z pohledu světla, a to tak, že do bufferu, nejlépe o
stejných rozměrech jako výstupní rozlišení, vykreslujeme
jednotlivé polygony, jako kdybychom chtěli klasicky zobrazit
scénu ve flat stínování. Místo barvy ovšem použijeme index
polygonu. Je nutné za prvky bufferu alokovat integery, protože
složitější scény mnohdy několikrát převyšují limit 254 polygonů
(index 0 slouží jako disjunktní činitel, tedy v podstatě globální
tma; její výhody ještě upřesním). Je také dobré polygony, které
jsou normálou natočeny od světla, nebo ty, na které kužel světla
ani nedopadne, vykreslit jako neosvětlené. Následuje vykreslování
z pohledu kamery. Ještě než začne, je dobré vykreslit do aktuálně
vygenerovaného shadow bufferu inverzní kružnici indexem 0, která
zajistí výsledný tvar kužele. Nikomu nebráním tuhle fázi
vynechat, ale kdo z vás kdy viděl čisté obdélníkové světlo ?
Podívejte se na obrázek , který zachycuje shadow buffer, jehož
aplikaci můžete zhlédnout na dalším screenshotu. O postproduktech
a všeobecné variabilitě v této fázi algoritmu pohovořím později.
Zato nesmíme zapomenout zachovat transformační matici z
předchozího průchodu i do této fáze, protože přijde ta
nejdůležitější část celého algoritmu. Postupujeme klasicky.
Ořezáme všechny viditelné polygony a transformujeme jejich body
z objectspace (za space se zde považuje relativní souřadný
systém) do cameraspace, spočítáme 2D souřadnice jejich vrcholů
a pomocí transformační matice z předchozího průchodu spočítáme i
jejich souřadnice [Xs,Ys,Zs] v lightspace. Následuje
vykreslování samotného polygonu. Kromě informací o textuře (např.
U a V) zavedeme lineární interpolaci souřadnic [Xs,Ys,Zs] tak, že
je násobíme převrácenou hodnotu Z-ové komponenty bodu v
cameraspace. Vše interpolujeme naprosto identicky jako 2D
souřadnice (např. texely U a V). Při samotném vykreslování
scanline postupujeme také identicky. Například každý 16 pixel
provedeme zpětnou transformaci [Xs/Zs,Ys/Zs], pak získáme 2D
souřadnice právě vykreslovaného bodu v shadow bufferu. Je potřeba
je samozřejmě posunout do středu shadow bufferu, podobně jako 2D
souřadnice bodu polygonu. Ty jednoduše lineárně interpolujeme při
samotném vykreslování textury a pomocí takto získaného odkazu do
shadow bufferu velmi jednoduše zjistíme, zda index právě
vykreslovaného polygonu koresponduje s indexem v shadow bufferu.
Pokud ano, jsme ve světle, jinak je tam tma. Geniálně jednoduché,
jednoduše geniální. Ale neradujme se předčasně!
Pokud jste pochopili podstatu, jistě vám neuniklo, že tento
velmi efektivní algoritmus má svoje poměrně závažné mouchy. Asi
nejmarkantnější je problém s polygony, jejichž průmět do pohledu
světla je velmi úzký. Tento problém v analytické metodě zřejmě
odpadá. Vzhledem k tomu, že celý prostor vlastně kvantujeme do
konečného rastru, musíme se smířit s tím, že nastane jistý
kvantizační šum. Ve výsledku se celá nedokonalost projevuje
zubatými přechody mezi světlem a stínem v oblastech, které jsou
od světla relativně vzdálenější, nebo v případě, kdy se na
polygonu právě střídá světlo a stín. Vhodnou volbou cesty kamery
můžeme první problém před divákem šibalsky skrýt, ale střídání
světla a stínu, které nastává právě při tenkém průměru polygonu
do shadow bufferu, je třeba řešit radikálním způsobem. Pokud
oželíme rychlost, je možné interpolovat barvu, a částečně tak
zubatost vyhladit, ale lepší cesta je zvolit jistou povolenou
tloušťku polygonu v shadow bufferu. Všechny polygonu, které jsou
moc tenké, označíme jako neosvětlené, takže ve výsledku se daný
polygonu zatemní skokem. V mnohých případech to divák prakticky
nezaregistruje. Pokud se budete pozorně dívat třeba v Spotlite,
zjistíte, že tento skok je jasně patrný ve scéně s kameny. Druhou
kvantizační chybu si můžete prohlédnout ve Fulcrum, nebo je jasně
patrná na tomto obrázku . Shodou okolností se jedná také o
šutráky, tentokrát levitující. Sledujte pozorně stíny, až bude
robot procházet chodbou s větrákem. Digisnap tento problém řeší
vhodnou volbou cesty kamery a světla, takže třeba ve Spotlite,
kde je celý "akční" prostor velmi uzavřený, se s touto chybou
nesetkáte. Z výše uvedených důvodů není tento systém vhodný pro
realtime enginy 3D her, protože k podobným kvantizačním chybám
může obecně docházet velmi často. Pro statické 3D scény dem je
však velmi užitečný a hlavně rychlý.
Ovšem to není zdaleka konec možností této metody. Výborně ji
lze využít například k emulaci promítačky. Prostě k shadow
bufferu přidáme ještě nějakou texturu a stejným postupem ji
nanášíme na polygony. Místo zvyšování intenzity textury ve
světle, zamixujem RGB hodnoty shadow textury do textury polygonu.
Vznikne tak obraz, který velmi realisticky simuluje promítačku.
Lze tak také vytvářet plynulé přechody mezi světlem a stínem na
hranicích kuželu, když se místo shadow textury vygeneruje jakýsi
light shadow buffer, který svým tvarem kopíruje inverzní kružnici
kužele, ale obsahuje informace o intenzitě daného bodu. Potíž je
ovšem v tom, že plynulý přechod nastane pouze na hranicích
kužele, nikoliv obecně na hranici mezi světlem a stínem. To občas
vypadá dosti nevěrohodně. Například ve Fulcrum světlo krásně
plynule přechází v tmu, ale stín robota je ostrý a ještě velmi
hrbolatý. Lze to řešit, pokud použijeme malý trik. Označíme
jistou plochu (např. podlahu) jako polygon, na který budeme vrhat
stíny. Pokud při vykreslování textur za pomoci shadow bufferu
zjistíme, že se nacházíme na přechodu mezi obecným polygonem a
podlahou v takové konstelaci, že právě počítaný pixel je na
podlaze, spočítáme kolik okolních pixelů leží na této ploše. Z
takto získané hodnoty volíme světlost daného bodu. Pokud by
Digisnap použil tento trik, mohl by být přechod stínu robota méně
kostrbatý. Ostatně modifikací tohoto principu označování polygonů
lze velmi efektivně eliminovat některé přechodové kvantizační
chyby úzkých polygonů v shadow bufferu. Zakážeme-li, aby některé
menší objekty na sebe navzájem vrhaly stíny, výrazně tak
urychlíme vykreslování scény bez výrazné újmy na výsledném
vizuálním dojmu. Zdá se, že Digisnap tento způsob eliminace
menších polygonů z procesu stínování používá také. I zde lze s
výhodou využít nesoustředění lidského oka. Například stín ruky
robota na vlastním těle není tak patrný jako stín jeho postavy na
podlaze. Je ale potřeba toto indexování volit chytře, aby
nedocházelo ke zřetelným chybám.
Na závěr se musím omluvit za poměrně odbornější charakter
tohoto článku, který vyžaduje už jisté znalosti problematiky 3D
enginů. Je tak trochu v závěsu za Shakulovým seriálem o 3D
enginech, který zatím není ještě v takové fázi, aby člověku,
který je v tomto obrou začátečníkem, poskytl informace k plnému
pochopení této stínovací metody. Chtěl jsem prostě co
nejjednodušeji a ve zkratce nastínit celou metodu včetně jejích
nedostatků a dalších možných aplikací. K její implementaci je
zapotřebí relativně rozsáhlý kód, takže zde nebudu uvádět nějké
příklady, které by byly samy o sobě vytržné z celkového kontextu.
Pokud by měl někdo hlubší zájem o implemntaci dynamických stínů,
nechť se obrátí na mojí adresu (redox@bbs.infima.cz) a já mu
poskytnu konkrétní informace a rady, jak na to.
ReDox
výheň