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