RANDAREA PE CPU

Articol de Vilvoiu Vasile-Cornel aka "Rimio"


Tutorialul de fata l-am conceput dandu-mi seama cat de putin stiu nou venitii (si de fapt cat de putin le pasa) despre ceea ce se intampla in spatele cortinelor, cum functioneaza de fapt randarea si ce implica un call la glVertex3f. Nu se va referi numai la notiunile de randare software (pe CPU), va acoperi o arie mai larga, incepand cu chestii simple cum ar fi notiunile de baza despre spatiul tridimensional si ajungand pana la metode de optimizare. Pentru cei care au cat de cat o idee desptre 3D, pot trece direct la capitolul VECTORI sau chiar MATRICI, insa recomand o citire integrala.

NU ma judecati prea aspru . Informatiile care le voi expune aici le-am adunat pe parcursul catorva ani (vreo 3) cat mi-au trebuit sa ajung de la un n00b amarat ce intreba cum se roteste un triunghi pana la un nivel mediu de cunostinte. Nu am dat copy paste de pe un site sau ebook, ci numai din cod propriu iar imaginile sunt partial facute de mine, partial compilate din imagini de pe net. Va rog sa imi semnalati eventualele greseli pentru a le repara mai tarziu. De asemenea puteti face commenturi sau adaugiri. Tot ceea ce voi posta ulterior voi marca cu LE (later edit) la inceputul paragrafului.

Tutorialul se adreseaza atat celor care nu au avut nici o treaba pana acum cu programarea 3D cat si celor care au ceva experienta sau sunt profi in domeniu (si ii intereseaza partea de software rendering). De asemenea, chair daca APIuri ca OpenGL sau Direct3D fac cam tot ce vom discuta in tutorial, o intelegere mai adanca nu strica nimanui!

O mica implementare a unui renderer software o puteti gasi aici (http://www.planetrimio.com/download/dosren.rar). Impreuna cu binarul este si codul sursa, scris in Borland Pascal 7 (nu incepeti cu posturile pe tema asta, pur si simplu m-a apucat nostalgia ), pe care il puteti folosi in ce mod vreti (desi ma indoiesc ca o sa scoateti ceva bani pe el). Ok atunci, sa-i dam drumul!


SPATIUL 3D

Ceea ce incercam noi sa facem in ziua de azi in jocuri si nu numai e sa aducem realitatea (sau o versiune contorsionata dupa placul mintii noastre a realitatii ) pe ecranele monitoarelor. Insa aici intervine o problema: realitatea ni se prezinta intr-un spatiul tridimensional (adica putem sa si zburam daca vrem, pe langa a merge in cele patru directii orizontale) iar ecranul este bidimensional (are latime si inaltime, exprimate in pixeli). Proiectia spatiului tridimensional in spatiu bidimensional o vom trata in tutorial. Dar haide sa intelegem mai bine care-i faza cu spatiul tridimensional.



Daca consideram trei axe, perpendiculare una pe alta (ca in figura 1), cu un singur punct comun, am definit un spatiu tridimensional cu originea in punctul de intersectie.

Sa presupunem ca stam pe loc, in picioare. De aici putem avansa cu pozitia noastra intr-o infinitate de directii, insa sa analizam numai 3 dintre ele: spre stanga sau dreapta pozitiei noastre curente (strafing pentru gameri ), inainte si inapoi, sau in sus (in jos nu prea se poate din motive de podea). In primul caz, mersul in stanga sau in dreapta, spunem ca ne-am deplasat pe axa OX. Pentru al doilea caz (inainte si inapoi) spunem ca ne-am deplasat pe axa OZ (sau in adancime) iar in cazul sariturii (mersul in sus si apoi cazutul inapoi pe pamant) spunem ca ne-am deplasat pe OY, pozitia noastra de inceput fiind originea.

Ce putem observa e ca putem ajunge in orice alta poztite dorim, mergand numai pe cele trei axe. Insa ca sa ajungem intr-un loc nu mergem numai in unghiuri drepte, ci mergem si pe diagonala. Putem sa definim pozitia finala in care vom ajunge ca trei deplasari distincte: una pe OX, una pe OY si una pe OZ. Aceasta este descompunerea unui vector in componentele sale (despre vectori vom vorbi mai tarziu).

Putem chiar si masura distanta parcursa pe fiecare axa (in metri, centimetri sau orice alta unitate - picioare, palme). Insa aici apare o problema: daca fac 20 metrii in stanga (pe OX) ajung in alt loc decat daca fac 20 metrii in dreapta. Trebuie sa alegem un sens al axelor. Aici sunt doua modele folosite in general: de mana stanga (left hand coordinate system) si de mana dreapta (right hand coordinate system), vizibile in figura 1. Ambele au valorile pozitive pe OX in dreapta si cele negative in stanga. Ambele au valorile pozitive ale lui OY in sus iar cele negative in jos. Insa difera dintre cele doua este la configuratia axei OZ: cea de mana stanga are valorile pozitive in fata iar cele negative in spate iar cea de mana dreapta pe invers. Mai sunt cateva diferente la rotatii, dar vom discuta de acestea mai tarziu.

Acum putem reprezenta orice punct din spatiu prin trei valori, reprezentand cele trei "drumuri" pe care le facem pe cele trei axe. De exemplu (-20, 70, 50), (45.2, 33.1, -17. sunt amandoua doua pozitii valide.

Pentru cei care vor sa invete mai multe, puteti vizita http://www.evl.uic.edu/ralph/508S98/coordinates.html

Acum ca am inteles chestiile de baza, putem trece mai departe si anume la ...


VECTORI

Vectorii nu sunt altceva decat mai multe valori la un loc care reprezinta ceva. In cazul nostru poate reprezenta o pozitie sau o directie (sau orice altceva).



Vectorii de pozitie sunt 3 valori (ca unul din exemplele de mai sus) care reprezinta un loc in spatiu, dupa cele trei coordonate (figura 2). Acestia ii folosim cel mai des si sunt practic sufletul lumii noastre 3D (vedem mai tarziu de ce).

Vectorii de directie sunt ceva mai dificil de inteles. Acestia contin tot coordonatele unui punct in spatiu, insa reprezinta directia (linia) formata de punctul din spatiu si origine. Acestia pot fi folositi la reprezentarea fortelor (pentru simulari fizice) sau la exprimarea directiei in care trage un jucator de shootere.

O particularitate interesnta a acestor vectori e ca aceeasi directie poate fi reprezentata prin mai multi vectori. De exemplu, vectorul (2, 4, 5) reprezinta aceeasi directie ca (20, 40, 50) sau (4, 8, 10). Pentru a putea face operatii pe acest tip de vectori trebuie sa-i aducem la o stare in care valorile sa fie egale pentru vectorii ce indica aceeasi directie. Aceasta este normalizarea vectorilor si consta in scalarea acestora (micsorarea sau marirea) astfel incat distanta de la origine la pozitia data de cele trei valori sa fie 1 (unu), directia ramanand neschimbata.

Pentru a normaliza un vector trebuie sa calculam modulul vectorului (in engleza "magnitude") si sa impartim fiecare din cele trei componente la el. Calcularea modulului unui vector se face aplicand Pitagora in spatiu:



Normalele (de care probabil ati auzit pe la fizica) sunt de fapt vectori de directie normalizati.

Vom mai discuta doua operatii care le putem aplica la vectori: produsul scalar si produsul vectorial.

Produsul scalar ("dot product" in engleza) returneaza un scalar (numar) ce reprezinta modulele celor doi vectori inmultite cu cosinusul unghiului dintre ei:



Unde A si B sunt vectori, |A| si |B| sunt modulele celor doi vectori iar cos(alfa) este cosinusul unghiului dintre cei doi vectori.

Produsul scalar se calculeaza si astfel:



Putem observa ca, daca facem produsul scalar a doi vectori normalizati (folosind a doua metoda) vom obtine chiar cosinusul unghiul dintre cei doi vectori si in consecinta unghiul (de notat ca unghiul nu poate depasi pi sau 180 grade), acesta fiind folositor in numeroase cazuri.



A doua operatie importanta este produsul vectorial ("cross product" in engleza). Acesta returneaza un vector care este perpendicular pe cei doi vectori si are modulul egal cu produsul dintre modulele celor doi vectori si sinusul unghiului dintre ei (figura 3):



Unde A, B si V sunt vectori, N este vectorul unitate (de modul 1) perpendicular pe A si B, |A| si |B| modulele celor doi vectori iar sin(alfa) este sinusul unghiului dintre A si B.

O alta metoda de a calcula V este urmatoarea:



Produsul vectorial este folosit pentru a determina vectorul perpendicular pe un plan, determinat la randul lui din trei punct. Sa analizam acest exemplu. Avem trei vectori de pozitie P1, P2, P3 care definesc un plan d. Daca calculam doi vectori de directie:



Si calculam vectorul V:



Atunci V va fi perpendicular pe planul d. De notat ca adunarea si scaderea a doi vectori se face adunand respectiv scazand fiecare din componentele celor doi vectori (A.x = P2.x - P1.x, A.y = P2.y - P1.y, A.z = P2.z - P1.z, in cazul primei scaderi).

Cam acestea ar fi notiunile de baza la vectori. Vom vedea mai tarziu ca vectorii ii vom gasi peste tot in implementarile noastre, definind obiectele cu care interactionam si monstrii cu care ne luptam.


REPREZENTAREA OBIECTELOR IN 3D

Ok, ok, dar cum reprezentam obiecte in 3D? Pai am putea din puncte, unde fiecare punct reprezinta o molecula sau un atom, insa ar fi cam "memory expensive", nu-i asa? Mai avem o solutie insa! Din triunghiuri!



Putem aproxima o suprafata de orice forma prin triunghiuri (figura 4). Cu cat numarul de triunghiuri este mai mare, cu atat reprezentarea este mai fidela. Ce-i drept, nu putem avea o reprezentare perfecta (numar infinit de triunghiuri? mai bine ne intoarcem la puncte), insa putem aproxima atat de bine incat nu se mai vede diferenta.

Numarul de triunghiuri este influentat de mai multe lucruri, insa factorul principal este hardware-ul pe care va fi rulata simularea. Acesta trebuie sa poata procesa numarul de triunghiuri in timp real (numarul optim de frame-uri pe secunda este 25 desi se comporta mai bine la 30).

Fiecare triunghi este definit de trei vertecsi. Viecare vertex contine mai multe date, cum ar fi pozitia (un vector, din acela de care vorbeam mai sus), culoarea, pozitia in textura si altele.

Sa nu confundam vertexul cu vectorul! Sunt doua lucruri total distincte. Pentru inceput, vertecsii cu care lucram au numai pozitie si imi voi permite sa zic "triunghi format din 3 puncte" sau "3 vectori", insa nu este o exprimare corecta.

De asemenea, in afara de triunghiuri, vom putea folosi si linii sau puncte pentru desenare (desi nu vom gasi in realitate linii sau puncte ). Vom numi toate tipurile de geometrie de baza care le putem desena - puncte, linii, triunghiuri, chiar si patrate sau poligoane pentru renderele sofisticate - primitive.

Asadar, la asta sunt folositi vectorii: la definirea triunghiurilor care compun obiecte!


MATRICI

Daca pana acum lucrurile au fost relativ simple, acum se vor complica putin, la aparitia matricilor. Matricile sunt tablouri (arrayuri pentru engleji ) bidimensionale de valori ce reprezinta ... ati ghicit, tot ceva . In general vom folosi matrici de 4x4 (patru linii si patru coloane) si, ca standard, le vom cere valorile in formatul:



Unde M este o matrice iar indexarea incepe cu 0 (prima linie este 0, prima coloana este 0). Matricile ne vor folosi la doua lucruri, care le vom discuta mai tarziu. Deocamdata sa invatam putina teorie.

Adunarea si scaderea a doua matrici se face, ca si la vectori, adunand sau scazand fiecare componenta cu sora ei din cealalta matrice. Simplu, dar de aici si prima regula: se pot aduna numai matrici cu acelasi numar de linii si coloane.

Inmultirea a doua matrici este ceva mai dificila, insa o sa o utilizam frecvent. Daca avem doua matrici 3x3, A si B:



(Ati observat ca am respectat regula linie-coloana ) Atunci matricea C = AxB este:



Mai pe romaneste, elementul de pe linia l si colana c din matricea noua este egal cu suma produselor dintre elementele de pe linia l din A si coloana c din B. Cam ciudat, insa se poate intelege cu putina vointa .

De notat este ca AxB != BxA deci atentie la ordinea inmutirii. De asemenea, putem inmulti si doua matrici nepatratice, cu conditia ca numarul de coloane din prima sa fie egal cu numarul de linii din a doua. Matricea rezultanta va avea numarul de coloane din a doua si numarul de linii din prima. Oricum nu trebuie sa ne batem capul cu asta, pentru ca noi vom inmulti matrici de aceeasi marime (4x4).

Ok, ok, ziceti voi. Am inteles, adunam, scadem, inmultim. Da' la ce ne trebuie ? Buna intrebare! In domeniul nostru vom folosi predominant doua tipuri de matrici: de transformare si de proiectie (care sunt, pana la urma, tot de transformare dar le zice altfel).

Sa analizam urmatoarea situatie: "stim" sa desenam un cauciuc de masina (sau, mai bine zis, avem stocate in memorie triunghiurile ce compun cauciucul). Dar noi trebuie sa il desenam de patru ori, pentru fiecare din roti. Si mai rau, trebuie desenat in pozitii total diferite si cu diferite rotatii aplicate. Ba chiar daca masina este un dragster, cauciucurile din fata vor fi mult mai mici ca cele din spate. Deci ce facem?

Un aspect foarte important al geometriei (a se citi "triunghiurile multe din memorie", nu disciplina de la scoala ) este ca poate fi folosita de mai multe ori. Dar cu ce ne ajuta daca desenam cauciucul de patru ori in acelasi loc, respectiv in origine?

Iata ce facem: trebuie sa gasim o metoda ca la fiecare desenare sa mutam, rotim si scalam vectorii ce definesc triunghiurile in acelasi fel pe toti, asa incat sa desenam cauciucul in alta pozitie, insa sa semene a cauciuc. Pentru asta folosim matricea de transformare.

Matricea de transformare are 4 linii si 4 coloane si defineste toate operatiile care le putem face unui vector: translatie (mutare), rotatie, scalare (si chiar si distorsiune, desi nu o sa folosim). Partea frumoasa e ca daca avem un cauciuc si transformam toti vectorii cu matricea, vom obtine tot forma unui cauciuc, numai ca in alta parte si eventual de alta dimensiune. Iar de aici vine un avantaj al folosirii matricilor: putem construi obiectul cu centrul in origine, ca si cum ar fi chiar in mijlocul lumii noastre virtuale, dar noi il vom putea desena oriunde vrem si de cate ori vrem!

Construirea unei matrici de transformare nu este un lucru greu. Sa analizam pe cazuri.

Pentru inceput, intotdeauna pornim de la matricea identitate:



Aceasta matrice are proprietatea ca, cu orice matrice am inmulti-o, sau daca inmultim orice matrice cu ea, obtinem matricea respectiva. O notam I (i mare) si scriem relatia de mai sus astfel (A matrice oarecare):



De asemenea, daca transformam un vector dupa I, acesta nu va suferi nici o schimbare.

Pentru a translata un vector cu (x, y, z) (adica x unitati pe axa OX, y pe axa OY si z pe axa OZ), vom folosi urmatoarea configuratie:



Transformand un vector dupa aceasta matrice vom obtine un vector mutat cu (x, y, z). De exemplu, daca transformam pe (2, 5, 1) dupa matricea



Obtinem vectorul (5, 9, 3), adica (2+3, 5+4, 1+2).

Scalarea se face construind o matrice de forma:



Unde x, y si z sunt factorii cu care se scaleaza pe OX, OY respectiv OZ. De exemplu, daca transformam pe (2, 5, 1) dupa matricea



Obtinem vectorul (10, 5, 2), adica (2*5, 5*1, 1*2).



Si nu in ultimul rand, rotatiile. Rotatiile se pot face dupa fiecare din cele trei axe. Insa sensul este distinct pentru cele doua metode de reprezentare a coordonatelor (de mana stanga si de mana dreapta). Noi vom folosi, de acum incolo, un sistem de mana dreapta (figura 5). Asta inseamna ca vom roti in sensul acelor de ceasornic pe OX si OY si in sens invers acelor de ceasornic pe OZ (sensurile se considera privind de la negativ la pozitiv de-a lungul axei).

Asadar, pentru a roti pe OX cu alfa radieni folosim o matrice ca:



Pentru a roti pe OY cu alfa radieni:



Iar pentru a roti pe OZ cu alfa radieni:



Acum partea frumoasa la matricile de transformare: pot fi combinate prin inmultire!

Incepand cu matricea identitate (I), construim alte matrici secundare (dupa modelele de mai sus) si le inmultim, pe rand, cu matricea principala. De notat ca ordinea este foarte importanta, deci una e sa translatezi si apoi sa rotesti, si alta e sa o faci pe invers. Si se inmulteste matricea principala cu fiecare matrice pe rand, nu invers.

Ca idee, este mai eficient sa construim o singura matrice de transformare prin inmultiri si sa transformam fiecare vector dupa ea, decat sa avem mai multe matrici pentru fiecare transformare simpla si sa trecem vectorii prin toate, pe rand.

Ok, o sa ziceti, am inteles ce si cum cu matricile, dar cum transformam un vector? Ei bine, transformarea unui vector este la fel de simpla ca inmultirea a doua matrici. De fapt este o inmultire de doua matrici, intre matricea de transformare si vectorul nostru !

Stiu, suna ciudat pana acum, dar pana la urma vectorul poate fi considerat o matrice cu 4 linii si o coloana. Cum patru? va intrebati. Este timpul sa vorbim despre coordonate afine si omogene.

Vorbeam acum ceva timp despre vectori si cum ca ei tin trei valori. Ei bine, este adevarat, pentru coordonate afine. Coordonatele afine sunt cele de care am vorbit pana acum: o valoare pentru fiecare axa. Trei axe trei valori.

Coordonatele omogene sunt ceva mai ciudate. Pentru n dimensiuni avem n+1 valori din care primele n au aceeasi semnificatie ca si in cazul coordonatelor afine iar ultima este un factor de scalare. Coordonatele omogene reprezinta defapt acelasi punct pe un plan de proiectie (ca idee se aseamana cu vectorii de directie desi sunt doua lucruri distincte). Nu vom intra in mai multe amanunte, trebuie doar sa stim ca un vector (x, y, z) in coordonate afine este (x, y, z, 1) in coordonate omogene. Ca sa aducem un vector A (x, y, z, w) de la coordonate omogene la coordonate afine facem urmatoarea conversie:



Cand inmultim un vector cu o matrice (de fapt, e exact pe invers, inmultim matricea cu vectorul, dar suna ciudat ) vom folosi vectorul in coordonate omogene, cu w=1. Atentie insa! Matricea returnata este tot un vector in coordonate omogene insa w nu mai este neaparat 1. Asa ca trebuie facuta conversia de mai sus inainte de a continua.

Pentru a nu mai construi o matrice secundara de fiecare data cand vrem sa transformam vectorul dupa o matrice, putem folosi direct urmatoarea formula:



Unde A este vectorul ce trebuie transformat, B este vectorul rezultant, M este matricea de transformare iar w este un scalar.

As da un exemplu, insa forumla de mai sus le pune capac la toate si nici nu trebuie sa va mai bateti capul cu coordonatele omogene. Si oricum, este vorba de o simpla inmultire, intre o matrice 4x4 si o matrice 4x1. Banal!

Pentru cei care vor sa invete mai mult:
http://mathworld.wolfram.com/HomogeneousCoordinates.html
http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/BEARDSLEY/node1.html
http://www.gamespp.com/tutorials/matrixTransformationTutorial.html

In continuare, trebuie sa intelegem cate ceva despre spatiul ce va fi reprezentat pe ecran. Vom vorbi despre ...



FRUSTA

... Sau "frustum" in engleza.

Chiar daca lumea noastra virtuala (pe care o vom numi scena de acum) are sute de obiecte, alcatuite din mii de triunghiuri, pe noi ne intereseaza sa reprezentam numai o parte din ele. Pentru a face acest lucru trebuie sa luam cateva concepte din realitate si sa le adaptam aici.

Pentru orice reprezentare, ne va trebui un punct din care vom observa scena. Acesta poate fi oriunde in scena: in origine, langa un obiect, deasupra unui obiect sau in orice alta pozitie posibila. Ca echivalent in viata reala avem pozitia capului, care determina ce este vizibil ochilor si ce nu.

Dar incotro ne uitam? Pentru asta ne trebuie un vector de directie, care va defini directia pe care ne uitam: direct in sus sau in jos, in stanga, in dreapta pozitiei noastre sau in orice alta directie arbitrara.

Acum stim unde suntem si stim incotro ne uitam, dar ce nu stim este rotatia (pe OZ) a capului nostru. Putem sa ne lasam capul pe umarul stang sau cel drept si, desi pozitia si directia sunt aceleasi, imaginile sunt diferite. Pentru a defini rotatia vom avea un al treilea vector, o normala, ce va indica mereu "susul" capului ("up vector" in engleza). Jucandu-ne cu acest vector vom schimba si rotatia capului. Valoarea implicita este (0, 1, 0), capul sta drept.

Pana acum avem tot ce ne trebuie pentru a defini un cap care se uita de la o anumita pozitie intr-o directie. Insa "cap" este un termen cam neprofesional, asa ca vom folosi "camera virtuala" sau "camera". Ca si camera de filmat reala are un singur ochi care reda, pe spatiu bidimensional (TV/monitor), o parte din scena.

Dar pentru a nu ne complica viata si mai tare, putem face o chestie foarte misto, si anume sa extragem o matrice de transformare din cei trei vectori. Interesul nostru nu este neaparat sa miscam camera printre obiecte ci sa dam impresia aceasta, miscand toate celelalte obiecte pe langa camera. Cand mergem pe un coridor, intr-un joc, de fapt se misca coridorul pe langa noi, dandu-ne impresia ca noi ne miscam. De fapt camera ramane tot timpul in origine, uitandu-se pe directia inainte (0, 0, -1) (in coordonate de mana dreapta) si avand normala (0, 1, 0). Toti ceilalti vectori din scena se transforma dupa matricea camerei, dand impresia de stationare a obiectelor si miscare a camerei. Matricea camerei se construieste astfel:



Sau direct:



Unde P este vectorul de pozitie al camerei, U este normala camerei, L este vectorul de directie al camerei, R este produsul vectorial dintre U si L (vectorul perpendicular pe cele doua, in partea dreapta), A este matricea de rotatie a camerei, B este matricea de translatie a camerei iar C este matricea de transformare finala a camerei.

Desi corect este sa inmultim fiecare vector intai cu matricea de transformare pe care o dorim si apoi cu matricea camerei, este mai eficient sa le inmultim pe cele doua si sa transformam vectorul dupa o singura matrice. De notat ca inmultim matricea de transformare cu matricea camerei, nu invers.

Deci stim cum sa facem sa aducem toate triunghiurile din scena intr-o pozitie in care putem considera camera ca fiind in origine. Acum trebuie sa determinam care parte din scena o vom desena.



Volumul vizibil de o camera are forma unei piramide cu baza la infinit (figura 6). Din aceasta piramida, numai corpul de piramida delimitat de cele doua plane de taiere (planul apropiat si cel departat), numit si frusta, are proprietatea ca va fi reprezentat integral (explicatia mai tarziu). Tot ce nu se afla in frusta nu va fi desenat deloc iar ceea ce se afla inauntru va fi desenat complet.



Frusta poate fi definita prin trei valori: planul apropiat de taiere ("near clipping plane"), planul departat de taiere ("far clipping plane") si unghiul camerei ("field of view - fov") (figura 7).



Acum, pentru a reprezenta obiectele tridimensionale din frusta, vom alege un plan intre pozitia camerei si planul apropiat de taiere (poate fi chiar planul apropiat) si facem proiectia fiecarui obiect pe acesta (figura . Cu putina gandire va veti da seama ca nu conteaza ce plan vom alege, proiectia va fi aceeasi.

Asadar, acum am inteles cum functioneaza faza cu camera. Mergem mai departe pentru a intelege cum anume se face proiectia de care vorbeam mai sus.



MATRICEA DE PROIECTIE

Triunghiurile (si primitivele in general) au o proprietate foarte importanta: un triunghi in spatiul tridimensional este tot un triunghi pe planul de proiectie. De aici ajungem la concluzia ca putem proiecta un triunghi proiectand fiecare din cele trei puncte ale sale.

Pentru a proiecta un vector (punct al unui triunghi) din frustum in planul de proiectie avem nevoie de o matrice de transformare mai speciala, numita matrice de proiectie. Aceasta este construita in felul urmator:



Unde P este matricea de proiectie, I este matricea identitate, fov este unghiul camerei, n este distanta de la camera la planul apropiat de taiere, f este distanta de la camera la planul departat de taiere iar asp este aspectul (4/3 pentru monitoare normale, 16/10 pentru widescreen sau orice alt aspect pentru randare in fereastra).

Dupa ce inmultim matricea de proiectie cu un vector vom obtine un alt vector, tot in trei dimensiuni. Fiecare din componentele sale ia valori in intervalul [-1, 1] daca vectorul initial se afla in interiorul frustei si alte valori daca se afla in afara frustei.



Astfel, x=-1 reprezinta partea stanga a proiectiei pe planul de proiectie, x=1 reprezinta partea drapta, y=-1 reprezinta partea de jos iar y=1 reprezinta partea de sus. Z ia valori tot de la -1 la 1 insa acesta nu mai influenteaza in nici un fel pozitia punctului in planul de proiectie si poate fi chiar ignorat. De notat este ca ne va fi util mai tarziu, iar z=-1 inseamna ca vectorul initial se afla chiar pe planul apropiat de taiere iar z=1 pe planul departat (figura 9).



O nota foarte importanta, care ne va folosi cand vom discuta despre rasterizare: daca x si y cresc liniar dupa proiectie fata de inainte, acelasi lucru nu se poate spune si despre z (figura 10).

Si aici, dragi cititori, se incheie prima parte a tutorialului. Mai departe vom discuta aspecte legate strict de randarea pe CPU, ajutandu-ne de cunostintele adunate pana acum. Sa incepem asadar cu ...



BUFFERELE

Daca pana acum am discutat lucrurile teoretic, acum vom vorbi despre implementari si algoritmi precum si diferite greutati ce le putem intampina pe drum si rezolvarile acestora. De asemenea, voi vorbi in paralel si despre implementarea mea, un mic software renderer care il puteti downloada aici (http://www.planetrimio.com/download/3dos.rar).

Vom vorbi putin despre buffere pentru ca este un concept destul de important. In implementarea mea sunt doua buffere: de culoare si de adancime. Ambele sunt doua tablouri bidimensionale de m linii si n coloane, in care fiecare celula reprezinta caractereisticile unui pixel. De exemplu, la o rezolutie de 800x600 vom avea un buffer de 600 linii si 800 coloane in cazul in care randarea se face fullscreen.

Spre deosebire de matrici, aceste buffere le vom apela sub forma:



Cu indexarea incepand de la 0. Deci coltul stanga sus va fi (0, 0) iar coltul drapta jos va fi (latime-1, inaltime-1).

Bufferul de culoare va tine in fiecare celula culoarea pixelului intr-un format oarecare. Cel mai utilizat in ziua de azi este RGB sau RGBA cu 8 biti pe componenta de culoare. Asta inseamna 24 sau 32 de biti (3 sau 4 bytes) pe culoare.

RGB inseamna Red Green Blue, deci fiecare culoare de baza va avea 8 biti la dispozitie (adica 256 valori) iar culoarea finala va fi amestecarea in proportiile specificate de cei 8 biti ai fiecarei culori de baza. RGBA mai adauga inca o componenta, componenta Alpha (sau transparenta) insa nu vom discuta de asa ceva in acest tutorial.

Bufferul de adancime ne va folosi pentru determinarea pixelilor vizibili. Sa analizam urmatoarea situatie: doua triunghiuri se intersecteaza, astfel incat fiecare se vede numai partial. Daca am desena in ordine fiecare primitiv, cel desenat ultimul va aparea peste cel desenat primul, ceea ce nu este corect. Pentru rezolvarea acestei probleme sunt doua solutii.

Prima consta in algoritmul pictorului ("painter's algorithm") si anume sa retinem toate primitivele ce trebuiesc desenate, sa le calculam la fiecare media aritmetica dintre cele trei valori z si apoi sa le sortam de la cel mai mare z la cel mai mic si sa le desenam (de notat ca vorbim de vectori proiectati). In acest fel desenam intai primitivele cele mai departate apoi cele mai apropiate. Insa aceasta metoda greseste in situatii mai complexe, cum este cea pe care o discutam: doua primitive care se intersecteaza.



Pentru a rezolva aceasta problema (figura 11) vom folosi un z-buffer (sau depth buffer, cum mai este numit). Acesta va retine z-ul fiecarui pixel si, inainte de a desena un pixel nou, verifica daca z-ul acestuia este mai mic decat cel deja in buffer. Daca nu este, inseamna ca pixelul se afla in spate iar desenarea lui este abandonata. Acest buffer este 100% corect si ne salveaza si de sortarea primitivelor.

Si nu in ultimul rand, trebuie sa discutam double buffering. V-ati intrebat cumva la ce ne trebuie un buffer de culoare cand putem scrie direct in memoria video? De ce sa mai folosim inca 1-2MB pentru un buffer care nu este necesar? Raspunsul este simplu: daca imediat dupa ce am terminat randarea ne apucam sa randam urmatorul frame, vom vedea practic cum se umple ecranul de pixeli. Oricat de rapid ar fi procesul, tot ar fi vizibil si ar arata extrem de urat.

In schimb, daca randam intr-un buffer de culoare si apoi copiem bufferul in memoria video (aka direct pe ecran) extrem de repede, imaginea ar sta nealterata pana am desena noul frame si l-am copia din nou, in memoria video. Am scapat de "flicker" !

In implementarea mea folosesc modul 320x200x256c, adica o rezolutie de 320x200 si 256 culori (nu, nu este RGB pe 24 biti, care are 16 milioane de culori ). Ne sunt de ajuns pentru scopuri demonstrative iar renderul, fiind codat in BP7, este limitat la 64kb pe segment de memorie (adica o variabila nu are voie sa aiba mai mult de 64k). Vom avea deci doua buffere, fiecare putin sub limita de 64k, unul pentru culoare si unul pentru adancime, fiecare de 8 biti.

Alocarea memoriei o fac dinamic iar mutarea valorilor dintr-o parte in alta a memoriei o fac cu procedura Move specifica Borland Pascal. Double bufferingul il fac copiind bufferul de culoare la adresa A000:0000 (inceputul memoriei video in cazul modului grafic folosit).



PIPELINEUL

Pipelineul reprezinta toti pasii care ii facem de la primirea datelor de intrare pana la predarea datelor de iesire. Acesta se va materializa sub forma unui algoritm complex ce va primi la fiecare apelare un singur primitiv din scena si il va desena in buffere si, in consecinta, pe ecran.

Primul pas la primirea unui primitiv este inmultirea matricii de transformare cu fiecare din vectori, pentru a determina pozitia finala in scena a primitivului. Dupa aceasta urmeaza inmultirea matricii de transformare a camerei cu fiecare vector, avand in momentul acesta primitivul pozitionat relativ fata de camera (in loc de origine, cum era inainte).

Dupa cum am mentionat mai devreme, putem inmulti cele doua matrici (de transformare si a camerei) inainte pentru a optimiza numarul de transformari de vectori. Aceasta metoda este cu atat mai folositoare cu cat obiectul are mai multi vertecsi (injumatatind practic numarul de transformari).

Urmeaza proiectia care se face prin inmultirea matricii de proiectie cu vectorii. Acum avem vectorii pozitionati in planul de proiectie (spatiu 2D) si suntem gata sa mergem mai departe.

Acum urmeaza clippingul. Pana aici am primit primitive atat din interiorul frustei, cat si partial sau total in afara ei. Acesta este pasul in care vom lua fiecare primitiv si il vom "taia" dupa cele sase planuri care delimiteaza frusta.



Procesul de taiere ("clipping") este unul complex si nu il voi discuta in acest articol (de fapt, clippingul ar putea face subiectul unui articol la fel de mare ca acesta, daca nu mai mare). Ce trebuie sa stiti este ca la sfarsit vor ramane de desenat numai partile din primitiv care sunt in frusta. Daca va intrebati ce se intampla cu un triunghi care intersecteaza doua planuri din cele sase, uitati-va la figura 12 si veti observa cum triunghiul este impartit in doua parti procesate separat.

In implementarea mea abordez o metoda de clipping extrem de proasta dar extrem de simplu de implementat. Din moment ce in demonstratie primitivele nu vor iesi cu mult in afara frustei, voi face clipping per pixel, adica la procesul de rasterizare, despre care vom vorbi mai tarziu, lasand primitivul la acest pas neatins.

Trecem la cuantizare, convertirea componentelor x si y a fiecarui vector din floaturi (scalari cu virgula mobila) in intregi, care reprezinta pozitia (in pixeli) in buffer al fiecarui punct. Deci (-1, -1) va deveni (0, 0), (0, 0) va deveni (latime/2, inaltime/2) iar (1, 1) va deveni (latime-1, inaltime-1). Aceasta conversie o facem in felul urmator:



Unde x si y sunt valorile intregi care le cautam, P este vectorul de pozitie al vertexului, dupa proiectie, iar latime si inaltime sunt dimensiunile bufferului.

La componenta z treaba sta putin altfel. Calculul se face in felul urmator:



Unde b este numarul de biti alocati depth bufferului. Astfel, pentru un depth buffer de 16 biti, -1 va deveni 0, 0 va deveni 32767 iar 1 va deveni 65535 (2 la puterea a 16-a).

Acum avem un primitiv definit prin coordonate intregi care se afla sigur in frustum. Trecem la urmatorul pas care este rasterizarea.



RASTERIZAREA UNUI PUNCT

Rasterizarea este procesul prin care, danduni-se un primitiv proiectat si cuantizat, noi umplem spatiul bidimensional dintre vertecsii sai cu culoare. Acest proces este responsabil pentru cea mai mare pierdere in putere de calcul in cazul randarii pe CPU. Timpul adunat rasterizarii unui frame (numai rasterizarea, nu si celelalte calcule) se numeste timp de umplere (sau "fill time" in engleza).

Vom incepe cu rasterizarea unui punct, care este si cea mai banala. Vom extrage intai din depth buffer valoarea curenta. Daca aceasta este mai mare decat z-ul vectorului care l-am primit, atunci vom scrie noul z peste cel vechi precum si culoarea pixelului in color buffer. Daca este mai mic in schimb, vectorul este in spatele geometriei desenate pana in acest moment, deci nu trebuie desenat. Nu mai scriem nimic.

Vorbeam despre metoda de clipping folosita de mine in demo. Ei bine, aceasta verifica, pe langa valoarea din z, si daca se afla in dimensiunile bufferului (sa nu aiba x, y sau z mai mici ca 0, x mai mare ca latimea, y mai mare ca inaltimea sau z mai mare ca marimea z-bufferului). Chiar daca la puncte nu se simte, daca desenam triunghiuri enorme (care ies cu mult din frusta), timpul de clipping va fi EXTREM de mare (ducand randarea la mult sub un frame pe secunda, poate chiar crapand). Deci nu este o metoda buna, mai ales ca poate complica si implementarea, lasand loc de o multime de erori "Division by zero".



RASTERIZAREA UNEI LINII

Ei, si iata ca am ajuns si la partea mai grea a rasterizarii. In primul rand, sa definim interpolarea.

Interpolarea este determinarea unor noi valori pornind de la un set de valori discrete. Noi vom folosi un tip de interpolare numit interpolare liniara. De exemplu, pentru a interpola intre 2 si 3 vom lua toade valorile dintre acestea. Nu e greu, insa noi vom face interpolare de cate trei seturi de astfel de valori (cate un set pentru fiecare axa).

Vom folosi algoritmul lui Bresenham (http://en.wikipedia.org/wiki/Bresenham's_line_algorithm) pentru a rasteriza linia. Vom incepe prin a determina panta dreptei definita de cele doua puncte in planul de proiectie. Panta dreptei o determinam astfel:





O regula de tinut minte este ca, la randarea unei linii, nu vom pune mai mult de un pixel si pe linie si pe coloana (figura 13). Vom avea fie mai multi pixeli pe o coloana, fie mai multi pe o linie, insa niciodata mai multi si pe linie si pe coloana.

Conform regulii de mai sus, trebuie sa gasim pe care din cele doua axe (x sau y) este diferenta de pixeli dintre cele doua coordonate mai mare. Daca pe x este mai mare decat pe y inseamna ca pe fiecare coloana nu va fi mai mult de un pixel. In schimb, daca pe y este diferenta mai mare decat pe x, nu vom avea mai mult de un pixel pe linie. Incercati sa analizati ce am spus pe o foaie de matematica.

Daca m > 1 suntem in primul caz si, trecand prin fiecare coloana de la x1 la x2, trebuie sa gasim la fiecare linia pe care se afla pixelul (dupa cum am stabilit, pe coloana nu se va afla mai mult de un pixel). Codul C va arata cam asa:



Putem optimiza daca nu vom calcula la fiecare pixel cate o inmultire si o impartire. Ba chiar putem sa ne folosim de panta (m) pentru a calcula y la fiecare pas, pentru ca 1/m reprezinta numarul de pixeli urcati pe y pentru fiecare pixel urcat pe x (1/m este subunitar). Cod C:



Dupa cum observati am scapat de o gramada de calcule, insa se mai poate optimiza! Conversia din float in integer mananca ceva timp, asa ca putem face urmatoarea faza:



Avand in vedere ca 1/m este subunitar, sigur nu va creste cu mai mult de 1 vreodata, deci suntem siguri ca va merge mereu.

Pentru m <= 1 vom face acelasi lucru, numai ca vom lua pe y de la y1 la y2 si vom interpola pe x. Si atentie, am facut asta numai pentru cazul x1 x2, y1 y2. Patru cazuri, care pot fi aduse pana la doua, scriind cod inteligent (eu le-am adus la trei in demo, stiu ca am reusit si cu doua odata ). Va las pe voi sa gasiti cum.

La ce trebuie sa fim atenti sunt diviziunile cu zero. Verificati inainte de fiecare impartire si puneti manual rezultatul infinit (sau un numar foarte mare) daca compilatorul vostru nu o face pentru voi. Este extrem de stresant sa iti crape programul la un moment arbitrar fara sa stii de ce.

Ce nu am facut in cod este interpolarea lui z. Da, da, ne trebuie si z, ca sa putem sa facem depth testing. Z se interpoleaza in acelasi mod ca si y in exemplul nostru, insa fara ultima optimizare (pentru ca pe z putem sa crestem si cu 10 unitati odata). Cod C:



Si cam atat de rasterizarea unei linii. Nu este prea simplu dar nici prea complicat insa asigurati-va ca intelegeti foarte bine cum funcioneaza, pentru ca la triunghiuri va fi MULT mai complicat.

Si inainte sa incheiem ideea, sa ne amintim putin de graficele din figura 10. Ce ne spuneau ele este ca z nu creste liniar. Iar noi facem interpolare liniara pentru z, ceea ce este gresit. Insa avand in vedere ca vom folosi aceeasi metoda pentru toate primitivele, nu vom avea probleme mai departe. Insa va veni un timp cand aceasta problema ne va da in cap si va trebui sa gasim o metoda sa o ocolim.

De asemenea, tot acele grafice ne spun ca nu trebuie sa pune planul apropiat de taiere prea aproape de camera. Cel mai elocvent argument este acesta: la un znear de 0.1 si zfar de 100, 50% din valori vor fi folosite numai pentru o zecime de unitate (de la 0.1 la 0.2), lasant restul pentru plaja [0.2, 100.0]. Cam nedrept, nu? Nici pentru znear de 1.0 situatia nu e mai roza. Dar ce inseamna asta? Inseamna ca primitivele din departare vor suferi de "z fighting", adica se vor bate pe aceeasi pozitie in depth buffer, dand un efect extrem de enervant de flicker (in care unul apare partial peste altul, pozitia schimbandu-se de la frame la frame). Atentie, atat OpenGL cat si Direct3D sufera de aceasta problema.

Asadar, sa continuam cu ...



RASTERIZAREA UNUI TRIUNGHI

Da, am ajuns la momentul crucial, si anume rasterizarea unui triunghi . Desi este mai complex ca la linie, foloseste acelasi principiu si veti vedea imediat cum.

Metoda pe care o folosim la triunghi consta in determinarea pe fiecare linie a pixelului de inceput si sfarsit. Dupa aceasta determinare vom rasteriza o serie orizontala de pixeli. Suna simplu, insa nu este chiar asa.

Primul pas pe care il vom face este sa ordonam vertecsii dupa y. Astfel, vom avea in v1 vertexul cel mai de sus al triunghiului, in v2 vertexul cel mai de jos iar in v3 vertexul de la mijloc. Acum putem imparti triunghiul in doua parti care le vom rasteriza separat: partea de deasupra lui v3 si de sub v3. De notat ca pixelul de inceput nu trebuie sa fie neaparat in stanga celui de sfarsit.

De data aceasta nu trebuie sa ne mai batem capul cu panta liniei si cele opt cazuri, asa ca vom face o interpolare simpla. Vom merge pe y, din unu in unu, de la y1 la y3. Vom initializa pasul pentru interpolare pentru ambele margini (de la x1 la x2 si de la x1 la x3) precum si pe z (de la z1 la z2 si de la z1 la z3). Dupa ce determinam (la fiecare pas al interpolarii) x de inceput si x de sfarsit precum si z de inceput si z de sfarsit mai interpolam odata pe linie, pentru a determina valorile lui z pentru fiecare x. Cod C:



De notat ca trebuiesc tratate separat cazurile xs xe.
Acum facem acelasi lucru pentru partea de jos, fara a mai reincepe interpolarea xs (care merge pe segmentul lung, de la v1 la v2). Cod C:



De notat ca nu este cea mai eficienta metoda (se mai pot face optimizari, daca va tine sa va afundati si mai tare in cod), insa aceasta este cea mai simpla.

Frumos, veti spune, dar de ce este de aceeasi culoare? Pai, daca vreti sa mai puneti si imagini pe triunghiuri, cititi in continuare, veti afla cum.



TEXTURAREA

Sau "texture mapping" in engleza. Pana acum am considerat fiecare vertex ca avand o singura proprietate (un vector de pozitie). Ei, acum ii mai adaugam una: pozitia in textura printr-o pereche de coordonate (u, v) (adica x si y in planul texturii). Aceasta va determina in ce fel va fi pusa textura pe primitiv. Cazul care il vom discuta este maparea texturii pe un triunghi (figura 14). Dupa cum se observa, fiecare vertex are o pozitie in textura. Aceasta nu se schimba (si nici pozitiile marginilor triunghiului in textura). Deci texelii (pixelii texturii) care ii avem in interiorul triunghiului mereu vor fi aceiasi, numai ca distorsionati dupa cum este proiectat triunghiul.



Sunt doua posibilitati de a reprezenta pozitia in textura, prin texeli (u si v reprezinta pixeli in textura) sau, varianta mai raspandita, reprezentarea scalara (cu valori de la 0 la 1, unde 0 este marginea din stanga sau marginea de sus iar 1 marginea din drapta sau marginea de jos). Aceasta metoda are avantajul de a fi independenta de marimea texturii (u=0.37 si v=0.56 va fi acelasi pentru o textura 32x32 sau 1024x1024 pe cand u=37 si v=56 va fi diferita in cele doua cazuri).

Texturarea nu ridica alta problema decat interpolarea coordonatelor (u, v) in acelasi mod in care interpolam si x, y sau z. Acestea vor fi interpolate ca si xs, xe, zs, ze pe toata marginea si apoi inca odata pe linie. Deci vom mai avea us, vs, ue, ve interpolate o data pe margini intre u1, v1, u2, v2, u3 si v3 si u si v interpolate odata pe linie intre us, ue, vs, ve. Nimic mai simplu .



Acum sa analizam urmatorul caz: doua triunghiuri care formeaza un patrat, mapate fiecare astfel incat sa putem reprezenta toata textura (fiecare vertex e mapat pe un colt). Acum sa il rotim dupa OX putin (figura 15). Observati o problema? Ei bine, ce am discutat pana acum se numeste texturare afina si, desi este rapida, nu este cea mai corecta (vom vedea de ce). Folositi demo-ul cu valorile (6, 1, 0.2) pentru a observa acelasi efect in real time.



TEXTURAREA CU CORECTIE DE PERSPECTIVA

Problema cu texturarea afina o puteti observa in figura 16. Marimea unui texel proiectat trebuie sa fie mai mica cu cat z-ul este mai departe. Interpoland liniar, noi nu tinem cont de acest lucru.



Cum rezolvam? Pai trebuie sa impartim fiecare coordonata de textura cu z-ul vertexului respectiv si sa interpolam valorile acestea. Deci vom interpola us, ue, vs, ve intre u1/z1, v1/z1, u2/z2, v2/z2, u3/z2 si v3/z3. Dupa asta vom interpola normal pe linie pe u si v intre us, vs, ue si ve, iar pe u si v le vom inmulti cu z.

Dar, aici vine problema care ziceam ca ne va da in cap. Z-ul pe care il interpolam noi nu este corect. Solutia este sa mai interpolam (inca?) o valoare. Este demonstrat aici (http://www.lysator.liu.se/~mikaelk/doc/perspectivetexture/) ca 1/z este liniar in spatiul ecranului, adica acesta, spre deosebire de z, creste cu un pas stabilit si calculabil.

Asadar, mai interpolam pe margini si pe dzs si dze intre 1/z1, 1/z2 si 1/z3 la fel cum facem cu xs si xe, dupa care interpolam pe linie pe dz intre dzs si dze iar din dz vom putea scoate z-ul real al pixelului. Impartind pe u si v la dz vom obtine coordonatele (u, v) reale ale pixelului.



OPTIMIZARI CORECTIE DE PERSPECTIVA

Desi e frumoasa corectia de perspectiva, este si mare consumatoare de putere de calcul. Sunt mai multe metode de a optimiza acest proces, insa cea mai raspandita si eficienta se executa la nivel de linie.

La ultima interpolare, cea pe linie, nu se mai calculeaza z-ul real la toti pixelii, ci din n in n pixeli (n poate fi 4, 8, 16 etc) iar intre acestia se face (alta?) interpolare liniara. Metoda imbunatateste performanta si, cu putin tweaking pentru fiecare rezolutie, se poate gasi n-ul magic la care sa nu se observe micile glitchuri.



INCHEIERE

Chiar mi-a placut sa scriu acest articol. Desi mi-a mancat doua zile scrisul lui efectiv si inca doua scrisul demoului, nu imi pare rau. Chiar deloc! Si am si invatat sa vorbesc pe romaneste in termeni tehnici! Multumiri celor care mi-au suportau mass-urile cu intrebari legate de traducere si nu numai, multumiri lui Nekitu care a lansat si sustine o comunitate de gamedevi in care eu ma simt ca acasa, multumiri mamei si tatei ... eh, sa ne oprim aici . Pana la urmatorul articol, auf wiedersehen!