Problema liniilor si suprafetelor ascunse in grafica 3D. Algoritmul PAINTER

Problema liniilor si suprafetelor ascunse in grafica 3D. Algoritmul PAINTER

Numele algoritmului provine de la similitudinea care exista intre ideea algoritmului si modul in care un pictor zugraveste o scena, desenand mai intai planurile indepartate apoi pe cele apropiate, in ordine. In acest fel primele desene sunt acoperite de cele efectuate ulterior , ramanand la vedere doar portiunile vizibile din locul din care este privita scena.

Iata etapele in care se desfasoara algoritmul:

1. Eliminarea suprafetelor ascunse;

2. Stabilirea unor prioritati pentru suprafetele vizibile;

3. Trasarea suprafetelor conform prioritatilor

1. Eliminarea suprafetelor ascunse

Pentru eliminarea suprafetelor ascunse se utilizeaza metoda testului de vizibilitate [2]. Sunt vizibile acele suprafete pemtru care produsul scalar dintre vectorul normal la suprafata si vectorul de vizualizare este pozitiv.

2. Stabilirea prioritatiilor pentru suprafetele vizibile

Stabilirea prioritatilor se face dupa cota Z a fiecarei suprafete. Cota Z este data de cea mai mare si de cea mai mica valoare a coordonatelor dupa axa OZ:

MinZ =

MaxZ =

unde n este numarul de puncte al suprafetei pentru care se calculeaza cota.

Prioritatile vor juca rolul unor ranguri cu ajutorul carora suprafetele vor fi sortate fie utilizand un algoritm de sortare prin numarare fie un algoritm de sortare topologica. Astfel, pentru oricare doua suprafete P si Q se va efectua o succesiune de teste in urma carora rezulta care din fete are prioritatea (rangul) mai mare:

Testul 1

Se noteaza cu MaxZ(P) , MinZ(P), MaxZ(Q) si MinZ(Q) cotele maxime si minime z pentru cele doua suprafete. Daca MaxZ(Q)<MinZ(P) , atunci fata Q este prioritara iar daca MaxZ(P)<MinZ(Q), fata P este prioritara (Figura 1).

Figura 1. Testul 1

Testul 2

Daca in urma aplicarii testului 1 nu se poate stabilii clar prioritatea unei fete, se trece la testul 2, care indica existenta suprapunerilor. Se incadreaza fetele in cate o zona rectangulara dupa cotele maxime si minime pe axele OX si OY, astfel:

Figura 2. Zona rectangulara a unei suprafete

Exista suprapuneri atunci cand zonele rectangulare ale celor doua suprafete se intrepatrund (Figura 4). Daca zonele rectangulare nu se intrepatrund (Figura 3), atunci suprafetele pot fi desenate in orice ordine.

Daca exista suprapuneri se trece la testul 3.

Testul 3

Acest test depisteaza suprapunerile reciproce. Planul care contine o suprafata imparte spatiul in doua. Daca o sprafata se afla in acelasi spatiu cu observatorul atunci aceasta va avea o prioritate mai mare decat suprafata care face impartirea, si invers, cand suprafata se afla in celalalt spatiu, ea va avea o prioritate mai mica. O suprafata se afla intr-o singura parte a unui plan atunci cand toate punctele ei se afla in acea parte. Atunci cand are puncte de-o parte si de alta a planului , suprafata este intersectata de plan.

Sa presupunem ca vrem sa vedem daca punctele suprafetei Q se afla de-o parte sau de alta a planului in care se afla suprafata P. Pentru aceasta se determina coeficientii A_P, B_P, C_P, D_P ale ecuatiei planului care contine P:

.

Forma determinant pentru ecuatia planului ce contine trei puncte de coordonate (x₁, y₁, z₁), (x₂ , y₂ , z₂ ) si (x₃, y₃, z₃ ) este:

.

Dezvoltand forma determinant si efectuand identificarea de termeni obtinem:

Daca inlocuim cu coordonatele punctelor care alcatuiesc fata Q in ecuatia planului mai sus determinata si obtinem numai valori mai mari sau egale cu zero, sau mai mici sau egale cu zero, atunci fata Q se afla de o parte sau de cealalta a planului P. Pentru valorile 0 punctele sunt chiar pe plan. Daca sunt puncte si de o parte si de cealalta a planului , atunci acesta intersecteaza fata.

Daca nici una dintre cele doua fete nu se afla fie de o parte fie de cealalta a planului care contine cealalta fata, avem suprapuneri reciproce si trecem la Testul 4.

Testul 4

In cazul suprapunerilor reciproce se recurge la scindarea uneia dintre fete. Impartirea se va face dupa intersectia dintre plane (P si Q). Iata o astfel de situatie in figura 5.

Figura 5. Suprapunere reciproca

In aceste situatii fie se imparte fata P fie fata Q. Prioritatile fetelor rezultate in raport de fata ramasa pot fi usor stabilite prin testele anterioare.

Intersectia dintre doua plane este o dreapta. Ecuatia carteziana a unei drepte in spatiu care contine doua puncte (x1,y1,z1) si (x2,y2,z2) este:

,

D: .

Se determina intersectia acestei drepte cu planul de ecuatie . Inlocuind relatiile D pentru x, y si z in ecuatia planului, obtinem:

.

Revenind si inlocuind in ecuatiile D se obtine x, y si z.

3. Trasarea suprafetelor conform prioritatilor

In urma efectuarii testelor, vor fi stabilite prioritati sub forma unor perechi de indici (i,j), cu semnificatia ca fata i este mai indepartata decat fata j si trebuie trasata prima. Trasarea suprafetelor se va face astfel incat sa fie respectate toate prioritatile (i,j). Pentru aceasta, extragerea suprafetelor se va realiza printr-un algoritm de sortare topologica.

Aplicatie

Consideram urmatorul obiect 3D reprezentand o casa:

Figura 6 Exemplu.

Datele prin care este descris obiectul sunt memorate intr-un fisier text, in felul urmator:

- pe prima linie este trecut n numarul de puncte din care este compus obiectul;

- in linia a doua este trecut m numarul de suprafete;

- pe urmatoarele n linii sunt trecute coordonatele fiecarui punct;

- pe ultimele 2m linii sunt trecute pentru fiecare suprafata numarul de puncte din care este compusa aceasta si punctele corespunzatoare.

Pentru casa din Figura 6 fisierul arata astfel:

Implementarea algoritmului

Pentru implementarea algoritmului am ales mediul Visual C si am utilizat functii din biblioteca grafica GDI. Iata cateva din procedurile care cuprind elemente esentiale ale implementarii:

void EcuatiaPlanului(double x1,double y1,double z1,double x2,double y2,double z2,

double x3,double y3,double z3,double &a,double &b,double &c,double &d)

void IntersectieDreaptaPlan(double x1,double y1,double z1,double x2,double y2,

double z2,double a,double b,double c,double d,

double &x,double &y,double &z)

void Scindare(int i,int j,int np[],int f[][10],double a[],double b[],

double c[],double d[],double punct[][3],int &m,int &n)

}

int p,l=0,l1=0,l2=0,f1[10],f2[10];

ps[k]=f[i][0];

for(p=0;p<k;p++)

if(p%2==0)

while(f[i][l]!=ps[p])

f1[l1]=n+p;l1++;

}

else

if(p!=k)

}

np[i]=l1;np[m]=l2;m++;

for(r=0;r<l1;r++)f[i][r]=f1[r];

for(r=0;r<l2;r++)f[m][r]=f2[r];

void Teste(int i,int j,double MaxZf[],double MinZf[],double MaxXf[],double MinXf[],

double MaxYf[],double MinYf[],

int npi,int npj,int f[][10],

double a[],double b[],double c[],double d[],

double o1,double o2,double o3,double p[][3],

int &k1,int &k2)

if(MaxZf[j]<=MinZf[i])

if(MaxXf[j]<=MinXf[i] || MaxXf[i]<=MinXf[j])

if(MaxZf[i]>MaxZf[j])else

if(MaxYf[j]<=MinYf[i] || MaxYf[i]<=MinYf[j])return;

if(MaxZf[i]>MaxZf[j])else

int DeOParteI,DeOParteJ;

// Se verifica daca toate punctele fetei i sunt intr-o parte a fetei j

r=0;

do

while(v==0&&r<npi);

if(r==npi)return;

ValoareI=v;

if(v<0)semn=-1.;else semn=1.;

DeOParteI=1;

while(r<npi)

}

r++;

}

// Clarificare fata i in raport cu observatorul

if(DeOParteI==1)

{

v = a[j]*o1+b[j]*o2+c[j]*o3+d[j];

if(v!=0)

{if(v*ValoareI>0)else }

}

// Se verifica daca toate punctele fetei j sunt intr-o parte a fetei i

r=0;

do

while(v==0&&r<npj);

if(r==npj)return;

ValoareJ=v;

if(v<0)semn=-1.;else semn=1.;

DeOParteJ=1;

while(r<npj)

}

r++;

}

// Se verifica pozitia observatorului in raport cu fata j

if(DeOParteJ==1)

{

v = a[i]*o1+b[i]*o2+c[i]*o3+d[i];

if(v!=0){if(v*ValoareJ>0)else }

}

k1=-2;

In Figura 7 sunt prezentate cateva iesiri obtinute prin rularea aplicatiei. Pozitiile difera prin schimbarea componentelor q si F din coordonatele sferice ale observatorului. Valoarea R a fost aleasa astfel incat observatorul sa se plaseze la o distanta de 10 ori mai mare decat cele mai distantate doua puncte intre ele care alcatuiesc obiectul. Deasemenea obiectul este centrat printr-o translatie a punctului O , care initial coincide cu punctul 1, in centrul de greutate al obiectului.

Figura 7

Algoritmul Z- Buffers

Pentru a putea prezenta ceea ce este si modul in care functioneaza un "Z buffer", mai intai trebuie sa prezentam notiunea de "Frame buffer".

Pe scurt, un Frame buffer este o matrice care aduna si memoreaza valorile pixelilor ce compun o imagine, pentru a putea fi folosite mai apoi de dispozitivul de afisare.

Sa avem in vedere un display de tip raster, ce are in spate un Frame buffer. Aceste display-uri pot sa deseneze foarte bine suprafete (poligoane pline) dar, in acelasi timp, pot sa lucreze si cu linii. In cazul in care folosim astfel de display-uri, problema suprafetelor ascunse poate fi pusa si in urmatorul mod: dorim sa aranjam Frame buffer-ul astfel incat culoarea afisata pentru fiecare din pixelii ce sunt memorati in matrice sa apartina suprafetei care este cea mai apropiata de observator pentru un anumit punct.

Pentru a face acest lucru, trebuie sa comparam intr-un fel toate suprafetele ce sunt proiectate pe acel pixel si apoi sa decidem care dintre ele poate fi vazuta. Va trebui sa sortam poligoanele in concordanta cu pozitia lor din spatiu. Aceasta sortare o vom numi "sortare geometrica". Notiunea este comuna problemelor legate de inlaturarea atat a suprafetelor ascunse cat si a liniilor ascunse.

O solutie simpla pentru o astfel de problema se bazeaza pe un dispozitiv numit "Z buffer".

Catmull a fost cel ce a descris primul un Z buffer. Acesta reprezinta o matrice de dimensiuni foarte mari, ce contine un punct de intrare pentru fiecare pixel al imaginii de afisat (in mod asemanator unui Frame buffer). Z buffer-ul este folosit pentru a retine valorile coordonatelor de pe axa OZ. Acest lucru ne este folositor pentru sortarea tuturor poligoanelor, in functie de pozitia de pe axa OZ a suprafetelor ce sunt afisate.

In momentul in care Frame buffer-ul este golit, toate elementele Z buffer-ului primesc o valoare negativa foarte mare (o valoare care nu poate sa apara in nici un caz, indiferent de modul in care arata imaginea ce trebuie afisata).

Valoarea initiala poate fi considerata drept pozitia de pe axa OZ a background-ului. Poligoanele vor fi introduse pe rand, unul cate unul in Frame buffer, de catre un interpretor al fisierului de afisare, folosind algoritmi de tip "scan conversion". Sa presupunem ca algoritmul care face vizibil fiecare pixel al poligonului cunoaste valoarea de pe axa OZ a proiectiei punctului ce trebuie afisat. Atunci, algoritmul ar putea sa compare pozitia de pe axa OZ a punctului din poligon cu valoarea care se regaseste in Z buffer si sa decida in urma acestei comparatii daca noua suprafata se situeaza in fata sau in spatele suprafetei ce este reprezentata in Frame buffer. Daca noua suprafata are o valoare z corespunzatoare proiectiei pe axa OZ mai mare decat valoarea ce este memorata in Z buffer, atunci aceasta se afla in fata actualei suprafete ce este memorata. Valoarea intensitatii ei este trecuta in Frame buffer, in timp ce valoarea z va fi pusa in Z buffer.

Daca insa, in urma comparatiei, algoritmul constata ca valoarea corespunzatoare z a suprafetei investigate este mai mica decat valoarea memorata in Z buffer, atunci aceasta suprafata se regaseste in spatele a cel putin unui poligon ce a fost investigat mai devreme. Noua suprafata va fi deci una ascunsa si nu va trebui sa fie desenata in cadrul imaginii la momentul respectiv. In consecinta, nu va fi introdusa nici o valoare noua in Frame buffer sau in Z buffer.

Comparatiile se desfasoara pentru fiecare pixel ce intra in componenta poligoanelor din imaginea afisata. Astfel, este necesar sa se poata determina valoarea proiectiei pe axa OZ a fiecarui pixel ce intra in alcatuirea poligoanelor.

Daca ar fi sa modificam sistemul nostru astfel incat sa poata folosi Z buffer-e pentru inlaturarea suprafetelor ascunse, am putea extinde fisierul de afisare pentru a retine coordonatele z ale vertex-urilor poligoanelor. Pornind de la coordonatele z ale vertex-urilor, se pot determina valorile z ale oricarui punct interior. Pentru a determina valorile coordonatelor z de-a lungul muchiilor la fiecare pas, tot ceea ce trebuie facut este sa se cunoasca valoarea z initiala si modificarile in z la fiecare pas in y pentru muchiile poligonului. Deci, pentru fiecare linie de scan, vom genera perechi de puncte corespunzatoare coordonatelor x, care vor indica unde sa se faca umplerea. Dar, in plus, cunoastem o valoare z pentru fiecare din punctele finale ale "fill - span-urilor". Daca aplicam din nou aceasta tehnica de interpolare liniara, de data aceasta folosind transformarea span-ului in z pentru fiecare pas in directia lui x, valorile lui z pentru fiecare pixel pot fi calculate.

Un algoritm de umplere ar trebui sa obtina coordonatele punctului final z drept argumente, sa efectueze interpolarea in x, si sa compare valorile z rezultate cu cele memorate in Z buffer. In urma acestor comparatii, va trebui sa decida daca este necesara schimbarea valorilor corespunzatoare intensitatilor din Frame buffer.

In cele mai multe cazuri, imaginile ce trebuiesc prelucrate sunt destul de complexe, astfel incat folosirea unui Z buffer poate fi extrem de costisitoare din punctul de vedere al sistemului de calcul.

Z buffer-ul necesita multa memorie (o intrare in matrice pentru fiecare pixel si fiecare intrare trebuie sa aiba alocat un numar suficient de biti pentru a acoperi toate valorile posibile pentru coordonatele z). Totodata, poate fi o mare consumatoare de timp, deoarece o decizie trebuie facuta pentru fiecare pixel in parte si nu pentru intreg poligonul.

Vazand aceste cerinte, s-ar putea considera faptul ca un Z buffer nu este tocmai o solutie viabila la problemele de inlaturare a suprafetelor ascunse. Totusi, Z buffer-ul are un mare avantaj: este o metoda foarte simpla. Atat de simpla incat ea este implementata hardware, pentru a rezolva problemele legate de viteza. Practic, de toate prelucrarile se va ocupa procesorul placii video, astfel incat procesorul sistemului poate fi folosit pentru alte operatii. Totodata, timpul necesar procesarii unei scene este proportional cu numarul obiectelor din scena (unele tehnici care compara fiecare poligon cu toate celelalte din scena necesita un interval de timp proportional cu patratul numarului de poligoane). Daca mai luam in considerare si faptul ca pretul memoriei este intr-o continua scadere, observam ca aceasta metoda (sau extensiile sale), reprezinta o solutie extrem de buna la problema suprafetelor ascunse.

In figurile urmatoare se vor putea observa diferentele dintre doua figuri geometrice simple, una in care se foloseste un Z buffer, iar cea de-a doua in care aceasta tehnica nu este folosita.

Figura 1. Reprezentare ce nu foloseste Z buffer-ul.

Figura 2. Reprezentare ce folosiste Z buffer-ul.

In OpenGL, Z buffer-ul si Frame buffer-ul se golesc astfel:

glClear(GL_DEPTH_BUFFER_BIT | GL_COLOR_BUFFER_BIT);

Totodata, Z buffer-ul este invocat in urmatorul mod:

glEnable( GL_DEPTH_TEST);