ˇ ´I TECHNICKE ´ V BRNE ˇ VYSOKE´ UCEN
ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ˇ ´ITACOV ˇ ´ ´ GRAFIKY A MULTIMEDI ´ ´I USTAV POC E
ˇ ORIENTOVANA ´ RADIOZITA OBJEKTOVE ´ ˇ ˇ TYMOV Y´ PROJEKT DO PREDM ETU PGR
ˇ PRACE ´ AUTORI David Baˇrina Kamil Dudka ´ Jakub Filak ´ s Hefka Lukaˇ
BRNO 2007
Objektovˇe orientovan´a radiozita
Zad´an´ı 1. Navrhnˇete tˇr´ıdy, kter´e n´ azornˇe a z hlediska OOP ˇcistˇe implementuj´ı radiozitu. 2. Vytvoˇrte demonstraˇcn´ı pˇr´ıklady - sc´ena m˚ uˇze b´ yt zad´ana kusy k´odu, kter´e instanciuj´ı vhodn´e objekty (nen´ı tˇreba naˇc´ıtat ze souboru apod.) 3. Vytvoˇrte nadstandardn´ı dokumentaci (oproti vˇseobecn´ ym poˇzadavk˚ um), kter´a dobˇre pop´ıˇse (napˇr. s pomoc´ı graf˚ u) a obh´aj´ı strukturu tˇr´ıd. 4. D˚ uraz je kladen na ˇcistotu OOP n´avrhu a kvalitu dokumentace.
Obsah ´ 1 Uvod 1.1 Pod´ıl jednotliv´ ych ˇclen˚ u t´ ymu na projektu . . . . . . . . . . . . . . . . . . .
2 2
2 Teoretick´ aˇ c´ ast 2.1 Radiozita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 V´ ypoˇcet konfiguraˇcn´ıho faktoru pomoc´ı OpenGL . . . . . . . . . . . . . . . .
3 3 4
3 N´ avrh ˇ reˇ sen´ı 3.1 Reprezentace sc´eny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 V´ ypoˇcet radiozity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Vizualizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 6 8 10
4 Implementace 4.1 Sestaven´ı a instalace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11 12
5 V´ ysledky
13
6 Z´ avˇ er
15
1
Kapitola 1
´ Uvod Radiozita je pokroˇcil´ a zobrazovac´ı metoda pouˇz´ıvan´a ve fotorealistick´e grafice. Jej´ı v´ ypoˇcet je ˇcasovˇe n´ aroˇcn´ y. Tato pr´ ace se zab´ yv´a jednoduchou implementac´ı v´ ypoˇctu radiozity, kter´ a vyuˇz´ıv´ a akceleraci zaloˇzenou na OpenGL. Pomoc´ı vznikl´eho programu byly vypoˇc´ıt´any vzorov´e sc´eny, kter´e se do t´eto dokumentace neveˇsly – lze st´ ahnout z http://dudka.cz/rrv. Kromˇe toho lze z webu st´ahnout kr´atk´e video (asi 20 vteˇrin), kter´e ukazuje, jak se ˇs´ıˇr´ı radiozita v pr˚ ubˇehu v´ ypoˇctu. Ned´ılnou souˇc´ ast´ı t´eto dokumentace je dokumentace API a diagramy tˇr´ıd, kter´e jsou dostupn´e rovnˇeˇz na webu projektu.
1.1
Pod´ıl jednotliv´ ych ˇ clen˚ u t´ ymu na projektu
David Baˇ rina, xbarin02 - V´ ypoˇcet konfiguraˇcn´ıch faktor˚ u pomoc´ı OpenGL - Pˇrevod primitiv (koule, v´ alec, ˇcajn´ık) na polygon´aln´ı reprezentaci Kamil Dudka, xdudka00 - Objektov´ y model - Dˇelen´ı na ploˇsky - Mezipamˇet’ pro konfiguraˇcn´ı faktory - Interpolace barev Jakub Fil´ ak, xfilak01 - Vstup/v´ ystup XML, DTD - Zpracov´ an´ı parametr˚ u pˇr´ıkazov´e ˇr´adky Luk´ aˇ s Hefka, xhefka00 - Program pro vizualizaci - Vzorov´ a vstupn´ı sc´ena Tento dokument byl vys´ azen syst´emem LATEX.
2
Kapitola 2
Teoretick´ aˇ c´ ast 2.1
Radiozita
Radiozita[7] je metoda glob´ aln´ı iluminace sc´eny (ˇs´ıˇren´ı svˇeteln´e energie) pouˇz´ıvan´a k renderov´an´ı 3D sc´eny v poˇc´ıtaˇcov´e grafice. Radiozita jako renderovac´ı metoda byla pˇredstavena v roce 1984 v´ yzkumn´ıky na Cornell University. Vych´az´ı ze z´akona zachov´an´ı energie. Proto vyˇzaduje energeticky uzavˇren´e sc´eny. Nedok´aˇze pracovat s pr˚ uhledn´ ymi objekty, zrcadly a texturami. Sc´ena mus´ı b´ yt reprezentov´ana polygon´aln´ım modelem. Zobrazovac´ı rovnice vych´ az´ı z dvousmˇerov´e distribuˇcn´ı funkce BRDF[4]. Plochy nejen ˇıˇr´ı se pouze dif´ odr´aˇzej´ı svˇetlo, ale mohou m´ıt i vlastn´ı z´aˇrivost. S´ uzn´ı odraz svˇetla. ’ Vlastn´ı v´ ypoˇcet m˚ uˇze prob´ıhat bud iteraˇcnˇe (progresivnˇe) nebo ˇreˇsen´ım soustavy rovnic (maticov´e ˇreˇsen´ı). Pˇred vlastn´ım v´ ypoˇctem je tˇreba polygony ve sc´enˇe rozdˇelit na mal´e ploˇsky a spoˇc´ıtat konfiguraˇcn´ı faktory (vliv kaˇzd´e ploˇsky na kaˇzdou jinou ploˇsku ve sc´enˇe). Ploˇsky, kter´e na sebe nevid´ı maj´ı konfiguraˇcn´ı faktor 0. Iteraˇcn´ı v´ ypoˇcet, kter´ y je pouˇzit v naˇsem projektu, m´ a v´ yhodu postupn´eho zobrazen´ı v´ ysledku po kaˇzd´e iteraci. Radiozita (z´ aˇrivost) kaˇzd´e ploˇsky je definov´ana jako: Bi = Ei + Ri
n X
Bj Fij
(2.1)
j=1
kde: • Bi je radiozita ploˇsky i. • Ei je vyzaˇrovan´ a energie t´eto ploˇsky. • Ri je odrazivost ploˇsky. • suma reprezentuje souˇcet energi´ı pˇrich´azej´ıc´ıch na ploˇsku i ze vˇsech ostatn´ıch ploˇsek. • Fji je konfiguraˇcn´ı faktor mezi ploˇskami i a j (vliv ploˇsky j na ploˇsku i).
3
2.2
V´ ypoˇ cet konfiguraˇ cn´ıho faktoru pomoc´ı OpenGL
Konfiguraˇcn´ı faktor[1] (form factor ) ˇr´ık´a, kolik energie energie ploˇsky (patche) i je pˇr´ımo pˇrijato ploˇskou j. Ploˇsky vzd´ alenˇejˇs´ı maj´ı od ploˇsky c´ılov´e maj´ı na tuto vliv menˇs´ı neˇz ploˇsky bliˇzˇs´ı. Ploˇsky viditeln´e z c´ılov´e ploˇsky ze strany maj´ı menˇs´ı vliv neˇz ploˇsky leˇz´ıc´ı pˇr´ımo pˇred c´ılovou ploˇskou (Lambert˚ uv kosinov´y z´ akon). K v´ ypoˇctu konfiguraˇcn´ıho faktoru je tˇreba vykreslit sc´enu z pohledu c´ılov´e ploˇsky (i) s rozsv´ıcenou ploˇskou zdrojovou (j). Toto vykreslen´ı (vyrenderov´ an´ı) sc´eny je tˇreba prov´est pro vˇsechny dvojice ploˇsek ve sc´enˇe. Vykreslen´ım vˇsech zdrojov´ ych ploˇsek rozd´ılnou barvou ke kaˇzd´e c´ılov´e ploˇsce najednou lze v´ ypoˇcet znaˇcnˇe urychlit. Sloˇzitost kles´a z kvadratick´e (poˇcet ploˇsek na druhou) na line´arn´ı. Z v´ ysledn´e vyrenderovan´e bitmapy se pak spoˇc´ıt´a form factor pro vˇsechny zdrojov´e ploˇsky viditeln´e v t´eto bitmapˇe k ploˇsce c´ılov´e (z jej´ıhoˇz pohledu byla sc´ena renderov´ana). Pˇri vlastn´ım renderovan´ı[3] je potˇreba vidˇet z pohledu c´ılov´e ploˇsky cel´ ych 180◦ svˇeta leˇz´ıc´ıho pˇred touto ploˇskou. D´ ale je tˇreba aplikovat Lambert˚ uv kosinov´ y z´akon a t´ım sn´ıˇzit vliv ploˇsek, kter´e se nach´ azej´ı z boku c´ılov´e ploˇsky, oproti ploˇsk´am leˇz´ıc´ıch pˇr´ımo naproti ˇ c´ılov´e ploˇsky. C´ım v´ıce z boku zdrojov´a ploˇska leˇz´ı, t´ım m´enˇe svˇetla z n´ı c´ılov´a ploˇska pˇrijme. K vyrenderov´ ani 180◦ sc´eny se pouˇz´ıv´a vyrenderov´ani do tzv. polokrychle (hemicube). To znamen´ a vyrenderov´ ani sc´eny pˇri pohledu ze stˇredu patche do pˇredn´ı stˇeny a do 4 boˇcn´ıch polostˇen. Renderuje se s u ´hlem pohledu 90◦ (perspektiva). Vyrenderov´ani pˇredn´ı stˇeny se kamera um´ıst´ı do stˇredu c´ılov´eho patche a bude se d´ıvat ve smˇeru norm´alov´eho vektoru tohoto patche. K renderov´ an´ı je pouˇzito OpenGL, konkr´etnˇe funkce gluLookAt() z knihovny GLU. UP“ vektor je zvolen rovnobˇeˇznˇe s jednou ze stran troj´ uheln´ıkov´eho patche. ” Pˇri renderov´ an´ı boˇcn´ıch stran se kamera opˇet d´ıv´a ze stˇredu patche a renderuje se opˇet s u ´hlem pohledu 90◦ . Smˇer pohledu je ovˇsem kolm´ y na norm´alov´ y vektor ( UP“ vek” tor z renderov´ an´ı pˇredn´ı stˇeny). Pro renderov´an´ı vˇsech 4 stran se kamera postupnˇe ot´ aˇc´ı ◦ po 90 . Z v´ ysledn´e bitmapy je podstatn´a pouze ˇc´ast nad horizontem c´ılov´eho troj´ uheln´ıku (tzn. polovina boˇcn´ı stˇeny). Vˇsechna renderov´an´ı prob´ıhaj´ı postupnˇe do jedin´eho framebufferu. Oblast framebufferu, do kter´e se bude kreslit, se nastavuje funkc´ı glViewport(). Pro dalˇs´ı zpracov´ an´ı je d˚ uleˇzit´e, aby na sebe pohledy do stran polokrychle spr´avnˇe navazovaly (spr´ avn´e UP“ vektory). Po dokonˇcen´ı renderov´an´ı je ve framebufferu zobrazena ” rozbalen´ a krychle (tvoˇr´ı kˇr´ıˇz). Podstatn´a je pouze vnitˇrn´ı ˇc´ast tohoto kˇr´ıˇze (bez spodn´ıch ˇc´ast´ı boˇcn´ıch pohled˚ u). V t´eto oblasti je nyn´ı nutn´e zohlednit Lambert˚ uv kosinov´ y z´akon. Velmi jednoduˇse ˇreˇceno, Lambert˚ uv kosinov´ y z´akon ˇr´ık´a, ˇze paprsek dopadaj´ıc´ı na stˇred ploˇsky kolmo m´ a na jej´ı osvˇetlen´ı vliv nejvˇetˇs´ı. Paprsek dopadaj´ıc´ı pod nˇejak´ ym u ´hlem m´ a vliv menˇs´ı u ´mˇernˇe tomuto u ´hlu (kosinus tohoto u ´hlu). Paprsek dopadaj´ıc´ı t´emˇeˇr rovnobˇeˇznˇe s povrchem ploˇsky m´ a vliv t´emˇeˇr zcela zanedbateln´ y. Pˇred vlastn´ım poˇc´ıt´ an´ım konfiguraˇcn´ıch faktor˚ u z vyrenderovan´e bitmapy je nutn´e pˇren´est obsah framebufferu do pamˇeti pomoc´ı funkce glReadPixels(). D´ale ji bitmapa postupnˇe proch´ azena po pixelech. Barva kaˇzd´eho pixelu ud´av´a, kterou zdrojovou ploˇsku
4
v tomto m´ıstˇe c´ılov´ a ploˇska vid´ı (barva pixelu je indexem zdrojov´e ploˇsky). Pouh´ ym sˇc´ıt´an´ım poˇctu pixel˚ u ve sc´enˇe dan´e barvy by se spoˇc´ıtal konfiguraˇcn´ı faktor nezohledˇ nuj´ıc´ı Lambert˚ uv kosinov´ y z´ akon (ˇc´ım v´ıce pixel˚ u ze zdrojov´e ploˇsky je vidˇeno ploˇskou c´ılovou, t´ım vˇetˇs´ı maj´ı na sebe vliv). Podle pozice (x, y) v bitmapˇe je spoˇcten vliv (koeficient) dan´eho pixelu na celkov´ y form factor k dan´e zdrojov´e ploˇsce. Nejvˇetˇs´ı vliv maj´ı pixely leˇz´ıc´ı ve stˇredu bitmapy (stˇredu pˇredn´ı stˇeny polokrychle), kde je tento koeficient roven 1. Nejmenˇs´ı vliv (koeficient roven 0) maj´ı pixely na vnˇejˇs´ıch hran´ach boˇcn´ıch polostˇen. Tento koeficient je poˇc´ıt´an jako souˇcin kosin˚ u pozice x a y, kde stˇred bitmapy m´a x i y rovno nule. Smˇerem ke stran´ am se x i y zmenˇsuje (doleva a nahoru) a zvˇetˇsuje (doprava a dol˚ u) aˇz k hodnotˇe π2 .
5
Kapitola 3
N´ avrh ˇ reˇ sen´ı V´ ypoˇcet radiozity je ˇcasovˇe n´ aroˇcn´ y a klade vysok´e n´aroky na v´ ykon stroje. Hlavn´ımi c´ıli n´avrhu tedy bylo: • Co nejv´ıce urychlit v´ ypoˇcet – vyuˇzit´ı HW akcelerace, maxim´aln´ı vyuˇzit´ı dostupn´e pamˇeti, ... • Moˇznost pracovat s meziv´ ysledky – pro co nejrychlejˇs´ı odhalen´ı nedostatk˚ u ve vstupn´ı sc´enˇe nebo zvolen´ ych parametrech v´ ypoˇctu. • Moˇznost nav´ azat na dˇr´ıve pˇreruˇsen´ y v´ ypoˇcet – v pˇr´ıpadˇe v´ ypadku elektˇriny, p´adu syst´emu, ...
3.1
Reprezentace sc´ eny
V´ ypoˇcet radiozity pracuje s polygon´aln´ım modelem – na nejniˇzˇs´ı u ´rovni jsou tedy tˇelesa ve sc´enˇe reprezentov´ ana mnoˇzinou polygon˚ u (troj´ uheln´ık˚ u). Jednomu troj´ uheln´ıku odpov´ıd´ a struktura Triangle. Na rozd´ıl od bˇeˇzn´ ych polygon´aln´ım model˚ u vˇsak nezad´av´ame pˇr´ımo barvu polygonu, kterou vid´ı uˇzivatel. Tato barva je vypoˇc´ıt´ana pomoc´ı radiozity. Zad´avaj´ı se m´ısto toho dvˇe sloˇzky: • emission – barva, kterou polygon vyzaˇruje. Pouˇz´ıv´a se pouze pro zdroje svˇetla, tˇelesa, kter´ a sama o sobˇe nez´ aˇr´ı, maj´ı tuto sloˇzku nulovou. • reflectivity – barva, kterou polygon odr´aˇz´ı. Jedn´a se tedy o barvu tˇelesa tak, jak ji vn´ım´ ame intuitivnˇe. Pˇri zad´ av´ an´ı sc´eny uˇzivatelem vˇsak nemus´ı b´ yt vˇzdy pr´ace s jednotliv´ ymi polygony zcela intuitivn´ı. Proto definuje objektov´ y model nˇekter´a z´akladn´ı primitiva – krychle, koule, 1 v´alec a ˇcajn´ık . Kaˇzd´e primitivum je reprezentov´ano samostatnou tˇr´ıdou, kter´a zapouzdˇruje pˇrevod na polygon´ aln´ı model. 1
Polygon´ aln´ı reprezentaci ˇcajn´ıku lze st´ ahnout z http://home.student.uu.se/yuca7825/Ass2 YuCao YaoWang.zip
6
Uˇzivatel m´ a tedy dvˇe moˇznosti, jak reprezentovat tˇelesa ve sc´enˇe – polygon´alnˇe nebo pomoc´ı primitiv. Tyto pˇr´ıstupy jsou z pohledu v´ ypoˇctu zamˇeniteln´e – proto je nad nimi definov´ ana abstraktn´ı tˇr´ıda Entity. Tˇr´ıda TriangleSet reprezentuje kontejner polygon˚ u na n´ızk´e u ´rovni. Nad jednotliv´ ymi tˇelesy je moˇzn´e prov´adˇet bˇeˇzn´e transformace ve 3D – k tomu slouˇz´ı ˇ ast objektov´eho tˇr´ıda TransformMatrix a metoda setTransformMatrix tˇr´ıdy Entity. C´ modelu reprezentuj´ıc´ı tˇeleso je zjednoduˇsenˇe zn´azornˇena na obr. 3.1.
Obr´ azek 3.1: Abstraktn´ı tˇr´ıda Entity Sc´ena je tedy z pohledu uˇzivatele tvoˇrena oddˇelen´ ymi tˇelesy. Vˇsechny tˇelesa ve sc´enˇe jsou spravov´ any tˇr´ıdou Scene. Tato tˇr´ıda, mimo jin´e, umoˇzn ˇuje sc´enu jako celek naˇc´ıst ze vs2 tupn´ıho XML souboru a zapsat do v´ ystupn´ıho XML souboru. Tˇr´ıda EntitySet reprezentuje kontejner entit na n´ızk´e u ´rovni. Kompozice tˇr´ıdy Scene je zn´azornˇena na obr. 3.2.
Obr´ azek 3.2: Tˇr´ıda Scene – reprezentace sc´eny Reprezentace sc´eny pomoc´ı oddˇelen´ ych tˇeles je vhodn´a pro uˇzivatele a tak´e pro nˇekter´e pomocn´e v´ ypoˇcty (napˇr. interpolace barev). Pro v´ ypoˇcet radiozity vˇsak tato reprezentace 2
DTD pro reprezentaci sc´eny je na adrese http://dudka.cz/dtd/scene.dtd
7
vhodn´a nen´ı. Radiozita uvaˇzuje vliv kaˇzd´e ploˇsky na ostatn´ı ploˇsky – bez ohledu na to, kter´emu tˇelesu ploˇsky patˇr´ı. Pro tento u ´ˇcel byly vytvoˇreny enumer´atory pro pˇr´ıstup k jednotliv´ ym ploˇsk´ am. Situaci zn´ azorˇ nuje obr. 3.3.
Obr´ azek 3.3: Enumer´ atory – tˇr´ıdy pro pˇr´ıstup k jednotliv´ ym ploˇsk´am Z´akladem je tˇr´ıda PatchSequenceEnumerator, kter´a implementuje sekvenˇcn´ı pr˚ uchod pˇres vˇsechny ploˇsky ve sc´enˇe. K indexovan´emu pˇr´ıstupu k ploˇsk´am slouˇz´ı tˇr´ıda PatchRandomAccessEnumerator, kter´ a se konstruuje z jiˇz existuj´ıc´ı instance sekvenˇcn´ıho enumer´atoru. Tato tˇr´ıda alokuje vˇetˇs´ı mnoˇzstv´ı pamˇeti, proto je vhodn´e jej´ı instanci sd´ılet mezi vˇsemi objekty, kter´e vyˇzaduj´ı indexovan´ y pˇr´ıstup k ploˇsk´am.
3.2
V´ ypoˇ cet radiozity
Pˇred vlastn´ım v´ ypoˇctem radiozity je nutn´e rozdˇelit troj´ uheln´ıky z vstupn´ı sc´eny na ploˇsky poˇzadovan´e velikosti. K tomu u ´ˇcelu slouˇz´ı metoda divide tˇr´ıdy Scene, kter´a odstartuje rekurzivn´ı dˇelen´ı troj´ uheln´ık˚ u. Rekurzivn´ı dˇelen´ı je vˇzdy zastaveno pˇri dosaˇzen´ı poˇzadovan´e velikosti (obsahu) troj´ uheln´ıku. Pro v´ ypoˇcet obsahu troj´ uheln´ıku je pouˇzit´ y Heron˚ uv vzorec[6]: p (3.1) S = s(s − a)(s − b)(s − c)
8
kde
a+b+c (3.2) 2 Vlastn´ı v´ ypoˇcet radiozity je zajiˇst’ov´an tˇr´ıdou RadiosityRenderer. Instance t´eto tˇr´ıdy se tvoˇr´ı metodou createRadiosityRenderer tˇr´ıdy Scene, kter´e se pˇredaj´ı parametry v´ ypoˇctu. Vztahy objekt˚ u pro v´ ypoˇcet radiozity jsou zachyceny na obr. 3.4 s=
Obr´ azek 3.4: Tˇr´ıda RadiosityRenderer – reprezentace sc´eny Z pohledu uˇzivatele trv´ a v´ ypoˇcet radiozity vˇeˇcnost – je tedy na m´ıstˇe pr˚ ubˇeh v´ ypoˇctu sledovat a nˇejak na nˇej reagovat. K tomuto u ´ˇcelu byl pouˇzit n´avrhov´ y vzor observer, pˇriˇcemˇz tˇr´ıda RadiosityRenderer je zde v roli sledovan´eho objektu. V souˇcasn´e verzi projektu jsou implementov´ any dva observery (pozorovatel´e) – ConsoleProgressIndicator a ContinousSaver. Jednotliv´e pozorovatele je moˇzn´e za bˇehu pˇripojovat a odpojovat. Tˇr´ıda ConsoleProgressIndicator bˇehem v´ ypoˇctu vypisuje do konzole z´akladn´ı informace o pr˚ ubˇehu. Tˇr´ıda ContinousSaver ukl´ad´a meziv´ ysledky do souboru s pˇredem nastavenou frekvenc´ı. Frekvence ukl´ ad´ an´ı se v pr˚ ubˇehu v´ ypoˇctu sniˇzuje, coˇz odpov´ıd´a sniˇzuj´ıc´ım se zmˇen´am radiozity ve sc´enˇe. Tyto meziv´ ysledky je moˇzn´e pouˇz´ıt napˇr´ıklad pro generov´ an´ı videa – viz. kapitola 5. J´adrem v´ ypoˇctu radiozity je v´ ypoˇcet konfiguraˇcn´ıch faktor˚ u – tento v´ ypoˇcet zajiˇst’uje tˇr´ıda FormFactorEngine. Jej´ı implementace pouˇz´ıv´a OpenGL pro urychlen´ı v´ ypoˇctu – viz. kapitola 2.2. Tento v´ ypoˇcet je vˇsak (zejm´ena pro sc´eny s velk´ ym poˇctem ploˇsek) n´aroˇcn´ ya je tedy nejslabˇs´ım m´ıstem aplikace z hlediska v´ ykonu. Nab´ız´ı se tedy ˇreˇsen´ı: ukl´ adat si vypoˇcten´e konfiguraˇcn´ı faktory do pamˇeti mezi jednotliv´ ymi pr˚ uchody. Mnoˇzstv´ı potˇrebn´e pamˇeti vˇsak roste s kvadr´atem k poˇctu ploˇsek ve sc´enˇe a pro netrivi´ aln´ı sc´enu se vˇsechny konfiguraˇcn´ı faktory do pamˇeti nevlezou. Rozumn´ ym kompromisem je uchov´ avat v mezipamˇeti tolik konfiguraˇcn´ıch faktor˚ u, kolik se jich tam vleze a to co moˇzn´ a nejefektivnˇejˇs´ım zp˚ usobem. Mezipamˇet’ pro vypoˇcten´e konfiguraˇcn´ı faktory zajiˇst’uje tˇr´ıda PatchCache3 . Tato mezipamˇet’ je hierarchick´ a – konfiguraˇcn´ı faktory vˇsech ploˇsek ovlivˇ nuj´ıc´ıch jednu konkr´etn´ı 3
Spolu s hodnotou konfiguraˇcn´ıho faktoru je potˇreba uchov´ avat odkaz na ploˇsku, ke kter´e se konfiguraˇcn´ı faktor vztahuje.
9
ploˇsku se shlukuj´ı v objektech tˇr´ıdy PatchCacheLine. Poˇcet potˇrebn´ ych objekt˚ u PatchCacheLine tvoˇr´ıc´ıch mezipamˇet’ je zˇrejmˇe stejn´ y jako poˇcet ploˇsek ve sc´enˇe. Jednotliv´e objekty PatchCacheLine spolu potom soutˇeˇz´ı o uloˇzen´ı v mezipamˇeti. Krit´eriem je pˇritom poˇcet uloˇzen´ ych konfiguraˇcn´ıch faktor˚ u uvnitˇr objektu (a t´ım p´adem velikost objektu v pamˇeti). Vyˇsˇs´ı prioritu pro uchov´an´ı pamˇeti maj´ı objekty s niˇzˇs´ı velikost´ı. Objekty s vyˇsˇs´ı velikost´ı je efektivnˇejˇs´ı znovu vypoˇc´ıtat. Diagram tˇr´ıd tvoˇr´ıc´ıch mezipamˇet’ je na obr. 3.5. Prioritn´ı fronta je implementov´ana pomoc´ı stejnojmenn´eho STL kontejneru[5].
Obr´ azek 3.5: Tˇr´ıda PatchCache – mezipamˇet’ pro konfiguraˇcn´ı faktory
3.3
Vizualizace
Vizualizaci sc´eny m´ a na starosti tˇr´ıda Visualizer. Vizualizaci je moˇzn´e prov´adˇet dvˇema zp˚ usoby: 1. Interaktivnˇ e – uˇzivatel m˚ uˇze mˇenit pozici kamery, pˇrep´ınat mezi r˚ uzn´ ymi zp˚ usoby zobrazen´ı a ukl´ adat aktu´ aln´ı pohled jako obr´azek. 2. D´ avkovˇ e – zobrazen´ a sc´ena se uloˇz´ı jako obr´azek do souboru a program skonˇc´ı. Interaktivn´ı vizualizaci zajiˇst’uje statick´a metoda visualize, d´avkovou vizualizaci zajiˇst’uje statick´ a metoda takeScreenshot. Tyto metody maj´ı jednu zvl´aˇstnost – po jejich zavol´an´ı se uˇz nikdy nevr´ at´ı ˇr´ızen´ı zpˇet4 a program je ukonˇcen funkc´ı std::exit(). Pˇri n´avrhu je potˇreba na tuto vlastnost br´ at ohled a zajistit spr´avn´e uvolnˇen´ı pamˇeti a ostatn´ıch zdroj˚ u. V´ ysledkem radiozity jsou hodnoty barev pro jednotliv´e ploˇsky. Aby uˇzivatel nevidˇel ruˇsiv´e pˇrechody barev mezi ploˇskami, je potˇreba prov´est interpolaci barev. Nejprve jsou pr˚ umˇerov´ an´ım vypoˇcteny barvy pro jednotliv´e vrcholy ploˇsek (metoda Entity::computeVertexColors()), samotnou interpolaci potom prov´ad´ı OpenGL bˇehem vykreslov´an´ı sc´eny. 4
Tohle chov´ an´ı je d´ ano rozhran´ım knihovny GLUT, kterou tˇr´ıda pouˇz´ıv´ a.
10
Kapitola 4
Implementace Cel´ y projekt byl implementov´ an v jazyce C++, vyuˇz´ıv´a knihovny standardu OpenGL a knihovnu GLUT. Volnˇe ˇsiˇriteln´ y parser XML[2] je souˇc´ast´ı archivu. Automatick´e sestaven´ı na r˚ uzn´ ych platform´ ach zajiˇst’uje multiplatformn´ı make syst´em CMake. Jak bylo naznaˇceno v n´avrhu, sestavuj´ı se dva spustiteln´e soubory: rrv-compute je program pro v´ ypoˇcet radiozity. V´ ypis parametr˚ u je moˇzn´e vypsat pˇrep´ınaˇcem --help, povinn´ ym parametrem je --filein n´asledovan´ y jm´enem vstupn´ıho souboru. Vstupn´ı soubor m˚ uˇze b´ yt vytvoˇren´ y uˇzivatelem, nebo to m˚ uˇze b´ yt meziv´ ysledek v´ ypoˇctu, na kter´ y chceme nav´azat. Dalˇs´ım d˚ uleˇzit´ ym parametrem je --divide, kter´ y urˇcuje nejvyˇsˇs´ı pˇr´ıpustn´ y obsah ˇ ploˇsky ve sc´enˇe bˇehem rekurzivn´ıho dˇelen´ı na ploˇsky. C´ım niˇzˇs´ı ˇc´ıslo nastav´ıme, t´ım je v´ ystup kvalitnˇejˇs´ı. Z´ aroveˇ n vˇsak roste doba v´ ypoˇctu, proto je dobr´e naj´ıt vhodnou hodnotu experiment´ alnˇe. V´ ypoˇcet je moˇzn´e urychlit nastaven´ım vhodn´e hodnoty parametru --cache. Tento parametr urˇcuje maxim´ aln´ı prostor vyhrazen´ y pro mezipamˇet’. Konfiguraˇcn´ı faktory, kter´e se do mezipamˇeti nevlezou je nutn´e poˇc´ıtat v kaˇzd´em pr˚ uchodu znovu, coˇz zpomaluje v´ ypoˇcet. V praxi vˇsak nen´ı vhodn´e nastavovat velikost mezipamˇeti vyˇsˇs´ı neˇz je velikost fyzick´e pamˇeti. rrv-visualize je program pro vizualizaci sc´eny. Pomoc´ı tohoto programu je moˇzn´e vizualizovat vstupn´ı sc´enu, jak´ ykoliv meziv´ ysledek i fin´aln´ı sc´enu s vypoˇctenou radiozitou. Jak bylo zm´ınˇeno v n´ avrhu, pracuje ve dvou reˇzimech. V´ ychoz´ı je interaktivn´ı reˇzim, d´ avkov´ y reˇzim se zap´ın´ a volbou --screenshot on. Povinn´ ym parametrem je opˇet --filein n´ asledovan´ y jm´enem vstupn´ıho souboru. Pozici kamery lze v interaktivn´ım reˇzimu mˇenit myˇs´ı. Lev´ ym tlaˇc´ıtkem se ot´aˇc´ı sc´ena, prav´ ym tlaˇc´ıtkem se kamera pˇribliˇzuje/oddaluje a kurzorov´ ymi ˇsipkami se kamera posouv´ a. D´ ale je moˇzn´e mˇenit zp˚ usob zobrazen´ı ploˇsek a zobrazen´ı barev pomoc´ı n´ asleduj´ıc´ıch kl´ aves:
11
Kl´avesa 1 2 3 7 8 Z X C V B N M
4.1
Funkce pouze vrcholy pouze hranice polygon˚ u vyplnˇen´e polygony zmenˇsit ˇs´ıˇrku bod˚ u/ˇcar zvˇetˇsit ˇs´ıˇrku bod˚ u/ˇcar barva odrazu barva zdroje svˇetla barva odrazu + barva zdroje svˇetla vypoˇcten´a radiozita (bez interpolace, barva ploˇsek) vypoˇcten´a radiozita (jedno´ urovˇ nov´a interpolace) vypoˇcten´a radiozita (jedno´ urovˇ nov´a interpolace, barva ploˇsek) vypoˇcten´a radiozita (dvoj´ urovˇ nov´a interpolace)
Sestaven´ı a instalace
Pro u ´spˇeˇsn´e sestaven´ı je potˇreba m´ıt nainstalovanou knihovnu GLUT, knihovny OpenGL, CMake a podporovan´ y pˇrekladaˇc. Vlastn´ı sestaven´ı a instalace jsou velmi jednoduch´e a pˇr´ımoˇcar´e: $ cmake . $ make $ make install Sestaven´ı bylo testov´ ano na operaˇcn´ıch syst´emech Linux, FreeBSD, Windows XP a Windows Vista. Na syst´emech Windows jsou podporov´any pˇrekladaˇce MinGW a Microsoft Visual Studio 2005. Pro v´ ypoˇcet konfiguraˇcn´ıho faktoru se pouˇz´ıv´a akceler´ator grafick´e karty, pˇriˇcemˇz ˇc´ıslo ploˇsky se k´ oduje jako barva. Pokud prov´ad´ı grafick´a karta vyhlazov´an´ı (aplikace vyhlazov´ an´ı sama nezap´ın´ a), bude v´ ysledek nesmysln´ y. Proto v nastaven´ı grafick´ e karty nesm´ı b´ yt zapnut´ a volba vynucen´ eho vyhlazov´ an´ı.
12
Kapitola 5
V´ ysledky V´ ypoˇcet radiozity byl testov´ an na nˇekolika vzorov´ ych sc´en´ach, kter´e jsou souˇc´ast´ı archivu. Vzhledem k omezen´ım na velikost odevzd´avan´eho souboru (a t´ım p´adem i dokumentace) nebylo moˇzn´e um´ıstit do t´eto dokumentace v´ ysledky jako obr´azky. N´ahled sc´eny s vypoˇc´ıtanou radiozitou je na obr. 5.1. Na webu projektu http://dudka.cz/rrv je spousta obr´azk˚ u z pr˚ ubˇehu v´ ypoˇctu. Tak´e jsou tam ke staˇzen´ı XML soubory s vypoˇctenou radiozitou, takˇze je moˇzn´e si prohl´ednout jiˇz spoˇc´ıtanou sc´enu. Kromˇe toho lze z webu st´ahnout kr´atk´e video (asi 20 vteˇrin), kter´e ukazuje, jak se ˇs´ıˇr´ı radiozita v pr˚ ubˇehu v´ ypoˇctu.
13
Obr´azek 5.1: Sc´ena s na http://dudka.cz/rrv
vypoˇc´ıtanou
radiozitou
14
–
origin´aln´ı obr´azek
naleznete
Kapitola 6
Z´ avˇ er Pˇrestoˇze je implementace v´ ypoˇctu radiozity pomˇernˇe jednoduch´a, poskytuje pˇekn´e v´ ysledky. Nav´ıc je d´ıky HW akceleraci v´ ypoˇcet rychl´ y. Konkr´etn´ı doba v´ ypoˇctu z´avis´ı na sloˇzitosti vstupn´ı sc´eny a zvolen´ ych parametrech. Pˇri testov´an´ı se doba v´ ypoˇctu pohybovala v rozmez´ı nˇekolika minut aˇz nˇekolika dn´ı. Byly splnˇeny vˇsechny poˇzadavky zad´an´ı i hlavn´ı c´ıle n´avrhu. Nav´ıc bylo pomoc´ı t´eto implementace v´ ypoˇctu radiozity vytvoˇreno zaj´ımav´e video. Hlavn´ı v´ yhoda projektu oproti bˇeˇznˇe dostupn´ ym implementac´ım vˇsak spoˇc´ıv´a v jeho jednoduchosti.
15
Literatura [1] Ashdown, I.: RADIOSITY - A Programmer’s Perspective. Wiley, 1994, ISBN 0-471-30488-3. [2] Berghen, D. I. F. V.: Small, simple, cross-platform, free and fast C++ XML Parser. http://www.applied-mathematics.net/tools/xmlParser.html. [3] Elias, H.: Radiosity. http://freespace.virgin.net/hugo.elias/radiosity/radiosity.htm, 2007. [4] Sillion, F. X.; Puech, C.: RADIOSITY & Global Illumination. 1994, ISBN 1-55860-277-1. [5] Stroustrup, B.: The C++ Programming Language. Addison-Wesley, special edition vyd´ an´ı, 1997, ISBN 0-201-88954-4. [6] Weisstein, E. W.: Heronian Triangle. http://mathworld.wolfram.com/HeronianTriangle.html. [7] Wikipedia: Radiosity. http://en.wikipedia.org/wiki/Radiosity, 2007.
16
