8 vizibilitate
DESCRIPTION
vizibilitateTRANSCRIPT
1
Determinarea vizibilitatii
2
Determinarea vizibilitatii
3
Algoritmi de eliminare a partilor nevizibile
Modelare Vizualiare Proiectie
Decupare Transformarea
fereastra-poarta
Generare primitive
Imagine
Obiecte 3D
4
Algoritmul Back Face Culling
5
Algoritmul Back Face Culling
Eliminarea fetelor spate
Poligon spate
6
Algoritmi de eliminare a partilor nevizibile
Modelare Vizualiare Proiectie
Decupare Transformarea
fereastra-poarta
Generare primitive
Imagine
Obiecte 3D Eliminare fete spate
7
Algoritmul Back Face Culling
Suprafete convexe
8
Algoritmul Back Face Culling
(x0,y0,z0)(x1,y1,z1)
(x2,y2,z2)
->
N
v1
v2
-
z
-
y
-
x
---
-----
k*Nj*Ni*NN
z1-z2 y1-y2 x1-x2
z0-z1 y0-y1 x0-x1
k j i
v2v1N
9
Back-face culling
α: [0o, 90o) poligon spate
α: 90o poligon = latura
α: (90o, 180o] poligon fata
V
F1
F2 N
α N
V
10
Algoritmul Back Face Culling
Fete spate
Fete fata
11
Algoritmul Back Face Culling - OpenGL
glEnable(GL_CULL_FACE);
glFrontFace(GL_CCW);
glCullFace(GL_BACK);
12
Algoritmi de eliminare a partilor nevizibile
Algoritmi in spatiul imagine
Algoritmi in spatiul obiect
13
Algoritmi de eliminare a partilor nevizibile
Algoritmi in spatiul imagine
for fiecare pixel P
determina obiectul O cel mai apropiat de observator de-a lungul proiectorului ce trece prin P
afiseaza pixelul P in culoarea obiectului O
14
Algoritmi de eliminare a partilor nevizibile
Algoritmi in spatiul obiect
for fiecare obiect O al scenei
Determina partile vizibile ale obiectului O (parti care nu sunt obturate de alte parti ale
sale sau de alte obiecte)
Afiseaza partile vizibile ale obiectului O
15
Eliminarea partilor nevizibile
Modelare Vizualiare Proiectie
Decupare Transformarea
fereastra-poarta
Generare primitive
Imagine
Obiecte 3D
Algoritmul z-buffer
16
Algoritmul z-buffer
2
1
3
P
•Algoritm in spatiul imagine
•Nu exista o ordine prestabilita pentru afisarea poligoanelor
17
Algoritmul z-buffer
Necesita ca strucura de date un buffer avand un numar de elemente egal cu rezolutia ecranului
Un element din buffer memoreaza informatia de adancime (z) asociata pixelului (x, y)
Pentru fiecare pixel este memorata si culoarea asociata
Poate fi implementat hard si soft
18
Exemplu - Z-buffer
19
Exemplu - Z-buffer
20
Exemplu - Z-buffer
21
Algoritmul z-buffer
//initializare
pentru fiecare pixel ecran (x, y)
ScriePixel(x, y, culoare_fond);
z_buff[x][y] = zmax; //zmax = z planului spate al
//volumului de vizualizare
pentru fiecare poligon P
pentru fiecare fragment (x, y, z) interior
daca z > z_buff[x][y] atunci
z_buff[x][y] = z;
cul = culoare fragment;
ScriePixel(x, y, cul);
22
Algoritmul z-Buffer
• Informatia de adancime pierde rapid precizia
• Z-fighting
• In OpenGL se poate folosi functia PoligonOffset
23
Algoritmul z-Buffer - OpenGL
glEnable(GL_DEPTH_TEST);
glDisable(GL_DEPTH_TEST);
glDepthFunc(functie); functie: GL_LESS, GL_LEQUAL,
GL_EQUAL, GL_NOTEQUAL, GL_GREATER, GL_GEQUAL,
glDepthMask(flag); flag: GL_FALSE, GL_TRUE
24
Algoritmul de partitionare binara a spatiului
Algoritm in spatiul obiect
Spatiul se partitioneaza prin plane de partitionare in mai multe zone
Procesul de partitionare continua pana se ajunge la o zona cu un singur poligon
In raport cu pozitia observatorului, algoritmul stabileste ordinea de afisare a seturilor de fete, pornind de la cea mai indepartata pana la cea mai apropiata
25
Algoritmul de partitionare binara a spatiului
1.Daca observatorul se afla in semiplanul fata al planului P, atunci ordinea de afisare a fetelor va fi F2, F1
2.Daca observatorul se afla in semiplanul spate al planului P, atunci ordinea de afisare a fetelor va fi: F1, F2
P - plan de partitionare->
N
semiplan fata
semiplan spate
F1
F2
26
Algoritmul de partitionare binara a spatiului
A C
B
2
4
1
3
A
C B
1 4 2 3
F
F F
S
S S
27
Algoritmul de partitionare binara a spatiului
A C
B
2
4
1
3
Obs
A
C B
1 4 2 3
F
F F
S
S S
28
Algoritmul de partitionare binara a spatiului
1
2 4
6
3
5
29
Algoritmul de partitionare binara a spatiului
1
2, 3b, 4b, 5
3a, 4a, 6
F S
1
2 4b
6
4a 3a
5
3b
30
Algoritmul de partitionare binara a spatiului
1 F S
3a
4a, 6
F
4b, 5a
2
F
3b,5b
2, 3b, 4b, 5
S
3a, 4a, 6
1
2 4b
5a
6
4a 3a
5b
3b
31
Algoritmul de partitionare binara a spatiului
1 F S
3a
4a, 6
F
4b, 5a
2
F
2, 3b, 4b, 5
S
3a, 4a, 6
3b
F
5b 1
2 4b
5a
6
4a 3a
5b
3b
32
Algoritmul de partitionare binara a spatiului
1
2 4b
5a
6
1 F S
4a 3a
3a
F
5b
2
F S
3b
3b
F
4b
F
5a 5b
4a
F
6
33
Algoritmul de partitionare binara a spatiului
ConstruiesteArbore(ListaPoligoane LP) daca LP == vida atunci intoarce NULL; P = alege un poligon din LP; Radacina = P; elimina P din LP
LFata = LSpate = NULL; pentru fiecare poligon Q din LP daca Q este in semiplanul fata planului Radacinii atunci Insereaza(Q, LFata); altfel daca Q este in semiplanul spate planului Radacinii atunci Insereaza(Q, LSpate); altfel descompune Q in QF si QS; Insereaza(QF, LFata); Insereaza(QS, LSpate); intoarce Arbore(Radacina, ConstruiesteArbore(LFata), ConstruiesteArbore(LSpate));
34
Algoritmul de partitionare binara a spatiului
AfisareScena(Arbore A)
daca A == vid atunci stop;
daca observatorul este in fata planului Radacinii atunci
AfisareScena(A->FiuSpate);
Afisare Radacina
AfisareScena(A->FiuFata);
altfel
AfisareScena(A->FiuFata);
Afisare Radacina
AfisareScena(A->FiuSpate);
35
Algoritmul Warnock
Divizeaza recursiv zona de afisare, pana se poate determina poligonul vizibil in acea zona sau dimensiunea zonei este 1 pixel.
acoperitor intersectat inclus disjunct
36
Algoritmul Warnock
37
0
0 0 0
00
0
1
M
1
1
1
1
M M
M
Algoritmul Warnock
0 – disjunct
1 – intersectat
M – mai multe fete poligonale
38
1 1 0 0
1 M M 1
1 M M M
0 1 1 1
Algoritmul Warnock
39
1
11
0
M M M M
M M M M
M M M M M
M M M
Algoritmul Warnock
40
Algoritmul Warnock
41
Algoritmul Warnock
acoperitor intersectat inclus disjunct
Poligoane:
•acoperitoare
•incluse
42
Algoritmul Warnock
Modelare Vizualiare Proiectie
Decupare Transformarea
fereastra-poarta
Generare primitive
Imagine
Obiecte 3D
Divizarea spatiului
43
Algoritmul Warnock
O zona de afisare cu dimensiunea mai mare de 1 pixel nu va mai fi divizata daca:
toate poligoanele sunt disjuncte fata de zona considerata
exista doar un poligon ce poate fi inclus sau acoperitor
exista mai multe poligoane incluse sau acoperitoare, dar cel mai apropiat de observator este un poligon acoperitor
44
Algoritmul Warnock
Warnock(Zona Z, ListaPligoane LP) { clasifica poligoanele din LP (poligoane incluse, acoperitoare, disjuncte, intersectate = incluse+disjunctte) elimina poligoanele disjuncte din LP ordoneaza poligoanele din LP in ordine descrescatoare dupa zmin al fiecarui poligon elimina din LP poligoanele care se afla in spatele primului (cel mai apropiat de observator) poligon acoperitor
45
Algoritmul Warnock
daca LP == vida atunci afiseaza zona Z in culoarea de fond; stop; daca LP contine un singur poligon atunci daca P este inclus atunci afiseaza zona Z in culoarea de fond; afiseaza poligon daca P este acoperitor atunci afiseaza zona Z in culoare poligon stop;
46
Algoritmul Warnock
daca zona Z are dimensiunea de 1 pixel (x, y) atunci
pentru fiecare poligon P din LP calculeaza z(x, y); determina max pentru z(x, y); afiseaza pixelul (x,y) in culoarea poligonului cu z(x, y) max stop; Warnock(Z1, LP); Warnock(Z2, LP); Warnock(Z3, LP); Warnock(Z4, LP); }
Z1
Z4Z3
Z2Z
47
Algoritmul Warnock
Warnock(Zona Z, ListaPligoane LP) { clasifica poligoanele din LP (poligoane incluse, acoperitoare, disjuncte, intersectate =
incluse+disjunctte) elimina poligoanele disjuncte din LP ordoneaza poligoanele din LP in ordine descrescatoare dupa zmin al fiecarui poligon elimina din LP poligoanele care se afla in spatele primului (cel mai apropiat de
observator) poligon acoperitor daca LP == vida atunci afiseaza zona Z in culoarea de fond; stop; daca LP contine un singur poligon atunci daca P este inclus atunci afiseaza zona Z in culoarea de fond; afiseaza poligon daca P este acoperitor atunci afiseaza zona Z in culoare poligon stop; daca zona Z are dimensiunea de 1 pixel (x, y) atunci pentru fiecare poligon P din LP calculeaza z(x, y); determina max pentru z(x, y); afiseaza pixelul (x,y) in culoarea poligonului cu z(x, y) max stop; Warnock(Z1, LP); Warnock(Z2, LP); Warnock(Z3, LP); Warnock(Z4, LP); }
Z1
Z4Z3
Z2Z