Završni rad br. 38

Programski jezik odabran za implementaciju algoritma predizračunatog prijenosa zračenja jest C++, zbog svoje moćne objektne paradigme i efikasnosti. Grafičko programsko sučelje korišteno pri izradi aplikacije jest OpenGL, koji je odabran prvenstveno zbog jednostavnosti uporabe. Zahtjevi nad programskom potporom su sljedeći: mogućnost rada s bilo kojim virtualnim okruženjem priloženim u odgovarajućem formatu; simulacija tog virtualnog okruženja u stvarnom vremenu s naprednim osvjetljenjem, koje pokazuje (barem neke) globalne učinke osvjetljenja koji se ne mogu simulirati postojećim lokalnim modelima. Prvi zahtjev je ispunjen tako da se virtualno okuženje interpretira kao skup objekata koji su raspoređeni u prostoru na neki predodređeni način, i koji posjeduju predodređene karakteristike. U toj interpretaciji, virtualno okruženje možemo nazvati scenom, a komponente virtualnog okruženja objektima scene. S tim u vidu, za potrebe demonstracije programske potpore, konstruirani su jednostavni 3D objekti korištenjem Autodesk Maya 2008 alata, i zatim eksportirani u jednostavni i općeprihvaćeni .obj format. U svrhu povezivanja tih individualnih objekata u cjelovitu scenu, potrebna je dodatna datoteka koja služi kao opisnik scene. Kao takva, njen je format vrlo jednostavan – riječ je tek o popisu objekata koji se pojavljuju na sceni. Budući da se u Maya alatu objekti mogu već prije eksportiranja translatirati, rotirati i postaviti na scenu u odgovarajuću poziciju, format opisa scene ne treba sadržavati takve podatke. Jedino što je potrebno jest označiti željenu teksturu. Dakle, opis scene se sastoji od stavaka sljedećeg oblika:

"NazivDatotekeObjekta.obj" "NazivDatotekeTeksture.tga"

Navodnici su potrebni da se omoguće praznine u nazivu datoteka. Sljedeći i glavni zahtjev se može ispuniti korištenjem predizračunatog prijenosa zračenja, što je trenutno ponajbolji izbor za interaktivnu simulaciju globalnog osvjetljenja. Nakon definiranja svih zahtjeva i općih smjernica njihovog ispunjenja, moguće je dizajnirati arhitekturu programske potpore. Prvi korak dizajna jest razlučivanje odgovornosti, i njihovo pridjeljivanje paketima. Shodno tome, možemo razlikovati četiri glavna paketa, kako to prikazuje sljedeći dijagram:

Temeljni paket jest System, koji je odgovoran za sve sistemske operacije poput stvaranja prozora za iscrtavanje, rukovanje ulaznim jedinicama itd. Zatim, paket SceneManager sadrži  i upravlja svim podacima koji određuju scenu. Između ostalog, razredi iz tog paketa će biti zaslužni za učitavanje .obj datoteka. Najvažniji paket jest PRT, koji sadrži svu funkcionalnost potrebnu za provođenje algoritma predizračunatog zračenja, dakle i predprocesiranje scene, i samo iscrtavanje. Na kraju, pomoćni paket VectorMath sačinjavaju razredi za rad s pravokutnim i sfernim vektorima. Sada slijedi detaljniji pregled svakog od ovih paketa, sa UML dijagramima razreda, te objašnjenjima.

System

Ovaj paket se sastoji od dvaju razreda, CSystem i CSystem::CCamera. Prvi razred enkapsulira računalni sustav i njegove ulazne jedinice. Stvaranje prozora za iscrtavanje se vrši direktnim pozivima Windows API-ja, dok se inicijalizacija crtaćeg konteksta ostvaruje OpenGL naredbama. Grafička kartica, predstavljena nekim programskim sučeljem poput OpneGL-a, se također može shvatiti kao jedinica unutar sustava. Razlikuje se faza inicijalizacije (stvaranje crtaćeg konteksta), faza aktivnog rada (opetovano iscrtavanje scene, određeni broj puta u sekundi), te faza deinicijalizacije i prekida rada (otpuštanje crtaćeg konteksta, oslobađanje memorije). Iz tog razloga, kao što se vidi na gornjem dijagramu, i funkcije upravljanja iscrtavanjem su podijeljene na te faze. Komunikacija s ulaznim jedinicama se ostvaruje pomoću DirectInput tehnologije, što je dio Microsoftovog DirectX skupa tehnologija. Reaktivnost aplikacije na ulazne podražaje (pritisci tipaka, pomaci miša) je ostvarena korištenjem paradigme vođene događajima (event driven paradigm). Naime, pojedine korisničke akcije su shvaćene kao događaji, te sustav detektira i identificira različite događaje korištenjem nekog sklopovskog sučelja niže razine (konkretno, DirectInput-a). Zatim, ti se događaji propagiraju kroz sustav posredstvom raspačivača (što je ovdje CSystem) tako da se pozivaju odgovarajuće funkcije rukovoditelji (event handlers). U općenitom slučaju, bilo koji objekt u aplikaciji može registrirati svoje rukovoditelje kod nekog objekta raspačivača, no u našem slučaju jedini raspačivač jest razred CSystem, a jedini rukovoditelj CSystem::CCamera (doduše, radi brzine izvođenja, provedena je optimizacija tako da se izbjegne dvostruko indirektni poziv, pa je tehnički gledano CSystem i raspačivač, i rukovoditelj). Kako se može naslutiti, razred CSystem::CCamera jest apstrakcija koncepta virtualne kamere, i sadrži podatke o položaju očišta (točka u kojoj se kamera nalazi), gledišta (točka fokusa kamere, odnosno „smjer gledanja“), te takozvani vektor prema gore, koji kazuje koji smjer je za kameru „gore“. Dakle, pritiscima tipaka i pomacima miša, moguće je pomicati pogled bilo gdje u sceni. Osim ove osnovne interaktivnosti, dozvoljeno je pomicati i točku izvora svjetlosti, i to tako da se ona rotira oko ishodišta za bilo koja dva kuta (θ, φ), pri čemu možemo reći da (θ, φ) zapravo predstavljaju sferne koordinate izvora svjetlosti. Konkretna izvedba rotacije projicirane funkcije upadnog svjetla je objašnjena u teorijskom izlaganju algoritma predizračunatog prijenosa zračenja, a implementirana je u CPRT razredu, koji je objašnjen kasnije u ovom tekstu. U ovom trenutku valja spomenuti da aplikacija podržava i klasično osvjetljenje Blinn-Phong lokalnim modelom, sklopovski dostupnim putem OpenGL-a. Budući da je podržano više od jednog istovremenog izvora svjetla, tipkama 1-8 se bira trenutno aktivno svjetlo (dakle, ono na koje se rotacija odnosi). Radi sklopovskog ograničenja na maksimalno osam istovremenih izvora svjetla, aplikacija ne podržava više od tog broja aktivnih svjetala, iako sam broj svjetala tek neznatno utječe na performanse iscrtavanja algoritmom PRT. Također, registriraju se i neke kontrole za olakšavanje testiranja programa. Sve navedene kontrole su pregledno dane sljedećom tablicom:

Tablica 1. Kontrole programa.

SceneManager

Sljedeći bitan skup razreda su CScene i CObject. Ova dva razreda redom predstavljaju enkapsulacije scene, te objekata scene. Iz tog razloga, aplikacija u pravilu treba instancirati samo jedan objekt tipa CScene. Konstruktor tog razreda automatski učitava zadanu ulaznu datoteku s opisom scene, te stvara potreban broj objekata, koje pohranjuje u internom spremniku. Sam postupak parsiranja .obj datoteka se delegira na novostvorene CObject objekte. Pojedini objekt scene je definiran svojim topološkim i geometrijskim podacima. Geometrijski podaci su jednostavno skup točaka koji definiraju poligone objekta, najčešće trokute, dok su topološki podaci logičke prirode. Naime, oni govore na koji način se prethodno definirane točke interpretiraju, odnosno, kojim redosljedom tvore poligone. Upravo ovakav pristup se koristi u .obj formatu, zato što omogućava da se vrhovi poligona zapišu samo jedanput, a zatim po potrebi dijele između susjednih poligona, čime se ostvaruje značajna ušteda na memoriji. Međutim, radi jednostavnosti kasnije obrade, vrhovi i poligoni se u CObject klasi ne pohranjuju odvojeno, već se točke jednostavno nižu onim redosljedom kojim tvore poligone, što znači da se većina njih ponavlja, i do nekoliko puta. Pojedini vrh je predstavljen strukturom CObject::SVertex, koja osim pozicije točke u prostoru pohranjuje i neke druge podatke vezane uz taj vrh, a to su koordinate teksture, boja, te koeficijenti projekcije funkcije prijenosa svjetlosti u sferne harmonike, u toj konkretnoj točki. Broj tih koeficijenata je limitiran na 16, budući da se pokazalo da je već i tako malen broj sasvim dovoljan za kvalitetne rezultate. Po potrebi, ovo se može i promijeniti, budući da nema nikakvog utjecaja na izvođenje samog algoritma (osim produljenja trajanja). Kako se može primijetiti, struktura za pohranu vrhova sadrži dva polja za pohranu boje. Razlog tomu je taj, što aplikacija podržava i klasično, lokalno osvjetljenje, i PRT osvjetljenje. Budući da je krajnji rezultat PRT algoritma boja pojedinog vrha, tu boju je potrebno pohraniti. No, boja utječe i na OpenGL-ov ugrađeni model osvjetljenja, pa je potrebno sačuvati bijelu boju za svaki vrh, i po potrebi alternirati između njih. Sam izvor svjetla je enkapsuliran CScene::SLight strukturom, koja pohranjuje sferne koordinate izvora, koeficijente izvorne projekcije funkcije osvjetljenja tog izvora, te rotirane koeficijente projekcije, koji su dobiveni rotacijom izvornih koeficijenata za kutove koji odgovaraju trenutnim sfernim koordinatama izvora. Izvorne koeficijente je potrebno sačuvati zato jer postupak rotacije opisan u prethodnom teorijskom izlaganju pretpostavlja apsolutnu rotaciju, a ne relativnu. Budući da je tokom izvršavanja aplikacije moguće tek dobivati relativne pomake između pojedinih iscrtavanja scene, ti relativni pomaci se moraju zbrajati. Zatim, izvorni koeficijenti projekcije se rotiraju za te zbrojene, apsolutne kutove.

PRT

Jezgra cijele aplikacije jest upravo razred CPRT. Naime, ovaj razred sadrži svu funkcionalnost potrebnu za provedbu algoritma predizračunatog zračenja. Glavne funkcije, koje ujedno čine javno sučelje razreda, su sljedeće:

void computeTransferFunctions(

CScene& Scene,

fpProgressCallback ProgressCallback,

bool FastMode

)

Ulazni argumenti:

Ova funkcija je zaslužna za predprocesiranje scene. Iz tog razloga, potrebno je prije njenog pozivanja imati izgrađen objekt scene. Sam postupak predprocesiranja može biti vrlo dugotrajan, stoga se omogućava objavljivanje napretka. U tu svrhu, upotrijebljen je mehanizam funkcije povratnog poziva (callback function). Naime, korisnik treba napisati vlastitu funkciju odgovarajućeg prototipa, i predati pokazivač na tu funkciju kao argument funkciji computeTransferFunctions. Tokom predprocesiranja, funkcija čiji je pokazivač predan će povremeno biti pozivana, točnije, prilikom svakih 1% obavljenog posla. Iz tog razloga, ovaj mehanizam se naziva povratnim pozivom. Generalno govoreći, očekuje se da će ta povratno pozivajuća funkcija obavještavati korisnika o napretku algoritma, primjerice, osvježavanjem nekog elementa grafičkog sučelja aplikacije i/ili tekstualnim ispisom. Upravo je to slučaj u ovoj aplikaciji, kako će biti objašnjeno kasnije. Posljednji argument funkcije specificira način obrade scene. Naime, kako je spomenuto u teorijskom izlaganju, funkcija prijenosa čija se projekcija računa za svaki vrh može biti različitog oblika. Ona može uključivati samo difuznu refleksiju, bez detekcije zaklonjenosti, ili se pomoću zrake sjene može dodatno utvrditi i da li je trenutni vrh u sjeni. Ovaj drugi način je očito sporiji, pa je za potrebe testiranja scene ili same aplikacije mnogo praktičnije preskočiti taj korak i značajno ubrzati obradu scene.

void computeLightFunctions(

CScene& Scene

)

Ulazni argumenti:

Ova funkcija također vrši projekciju u sferne harmonike, no ovaj put za svjetla. Budući da je za funkciju izlaznog isijavanja izvora uzeta konstanta, ovaj je postupak relativno jednostavan i brz. Geometrijske karakteristike scene nisu bitne, no podaci o svjetlima jesu, pa je potrebna referenca na objekt scene, koji sadrži podatke o svjetlima.

static void RotateSHCoefficients(

int numBands,

double* unrotatedCoeffs,

double* rotatedCoeffs,

double theta, double phi

)

Ulazni argumenti:

Izlazni argumenti:

Funkcija za rotiranje koeficijenata projekcije vrši prethodno opisan postupak rotacije. Prvo se rekurzivnim postupkom generiraju matrice za rotaciju oko Z i X osi, a zatim se one izmnože i time stvori konačna matrica rotacije. Množenjem izvornih koeficijenata s tom matricom dobiju se rotirani koeficijenti, koji se pohranjuju u spremnik čiji je pokazivač predan kao argument funkciji. Ova funkcija je deklarirana kao statička, iz razloga da se omogući njeno korištenje i bez instanciranja razreda kojemu pripada.

Ostali članovi razreda CPRT, koji sačinjavaju njegov privatni dio, su određene pomoćne funkcije koje nemaju svrhu same za sebe, već su potrebne za prethodne tri funkcije. U ovu skupinu spadaju metode za generiranje uniformnih uzoraka sfere, konstruiranje asociranih Legendre polinoma, evaluaciju funkcija sfernih harmonika u danoj točki, generiranje matrica rotacije oko Z i X osi, i slično. Implementacije tih metoda su direktno preuzete iz teorijskog izlaganja algoritma.

VectorMath

Posljednji, i najmanji paket se sastoji od dvaju razreda za olakšavanje računanja s vektorima, zadanih sfernim ili kartezijevim koordinatama. Njihovo javno sučelje jest identično, i uključuje često korištene operacije poput rotacije oko proizvoljne osi, normalizacije, skaliranja, skalarnog množenja itd. Zbog česte i raširene potrebe za vektorskom matematikom, ove operacije su enkapsulirane u zasebnom paketu, kojeg koriste svi ostali paketi.

*

*  *

Dizajn paketa i razreda programskog rješenja predstavlja njegovu logičku arhitekturu, čiji je pregled upravo dan. Fizički dizajn uključuje raspodjelu aplikacije u izvršne module i podatke. Budući da implementirani algoritam jasno razlikuje dvije odvojene faze – predprocesiranje i samo iscrtavanje – i programska podrška je fizički dizajnirana kao dvije odvojene aplikacije. Prva aplikacija se naziva SHBuilder, i služi za obradu scene i generiranje koeficijenata projekcije funkcije prijenosa. Druga aplikacija, koja se naziva SHDemo, učitava prethodno generirane koeficijente, i na temelju njih vrši iscrtavanje scene u stvarnom vremenu. Pritom obje aplikacije koriste iste, prethodno opisane pakete razreda. Jedina je razlika u tome što SHBuilder sadrži grafičko korisničko sučelje, za lakšu interakciju s programom. Iz tog razloga, umjesto paketa System, koristi se Microsoftova biblioteka MFC, koja omogućava jednostavniju izgradnju Windows aplikacija s grafičkim korisničkim sučeljem. Sada možemo na konkretnom primjeru pokazati korisnost prethodno objašnjenog mehanizma povratnog poziva – kako predprocesiranje scene napreduje, tako se osvježava ProgressBar kontrola (horizontalni stupac, inicijalno prazan, koji progresivno postaje sve ispunjeniji), te se ispisuje očekivano vrijeme trajanja obrade scene (na temelju trajanja obrade dotad obrađenog dijela scene). Budući da vrijeme procesiranja može biti dugotrajno (na Pentium IV 2.0 GHz računalu je trajalo otprilike tri sata za demonstracijsku scenu), u prilogu ovom radu se nalazi aplikacija s demonstracijskom scenom s već predizračunatim koeficijentima. Rezultati implementacije su u skladu s očekivanjima. Iz testiranja na nekoliko računala, osvjetljenje PRT algoritmom je tek oko 15%, do najviše 40% sporije nego osvjetljenje dobiveno ugrađenim OpenGL modelom osvjetljenja (pogledati donju tablicu). Valja imati na umu da je ovdje riječ o naivnoj implementaciji, koja direktno slijedi teorijske rezultate bez ikakvih optimizacija. Prvi korak koji bi svaka ozbiljna implementacija trebala poduzeti jest prebacivanje izračuna boje pojedinog vrha na grafičku karticu. Iako je ta operacija vrlo jednostavna, i sastoji se tek od 16 množenja i zbrajanja, takve operacije grafičko sklopovlje izvršava mnogo brže nego glavni procesor. Također, budući da će sve podatke o vrhovima pohranjivati i obrađivati grafička kartica, ne gubi se vrijeme na komunikaciju glavnog procesora i grafičke kartice. Osim toga, i postupak predprocesiranja scene se može barem djelomično implementirati nekim jezikom sjenčanja, i time značajno ubrzati. Optimizirane implementacije PRT algoritma bi zapravo lako mogle biti i brže od lokalnih modela osvjetljenja, ukoliko uzmemo u obzir situacije s više od jednog svjetla na sceni. Naime, konačna boja nekog vrha jest skalarni umnožak vektora koeficijenata tog vrha, i konačnog vektora koeficijenata osvjetljenja. Taj konačni vektor osvjetljenja se dobije kao zbroj vektora koeficijenata svih izvora. Taj se zbroj može izračunati jedanput, a zatim, ukoliko dođe do rotacije pojedinog svjetla, dovoljno je izračunati razliku u odnosu na nerotirano svjetlo, i taj vektor razlike pribrojiti ukupnom zbroju. Drugim riječima, kompleksnost izračuna boje danog vrha time postaje konstantna, uopće ne oviseći o broju svjetala. S druge strane, kod lokalnih modela osvjetljenja, za svako svjetlo se cjelokupan postupak računanja mora ponoviti. Sljedeća tablica ilustrira performanse (izražene u broju iscrtanih slika u sekundi) ove neoptimizirane implementacije, i dobro pokazuje da je upravo centralni procesor usko grlo:

Promatrajući generirane slike, do izražaja dolazi činjenica da algoritam računa boju po vrhu. Naime, prilikom kreiranja konačne slike, u postupku rasterizacije se mora odrediti boja svakog pojedinog slikovnog elementa. Budući da boju specificiramo po vrhovima, slikovni elementi koji upadaju na područja između pojedinih vrhova, nakon projekcije u prostor slike, imaju nedefiniranu boju. Jednostavno rješenje problema jest linearna interpolacija boje između dva susjedna vrha. No, to znači da ukoliko imamo nedostatan broj vrhova, diskretizacija će biti očita, budući da će zamjetno velika područja slike biti obojana istom bojom. To također znači da neće biti finih prijelaza osvjetljenja, već će biti vidljive grube razine. Primjer daje slika 27, nastala isključivanjem tekstura (usporedbe radi, ta je slika nastala u istovjetnim uvjetima kao slika 21).

Na sjeni koju baca torus, uočavaju se dvije razine – najtamnija, središnja sjena, koja se naziva umbra, te okolna, svjetlija sjena koja se naziva penumbra. Prijelaz između umbre i penumbre bi trebao biti gladak, no lako se mogu uočiti diskretne razine osvjetljenja, budući da su pojedini vrhovi koji su unutar umbre gotovo potpuno crni, no dijelovi poligona koji bi također trebali biti unutar umbre su sivi, budući da je boja tih slikovnih elemenata dobivena linearnom interpolacijom između vrha unutar umbre, i vrha unutar penumbre. Na sjeni koju torus baca na samog sebe, takvi artefakti su mnogo teže uočljivi, budući da se torus sastoji od 10800 jedinstvenih vrhova, dok se okolne plohe sastoje od svega 2700 vrhova. Međutim, ukoliko usporedimo ovu sliku sa slikom 21, koja je ista ali s uključenim teksturama, navedeni artefakti više uopće nisu vidljivi, budući da ih tekstura čini nezamjetnima. Također, današnje aplikacije već barataju i s mnogo većim brojem vrhova, tako da ovo zasigurno više nije problem.