Facultatea de Automatica si Calculatoare

Sectia Calculatoare

 

Randarea in timp real a multimilor de persoane

Introducere

"- Vreau sa vad o mie de iepuri albastri dansand in jurul unui foc de tabara!

- Nicio problema!"( Hargreaves, 2009)

Termenul de randare de multimi descrie procesul prin care se genereaza pe calculator imagini ale unor scene compuse dintr-un numar foarte mare de obiecte complexe din punct de vedere al geometriei si apropiate in spatiu.

Desi ideea de multime este in general corelata cu cea a unui grup de persoane, procesul de randare de multimi este de fapt agnostic de continut.

Intr-adevar, in cele mai multe dintre aplicatiile grafice, caracterele umane reprezinta principalul continut digital, dar exista si cazuri in care modele de flora, animale, sau alte entitati ce necesita un nivel sporit de detaliu in reprezentarea grafica fac subiectul unui proces de randare de multimi.

Observam in fiecare zi multimi de oameni - in statii de autobuz, in magazine, pe strada, etc. Prin urmare, atunci cand incercam sa simulam acelasi lucru intr-un mediu virtual, se impune sa mimam realitatea, astfel incat mediul creat si toate regulile sale sa fie modelate cat mai aproape posibil de lumea cunoscuta de noi. Aceasta este insa atat de complexa, incat in realitate, in mod normal, avem tendinta sa o observam in ansamblu, fara a acorda o atentie sporita detaliilor minore. In schimb, cand privim o multime generata de calculator, in care unele amanunte sunt omise, ne punem intrebarea 'de ce nu pare real?"

In ultimii ani in industria cinematografiei am putut vedea scene, reprezentand multimi de oameni, care ar fi fost imposibil de realizat in trecut prin metode clasice si care au reusit sa ofere un spectacol grandios publicului.

Crearea unei multimi inteligente, autonome, ai carei membri sa fie capabili sa gandeasca independent si sa reactioneze in mod interactiv este esentiala in prezent pentru industria efectelor speciale.

In figura I.1 sunt prezentate doua scene din trilogia 'The Lord of The Rings', in care multimi de aproximativ 20.000 de oameni au fost randate pe calculator pentru a prezenta scenele de razboi.

Randarea acestor scene a fost realizata intr-un mod neinteractiv, intr-o ferma de randare compusa - conform afirmatiei lui Joe Letteri (supervizor efecte speciale Weta Digital) - din aproximativ 200 de computere (USA Today, 2003).

Fig I.1 - Multimi generate neinteractiv - The Lord of The Rings (IMDB, 2009).

Desi ridica un set unic si vast de provocari, aducerea acestui tip de multimi in domeniul timpului real poate intensifica in mod considerabil nivelul de realism al unui mediu virtual in perceptia observatorului. In acest context, termenul de timp real se refera la o aplicatie care afiseaza cadrele reprezentand imaginea unei multimi in mod interactiv, oferind observatorului senzatia de continuitate a acestora. Trebuie avut in vedere insa faptul ca desi obiectivul principal pare a fi obtinerea unei frecvente a cadrelor care sa pacaleasca ochiul, asa cum am mentionat anterior, observatorul va fi foarte atent la detalii, iar sentimentul de imersiune in mediu va disparea imediat ce membrii multimii inceteaza sa mai para reali.

Necesitatea de interactivitate elimina unele posibilitati de optimizare care pot fi exploatate in cazul randarii neinteractive, cum ar fi coerenta cadrelor sau informatiile precalculate referitoare la lumini si vizibilitate, astfel incat trebuie luate in considerare alte metode pentru imbunatatirea timpului de procesare si de redare a scenelor.

In figurile I.2 si I.3 sunt reprezentate scene din jocuri video care contin peisaje cu o vegetatie abundenta si caractere afisate la un nivel mare de detaliu. Camera poate fi deplasata in scena, utilizatorul avand deplina libertate de miscare. Campul de vizualizare se deplaseaza, imaginea randata fiind actualizata in timp real.

Fig I.2 Overlord II PC (Gamespot, 2007)

Fig. I.3 - Empire Total War (Gamespot, 2009)

Aceste imagini au fost generate de sistem in mai putin de a 60-a parte dintr-o secunda pentru a putea da jucatorului impresia de miscare continua, reala.

Randarea in timp real a unor astfel de imagini reprezinta un subiect foarte solicitant pentru domeniul graficii pe calculator, intrucat impune cerinte foarte mari pe de o parte pentru dispozitivele hardware utilizate, iar pe de alta parte pentru designerii de continut digital, care au responsabilitatea de a crea colectii foarte mari si foarte variate de modele cu un nivel mare de detaliu, eventual animate, care sa satisfaca cerintele din ce in ce mai mari de realism al mediilor virtuale.

Un joc video 3D tipic creat pentru actualele computere si console de joc consuma majoritatea timpului disponibil de procesare pentru randarea scenelor. Scene ca cele prezentate anterior sunt formate din punct de vedere geometric din milioane de poligoane. Desi putem afisa, respectiv vizualiza mii de poligoane la o frecventa interactiva a cadrelor, pentru un numar de ordinul milioanelor de poligoane apar intarzieri intre cadre, ceea ce duce la scaderea calitatii experientei utilizatorului.

Exista o multitudine de materiale publicate pe tema optimizarii in randarea multimilor. In general, sunt utilizate patru clase de metode pentru accelerarea acestui proces: reprezentarea pe niveluri de detaliu, eliminarea suprafetelor ascunse, instantierea hardware si randarea bazata pe imagini.

Lucrarea de fata isi propune explorarea acestor metode de optimizare si implementarea unei aplicatii cu rol demonstrativ (proof-of-concept), avand ca suport noile platforme Microsoft .NET Framework 3.5 si Microsoft XNA Framework 3.0.

Aplicatia propusa reprezinta un motor de randare a unei multimi de persoane, cu capabilitati desigur reduse, prin care se doreste urmarirea evolutiei performantei pe de o parte din punct de vedere al tehnicilor implementate, iar pe de alta parte din punct de vedere al comportamentului aplicatiilor grafice ce ruleaza pe platforme managed(detin mecanisme automate de gestiune a memoriei).

In primul capitol va fi explorat sumar contextul in care ne regasim la momentul actual in industria aplicatiilor video si vor fi mentionate cateva motoare de randare deja existente. Capitolul II se axeaza pe conceptele teoretice care stau la baza aplicatiei propuse, continuandu-se cu capitolul III - in care aceasta este prezentata din punct de vedere conceptual - si cu capitolul IV, in care sunt descrise proiectarea arhitecturala si implementarea efectiva sistemului. In Capitolul V vor fi prezentate metricile de performanta luate in considerare in evaluarea aplicatiei si rezultatele obtinute, iar, pe baza acestora, in Capitolul VI va fi realizat un sumar al concluziilor si vor fi analizate posibilele directii pentru dezvoltarea ulterioara a proiectului.

Capitolul I
Contextul Actual

In acest capitol vor fi prezentate metodele utilizate in prezent pentru randarea de scene ample si foarte detaliate in timp real. In prima sectiune este prezentata o imagine de ansamblu asupra dispozitivelor hardware si a instrumentelor software utilizate in prezent; in cea de-a doua sectiune va fi descrisa banda grafica asociata procesului generic de randare, iar in ultima sectiune vor fi prezentate pe scurt doua dintre solutiile de randare actuale.

Hardware-ul grafic

Este evident ca atunci cand se discuta despre dispozitivele hardware in general si despre cele grafice in particular, contextul actual va fi considerat depasit intr-o perioada foarte scurta de timp, cel probabil de ordinul lunilor.

Cand comparam dispozitivele hardware grafice ale ultimei generatii cu dispozitivele hardware de actualitate, se observa o permanenta crestere a performantelor de randare. Aceste imbunatatiri sunt acompaniate in prezent si de o schimbare a principiilor de design a dispozitivelor grafice. In general, dispozitivele de randare grafica sunt sisteme hibride, compuse dintr-o unitate centrala de procesare si o unitate de procesare grafica ce comunica printr-o magistrala; unitatea de procesare grafica este utilizata in general strict pentru randare, unitatea centrala de procesare avand rolul de manevrare logica a aplicatiei - actualizarea starii animatiei, tratarea comenzilor primite de la utilizator, etc.

Fig. 1.1 - Imagine de ansamblu benzii grafice

In figura 1.1 este reprezentata structura benzii generale de asamblare a unei unitati de procesare grafica tipice. Liniile punctate reprezinta functionalitatile introduse de banda de asamblare programabila. Operarea unei unitati de procesare grafica poate fi, dupa cum se observa din aceasta figura, divizata in doua etape - procesarea la nivel de vertex si procesarea la nivel de pixel.

Un vertex este primitiva geometrica de baza in grafica pe calculator. El reprezinta un punct in spatiu si cu ajutorul lui sunt generate alte primitive - linii, poligoane.

O colectie de vertecsi si primitive poarta denumirea de mesh.

Termenul de fragment defineste unitatea primitiva de imagine generata de unitatea grafica; este corelat cu termenul mai general de pixel, insa acesta din urma descrie doar culoarea, pe cand un fragment poate avea si alte atribute, de exemplu adancimea.

Procesarea geometrica consta in transformarea vertecsilor in functie de pozitia observatorului si directia de vizualizare; este urmata de culling, decuparea (clipping) triunghiurilor si apoi de proiectia in spatiul 2D (viewport) pentru rasterizare.

Termenul de culling defineste procesul de remitere a anumitor componente geometrice care nu sunt vizibilie observatorului in scena finala.

Decuparea verifica daca triunghiurile ramase in scena se intersecteaza cu limitele ecranului si decupeaza partile exterioare volumului de vizualizare.

Rasterizarea tranforma vertecsii in fragmente si le stocheaza pe acestea intr-un buffer de fragmente.

Bufferul de cadre (frame buffer) este principalul buffer de fragmente care este prezentat utilizatorului la sfarsitul perioadei de randare. Cu cat mai repede poate fi randat un cadru, cu atat mai des imaginea scenei este actualizata in decurs de o secunda, ceea ce are ca rezultat impresia unei animatii fluide si reducerea latentei aplicatiei vis-à-vis de tratarea comenzilor utilizatorului.

Componentele hardware-ului grafic

Unitatea centrala de procesare

Unitatea centrala de procesare este reprezentata de un microprocesor de uz general, utilizat pentru executia oricarui tip de cod. Desi constituie un element sine qua non pentru modulul grafic al unui sistem, o prezentare detaliata a designului sau ar constitui o abatere de la subiectul lucrarii de fata, motiv pentru care ne vom rezuma doar la mentionarea sa.

Unitatea de procesare grafica

In comparatie cu unitatea centrala de procesare, unitatea grafica este un procesor specializat, ce ofera un model de programare bazat pe siruri de date (streams) si nuclee de procesare. Structura tipica a acesteia este prezentata in figura 1.2

Fig. 1.2 - Structura generica a unei unitati de procesare grafica

Un sir de date (stream) este definit ca un set ordonat de date de acelasi tip; nucleele de procesare efectueaza operatii simple pe elementele sirurilor de date si le transmit foarte rapid spre iesire.

In primele generatii de dispozitive grafice, procesoarele de geometrie si de fragmente erau hardwired[1], aceasta arhitectura purtand numele de banda de asamblare fixa (fixed pipeline). O banda de asamblare fixa detine o stare configurabila, ceea ce inseamna ca anumite parti ale sale pot fi activate/dezactivare sau usor modificate. Insa posibilitatile oferite de aceasta arhitectura sunt foarte reduse.

In timp, locul benzii fixe de asamblare a fost preluat de arhitectura de banda grafica programabila (programmable pipeline), prin inlocuirea procesoarelor hardwired cu unitati programabile. Desi mosteneste structura benzii de asamblare fixe, banda programabila de asamblare introduce unitati noi, menite sa ofere mai multa flexibilitate in anumite stadii ale randarii.

Este vorba in primul rand de unitatile programabile destinate executiei de programe shader. Termenul de shading este utilizat cu scop general pentru a defini modificari - de culoare, pozitie, etc - aduse primitivelor grafice la nivelul Unitatii Grafice de Procesare (si nu la nivelul Unitatii Centrale de Procesare), in timpul procesului de randare. Programele shader sunt insa inca restrictive in comparatie cu programele executate pe Unitatea Centrala de Procesare.

Un alt tip de unitate introdusa in banda grafica programabila este unitatea dedicata texturilor. In combinatie cu programe shader, cu ajutorul texturilor poate fi simulata o gama foarte larga de materiale din lumea reala. Combinatia dintre hartile de textura, programele shader si parametrii acestora poarta numele de material.

In mod evident, arhitectura actuala nu reprezinta un pas final in dezvoltarea Unitatilor Grafice de Procesare; enumerand cateva din placile video de top existente la momentul realizarii lucrarii de fata (Nvidia GeForce GTX 295, Asus Radeon HD4870 X2, Sapphire 1GB HD4870 GFX, etc.), asa cum am mentionat anterior, cel mai probabil acestea vor fi considerate depasite in decursul catorva luni.

La (Tom's Hardware, 2009) se gaseste un articol foarte interesant despre evolutia placilor video Nvidia, iar FiringSquad (FiringSquad, 2009) prezinta o istorie a dispozitivelor lansate de ATI ; ambele articole vin sa intareasca afirmatia anterioara referitoare la persistenta in linia de varf a dispozitivelor hardware grafice.

In Fig. 1.3 sunt prezentate cele mai vechi - in partea stanga - si respectiv cele mai noi - in partea dreapta - dispozitive hardware lansate de Nvidia (a) si ATI(b)

Fig. 1.3 - Dispozitive video Nvidia (a) si ATI (b)

Tendinta generala este in prezent abordarea de arhitecturi paralele si migrarea Unitatii de Procesare Grafica spre un procesor de uz general (GPGU). Posibilitatea de a realiza programe strict pentru Unitatile de Procesare Grafica ar deschide noi oportunitati pentru aplicatiile grafice - ar fi posibila de exemplu executia ray tracing in timp real, iar conceptul de stocare accelerata de Unitatea Grafica ar putea permite criptarea si comprimarea fisierelor pe loc; in plus, din punct de vedere conceptual, GPGU nu este restrictionat doar la sisteme si statii de lucru desktop - exista o perspectiva de multiprocesare si pe dispozitive mobile.

Un alt posibil scenariu este ca aceasta initiativa sa fie doar o masura provizorie pana la convergenta platformelor Unitatii Centrale de Procesare si Unitatii Grafice de Procesare. Asa cum afirma Tim Sweeney, 'in urmatoarea generatie, consolele ar putea consista dintr-un singur chip; ar putea fi un procesor de uz general evoluat dintr-o arhitectura de UCP sau UGP si ar putea executa orice - grafica, inteligenta artificiala, sunet - intr-o maniera omogena. Este o perspectiva foarte interesanta, pentru ca ar simplifica dramatic setul de instrumente si procese necesare in dezvoltarea aplicatiilor.' (ArsTechnica, 2009). Aceasta afirmatie orienteaza atentia spre proiectul Larabee al Intel, programat pentru lansare la inceputul lui 2010(Intel® Software Network, 2008). Este deci posibil ca o schimbare dramatica in arhitectura generala a procesoarelor sa fie foarte aproape, iar Unitatile Grafice de Procesare vor juca un rol important in aceasta schimbare.

Motoare de randare existente

In cele ce urmeaza vor fi prezentate pe scurt doua dintre cele mai comune motoare 3D open-source cu suport pentru randarea de multimi - OGRE3D si Horde3D. Este de mentionat ca in prezent, exista deja dezvoltate numeroase implementari de astfel de motoare utilizate in jocuri - printre care enumeram Gamebryo, Dunia Engine, Source Engine, Unreal 3, etc - dar acestea reprezinta tehnologii proprietare si nu sunt accesibile publicului general.

OGRE 3D

OGRE (Object-Oriented Graphics Rendering Engine) este un motor 3D flexibil, orientat pe scene, scris in C++ si cu o arhitectura intuitiva conceputa special pentru a fi usor de utilizat de dezvoltatori. Este in fapt o librarie de clase care abstractizeaza toate detaliile de utilizare a sistemelor de baza (OpenGL si Direct3D) si ofera o interfata bazata pe obiecte si clase intuitive. In Fig. 1.4 sunt prezentate doua scene complexe realizate cu OGRE3D.

Fig. 1.4 - Scene randate cu Ogre3D (Ogre3D, 2009)

Horde3D

Horde3D este, ca si OGRE3D, un motor de randare open-source. A fost scris, conform declaratiei dezvoltatorilor, cu scopul de a oferi efecte vizuale exceptionale fiind in acelasi timp cat se poate de compact si simplu din punct de vedere conceptual. Dispune de o interfata simpla si intuitiva accesibila teoretic din orice limbaj de programare si este in special potrivit randarii de multimi mari de caractere animate. In Fig. 1.5 sunt prezente capture de ecran din scene realizate cu Horde3D.

Fig. 1.5 - Scene randate cu Horde3D (Horde3D, 2009)

Capitolul II
Premise Teoretice

Datorita complexitatii sporite, randarea multimilor de persoane a fost un subiect intens studiat. Au fost dezvoltate numeroase metode cu scopul de a reduce overhead-ul in randarea unui numar mare de obiecte complexe din punct de vedere geometric.

Cum a fost precizat anterior, exista patru categorii majore de metode pentru optimizarea acestui proces: determinarea si eliminarea suprafetelor ascunse, instantierea, reprezentarea pe niveluri de detaliu si randarea bazata pe imagini.

In prima sectiune a acestui capitol vor fi prezentate cele mai importante abordari specifice fiecarei categorii de metode enumerate, urmand ca in cea de-a doua sectiune sa fie descrise si cateva din metodele de animatie a personajelor.

Metode de optimizare a proesului de randare

1. Algoritmi de eliminare a suprafetelor ascunse

In grafica 3D pe calculator, termenul de eliminare a suprafetelor ascunse (cunoscut si ca determinarea suprafetelor vizibile) defineste procesul utilizat pentru a decide care suprafete sau petice de suprafete nu sunt vizibile dintr-un anumit punct de observare (Wikipedia 2009) . Un algoritm de eliminare a suprafetelor ascunse reprezinta o solutie pentru problema vizibilitatii, care a fost una din primele probleme majore ale domeniului graficii 3D pe calculator. Procesul determinarii suprafetelor ascunse poarta uneori si numele de ascundere si un astfel de algoritm este numit ascunzator. Determinarea suprafetelor ascunse este necesara in primul rand pentru a randa corect o imagine, astfel incat observatorul sa nu poata vedea e lemente ascunse (de exemplu ce se afla in spatele unor pereti).

Exista numeroase metode de determinare a suprafetelor ascunse, ce difera prin modul de tratare a pasilor procesului de randare; printre acestea se numara: culling, buffer Z (de adancime), buffer de acoperire (Coverage buffer), buffer de suprafata (Surface buffer), utilizarea unei liste sortate de muchii active (SortedActiveEdgeList - utilizata in Quake I), algoritmul pictorului, partitionarea binara a spatiului, ray tracing, algoritmul Warnok, etc.

In sectiunile urmatoare vor fi detaliate metodele de culling si utilizarea bufferului Z.

Culling

In mod trivial, putem afirma ca una dintre cele mai eficiente metode de a imbunatati performanta procesului de randare a unei scene in grafica computerizata este de a nu randa toate obiectele din scena respectiva. Termenul de culling (triere) defineste o categorie de metode prin care se determina ce obiecte dintr-o scena trebuie desenate si ce obiecte pot fi remise fara a afecta imaginea prezentata observatorului. Cu alte cuvinte, obiectele care pot fi eliminate dintr-o scena sunt acele obiecte care nu sunt vizibile in scena randata la final. Acest concept a nutrit ani intregi de cercetare si dezvoltarea de numeroase tehnici utile in prezent.

Premisa de la baza acestui procedeu este de a determina daca un obiect geometric trebuie desenat inainte de a incepe desenarea efectiva a sa. Asadar, primul pas este de a defini obiectele ce urmeaza a fi testate. In cele mai multe cazuri, nu este fezabil din punct de vedere computational sa se testeze obiectul in sine, intrucat acesta poate sa fie un obiect geometric foarte complex; in schimb, este utilizata o reprezentare simplificata a acestuia, volumul de incadrare (bounding volume). Aceasta reprezentare poate lua forma unei sfere, a unui cub sau a unui alt corp 3D mai complex, cu restrictia ca acesta trebuie sa fie convex.

O sfera de incadrare se constituie dintr-un punct si o raza definite astfel incat sa cuprinda in intregime toate extensiile obiectului geometric pe care il reprezinta. Un astfel de model este foarte eficient in efectuarea de teste, dar nu si in determinarea extremitatilor obiectului. Sferele de incadrare se pot aplica cu o acuratete rezonabila in cazul in care incadreaza un obiect ale carui extremitati au dimensiuni similare (ex: obiecte cubice, cum ar fi cladiri, vehicule, motoare, etc). Totusi, ele dau o reprezentare foarte slaba in cele mai multe din cazuri, si anume atunci cand o singura dimensiune a obiectului este mult mai mare decat alta. De exemplu, sfera de incadrare a unui obiect alungit este mult mai mare decat extremitatile reale ale acestuia. Printre astfel de obiecte se numara copaci, creioane, stalpi, etc.

De notat este ca un castig mare de eficienta este inregistrat atunci cand mai multe obiecte apropiate ca pozitie in spatiu sunt grupate intr-o singura sfera de incadrare si testul de apartenenta se face cu o singura sfera, nu cu sferele individuale ale obiectelor din grup. Pentru aceasta, este recomandat ca obiectele din scena sa fie grupate ierarhic, cu informatia despre sfera de incadrare determinata la nivelul cel mai jos si propagata ascendent in arborele ierarhiei. Un test al sferei de incadrare al unui grup mai mare de obiecte poate determina rapid daca unul dintre obiectele componente trebuie testat, evitandu-se astfel testarea redundanta a fiecarui obiect in parte. Procesul recursiv de testare a sferei de incadrare poate continua pana la obiecte geometrice individuale.

Atunci cand este nevoie de un test mai precis al extremitatilor geometrice, se pot utiliza volume paralelipipedice de incadrare. Nivelul la care testele pe sferele de incadrare sunt inlocuite de teste pe paralelipiedele de incadrare poate fi bazat pe timpul acordat procesului de triere a obiectelor din scena sau poate fi fixat la un anumit prag. Este foarte important de mentionat ca timpul acordat procesului de triere trebuie sa fie bine balansat cu timpul de desenare. Un proces precis de triere care dureaza mai mult decat timpul alocat randarii unui cadru nu este foarte util. Pe de alta parte, o incheiere prematura a acestui proces va avea drept consecinta desenarea de geometrie in exces, ceea ce va afecta in mod direct frecventa cadrelor.

Volumele paralelipipedice de incadrare prezinta de asemenea cateva dintre problemele sferelor de incadrare. In particular, un astfel de volum, in cazul in care este orientat in mod gresit, poate avea aceeasi eroare in reprezentarea unui obiect cu forma alungita - o reprezentare slaba a obiectului, cauzand erori in procesul de triere. In (Cok, 2000) se gaseste un algoritm ce isi propune sa rezolve in mod eficient problema determinarii volumelor de incadrare.

Backface Culling

Eliminarea fettelor ascunse reprezinta cea mai triviala forma de a simplifica randarea unei scene. Ea are la baza observatia ca daca toate obiectele din scena sunt inchise, atunci poligoanele a caror fata nu este orientata spre observator nu pot fi vazute de catre acesta.

Interpretarea geometrica se rezuma la calculul unghiului dintre directia de observatie si normala la suprafata poligonului: daca unghiul format de acesti doi vectori este mai mare de 90°, adica produsul scalar este strict pozitiv, atunci poligonul poate fi eliminat.

Este important de mentionat ca semnificatia acestui produs scalar este inversata atunci cand observatorul se gaseste in interiorul unui obiect. Posibilitatea ca punctul de observare sa patrunda in interiorul unui obiect trebuie tratata in toate cazurile in care directia normalei este relevanta.

Fig 2.1 - stanga: observatorul se gaseste in afara camerei; dreapta : observatorul este in interior (GameDev, 2009).

Avantajul acestei metode este obtinerea unei cresteri importante a vitezei de randare, intrucat testul este simplu, consumul de resurse computationale fiind minim, iar procentul de poligoane eliminate se ridica la aproximativ 50%.

Fig 2.2 - stanga: tor cu toate fetele desenate; dreapta: tor cu fetele ascunse eliminate

Totodata, aceasta metoda este usor de implementat in dispozitivele hardware, motiv pentru care se regaseste in dispozitivele grafice din prezent si este expusa de setul lor de functii.

Pentru utilizarea acestei metode intr-o aplicatie XNA, se utilizeaza proprietatea CullMode a obiectului RenderState asociat dispozitivului grafic, conform SC.2.1

SC 2.1 - Utilizarea proprietatii CullMode a obiectului RenderState

In ciuda avantajelor enumerate anterior, trebuie avut in considerare faptul ca aceasta metoda nu reprezinta o solutie completa de optimizare a procesului de randare, ci este utilizata in general in conjunctie cu un algoritm mai specific de determinare a suprafetelor ascunse.

View Frustum Culling

Una din cele mai simple si naive forme de culling este reprezentata de ViewFrustumCulling(trierea volumului de vizualizare). La baza acestei metode sta faptul ca doar obiectele aflate in volumul de vizualizare curent pot fi efectiv vazute de observator, deci doar acestea trebuie desenate.

Volumul de vizualizare este definit in general de 6 plane, si anume planele de decupare fata, spate, stanga, dreapta, sus, jos, care formeaza un trunchi de piramida. Planurile fata si spate trebuie definite ca planul in care se afla observatorul, respectiv ca un plan aflat la o distanta "infinita".

Obiectele geometrice din scena sunt etichetate in acest context ca total-interioare, total-exterioare sau partiale vis-à-vis de volumul de vizualizare.

Obiectele geometrice care se gasesc in totalitate in exteriorul volumului de vizualizare pot fi remise in siguranta.

Obiectele geometrice etichetate ca fiind total in interiorul volumului de vizualizare trebuie desenate, in cazul in care nu sunt remise intr-un alt pas al procesului de triere.

Obiectele care se regasesc partial in interiorul volumului de vizualizare pot fi impartite in cele doua portiuni formate de intersectia cu planul volumului de vizualizare care le sectioneaza, caz in care va fi redata doar portiunea interioara, sau pot fi adaugate in intregime la lista de obiecte interioare, decuparea fiind facuta de unitatea grafica la randare.

In varianta naiva a acestui algoritm, fiecare obiect din scena este testat fata de cele 6 planuri, acest calcul avand o complexitate asimptotica de O(n) in cazul mediu, ceea ce inseamna ca viteza de executie a sa creste liniar cu numarul obiectelor din scena.

O exemplificare a implementarii acestui algoritm poate fi analizata in SC.2.2

SC 2.2 - Exemplu de implementare naiva a Frustum Culling

Beneficiul maxim al trierii volumului de vizualizare este dat de o metoda ierarhica de triere, prin care spatiul scenei este divizat recursiv in subspatii, intr-o structura de arbore, fiecare obiect din scena fiind atribuit unui astfel de subspatiu.

Astfel, analog algoritmului de testare a volumelor de incadrare, testele pornesc din radacina ierarhiei, fiind eliminate testele redundante: daca un subspatiu este etichetat ca total-exterior, atunci toate subspatiile sale sunt implicit total-exterioare, deci pot fi remise in siguranta.

In implementarea acestei metode sunt utilizati de obicei arbori binar, cvadrali sau octali .

Fig 2.3 - Stanga: descompunerea unui arbore cvadral; dreapta: descompunerea recursiva a unui cub in octanti si arborele octal asociat (GameDev, 2009)

Un exemplu de implementare si utilizare a descompunerii in arbori octali va fi prezentata si in capitolul III, in sectiunea dedicata descrierii claselor aplicatiei.

Occlusion Culling

Occlusion Culling (trierea suprafetelor ocluzionate) reprezinta procesul prin care se determina care obiecte din volumul de vizualizare sunt vizibile observatorului. Doar obiectele care nu se gasesc in spatele unor obiecte mate sunt vizibile in forma finala a scenei randate.

Obiectele care sunt vizibile se numesc obliteranti, iar cele blocate poarta denumirea de obliterati. Determinarea setului optimal de obliteranti reprezinta scopul unui algoritm de triere prin ocluziune. Obiectele din acest set optimal sunt singurele obiecte care trebuie desenate si toate celelalte obiecte pot fi eliminate.

O metoda de triere prin ocluziune este utilizarea volumelor de incadrare ierarhice in conjunctie cu un buffer de adancime hardware. Scena este sortata intr-o ordonare neprelucrata fata-spate si toate obiectele geometrice din scena sunt marcate ca potentiali obliteranti.

Sortarea in adancime este necesara pentru a profita de efectul natural de vizibilitate - cand un obiect apropiat obstructioneaza de obicei observarea unui obiect mai indepartat. Volumele de incadrare ale fiecarui obiect sunt randate in ordine, iar bufferul de adancime este comparat cu bufferul de adancime obtinut anterior. Daca bufferul de adancime isi schimba valoarea intre desenarea a doua obiecte, atunci primul obiect este vizibil, nefiind ocluzionat. Daca in schimb valoarea bufferului nu se modifica, obiectul nu va fi vizibil, deci poate fi eliminat.

Fig. 2.4 - Efectul combinat al Frustum Culling si Occlusion Culling (GameDev, 2009)

Este de mentionat faptul ca in cazurile in care in scena nu exista obiecte transparente, aceasta metoda se reduce la metoda bufferului Z.

Contribution culling

O alta metoda prin care se pot tria obiectele pentru randarea unei scene este realizata prin eliminarea obiectelor care sunt destul de mici pentru ca absenta lor din scena sa nu fie observata.Aceasta metoda, numita ContributionCulling (triere prin contributie), ia o decizie binara de a desena sau nu un obiect in functie de numarul de pixeli acoperiti de obiect in spatiul scenei. Un obiect care ocupa doar cativa pixeli in acest spatiu poate fi eliminat in siguranta, impactul asupra intregii scene fiind minim.

Aceasta metoda poate fi aplicata in cazul obiectelor aflate la o distanta foarte mare de observator sau al obiectelor care sunt foarte mici in comparatie cu intreaga scena.

Algoritmul de Contribution Culling poate fi utilizat concomitent cu algoritmul deOcclusion Culling, intrucat, in mod evident, obiectele foarte mici nu reprezinta obliteranti buni.

Un model de implementare a acestui algoritm este prezentat in SC 2.3 :

SC 2.3 - Exemplu de implementare a Contribution Culling

Algoritmul Z-Buffer

Utilizarea bufferului Z (sau depth buffer) reprezinta o modalitate consacrata de a determina vizibilitatea unui pixel in procesul de randare.

Bufferul Z este un buffer de dimensiunile bufferului de cadre, in care se inregistreaza adancimea corespunzatoare fiecarui pixel randat. Atunci cand se solicita randarea unui pixel pentru a doua oara - ca in cazul in care doua obiecte se suprapun in scena - bufferul Z fie va pastra valoarea retinuta anterior, fie o va inlocui cu valoarea noua. Determinarea valorii care trebuie pastrata poarta numele de test de adancime (depth test) si se realizeaza printr-o functie ce este apelata de fiecare data cand un pixel este randat; daca pixelul trece testul de adancime, atunci culoarea sa este scrisa in render target si adancimea sa este inregistrata in bufferul de adancime.

Adancimea unui pixel este determinata pe baza dimensiunilor matricelor de vizualizare si de proiectie selectate pentru randare. Un pixel care atinge planul apropiat al proiectiei are adancimea 0, iar unul care atinge planul indepartat are adancimea 1. Pe masura ce fiecare obiect din scena este randat, sunt pastrati acei pixeli care sunt mai apropiati de camera. In fig. 2.5 este reprezentata o scena simpla si vizualizarea ei in niveluri de adancime.

Fig. 2.5 - Vizualizarea adancimii pixelilor intr-o scena 3D (Wikipedia, 2009)

De obicei, in asociere cu bufferul de adancime se utilizeaza inca un tip de buffer, si anume un stencil buffer. Un stencil buffer este similar cu bufferul de adancime - in aplicatiile XNA chiar utilizeaza o parte din acesta; dar in plus, permite utilizarea unei functii care sa testeze o valoare globala de referinta la momentul randarii unui pixel. Rezultatul acestei functii va determina daca adancimea pixelului randat va fi scrisa in bufferul de adancime si culoarea sa va fi scrisa in render target. Stencil buffer-ul poate fi utilizat in operatii mai sofisticate insa - pot fi specificate actiuni (StencilOperation) mai complexe decat inlocuire/incrementare/decrementare pentru a fi executate dupa fiecare test cu rezultat pozitiv si se poate utiliza o masca (StencilMask) pentru a asigura ca testele opereaza doar pe o portiune a stencil buffer-ului.

Formatul bufferului de adancime defineste, in contextul unei aplicatii XNA, compozitia acestuia ; bufferul de adancime are intotdeauna 32 de biti, dar acestia pot fi organizati in moduri diferite. Printre formatele mai des intalnite se numara Depth32 - toti cei 32 de biti sunt utilizati pentru informatia de adancime, Depth24Stencil8 - 24 biti sunt utilizati pentru calcularea adancimii si 8 sunt utilizati de stencil buffer, sau Depth28Stencil8Single - cei 24 de biti utilizati pentru informatia de adancime sunt organizati ca un numar in virgula mobila.

Pentru a utiliza un buffer de adancime intr-o aplicatie XNA, se utlizeaza proprietatea DepthBufferEnable a obiectului RenderState - pentru a activa/dezactiva utilizarea bufferului, si proprietatea DepthBufferFunction pentru a specifica functia de comparatie utilizata in testul de adancime. In SC. 2.4 este prezentat un exemplu de utilizare a bufferului de adancime intr-o aplicatie XNA.

SC. 2.4 - Utilizarea bufferului de adancime

2. Instantierea hardware

In procesul de randare a unor scene complexe si in particular a unei multimi, este necesara randarea mai multor copii ale unui acelasi model de baza. Apelurile necesare pentru randarea unui model sunt relativ costisitoare din punct de vedere al timpului de executie si au un impact foarte mare asupra performantei aplicatiei atunci cand se doreste desenarea unui numar mare de entitati.

Ideea de instantiere hardware se refera la metoda de utilizare a dispozitivelor hardware pentru a genera varfuri transformate, cu scopul de a reduce numarul de cereri de desenare efectuate de unitatea centrala catre unitatea grafica - practic, pentru a desena acelasi model, dar cu anumite proprietati modificate, de mai multe ori, printr-un singur apel catre API-ul unitatii grafice.

In procesul de instantiere hardware, doua siruri de vertecsi sunt trimise catre unitatea de procesare grafica: unul din siruri contine setul initial de vertecsi, iar al doilea sir transmite informatiile de instantiere - concret, fiecare pozitie in care trebuie desenata fiecare instanta a setului de vertecsi (fluxul de date este reprezentat in Fig.2.6). Astfel, orice obiecte complexe din punct de vedere geometric ce folosesc acelasi set de efecte pot si trebuie desenate simultan, printr-un singur apel de desenare catre unitatea grafica de procesare.

Exista mai multe tehnici de instantiere hardware si desi niciuna nu poate fi considerata perfecta, fiecare din ele poate reduce semnificativ timpul de calcul necesar unitatii centrale de procesare pentru a desena modelele.

Totusi, in unele cazuri, utilizarea acestor tehnici poate avea un efect nesemnificativ asupra performantei generale a aplicatiei sau chiar determina o crestere a costului pentru unitatea grafica.

Timpul necesar unitatii centrale pentru desenarea unui model este independent de complexitatea modelului, insa costul de procesare la nivelul unitatii grafice creste proportional cu numarul de triunghiuri ce formeaza modelul si cu dimensiunea si complexitatea programului de shader. Intuitiv, in cazul desenarii de modele simple performanta va fi cel mai probabil limitata de unitatea centrala de procesare, pe cand in cazul desenarii unor modele complexe unitatea grafica va constitui elementul limitator.

In cazul in care unitatea grafica este cea supraincarcata, aplicarea unei tehnici de instantiere hardware nu va aduce niciun beneficiu performantei generale a aplicatiei ; de asemenea, daca modelele sunt foarte complexe, overhead-ul de memorie necesar instantierii hardware poate fi prohibitiv. Instantierea hardware aduce cel mai mare castig de performanta in cazul utilizarii pentru modele relativ simple, compuse din 1000 de triunghiuri sau mai putin.

Instantierea hardware presupune un anumit mod de organizare a datelor despre vertecsi si indecsi.

Fara a utiliza instantiere hardware, pentru fiecare instanta activa a modelului se seteaza proprietatile dispozitivului grafic si se apeleaza metoda DrawIndexedPrimitives(). O exemplificare in cod este prezentata in SC 2.5

SC 2.5 - Randarea scenei folosind apeluri individuale DrawIndexedPrimitives pentru fiecare element

In continuare vor fi prezentate tehnicile utilizate in prezent pentru instantierea obiectelor din scena.

Instantiere Hardware (Hardware instancing) - Windows, Shader 3.0

In aceasta tehnica, instantierea este realizata in totalitate pe unitatea grafica, motiv pentru care unitatea centrala de procesare are un grad de incarcare extrem de mic indiferent de numarul de instante desenate.

Poate fi aplicata doar in aplicatii realizate pentru platforme Windows si necesita un dispozitiv grafic capabil sa interpreteze programe shader versiunea 3.0.

In randarea conventionala neindexata, fiecare set de trei indici formeaza un triunghi. Indicii sunt utilizati pentru a efectua o cautare intr-un vertex buffer in care sunt stocate informatii cum ar fi pozitia, normala sau coordonatele de textura.

Diagrama din figura 2.6 prezinta structurile de date utilizate la randarea unui model simplu de dreptunghi - alcatuit din doua triunghiuri specificate prin sase varfuri si patru vertecsi, fara a utiliza o tehnica de instantiere.

Fig. 2.6 - Reprezentarea structurilor si a fluxului de date utilizate la desenarea a doua primitive (Nguyen, 2008)

In procesul de instantiere hardware nu este nevoie de modificarea acestor structuri de date, ci doar de adaugarea unei noi surse de informatie. Aceasta va fi reprezentata de un nou vertex buffer in care vor fi stocate matricile de transformare asociate fiecarei instante in parte. Acest buffer va avea o dimensiune egala cu numarul de instante ce vor fi desenate printr-un singur apel (nu este obligatoriu sa aiba dimensiunea vertex buffer-ului original) si va fi actualizat cu fiecare cadru, prin apelarea metodei SetData().

Pentru a transmite ambele buffere in programul shader, trebuie modificat obiectul VertexDeclaration utilizat astfel incat sa includa datele aditionale: se seteaza pe dispozitivul grafic primul vertex buffer, ce contine informatiile de geometrie si apoi al doilea vertex buffer, ce contine matricile de transformare (analog SC.2.6)

SC. 2.6 - Adaptarea VertexDeclaration pentru instantierea hardware (MSDN, 2009)

Diagrama din fig. 2.7 prezinta fluxul de date realizat pentru desenarea a doua copii ale aceluiasi model utilizand instantiere hardware.

Fig. 2.7 - Reprezentarea structurilor si a fluxului de date utilizate pentru Hardware Instancing (Nguyen, 2008)

Datele utilizate pentru a desena prima instanta sunt reprezentate in albastru, iar cele utilizate pentru a doua instanta sunt reprezentate cu verde. Este de notat faptul ca perechile de triunghiuri (0,1) si (2,3) utilizeaza aceiasi indecsi pentru a adresa datele din vertex buffer insa folosesc cate o matrice diferita din al doilea vertex buffer.

Instantiere Shader (Shader Instancing) - Windows, Shader 2.0

Tehnica prezentata anterior (hardware instancing) pare sa fie solutia ideala, insa este dezavantajata de faptul ca necesita dispozitive hardware ce suporta programe shader 3.0 si in prezent acestea nu au o raspandire foarte larga.

Prin shader instancing se obtine un castig similar de performanta ca si in cazul instantierii hardware, insa intr-un mod compatibil cu dispozitivele hardware ce pot executa doar cod shader 2.0 si cu un necesar mai mare de memorie.

Ideea care sta la baza acestei tehnici este realizarea unor copii ale datelor de geometrie si stocarea lor consecutive in vertex buffer si in index buffer; astfel, este posibila desenarea mai multor copii ale aceluiasi model printr-un singur apel, doar prin specificarea unui numar mai mare de triunghiuri pentru functia DrawIndexedPrimitives(). In plus, pentru a determina ce instanta deseneaza la un moment dat, programul shader va mai necesita un canal de date in care sunt specificati indecsii instantelor. In functie de indexul din acest canal de date, shaderul va selecta matricea de transformare corespunzatoare pentru desenarea fiecarei instante. In figura 2.8 este prezentat fluxul de date corespunzator operatiilor descrise:

Fig.2.8 - Reprezentarea structurilor si a fluxului de date utilizate pentru Shader Instancing (Nguyen, 2008)

Datele utilizate pentru prima instanta sunt marcate cu albastru, iar cele utilizate pentru a doua instanta cu verde. Se observa ca vertex buffer-ul contine doua copii ale aceluiasi set de pozitii, normale si texturi, insa indexate diferit.

Limitarile majoreale acestei metode sunt date de numarul de registri de constante shader disponibili pentru a pastra matricele de transformare si de dimensiunea limitata a valorilor de index (16 biti), care in consecinta restrictioneaza numarul de instante ce pot fi desenate intr-un singur apel.

O posibila implementare a unei metode ce deseneaza o lista de modele utilizand aceasta tehnica este prezentata in S.C. 2.7

S.C. 2.7 - Exemplu de implementare a tehnicii shader instancing

Instantiere VFetch (VFetchInstancing) - Xbox360

Aceasta metoda este specifica platformei Xbox 360 si are ca avantaj fata de tehnicile de tehnica prezentata anterior faptul ca nu mai sunt replicate si datele din VertexBuffer, ci doar cele din IndexBuffer, multumita posibilitatii de a utiliza o semantica HLSL proprie Xbox360, prin care se poate cere ca valoarea bruta a indexului sa fie transmisa catre vertex shader. In Fig. 2.9 este prezentat fluxul de date utilizat pentru aceasta tehnica.

Fig. 2.9 - Reprezentarea structurilor si a fluxului de date utilizate pentru VFetchInstancing (Nguyen, 2008)

In continuare, ca o concluzie, in tabelul T 2.1 este realizata o comparatie a tehnicilor prezentate in aceasta sectiune.

T 2.1  - Comparatie a tehnicilor de instantiere

3. Reprezentarea pe niveluri de detaliu

Gestionarea nivelurilor de detaliu (Level of Detail - sau prescurtat, LOD) reprezinta o metoda care este la fel de relevanta si in prezent ca si acum peste treizeci de ani, cand a fost definita. In ciuda dezvoltarii uimitoare a dispozitivelor hardware grafice, tensiunea dintre viteza si realism vizual continua sa se faca resimtita.

Complexitatea modelelor create de artistii vizuali - definita prin numarul de primitive ce le construiesc, pare sa creasca mai rapid decat capacitatea dispozitivelor grafice de a le randa. Indiferent de cat de mare este capacitatea de procesare si randare, intotdeauna pare ca numarul de primitive ce trebuie desenate depaseste numarul de primitive pe care sistemul le poate randa in mod interactiv. De exemplu, in Fig. 2.10 este prezentata o imagine a modelului digital scanat al statuii lui David, care este constituit din aproximativ 56 de milioane de poligoane - ceea ce reprezinta un numar foarte mare chiar si pentru dispozitivele grafice actuale de top (Luebke, 2003).

Fig. 2.10 - Imagine a modelului digital scanat al statuii lui David (Luebke, 2003 p.4)

In acest context, reprezentarea in niveluri de detaliu reprezinta o tehnica vitala pentru aplicatiile grafice in timp real ; in ultimul deceniu s-au realizat numeroase proiecte de cercetare si dezvoltare in jurulproblemei simplificarii obiectelor in scopul obtinerii unei reprezentari cat mai realiste, rezultatul fiind o suita vasta de algoritmi, mecanisme si metrici. In prezent, domeniul a atins un oarecare nivel de maturitate si avem la dispozitie un set de algoritmi, fiecare cu avantajele sale - unii sunt mai simpli, unii mai rapizi, iar altii reusesc simplificari foarte realiste ale modelelor. Acesti algoritmi sunt divizati in trei categorii principale : reprezentarea in niveluri discrete de detaliu, reprezentarea in niveluri continue de detaliu si reprezentarea dependenta de vizualizare.

Reprezentarea pe niveluri discrete de detaliu

Aceasta este abordarea traditionala a reprezentarii in niveluri de detaliu. Schema originala a fost propusa de James Clark in 1976 si a fost si inca este utilizata intr-o multitudine de aplicatii grafice. In aceasta abordare se creaza multiple variante ale aceluiasi model, fiecare corespunzatoare unui anumit nivel de detaliu intr-o faza de preprocesare. In timpul executiei, pentru fiecare model se selecteaza nivelul de detaliu corespunzator si se deseneaza varianta asociata. Intrucat variantele modelului sunt precalculate, procesul de simplificare nu poate prezice din ce directie va fi vizualizat obiectul, motiv pentru care simplificarea trebuie realizata uniform pe model ; din acest motiv, aceasta abordare mai poarta si numele de nivel de detaliu izotropic (sau independent de vizualizare).

Schema de niveluri discrete de detaliu prezinta numeroase avantaje, insa cel mai important este dat de simplitatea algoritmului. Un exemplu de implementare a acestui tip de reprezentare va fi prezentat in Capitolul IV, in sectiunea de descriere a componentelor aplicatiei.

Reprezentarea pe niveluri continue de detaliu

Aceasta metoda are la baza abordarea initiala dar difera de aceasta prin faptul ca in loc sa creeze hartile nivelurilor de detaliu in stadiul de preprocesare, sistemul pastreaza o structura de date ce codifica un spectru continuu de detaliu. Apoi, in timpul executiei, nivelul solicitat de detaliu este extras din aceasta structura de date.

Avantajul major al acestei abordari este dat de o granularitate mai fina, intrucat nivelul de detaliu este specificat cu precizie pentru fiecare obiect, si nu selectat dintr-o serie de modele preprocesate.

O implementare a acestei reprezentari a fost incercata in Microsoft MDX 2.0, prin clasa ProgressiveMesh, bazata pe cercetarile efectuate de Hugues Hoppe (Hoppe, Jovan Popovic, 1997), insa in noua platforma XNA s-a renuntat la aceasta.

In Fig. 2.11 este redata o imagine extrasa din (Hoppe, 1997), in care sunt prezentate variatii ale unui mesh progresiv in functie de numarul de varfuri desenate.

Fig. 2.11 - Variatii ale unui mesh progresiv (Hoppe, 1997).

4. Randarea bazata pe imagini

Randarea bazata pe imagini se refera la un set de tehnici si reprezentari care permit scenelor 3D sa fie vizualizate intr-un mod realist fara sa realizeze o reconstructie totala a modelelor 3D din scena.

Acest set de tehnici este foarte amplu- o prezentare detaliata poate fi analizata in (Shum, Chan, Kang 1999) - motiv pentru care prezentarea din aceasta sectiune se va rezuma la descrierea pe scurt a tehnicii utilizate in aplicatia propusa in urmatorul capitol, si anume utilizarea impostorilor.

Un impostor afiseaza un personaj ca un poligon texturat, in cazul cel mai general un dreptunghi, care este intotdeauna orientat cu normala pe directia de vizualizare. Coordonatele de textura pentru acesto poligon se modifica in functie de pozitia actuala a camerei. In cazul modelelor animate, acestea se vor schimba si in functie de cadrul curent de animatie. In cele mai multe dintre abordarile bazate pe impostori este necesar un stadiu de preprocesare, in care se realizeaza un set discret de imagini ce definesc modelul de randat - un exemplu este prezentat in figura 2.12.

Fig. 2.12 - Reprezentarea diferitelor ipostaze ale unui impostor in imagini.

Avantajul acestei metode este dat de simplitatea modelelor - practic se deseneaza doua poligoane texturate pentru fiecare din personaje, ceea ce inseamna ca practic se pot randa peste un milion de caractere pe o unitate video nu foarte avansata.

Exista totusi si un dezavantaj in sensul realismului vizual oferit de o scena in care personajele sunt randate pe baza de imagini.

In primul rand, apare in senzatia ca suprafete sunt plane ; iar daca acest inconvenient este depasit prin utilizarea unor metode mai avansate de texturare (de exemplu parallax mapping), atunci intervine problema continuitatii cadrelor in cazul in care se schimba unghiul de vizualizare a personajului - dupa cum am precizat anterior, imaginile utilizate prezinta un set discret de ipostaze ale personajului, motiv pentru care interschimbarea acestora poate fi observabila cand personajul se afla in prim-plan.

Din acest motiv, aceasta metoda este utilizata in general in corelatie cu o reprezentare pe niveluri de detaliu, impostorii fiind afisati in planurile mai indepartate, unde este necesar un nivel redus de detaliu, fiind inlocuiti apoi pe masura apropierii de camera cu modele mai complexe.

In Fig 2.13 sunt reprezentate doua imagini ale aceleiasi scene - copacii sunt randati utilizand modele geometrice complete - in partea stanga, respectiv impostori - in partea dreapta. Conform (Intel® Software Network , prima scena este randata la 3FPS, iar a doua la 90FPS. Dupa cum demonstreaza aceste valori, randarea bazata pe impostori este o tehnica esentiala de optimizare in cazul scenelor complexe.

Fig. 2.13 -Randarea unei scene utilizand modele geometrice complete si impostori (Intel® Software Network, 2008)

Animatia personajelor

Exista doua tipuri principale de animatie: animatia scheletului (skeletal animation) si animatia in cadre cheie (keyframed animation), fiecare din acestea prezentand o serie de avantaje si dezavantaje.

Animatia in cadre cheie

Pentru acest tip de animatie se pastreaza cate un model de mesh static corespunzator fiecarui cadru al animatiei. De exemplu, pentru a anima modelul din figura2.14, ar trebui realizate si incarcate in aplicatie cinci modele diferite, pentru ca in bucla de randare sa se determine si sa se deseneze modelul corespunzator cadrului cheie curent - cu gri sunt prezentate componentele modelului care trebuie modificate in fiecare cadru. Este important de mentionat ca in acest tip de animatie este nevoie numai de cadrele cheie, deci numai acestea sunt exportate din instrumentele de design si utilizate in aplicatie. De exemplu, in figura 2.14, mai pot exista numeroase alte cadre intermediare intre primul si al doilea cadru de animatie, cu rolul de a face animatia mai fluenta ; acest efect poate fi obtinut insa si prin alte metode in timpul executiei aplicatiei, cum ar fi interpolarea cadrelor - prin interpolarea liniara a pozitiilor fiecarui vertex intre acestea.

Fig 2.14 - Cadrele corespunzatoare animatiei unui om in mers (Grootjans, 2008)

Avantajul major al acestei tehnici de animatie este dat de viteza de calcul - intrucat nimic nu trebuie efectiv calculat in timpul animatiei ; toate elementele animatiei sunt incarcate la initializarea aplicatiei si stocate in memorie, iar in timpul executiei mai este necesara doar selectarea modelului desenat la momentul curent.

Dezavantajul este dat insa din consumul mare de memorie in situatiile in care scena este alcatuita din obiecte cu animatii complexe, pentru care este necesara stocarea modelelor. In concluzie, pentru scene cu un numar foarte mare de obiecte care au elemente de animatie comune aceasta tehnica se poate dovedi foarte eficienta.

Animatia scheletului

Un alt mod de a realiza animatia unui model este prin animarea scheletului acestuia, tehnica ce se bazeaza pe deformarea realista a mesh-urilor. Intr-o animatie de acest tip, fiecare vertex poate fi atribuit unui numar de maxim patru articulatii (bones) ale scheletului, acestea reprezentand transformari ierarhice. Fiecare astfel de asociere vertex-articulatie are atribuita o pondere. De exemplu, fiind dat un vertex care apartine antebratului unui caracter uman, acesta poate fi asociat cu articulatia cotului cu o pondere de 0.5 si cu articulatia incheieturii cu aceeasi pondere de 0.5, astfel incat acest vertex se va deforma realist odata cu cele doua articulatii. Pentru aceasta, trebuie construit un schelet (o ierarhie de oase) care sa poata fi asociat modelului prin conectarea fiecarui os din ierarhie la vertecsii corespunzatori din mesh (Grootjans, 2008) . Trebuie mentionat ca o animatie a scheletului este in fond tot o animatie bazata pe cadre cheie si pe interpolarea acestora in timpul executiei - informatia necesara animatiei este stocata sub forma de cadre cheie care definesc transformarile aplicate asupra articulatiilor la anumite momente de timp.

Pentru a construi un model cu schelet animat pot fi utilizate diverse instrumente de design (3DsMax, Maya, MotionBuilder, Blender, etc), din care modelele pot fi exportate intr-un format suportat de XNA - formatele suportate native sunt X (DirectX) si FBX (Autodesk). In fig.2.15 este prezentat modelul utilizat de RenderX, vizualizat in MotionBuilder.

Fig.2.15 - Model vizualizat in MotionBuilder

Animatia scheletului are numeroase avantaje in comparatie cu animatia in cadre cheie. In primul rand permite multiplexarea animatiilor; de exemplu, pentru modelul utilizat ar putea fi executate in acelasi timp mai multe animatii : una care face caracterul sa se deplaseze (mers), una care ii determina miscarea capului, a mainilor sau a oaselor faciale, etc. De asemenea, permite conectarea oaselor unui schelet cu oase dintr-un alt schelet, astfel incat cele doua obiecte sa se miste in acelasi timp (un exemplu evident este cazul in care un caracter tine un obiect in mana si miscarea mainii trebuie sa determine miscarea obiectului).

Dezavantajul este dat insa faptul ca multiplicarea matricilor este realizata de unitatea centrala de procesare - ceea ce poate constitui un bottleneck, intrucat operatiile pe matrici sunt costisitoare - si in plus sunt utilizati toti parametrii de program shader, ceea ce face imposibila aplicarea unei metode de instantiere in unitatea grafica de procesare.

In prezent acest tip de animatie este utilizat mai des decat animatia simpla in cadre cheie; implementarea sa XNA va fi prezentata mai detaliat in capitolul IV .

Capitolul III
Conceptul unui sistem de randare de multimi

Prezentare generala

Jocurile video reprezinta unul din cele mai comune domenii in care sunt necesare motoare de randare in timp real. Luand in considerare spre exemplu un joc de curse de masini sau unul de razboi, ne putem imagina scene foarte complexe, ce cuprind modele geometrice detaliate (oameni, arme, masini, etc.) si cadre inconjuratoare bogate. In plus, acestea sunt insotite de alte efecte grafice, cum ar fi lumini, reflexii, umbre, sisteme de particule. Cu toate acestea, in timp ce scenele sunt randate, observatorul se poate deplasa in scena intr-un mod natural, simuland urmarirea autoturismului, respectiv a unui personaj din multime. Pentru a realiza senzatia de miscare naturala - a da jucatorului impresia de raspuns imediat la comenzi, este nevoie de o schimbare rapida a pozitiei camerei si a obiectelor in scena, ceea ce face intregul proces de randare mai complex si, implicit, mai dificil.

Pe langa randare insa, mai exista o serie de operatii care trebuie executate in timpul jocului, cum ar fi procesarea comenzilor si actualizarea starii jocului in functie de acestea, simularea unor procese fizice, executarea unor algoritmi de inteligenta artificiala (in cazul jocului impotriva unor oponenti) sau detectia si tratarea coliziunilor.

Considerand cele precizate anterior, in cazul unui motor de randare de multimi (cum ar fi cazul scenei de razboi mentionate), putem sumariza responsabilitatile ce trebuie avute in vedere:

Gestiunea structurilor de date ce contin modelele ce trebuie reprezentate in scena (atat obiectele multimii cat si elementele mediului inconjurator).

Randarea modelelor geometrice foarte detaliate

Randarea unui numar mare de modele de detaliu scazut (elemente cum ar fi portiuni de teren, cerul, etc.).

Randarea de efecte speciale, cum ar fi umbre si reflexii.

Distribuirea eficienta a procesorului intre procesul de randare si cel de executie a logicii jocului.

Balansarea nivelului de incarcare intre Unitatea Grafica de Procesare si Unitatea Centrala de Procesare.

Cerinte si obiective

In cele ce urmeaza vor fi detaliate principalele obiective si cerinte ale sistemului propus.

Performanta

Performanta unui sistem grafic de randare in timp real este dificil de estimat si masurat in mod obiectiv intrucat sufera variatii foarte mari in functie de continutul si de scopul aplicatiei.

Poate fi luata in considerare totusi o valoare ce ofera o estimare generala a performantelor unui sistem: capacitatea de procesare.

Avand in vedere ca un motor de randare are o arhitectura de banda de asamblare, capacitatea sa este data de cantitatea de date pe care o poate procesa intr-o unitate finita de timp. Aceasta este intotdeauna limitata de cel mai lent stadiu al benzii de asamblare - numit si bottleneck.

O performanta buna este in mod evident un obiectiv important al unui sistem de randare in timp real, insa este dificil de specificat in mod exact ca o cerinta, din cauza numarului mare de factori ce influenteaza comportamentul sistemului.

Portabilitate

Portabilitatea reprezinta un subiect ce trebuie tratat in cazul general al implementarii unui sistem software. Intr-o situatie ideala, orice sistem software ar putea fi compilat si rulat independent de platforma, insa situatia reala este complet diferita.

O motivatie mai detaliata a selectarii modului de implementare va fi realizata in capitolul urmator. Pentru moment, trebuie mentionat ca sistemul propus este implementat in C#, avand ca suport platformele Microsoft XNA si .NET Framework 3.5, motiv pentru care poate fi compilat si rulat doar pe PC-uri pe care sunt instalate cele doua platforme sau pe console Xbox 360.

Functionalitate

In realizarea designului motorului de randare trebuie sa fie luate in considerare un numar mare de tehnici - deja existente si des intalnite - de optimizare a procesului de randare pentru a obtine performantele unui sistem in timp real.

Motorul va trebui sa fie capabil sa gestioneze in mod eficient modelele din multime, instantierea si individualizarea acestora - prin modificarea materialelor sau a cadrelor de animatie - si apelurile de functii de desenare catre Unitatea Grafica de Procesare. Vor fi nicesare si efecte speciale pre si post-procesare (umbre, etc).

RenderX

RenderX a fost conceput si dezvoltat pentru a analiza si demonstra capabilitatile unui motor de randare construit intr-un limbaj managed.

Profitand de facilitatile oferite de platformele utilizate, RenderX are structura unei aplicatii bazate pe sablonul Plugin (Shalloway, Trott, 2004), fiind construit dintr-un set de componente atasate modulului principal de executie. Arhitectura sistemului va fi prezentata in detaliu in capitolul urmator, ce vizeaza implementarea efectiva a motorului de randare.

Dintre metodele prezentate in capitolul II, RenderX le implementeaza si utilizeaza pe urmatoarele :

Backface Culling

View Frustum Culling

Contribution Culling

Z-buffer

Instantiere Hardware

Skinning

Animatie

Reprezentarea nivelurilor de detaliu

Fiind un proiect de cercetare, RenderX a fost conceput ca un prototip cu rol demonstrativ pentru metodele prrezentate in capitolul anterior si nu ca un motor de randare complet functional.

Arhitectura si implementarea sa efectiva vor fi detaliate in urmatorul capitol.

Capitolul IV
Proiectarea si implementarea sistemului

In acest capitol vor fi descrise instrumentele utilizate pentru implementarea RenderX, arhitectura adoptata si componentele aplicatiei

Intrucat a fost aleasa utilizarea unor instrumente mai putin conventionale pentru domeniul aplicatiilor grafice, in prima sectiune a capitolului va fi prezentata o motivatie a acestei alegeri.

In cea de-a doua sectiune va fi prezentat modelul general al unei aplicatii, urmand ca in celelalte sectiuni sa fie prezentate arhitectura si implementarea efectiva a RenderX, modul de executie a acestuia si modalitatile de utilizare.

Motivatia alegerii C# si XNA

Exista numeroase discutii, in special pe forumuri de specialitate (GameDev, XNA Creators, etc.) referitoare la diferentele dintre C++ si C# in contextul dezvoltarii aplicatiilor grafice si in general, dupa cateva replici se ajunge la un razboi al limbajelor lipsit de sens, in care practic nu este atacat C# in mod direct ca limbaj, ci este atacata ideea de cod managed pentru aplicatii grafice.

Luand in considerare insa evolutia limbajelor de programare, asemenea polemici aveau loc si in perioada in care C a inlocuit Assembler sau cand C++ a inlocuit C ; si totusi, chiar si in prezent, la mai mult de 20 de ani de la dezvoltarea C++ de catre Bjarne Stroustroup, in multe din aplicatiile grafice este utilizat tot C, fara sa se profite la maxim de facilitatile oferite de C++ si unele din motoarele populare de jocuri (de exemplu Quake sau Half-Life) sunt scrise in cod care seamana mai mult cu C decat cu C++ .

In prezent, programatorii C++ sunt sceptici in ceea ce priveste eficienta C# in special in dezvoltarea de jocuri si alte aplicatii grafice cu cerinte critice de performanta.

Totusi, abordand o perspectiva obiectiva, in contextul actual al industriei software, trebuie luati in considerare mai multi factori in decizia asupra limbajului utilizat:

Costul de dezvoltare

Dimensiunea proiectului si ciclurile de dezvoltare

Functionalitatile aplicatiei

Usurinta de gasire si instruire a dezvoltatorilor

Performanta

Daca dimensiunile unui proiect sunt relative ample si planificarea dezvoltarii acestuia este stransa, C++ devine o optiune mult mai slaba decat C#.

Un argument tipic - si foarte puternic - in acest sens este dat de faptul ca in C# memoria este managed, mecanismul de GarbageCollection asigurand evitarea celor mai multe probleme legate de eliberarea resurselor de memorie, in timp ce in C++ problemele legate de memorie sunt dificil de depistat si rezolvat.

Platforma XNA pune la dispozitie de asemenea o serie de elemente de baza reutilizabile, ceea ce se traduce intr-un castig de timp de dezvoltare.

Compromisul apare insa prin sacrificarea de performanta.

Totusi, daca diferenta de performanta nu este observabila si nu afecteaza calitatea programului, este mai eficienta, in mod evident, alegerea celei mai simple abordari, prin aplicarea cunoscutului algoritm al strutului : 'stick your head in the sand and pretend there is no problem at all' (Tanenbaum 2002).

In prezent, sistemele de calcul dispun Unitati Centrale de Procesare si Unitati Grafice de Procesare foarte performante, ceea ce face ca diferenta intre programele C# si programele C++ sa fie minore in cele mai multe dintre situatii.

Dupa cum afirma Benjamin Nitschke: "Intotdeauna sa iti amintesti, atunci cand intalnesti persoane care iti spun ca C++ este superior si ca C# este pentru incepatori, ca acelasi lucru s-a intamplat cu Assembler si C++ cu cativa ani in urma si ca in viitor vor exista limbaje noi care sa ne faca viata mai usoara si unii oameni vor ezita in continuare sa le adopte. " (Nitschke, 2007), exista o tendinta generala, nu numai in industria dezvoltarii de aplicatii grafice ci in industria software in general, de a pastra o reticenta fata de limbajele noi de programare motivata prin teama de a nu avea penalitati mari de performanta sau de a renunta la vechile librarii si componente.

In Tabelul T4.1 este prezentata o schema realizata de Benjamin Nitschke pentru a arata diferentele dintre DirectX cu C++ si Managed DirectX (precursorul Microsoft XNA) in C#.

Se poate observa ca in Managed DirectX codul are pe jumatate dimensiunea codului unmanaged. I

In XNA codul este chiar mai scurt si mai simplu, insa o comparatie precisa cu Managed DirectX ar fi dificila, din cauza diferentelor conceptuale existente intre cele doua platforme.

Pentru incepatori, invatarea C# si XNA este un proces mai rapid si mai usor decat in cazul C++ si DirectX sau OpenGL, luand in considerare strict cunostintele de limbaj - alte cunostinte necesare dezvoltarii aplicatiilor grafice nu fac subiectul lucrarii de fata.

T4.1 - Comparatie intre codul C++ si codul C# pentru incarcarea unei texturi (Nitschke, 2007)

Cod C++ (DX9)

Cod C# (MDX)

LPDIRECT3D9 g_pD3D = NULL; LPDIRECT3DDevice9 g_pd3dDevice = NULL; LPDIRECT3DVERTEXBUFFER9 g_pVB = NULL; LPDIRECT3DTEXTURE9 g_pTexture = NULL; [] if(NULL == (g_pD3D = Direct3DCreate9(D3D_SDK_VERSION))) return E_FAIL; D3DPRESENT_PARAMETERS d3dpp; ZeroMemory(&d3dpp, sizeof(d3dpp)); d3dpp.Windowed = TRUE; d3dpp.SwapEffect = D3DSWAPEFFECT_DISCARD; d3dpp.BackBufferFormat = D3DFMT_UNKNOWN; d3dpp.EnableAutoDepthStencil = TRUE; d3dpp.AutoDepthStencilFormat = D3DFMT_D16; if(FAILED (g_pD3D->CreateDevice( D3DADAPTER_DEFAULT, D3DDEVTYPE_HAL, hWnd, D3DCREATE_SOFTWARE_VERTEXPROCESSING, &d3dpp, &g_pd3Device))) g_pd3Device->SetRenderState( D3DRS_CULLMODE, D3DCULL_NONE); g_pd3Device->SetRenderState( D3DRS_LIGHTING, FALSE); g_pd3Device->SetRenderState( D3DS_ZENABLE, TRUE); if(FAILED(D3DXCreateTextureFromFile( g_pd3Device, 'banana.bmp', &g_pTexture)))

Device device = null; VertexBuffer vertexBuffer = null ;  Texture texture = null; public void InitializeGraphics()

In concluzie, urmatorii factori pot fi decizionali in alegerea limbajului de implementare :

Penalitatea de performanta

Planificarea si bugetul alocat proiectului

Cerinte de portabilitate (trebuie luat in considerare ca programele XNA pot fi rulate si pe Xbox, insa sunt limitate, in cazul PC-urilor la platforme Windows, pe cand alte programe nu pot fi rulate pe Xbox dar pot oferi o flexibilitate mai mare in cazul PC-urilor).

Complexitatea proiectului si necesitatea de scalabilitate

Resursele umane alocate proiectului si timpul disponibil pentru instruire.

Modelul unei aplicatii XNA

In aceasta sectiune vor fi prezentate conceptele generale prezente intr-o aplicatie XNA.

Framework-ul XNA este compus din trei unitati esentiale:

Motorul grafic XNA - Microsoft.Xna.Framework.dll

Modelul de aplicatie XNA - Microsoft.Xna.Framework.Game.dll

Content Pipeline - Microsoft.Xna.Framework.Content.Pipelin.dlls

Fig. 4.1 - Componentele Platformei XNA (Lobao, 2008)

Toate aceste librarii sunt scrise in C# si sunt complet gestionate, ceea ce inseamna ca pot fi explorate cu unelte de reflectie[4].

Fiecare proiect XNA are ca punct de pornire o clasa ce mosteneste din clasa de baza Game si mentine o lista a componentelor, dispozitivul grafic, setarile ferestrei, obiectul responsabil pentru gestiunea continutului, etc. Aceasta clasa poate fi vazuta ca o radacina a arborelui aplicatiei.

Cele mai importante metode utilizate de clasa Game (si implicit de clasele care mostenesc din aceasta) sunt cele prezentate in SC 4.1 :

SC 4.1 - Metodele clasei Game

In metoda Initialize trebuie efectuata logica de initializare - incarcare a continutului, citirea setarilor si initializarea tuturor componentelor necesare.

Metoda Update este apelata inainte de desenarea fiecarui cadru si in cadrul ei trebuie efectuata logica de actualizare - actualizarea timpului global, tratarea comenzilor primite de la utilizator, actualizarea starii aplicatiei, etc. Daca aplicatia ajunge intr-o stare in care este limitata de Unitatea Grafica de Procesare, atunci metoda Update va fi apelata mai frecvent decat metoda Draw, motiv pentru care logica trebuie separata total intre aceste doua metode - in Update nu trebuie sa existe logica de desenare si in Draw nu trebuie sa existe logica de actualizare.

In plus, la o aplicatie XNA pot fi adaugate componente - clase care mostenesc din clasa de baza GameComponent si care ajuta la realizarea unei arhitecturi modulare, ce respecta sablonul Plugin; fiecare componenta poate fi inregistrata in radacina aplicatiei si metodele sale Update si Draw vor fi apelate automat la fiecare ciclu de randare. Astfel componentele pot fi gestionate dinamic si aplicatia devine mai flexibila.

Modelul de executie al unei aplicatii tipice XNA este reprezentat in Fig. 4.2

Fig. 4.2 - Modelul de executie al unei aplicatii XNA

Content Pipeline

Banda de asamblare pentru continut este utilizata pentru a importa, compila si incarca diverse resurse externe, cum ar fi texturi, modele 3D, programe shader, fisiere de sunet, de font, de efecte, etc, reducand considerabil numarul de linii de cod necesare pentru initializarea aplicatiei - sunt folosite obiecte content importer care proceseaza automat si compileaza toate datele necesare intr-un fisier binar (la compilarea aplicatiei) iar in timpul executiei incarca respectivul fisier si ofera acces la aceste date stocate.

Fig. 4.3 - Model de importare a unei resurse prin intermediul ContentPipeline (Carter, 2008)

Componenta ContentPipeline este alcatuita din cinci librarii (Cawood, McGee 2007)

Microsoft.Xna.Framework.Content.Pipeline.dll - contine functiile de baza pentru Content Pipeline

Microsoft.Xna.Framework.Content.Pipeline.EffectImporter.dll - este utilizata pentru a compila si importa programe shader.

Microsoft.Xna.Framework.Content.Pipeline.FBXImporter.dll - este cea mai complexa dintre librarii si ofera suport pentru incarcarea de modele 3D in format .fbx, pentru skinning, animatii, etc.

Microsoft.Xna.Framework.Content.Pipeline.TextureImporter.dll - este utilizata pentru importarea texturilor - fie fisiere in format .dds fie in alte formate : .png, .jpg, .bmp, .tga

Microsoft.Xna.Framework.Content.Pipeline.Ximporter.dll - permite importarea modelelor 3D in format .x - un format comun aplicatiilor DirectX.

In plus, pot fi create procesoare de continut individualizate, care permit compilarea oricarui alt tip de resursa in fisiere .xnb.

In Figura 4.4 este reprezentata banda de asamblare XNA pentru procesul de randare.

Fig 4.4 - Stadiile procesului de randare in aplicatiile XNA

Arhitectura RenderX

In stabilirea arhitecturii proiectului am urmarit utilizarea cat mai eficienta si intr-o maniera cat mai eleganta a instrumente oferite de platformele XNA si Microsoft .NET.

Astfel, am abordat o structura de aplicatie bazata pe componente si am alcatuit doua librarii de clase - AnimatedContentPipeline.dll si AnimatedModel.dll, si o aplicatie executabila, aplicatia principala - RenderX. (Fig. 4.5)

Fig. 4.5 - Componentele principale ale RenderX

Banda de asamblare a continutului si biblioteca model

XNA nu suporta in mod nativ modele cu schelet animat si desi banda implicita de asamblare a continutului este capabila sa importe astfel de modele, procesorul standard de resurse este limitat la procesarea mesh-ului si scheletului, ignorand informatia relevanta pentru animatie.

Din acest motiv, pentru a putea realiza animatia scheletului unui model, este necesara extinderea acestui modul pentru a adauga suport in acest sens.

In Fig. 4.6 este prezentata o diagrama sumara a componentelor utilizate pentru importarea, procesarea, compilarea si interpretarea fisierelor in care sunt stocate modele.

Fig 4.6 - Schema componentelor benzii de asamblare a continutului

Intr-o prima faza, modelele sunt importate de modulul corespunzator formatului fisierelor in care sunt stocate. Rezultatul acestei operatii este un obiect NodeContent - un obiect ce descrie un tip grafic ce detine un sistem propriu de coordonate si o lista de descendenti - care poate pastra ca descendenti un obiect MeshContent si un obiect BoneContent.

Obiectul NodeContent este apoi prelucrat de o instanta a clasei ModelProcessor intr-un obiect ModelContent care contine informatiile procesate despre model ; acestea vor fi stocate intr-un fisier binar .XNB.

Pentru a putea scrie acest fisier, obiectul ModelContent si fiecare tip de membru al acestuia trebuie sa aiba asociat un obiect ContentTypeWriter care defineste cum anume vor fi scrise (stocate) informatiile referitoare la tipul respectiv in fisier.

Analog, in timpul executiei, obiectul ContentManager va utiliza un obiect ContentTypeReader pentru fiecare tip de date pentru a citi informatiile din fisierul .XNB si a returna obiectul Model stocat.

Componentele si fluxul procesului descris sunt reprezentate schematic in Fig. 4.7.

Fig. 4.7 - Procesul de citire a modelelor (Nitschke, 2007)

Dupa cum am precizat anterior, pentru a obtine informatia referitoare la animatia modelului, aceasta banda de asamblare trebuie extinsa prin adaugarea unui nou procesor de modele capabil sa interpreteze si sa stocheze intr-un mod transparent datele respective.

Este necesara de asemenea crearea unor clase care sa abstractizeze si sa prelucreze aceasta informatie, precum si implementarea unor obiecte ContentTypeWriter si ContentTypeReader capabile sa gestioneze noile tipuri de date.

In Fig. 4.8 sunt reprezentate schematic componentele si flow-ul noului proces de asamblare; modificarile aduse modelului initial sunt marcate cu rosu.

Fig. 4.8 - Procesul de citire a modelelor, adaptat pentru modele animate.

Clasele utilizate pentru a incapsula obiectele stabilite ca necesare in noul proces de importare a modelelor animate sunt cele prezentate in Fig. 4.9.

Fig 4.9 - Clasele librariei AnimatedContentPipeline.dll

Clasa AnimatedModelProcessor extinde clasa ModelProcesseor implementand si procesarea informatiilor de animatie din modelul importat prin suprascrierea functiiei Process.

Clasele AnimationClipWriter, KeyframeWriter si AnimationDataWriter extind, dupa cum se observa din Fig. 4.9 clasa generica ContentTypeWriter<> cu tipurile AnimationClip, Keyframe respectiv AnimationData; asa cum am mentionat anterior, acestea reprezinta obiecte care scriu instante ale tipurilor asociate in fisierele binare .xnb. Scrierea se face la apelul de catre sistem, atunci cand se doreste scrierea unui tip, a metodei Write definita in clasa asociata.

In plus, pentru fiecare astfel de tip trebuie definit un tip omolog pentru citirea datelor din formatul binar compilat. Pentru a asocial unui tip un alt ContentTypeReader decat cel standard, trebuie suprascrisa metoda GetRuntimeReader in clasa care extinde ContentTypeWriter.

In C.S 4.2 este exemplificata implementarea unui astfel de obiect, si anume clasa KeyframeWriter.

C.S 4.2 - Implementarea clasei KeyframeWriter

Pentru a putea utiliza modelele animate procesate de noul processor de modele, se defineste o librarie de model ce contine clasele care incapsuleaza structurile de date necesare manipularii acestora. Diagrama de clase a librariei de model este prezentata in Fig.4.10

Fig. 4.10 - Diagrama de clase pentru libraria model.

Clasele AnimationClipReader, KeyframeReader si AnimationDataReader reprezinta corespondentele claselor AnimationClipWriter, KeyframeWriter si respective AnimationDataWriter din componenta procesorului de modele, fiind deci utilizate pentru a citi structurile de date din fisierul compilat in format binar .xnb. Se observa ca toate aceste clase extind clasa generica ContentTypeReader<> ; citirea datelor se realizeaza in corpul metodei Read, care va fi apelata de sistem de fiecare data cand este necesara citirea unor structuri de date asociate tipului corespunzator clasei din fisierul .xnb.

Clasa Keyframe constituie un container pentru datele ce definesc un cadru cheie al unei animatii (conform metodei de animatie a scheletului unui model prezentata in Capitolul II); aceasta expune in exterior o matrice de transformare, indicele articulatiei asupra careia trebuie aplicata aceasta transformare, precum si durata cadrului definit.

Clasa AnimationClip incapsuleaza o animatie, alcatuita dintr-o lista de cadre cheie - instante ale clasei Keyframe.

Clasa AnimationData incapsuleaza informatiile de animatie continute de un model - o lista de obiecte AnimationClip, doua matrici de transformare si o lista in care este retinuta iararhia de articulatii.

Clasa AnimationPlayer este responsabila de calcularea transformarilor de aplicat fiecarei articulatii pe baza animatiei obieactului si a momentului de timp (mai exact a intervalului de timp scurs de la pornirea animatiei), prin apelarea metodei Update() - aceasta calculeaza momentul de timp relativ al animatiei si atribuie fiecarei articulatii transformarile definite de cadrul cheie cel mai recent. Aceste transformari sunt apoi transmise ca parametri catre shader in apelul functiei Draw.

Aplicarea efectului de animatie intr-un program shader este prezentata in SC.4.3.

SC 4.3 - Calcularea transformarilor corespunzatoare unui cadru de animatie intr-un program HLSL

RenderX

Componenta RenderX reprezinta de fapt aplicatia principala a proiectului, continand referinte catre cele doua librarii descrise in sectiunea anterioara.

Intrucat platforma XNA pune la dispozitie posibilitatea de a organiza o aplicatie intr-un set de componente si servicii, conform sablonului Plug-in, am putut profita de acest beneficiu in definirea structurii RenderX.

Componentele reprezinta in XNA clase care mostenesc clasa de baza GameComponent. Orice instanta a clasei Game detine in mod standard o lista de instante ale acestor clase, iar la initializare, actualizare si desenare (metodele Initialize, Update si Draw) apeleaza metodele corespunzatoare ale fiecareia din instante.

Pentru a realiza o componenta care are si comportament de desenare, este necesara mostenirea din clasa DrawableGameComponent(MSDN, 2009).

Avantajul utilizarii componentelor este dat de faptul ca acestea pot fi manevrate dinamic in timpul executiei - pot fi eliminate/adaugate din lista de componente ale instantei clasei Game intr-un mod foarte simplu si transparent, prin apelarea metodelor Remove, respectiv Add pe lista de componente active Components.

Serviciile reprezinta un mecanism prin care se mentine o cuplare slaba intre obiectele de uz general ale aplicatiei si prin care acestea sunt puse la dispozitia tuturor componentelor intr-un mod omogen - prin mediatorul Game.Services. (MSDN, 2009)

Pentru RenderX s-a stabilit necesara construirea a cinci componente independente, prezentate in Fig. 4.11, dintre care doua reprezinta servicii - Camera, respectiv Meniu.

Fig. 4.11 - Componentele si Serviciile RenderX

Decor

Aceasta componenta, dupa cum sugereaza si numele sau, este responsabila pentru desenarea decorului scenei; in cazul aplicatiei implementate, aceasta realizeaza desenarea cerului. Am ales metoda unui skybox in pofida unui skydome din considerente de performanta. Desi un Skydome prezinta avantajul posibilitatii de a realiza mai multe straturi de efecte si de a anima texturile, crescand realismul vizual al scenei, acesta necesita o structura mai complexa, cu un numari mai mare de primitive ; iar din moment ce proiectul nu este focalizat pe acest aspect, solutia unui skybox - care este mult mai usor de construit si este randat mai rapid, fiind compus doar din douasprezence triunghiuri - este mult mai eficienta. In figura 4.12 sunt prezentate schematic clasele utilizate de aceasta componenta.

Fig. 4.12 - Clasele componentei Decor

Clasa SkyBoxModel incapsuleaza informatiile utile efectiv pentru desenarea cerului - texturi, pozitii, etc, iar clasa SkyBox este cea care extinde clasa DrawableGameComponent.

Teren

Aceasta componenta are ca scop desenarea terenului in scena; in stadiul actual al proiectului terenul este o simpla suprafata plana texturata, insa pentru o eventuala dezvoltare ulterioara aceasta componenta poate fi usor inlocuita sau extinsa, in cazul in care se doreste realizarea unui teren cu o suprafata mai complexa. Analog componentei Decor, componenta este constituita din doua clase, prezentate in Fig. 4.13; clasa TerrainModel incapsuleaza datele referitoare la teren, iar clasa Terrain extinde clasa DrawableGameComponent.

Fig. 4.13 - Clasele componentei Teren

Camera

Aceasta componenta este responsabila pentru gestionarea camerei in aplicatie. Intrucat toate celelalte componente ale aplicatiei necesita date prelucrate de aceasta componenta (in principal matricea de vizualizare, matricea de proiectie, pozitia camerei in scena, etc.), ea este publicata si ca un GameService, definind drept contract interfata ICamera. Structura interfetei ICamera si a clasei care o implementeaza, Camera, este prezentata in Fig. 4.14. Diverse moduri de implementare a unei camere sunt descrise in (Grootjans, 2008). In implementarea actuala, utilizatorul are posibilitatea de a roti camera si a o deplasa camera pe cele trei axe.

Fig. 4.14 - Contractul ICamera si clasa care il implementeaza, Camera

Meniu

Aceasta componenta este responsabila pentru interceptarea si gestionarea comenzilor primate de la dispozitivele de intrare (tastatura/mouse) pe parcursul executiei aplicatiei. Intrucat si celelalte componente ale aplicatiei trebuie informate cu privire la comenzile primite de la utilizator, si aceasta componenta, analog componentei Camera, este publicata ca un GameService, prin contractul definit de interfata ImenuManager. Prin aceasta se expune o singura metoda - IsKeyPressed - care poate testa daca o anumita tasta a fost (si eventual este inca) apasata in pasul anterior al buclei de executie.

Structura celor doua elemente ale componentei Meniu este prezentata in Fig. 4.15.

Fig. 4.15 - Elementele componentei Meniu

Multime

Aceasta este cea mai complexa componenta a RenderX si are ca scop gestionarea multimii randate. Clasele membre ale acestei componente sunt prezentate in Fig. 4.16

Fig. 4.16 - Clasele componentei Multime

Clasele StaticCrowd si AnimatedCrowd reprezinta componentele ce implementeaza contractul ICrowd ; acestea extind DrawableGameComponent si pastreaza ca date membre instante ale claselor ce realizeaza gestiunea diverselor metode de optimizare mentionate in capitolul II al lucrarii : ambele implementari pastreaza o instanta a clasei ViewFrustumManager (implementeaza algoritmii de View Frustum Culling) si in plus, clasa StaticCrowd pastreaza si o instanta a clasei InstancingManager (care gestioneaza modul de instantiere).

Dupa cum este definit in interfata ICrowd, ambele clase prezinta posibilitatea de adaugare/eliminare de personaje si dau informatii referitoare la modul curent de instantiere, optiunea curenta de ViewFrustumCulling, numarul de instante, precum si numarul de instante vizibile in scena (acesta va fi diferit de numarul total de instante in cazul aplicarii algoritmilor de ViewFrustumCulling).

Clasele AnimatedCrowdMember si StaticCrowdMember reprezinta abstractizari ale membrilor celor doua tipuri de multimi; amandoua implementeaza contractul definit de interfata IcrowdMember si sunt responsabile de actualizarea si desenarea personajelor din multime.

Instantele clasei StaticCrowdMember vor apela in timpul actualizarii metode din clasele LodManager si ModelsPoolManager pentru a obtine modelul pe care trebuie sa il randeze in functie de pozitia in scena (asa cum este prezentat in S.C 4.4).

S.C 4.4 - Actualizarea unei instante StaticCrowdMember

Clasa ViewFrustumManager este responsabila de gestionarea volumului de vizualizare si determinarea instantelor vizibile, utilizand fie o metoda interna - pentru executarea algoritmului naiv - fie clasa OcTreeNode pentru a construi un arbore octal al scenei. Metodele ToggleContributionCullingMode si ToggleViewFrustumCullingMode sunt utilizate pentru a schimba optiunea curenta pentru cele doua metode corespunzatoare (Contribution Culling si View Frustum Culling).

Clasa OcTree implementeaza metoda de View Frustum Culling bazata pe un arbore octal. Prin metoda interna AddModel, un obiect ce implementeaza interfata ICrowdMember poate fi distribuit in arbore, asa cum este prezentat in S.C 4.5.

S.C 4.5 - Implementarea operatiei de adaugare a unui model arborelui octal

Clasa ModelPoolManager este utilizata de instantele StaticCrowd pentru a selecta modelul pe care trebuie sa il deseneze in functie de nivelul de detaliu in care se afla, bineinteles in cazul in care reprezentarea in niveluri de detaliu este activa.

Aceasta clasa retine un dictionar static cu asocieri intre o lista de modele si elementele enumeratiei LOD, iar la cerere intoarce aleator unul din modelele asociate nivelului de detaliu solicitat (S.C 4.6).

Este de remarcat relativ la implementarea acestei clase ca am utilizat patru niveluri de detaliu: pentru primele doua niveluri sunt randate modele geometrice complete 3D, iar pentru celelalte doua niveluri sunt utilizati impostori, dupa tehnica descrisa in Capitolul II.

Modul de executie a aplicatiei

Procesul de executie a aplicatiei implementate se supune modelului general de aplicatie XNA, prezentat anterior in acest capitol. In pseudocod, bucla aplicatiei are forma prezentata in S.C. 4.4.

S.C. 4.4 - Bucla unei aplicatii XNA generice

Partea de incarcare a resurselor presupune incarcarea de catre fiecare componenta a continutului necesar :

componenta Teren incarca textura din imaginea ground.png si efectul effect.fx

componenta Decor incarca imaginile necesare pentru crearea cerului

Componenta Multime incarca modelele personajelor (multimea animata incarca modelul dude.fbx iar multimea statica incarca un set intreg de modele prin intermediul clasei ModelsPoolManager, descrisa in sectiunea anterioara.

Obtinerea datelor de la utilizator se face prin intermediul componentei Meniu in fiecare pas al buclei.

Logica de actualizare este divizata intre componente, dupa cum urmeaza :

Componenta Camera actualizeaza pozitia camerei

Componenta Meniu colecteaza comenzile primite de la tastatura.

Componenta Multime actualizeaza in mod corespunzator personajele:

o      Membrii multimii animate isi actualizeaza cadrul curent de animatie si pozitia;

o      Membrii multimii statice actualizeaza dupa caz modelul pe care il deseneaza (in functie de distanta fata de camera); in cazul billboard-urilor se actualizeaza si pozitionarea.

Utilizarea aplicatiei

In aceasta sectiune va fi realizata o scurta descriere a modului in care aplicatia poate fi utilizata. Este pus la dispozitia utilizatorului urmatorul meniu de functionalitati:

1. Modificarea interactiva a multimii vizualizate - prin apasarea combinatiei de taste CTRL+M se pot vizualiza pe rand multimea animata si cea statica - in fiecare dintre ele se pastreaza starea (numarul de indivizi si optiunile selectate).

2. Resetarea multimii - eliminarea tuturor instantelor - prin apasarea combinatiei de taste CTRL+R.

3. Modificarea interactiva a metodelor de optimizare utilizate:

BackfaceCulling - prin apasarea tastei B se navigheaza printre cele trei modalitati posibile: in sensul acelor de ceas (clockwise), in sens trigonometric (counterclockwise) sau fara aplicarea metodei (none).

ViewFrustumCulling - prin apasarea tastei F se navigheaza prin trei optiuni: varianta naiva (naïve culling), utilizarea unui arbore octal (octree) sau fara aplicarea algoritmului (none); Este de mentionat ca algoritmul ContributionCulling, ca si bufferul de adancime, este utilizat in mod standard si nu poate fi dezactivat.

ContributionCulling - prin apasarea tastei C se poate activa/dezactiva optiunea de executie a ContributionCulling.

HardwareInstancing - prin apasarea tastei H se navigheaza prin cele trei optiuni disponibile de pe platforme PC - HardwareInstancing, ShaderInstancing sau fara instantiere. In functie de capabilitatile Unitatii de Procesare Grafica insa, prima varianta poate sa nu fie activa (in cazul in care unitatea video nu suporta programe shader in versiunea 3.0). Aceasta optiune este valida doar in cazul in care multimea activa este cea statica.

Reprezentarea pe niveluri de detaliu - prin apasarea tastei L se activeaza/dezactiveaza utilizarea hartii de nivel de detaliu. Optiunea este valabila doar in starea in care este activa multimea statica.

4. Afisarea unui grafic ce prezinta in mod interactiv evolutia vitezei de randare in timp - prin apasarea combinatiei de taste CTRL+G.

5. Afisarea unor elemente de Ajutor - afisarea tastelor de meniu, prin apasarea tastei F1 si informatiile referitoare la dispozitivul grafic curent.

In Fig. 4.18 sunt prezentate capturi de imagine din timpul executiei aplicatiei; Se observa ca informatiile despre starea curenta sunt afisate in portiunea din stanga a ecranului.

Prima captura prezinta modul standard de afisare - cu statisticile afisate sus in partea stanga a ecranului ; in cea de-a doua captura este prezent si afisajul de Ajutor - central in partea stanga, iar in cea de-a treia este vizibil si graficul de evolutie a vitezei de executie a aplicatiei ; cea de-a patra captura prezinta cel de-al doilea tip de multime - multimea statica in care este evidentiata utilizarea nivelurilor de detaliu si a impostorilor - in mod de afisaj complet.

Fig. 4.17 - Aplicatia in executie

Capitolul V
Evaluarea performantelor proiectului

'Un computer este ca o cutie mica de carton. In aceasta cutie locuieste un elf. Elful se supune instructiunilor programului meu si le executa in ordinea in care ii sunt trimise. Unele instructiuni ii spun elfului sa deseneze imagini pe ecran' (Heagreave, 2008)

Pentru a scrie aplicatii grafice performante, trebuie sa intelegem foarte bine costurile diferitelor operatii pe care dorim sa le efectuam.

Dupa cum afirma Stephen Covey in lucrarea sa "The 7 Habbits of Highly Effective People", trebuie sa "incepem cu sfarsitul in minte". Aceasta idee este cruciala pentru dezvoltarea personala, dar si foarte importanta cand gandim o problema din punct de vedere al performantei. Inginerii software trebuie sa aiba stabilite scopuri si sa fie perseverenti in a masura performantele vis-à-vis de aceste scopuri pe masura scrierii codului. 'Sfarsitul' se poate schimba si in consecinta trebuie ajustat conform necesitatilor.

Aplicatiile grafice reprezinta o gama de software deosebita prin faptul ca, pentru executia lor, lucreaza in paralel doua unitati distincte de procesare, motiv pentru care detectarea regiunilor de cod care scad performanta generala este un proces mai anevoios.

Cand o aplicatie software oarecare este executata prea incet, se pot utiliza unelte de profiling pentru a analiza parcursul operatiilor si pentru a observa unde sunt consumate resursele de timp. In cazul aplicatiilor grafice insa, nu sunt disponibile astfel de unelte, iar executia codului in unitatea grafica de procesare ramane un proces blackbox ale carei performante sunt dificil de masurat.

Un aspect esential al analizei performantei in lucrul cu o aplicatiile grafice este prin urmare formarea unui model mental solid al proprietatilor acestora si a modului in care functioneaza dispozitivele grafice.

Performanta unitatilor de procesare grafica este o functie neliniara si, fara o buna intelegere a modului lor de lucru, rezultatele aceasteia pot parea intamplatoare (de exemplu, eliminarea unui model poate sa nu afecteze vizibil performanta pe cand o modificare minora a unui alt model poate dubla frecventa cadrelor) si se poate pierde mult timp prin investigarea aleatorie a unitatilor de cod, fara a ajunge la un rezultat.

Motto-ul acestui capitol poate fi considerat modelul pe care multi oameni il asociaza unui computer. Din punct de vedere functional, o astfel de descriere este plauzibila, insa nu suficienta pentru intelegerea performantelor computerului - in special a aplicatiilor grafice executate de acesta.

Un model mai explicit ar fi urmatorul:

"Un computer este ca o cutie de carton locuita de o pereche de elfi, Charles Pidgeon Underhill si fratele mai mic al acestuia, George Pekkala Underhill - amandoi mai bine cunoscuti dupa initialele lor.

Charles este foarte inteligent si bine educat si vorbeste fluent o multime de limbaje - C, C++, Java, C#, etc.

Pe de alta parte, George este un savant autist. Lui ii este foarte greu sa comunice cu oricine altcineva decat fratele sau mai mare; isi planifica toate activitatile in avans si devine confuz cand i se cere sa isi schimbe planurile fara un preaviz. Are o abilitate exceptionala de a inmulti numere in virgula mobila si ii plac in mod deosebit calculele cu vectori si matrici.

Cand un program se executa pe computer, Charles citeste datele de intrare si face ceea ce i se cere. De fiecare data cand intalneste o instructiune de desenare, el o noteaza pe un billet. La un moment ulterior (cand biletul se umple sau cand primeste o instructiune Present), el traduce intregul mesaj de pe billet din limbajul original intr-un limbaj secret pe care doar el si George il pot intelege si ii transmite instructiunile rezultate fratelui sau, care le executa.' (Hagreaves, 2008)

Acest model explica foarte bine subtilitatea caracteristicilor de performanta ale unei aplicatii grafice. Daca s-ar utiliza un profiler pentru a analiza codul executat de Charles, rezultatul ar fi acelasi in cazul unei cereri de desenare pentru cinci triunghiuri sau pentru un milion de triunghiuri, intrucat Charles nu face altceva decat sa noteze cererile de desenare pe care trebuie sa i le transmita ulterior lui George. Charles poate sa scrie la fel de repede "deseneaza 3 triunghiuri" sau "deseneaza un miion de triunghiuri"; cel care va simti diferenta este, in mod intuitiv, George, in momentul procesarii cererii.

Este deci foarte importanta intelegerea paralelismului executiei unei aplicatii grafice pentru o estimare corecta a comportamentului si a performantelor acesteia.

Intr-un proces ideal de executie, atat unitatea centrala de procesare cat si unitatea grafica ar trebui sa lucreze constant (fig. 6.1a). In realitate insa, echilibrarea perfecta a instructiunilor pe unitatea centrala si pe unitatea grafica este foarte dificil de obtinut si exista astfel doua situatii posibile:

Supraincarcarea unitatii centrale de procesare (CPU bound) - in acest caz, unitatea grafica se va gasi in starea idle cat timp va astepta instructiuni de la unitatea centrala de procesare, dupa incheierea prelucrarii cadrului curent. (fig. 6.1b). Este evident ca in aceasta situatie orice incercare de a reduce numarul de instructiunie pentru unitatea grafica nu va avea practice nicio influenta asupra performantei aplicatiei, intrucat odata cu scaderea timpului de procesare va crese timpul de asteptare in starea idle si in final frecventa cadrelor va ramane aceeeasi. In schimb, este indicata incarcarea unitatii grafice cu instructiuni cu un cost nesemnificativ pentru unitatea centrala, pentru a profita de timpul disponibil.

Supraincarcarea unitatii de procesare grafica (GPU bound) - in acest caz, unitatea centrala este cea care asteapta in starea idle pana cand unitatea grafica poate primi noi instructiuni. Analog situatiei anterioare, este inutila incercarea de a reduce timpul de executie pe unitatea centrala, intrucat unitatea grafica este cea care genereaza latenta. In schimb, se recomanda adaugarea de operatii destinate unitatii centrale, pentru a minimiza timpul petrecut in starea idle.

Fig.5.1 - Distributia operatiilor intre Unitatea Centrala de Procesare si Unitatea Grafica de Procesare (Hargreaves, 2009)

In concluzie, pentru a optimiza corect o aplicatie grafica este necesar sa se determine care dintre unitatile de procesare este mai incarcata, pentru a putea profita de timpul disponibil de procesare al unitatii omoloage.

Performanta Unitatii Grafice de Procesare

Unitatile Grafice de Procesare moderne dispun de benzi grafice complexe, cu sute de nuclee de procesare ce lucreaza in paralel. Pentru a optimiza executia codului pe acestea, este necesar sa se determine care dintre etapele de procesare pot fi accelerate.

In mod evident, banda grafica este diferita in fiecare model de dispozitiv video, insa etapele principale sunt comune:

Citirea informatiilor despre vertex din memorie, de catre unitatea vertex fetch.

Procesarea acestor informatii de catre vertex shader.

Unitatea de rasterizare determina ce pixeli sunt acoperiti de fiecare triunghi.

Culoarea fiecarui pixel este calculata de catre pixel shader

Unitatea texture fetch incarca texturile solicitate de pixel shader.

Unitatea stencil citeste, testeaza si actualizeaza bufferul de adancime.

Bufferul de cadre-ul stocheaza cadrul final si aplica alpha blending[5].

In functie de aplicatie, fiecare din aceste etape poate constitui un bottleneck si este important ca factorii care le influenteaza sa fie cunoscuti. In tabelul T5.1 sunt rezumati acesti factori.

T. 5.1 - factorii care influenteaza performanta unei aplicatii in fiecare din stadiile de procesare

Studiu de caz

In aceasta sectiune vor fi prezentate rezultatele obtinute la executarea aplicatiei pe urmatoarele configuratii de sisteme hardware:

#1. Intel Core 2 CPU T5500 @ 1.66 GHz, Mobile Intel(R) 945GM Express Chipset Family

#2. Intel Pentium D @3GHz, ATI Radeon X1050

  Au fost testate functionalitatile prezentate in capitolul anterior si frecventele de cadre obtinute au fost figurate in grafice in functie de numarul de instante de personaje gestionate in scena.

Pentru a facilita interpretarea graficelor, s-a marcat pe fiecare dintre ele o limita de interactivitate, ce reprezinta frecventa minima de cadre care da senzatia de fluenta (sub aceasta limita apare o latenta in actualizarea cadrelor si in tratarea comenzilor primite de la dispozitivele de intrare).

Este de mentionat ca desi numarul de instante este in mod natural o masura a performantei aplicatiei - in sensul ca o aplicatie care poate randa un numar foarte mare de personaje este buna - trebuie luata in considerare si complexitatea geometrica a personajelor ; in cazul multimii animate prezentate un singur personaj este alcatuit din ~22500 de poligoane, ceea ce inseamna ca pentru randarea a >200 de astfel de caractere este nevoie de mai mult de 4.5 milioane de poligoane. Acest aspect trebuie luat in considerare la interpretarea rezultatelor obtinute.

In subsectiunile urmatoare vor fi prezentate graficele obtinute la evaluarea metodelor implementate, iar in finalul sectiunii va fi prezentat un tabel de concluzii referitoare la acestea.

1. Backface culling

In primul grafic am urmarit prezentarea unui aspect interesant al utilizarii proprietatii CullMode a obiectului RenderState. Se observa din graficul obtinut ca in mod - aparent - paradoxal, setarea acestei proprietati astfel incat sa se realizeze backface culling are un impact negative.

Explicatia este data de faptul ca in modelele utilizate, toate poligoanele au proprietatea Culling setata pe valoarea CullingOff, ceea ce face ca toate poligoanele sa fie desenate in oricare din cazuri; impactul negativ este dat de faptul ca in cazul in care CullMode este setata pe una din cele doua valori Clockwise sau CounterClockwise, pe Unitatea Grafica de Procesare se realizeaza teste in plus, fara a avea ca rezultat eliminarea unei multimi de poligoane; de aici rezulta o crestere a timpului de randare, indiferent de performantele dispozitivului hardware utilizat.

In concluzie, utilizarea acestei metode trebuie precedata de o examinare a modelelor ce urmeaza a fi randate, pentru a evita astfel de situatii.

2. View Frustum Culling

In cazul multimii statice, algoritmii de ViewFrustum Culling au fost testati pastrand inactive reprezentarea pe niveluri de detaliu si instantierea personajelor.

Din graficele obtinute putem deduce ca performanta procesului de randare este limitata de Unitatea Centrala de Procesare, intrucat desi numarul de obiecte din scena se modifica, frecventa cadrelor pastreaza aproximativ aceleasi serii de valori; tinand cont de diferentele existente intre implementarea multimii statice si cea a multimii animate, putem deduce ca este necesara si o optimizare a procesului de animatie.

Trebuie avut in vedere insa si faptul ca animatia modelului utilizat este alcatuita din 4096 cadre de animatie, ceea ce duce in mod evident la o procesare lenta, intrucat clasa AnimationClip pastreaza intern o lista completa a acestor cadre.

In cazul multimii statice exista insa o crestere vizibila de performanta; trebuie mentionat ca in timpul testarii am deplasat camera astfel incat sa ramana in scena un numar cat mai mare de personaje; faptul ca impactul a fost pozitiv sugereaza ca limitarea este data in aceasta situatie de Unitatea Grafica de Procesare.

3. Reprezentarea pe niveluri de detaliu si randare bazata pe imagini

Aceasta serie de teste a urmarit impactul utilizarii metodei de reprezentare pe niveluri de detaliu descrise in capitolul IV.

Dupa cum se poate observa din graficul rezultat, utilizarea acestei metode este extrem de eficienta.

Este de mentionat aici - intrucat acest fapt nu reiese din grafic - ca s-a atins un numar de ~400 de instante randate la o frecventa interactiva de cadre (fara activarea celorlalte metode de optimizare) pe sistemul de test #1.

4. Instantierea modelelor

In continuare, in tabelul T. 5.2 este prezentata o centralizare a rezultatelor generale obtinute pe cele 4 sisteme de test (numar maxim de personaje randate la limita de interactivitate):

T. 5.2

Capitolul VI
Concluzii si dezvoltari ulterioare

In aceasta lurcare a fost prezentat un prototip al unui sistem hibrid ce realizeaza randarea unei multimi animate de caractere in timp real, cu un dublu scop: pe de o parte de a analiza castigul de performanta adus de unele din metodele mai mult sau mai putin clasice de optimizare utilizate pe scara larga in domeniul aplicatiilor grafice - algoritmi de eliminare a suprafetelor ascunse, instantiere hardware, reprezentarea pe niveluri de detaliu, etc; si pe de alta parte de a demonstra capabilitatea unei platforme managed de a sustine aplicatii grafice in timp real. Tinand cont de faptul ca ambele domenii abordate de acest sistem - pe de o parte principiile si algoritmii ce stau la baza unui motor de randare general, pe de alta parte platformele Microsoft .NET si Microsoft XNA constituie subiectul unei cantitati colosale de documentatie, este de la sine inteles ca acestea nu pot fi tratate exhaustiv intr-un numar redus de pagini ; speram insa ca lucrarea de fata sa fi reusit crearea unei perspective de ansamblu clara, corecta si destul de detaliata incat sa poata fi dezvoltata de cititori prin explorari ulterioare.

Desi sistemul implementat se afla intr-o faza in care, comparativ cu alte sisteme din aceeasi categorie existente pe piata, poate fi considerat rudimentar, el profita de o arhitectura modulara, slab cuplata, ce poate fi in orice moment extinsa si imbunatatita.

Comportamentul actual al multimii este simplist, caracterele fiind limitate la o singura animatie, intrucat modelarea de caractere si animatii nu au constituit obiective pentru lucrarea prezentata. In dezvoltari ulterioare se impune insa acomodarea cu instrumentele de design in scopul imbogatirii setului de caractere si animatii, pentru a putea oferi un realism vizual sporit.

Pentru a spori realismul comportamentului personajelor din multime, este necesara implementarea unui mecanism eficient de detectare si tratare a coliziunilor si a unor tehnici LODAI (Level of Detail AI - Inteligenta Artificiala pe niveluri de detaliu), pentru a coordona elementele de animatie si a asigura autonomia multimii.

Din punct de vedere al metodelor de optimizare, atentia trebuie indreptata in viitor spre doua obiective: pe de o parte aprofundarea metodelor de reprezentare pe niveluri de detaliu si de randare pe baza de imagini, iar pe de alta parte spre imbunatatirea programelor shader, ceea ce impune si o explorare mai detaliata a limbajului HLSL. Se doreste de asemenea implementarea efectiva a metodelor HardwareInstancing si VFetchInstancing pe dispozitive hardware compatibile.

O alta posibila directie de imbunatatire a proiectului este in sensul sporirii calitatii decorului - prin plasarea multimii intr-un cadru mai realist (de exemplu un oras, un camp de lupta, etc.), adaugarea de alte elemente de decor, sau prin animarea texturilor utilizate pentru desenarea cerului.

Avand in vedere cel de-al doilea scop mentionat la inceputul acestui capitol, si anume cel de a demonstra capabilitatea unei platforme managed de a sustine aplicatii grafice in timp real, putem nu numai sa observam ca obiectivul a fost indeplinit, ci mai mult, ca prototipul realizat constituie un punct de pornire intr-un domeniu extrem de vast si captivant.

In primul rand, printr-un simplu mecanism de migrare, acesta poate fi portat pe o consola Xbox360.

In al doilea rand, se poate profita nu numai de facilitatile codului managed (prezentate in Capitolul IV), ci si de alte instrumente puternice si extensibile puse la dispozitie de platformele .NET si XNA . Dintre acestea enumeram suportul pentru expresii Lambda - deja existent in versiunea 3.5 a .NET Framework, si suportul pentru paralelizarea aplicatiilor ce va fi disponibil prin intermediul librariei TaskParallelLibrary (TPL) in urmatoarea versiune a platformei .NET. Daca unicul rol al utilizarii expresiilor Lambda este -cel putin in prezent - doar sporirea calitatii codului in sine, in cazul librariei TaskParallelLibrary beneficiul este enorm in contextul actual - in care tendinta generala a designului sistemelor de calcul este de orientare spre arhitecturi paralele si calcul distribuit - intrucat ofera dezvoltatorilor o maniera transparenta si comprehensibila de a utiliza foarte eficient resursele hardware puse la dispozitia aplicatiei create.

Rezultatele obtinute, prezentate in capitolul anterior demonstreaza ca performantele generale ale unei aplicatii grafice variaza in functie de o multitudine de factori atat hardware (arhitectura sistemului utilizat, capabilitatile dispozitivelor, etc) cat si software (algoritmii utilizati), dezvoltatorii fiind nevoiti in permanenta sa gaseasca raspunsuri la intrebari cum ar fi 'care sunt functionalitatile strict necesare?', 'care este platforma tinta pentru executia aplicatiei?', 'care sunt cerintele minime pentru sistemele utilizatorilor?' si asa mai departe; 

Din toate cele precizate anterior, putem concluziona ca, intr-un mod general, o aplicatie grafica performanta se construieste pe trei fundamente bazate, desigur, pe cunoasterea si intelegerea modului in care software-ul, API-urile unitatilor grafice si intreg sistemul de calcul interactioneaza intre ele. Intrucat in multe cazuri aplicatiile grafice consuma mult timp procesand informatii care nu sunt strict legate de utilizarea unitatii de procesare grafica, primul fundament consta in scrierea de cod de calitate pentru toate componentele unei aplicatii, tinand cont de faptul ca o intarziere in executia oricarei linii de cod se traduce intr-o scadere a performantei globale. Al doilea fundament rezida pe o structura grafica eficienta si pe o interactiune buna cu hardware-ul sistemului. API-urile unitatilor grafice pot fi implementate ineficient si acest fapt nu poate fi schimbat sub nicio forma din cod extern. Din pacate, un cod scris elegant si un set optimizat de apeluri de functii nu pot compensa o alegere neinspirata a algoritmilor utilizati. Folosirea unor algoritmi eficienti reprezinta deci cel de-al treilea nivel al fundatiei pe care se constituie performantele aplicatiei. Este evident ca un algoritm lent poate efectiv sa suprime orice castig de performanta adus de un set de optimizari.

Lucrarea va conchide prin a afirmatia ca nu exista - si nici nu poate fi definita notiunea de - sisteme de randare perfecte; fiecare sistem are propriul set de avantaje si dezavantaje si este adaptat unui anumit gen de cerinte. Crearea de aplicatii grafice performante poate fi un proces dificil ; cumpararea unui sistem mai performant poate fi o solutie, insa o solutie temporara, ce nu se preteaza in cele multe din situatii. Este mult mai simplu - si mai ieftin pe termen lung - sa depunem efort pentru a examina cum interactioneaza sistemul software si sistemul hardware si a modifica o aplicatie intr-un mod corespunzator decat sa adaptam sistemul hardware la solutia oferita de aplicatie. Acest efort a reprezentat dintotdeauna si continua sa reprezinte unul din cele mai interesante si mai satisfacatoare aspecte ale dezvoltarii de aplicatii grafice. Si in mod cert, singura cale de a formula solutii din ce in ce mai bune este exercitiul, intrucat, amintind cuvintele lui Albert Einstein, 'singura sursa de cunoastere este experienta'.

Bibliografie

Alexandre Lobao, Bruno Evangelista si José Antonio Leal de Farias

Beginning XNA 2.0 Programming - From Novice to Professional.

Apress, 2008

Riemer Grootjans

XNA 2.0 Game Programming Recipes, A Problem-Solution Approach.

Apress, 2008

Chad Carter

Microsoft XNA Unleashed: Graphics and Game Programming for Xbox 360 and Windows

Sams, 2008

Benjamin Nitschke

Professional XNA Game Programming For Xbox360 and Windows

Wrox Press, 2007

Hubert Nguyen

GPU Gems 3 Capitolul II - Animated Crowd Rendering

Nvidia 2008.

Stephen Cawood, Pat McGee

Microsoft XNA Game Studio: Creator's Guide.

The McGraw-Hill Companies, 2007.

Alan Shalloway, James Trott

Design Patterns Explained A New Perspective on Object Oriented Design 2nd Edition

Addison-Wesley Professional, 2004

Andrew S. Tanenbaum

Modern Operating Systems, 2^nd Edition

The McGraw-Hill Companies, 2002.

Keith Cok

Developing Efficient Graphics Software: The Yin and Yang of Graphics.

ACM Siggraph, 2000

Heung-Yeung Shum, Shing-Chow Chan si Sing Bing Kang

Image Based Rendering

Springer, 1999

Hugues Hoppe, Juan Popovic

Progressive Simplicial Complexes

ACM Siggraph, 1997

Disponibil la: https://research.microsoft.com/en-us/um/people/hoppe/proj/psc/

La Data : Iunie 2009

Robert W. Gill

Basic Rendering: Effective Drawing for designers, Artists and Illustrators

Thames & Hudson, 1991.

Gamedev

Geometry culling in 3D engines

Disponibil la: https://www.gamedev.net/reference/articles/article1212.asp

La data : Aprilie 2009

Wikipedia 2009

Hidden Surface Determination

Disponibil pe: https://en.wikipedia.org/wiki/Hidden_surface_determination

La data: 20.06.2009

Shawn Hargreaves

Understanding GPU Performance

Disponibil la:

https://blogs.msdn.com/shawnhar/archive/2008/03/14/understanding-gpu-performance.aspx

La data: Mai 2009

Shawn Hargreaves

Santa's Production Line

Disponibil la:

https://blogs.msdn.com/shawnhar/archive/2008/04/11/santa-s-production-line.aspx

La data: Mai 2009

Shawn Hargreaves

Displaying the framerate

Disponibil la: https://blogs.msdn.com/shawnhar/archive/2007/06/08/displaying-the-framerate.aspx

La data: Mai 2009

USA Today

'The Lord of the Rings' and 'The Two Towers' Visual Effects Supervisor Joe Letteri

Disponibil la: https://cgi1.usatoday.com/mchat/20030320003/tscript.htm

La data : Martie 2009

IMDB

The Lord of the Rings - The Two Towers

Disponibil la : https://www.imdb.com/title/tt0167261/

La data : Mai 2009

Horde3D

Overview

Disponibil la : https://horde3d.org/

La data : Iunie 2009

Gamespot

Overlord II Xbox 360

Disponibil la : https://www.gamespot.com/xbox360/action/overlordii/index.html

La Data : Mai 2009

Gamespot

Empire Total War PC

Disponibil la : https://www.gamespot.com/pc/strategy/empiretotalwar/index.html

La Data : Mai 2009

ArsTechnica

Twilight of the GPU: an epic interview with Tim Sweeney

Disponibil la:

https://arstechnica.com/gaming/news/2008/09/gpu-sweeney-interview.ars

La Ddata : Iunie 2009

MSDN

Parallel Performance : Optimize Managed Code For Multi-Core Machines

Disponibil la: https://msdn.microsoft.com/en-us/magazine/cc163340.aspx

La Data : Iunie 2009

MSDN

Lambda Expressions (C# Programming Guide)

Disponibil la: https://msdn.microsoft.com/en-us/library/bb397687.aspx

Disponibil la : Iunie 2009

Ogre3D

About Ogre3D

Disponibil la : https://www.ogre3d.org/about

La Data : Iunie 2009

Tom's Hardware

13 Years of Nvidia Graphics Cards

Disponibil la:

https://www.tomshardware.com/picturestory/464-nvidia-graphics-cards.html

La Data : Iunie 2009

FiringSquad

History of ATI

Disponibil la: https://www.firingsquad.com/features/atihistory/

La Data : Iunie 2009

Intel® Software Network, 2008

Impostors Made Easy

Disponibil la: https://software.intel.com/en-us/articles/impostors-made-easy/

La Data : Iunie 2009

David Luebke et al.

Level of Detail for 3D Graphics

Morgan Kaufman, 2003

Anexa - Licenta permisiva Microsoft (utilizarea modelului dude.fbx)

Microsoft Permissive License (Ms-PL)

This license governs use of the accompanying software. If you use the software, you accept this license. If you do not accept the license, do not use the software.

1. Definitions

The terms "reproduce," "reproduction," "derivative works," and "distribution" have the same meaning here as under U.S. copyright law.

A "contribution" is the original software, or any additions or changes to the software.

A "contributor" is any person that distributes its contribution under this license.

"Licensed patents" are a contributor's patent claims that read directly on its contribution.

2. Grant of Rights

(A) Copyright Grant- Subject to the terms of this license, including the license conditions and limitations in section 3, each contributor grants you a non-exclusive, worldwide, royalty-free copyright license to reproduce its contribution, prepare derivative works of its contribution, and distribute its contribution or any derivative works that you create.

(B) Patent Grant- Subject to the terms of this license, including the license conditions and limitations in section 3, each contributor grants you a non-exclusive, worldwide, royalty-free license under its licensed patents to make, have made, use, sell, offer for sale, import, and/or otherwise dispose of its contribution in the software or derivative works of the contribution in the software.

3. Conditions and Limitations

(A) No Trademark License- This license does not grant you rights to use any contributors' name, logo, or trademarks.

(B) If you bring a patent claim against any contributor over patents that you claim are infringed by the software, your patent license from such contributor to the software ends automatically.

(C) If you distribute any portion of the software, you must retain all copyright, patent, trademark, and attribution notices that are present in the software.

(D) If you distribute any portion of the software in source code form, you may do so only under this license by including a complete copy of this license with your distribution. If you distribute any portion of the software in compiled or object code form, you may only do so under a license that complies with this license.

(E) The software is licensed "as-is." You bear the risk of using it. The contributors give no express warranties, guarantees or conditions. You may have additional consumer rights under your local laws which this license cannot change. To the extent permitted under your local laws, the contributors exclude the implied warranties of merchantability, fitness for a particular purpose and non-infringement.