Sistemi Multimediali II
Lezione 9:
davanti e dietro.
rimozione delle superfici nascoste
Università dell’Insubria
Facoltà di Scienze MFN di Varese
Corso di Laurea in Informatica
Anno Accademico 2004/05
Marco Tarini
Rimozioni delle superfici nascoste
• Gli oggetti più vicini devono
coprire quelli più lontani
– gli oggetti lontani sono "occlusi"
da quelli più vicini
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 2/40
Rimozioni delle superfici nascoste
• Non e' occlusion culling
– che puo' solo rimuovere
interi triangoli occlusi (magari a gruppi)
– che è solo una ottimizzazione
superfici
• Back-face culling non basta
non back-facing,
non totalmente occluse
ma parzialemnte occluse
– esempio:
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 3/40
Rimozioni delle superfici nascoste
• Soluzione 1:
– dividere ogni triangolo
parzialmente occluso
in parte visibile e parte occlusa?
• facendo una operazione di clipping
Come si trovano le coppie occluso/occlusore?
Clipping di un triangolo e un altro?
E dove, nel pipeline HW?
SOLUZIONE IMPROPONIBILE
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 4/40
Rimozioni delle superfici nascoste
• Soluzione 2:
– disegnare solo poligoni interi,
ma nell'ordine giusto
– noto come "algoritmo del pittore"
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 5/40
Algoritmo del pittore (depth sorting)
• Data una scena (composta da primitive)
– ordinare le primitive per profondità
• dalla più remota alla più vicina al punto di vista
– mandarle tutte (in ordine)
Scomodo!
Poco efficente!
Pensare al progetto
che abbiamo fatto.
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 6/40
x
Algoritmo del pittore (depth sorting)
setup
rasterizer
punti
setup
rasterizer
triangoli
setup
rasterizer
segmenti
computazioni
per frammento
Vertici poriettati
& attributi
computati
Vertici
computazioni
per vertice
& loro attributi
DOVE?
Frammenti
& attributi
interpolati
prima di mandare i triangoli.
Fatto dalla CPU ! 
Screen
buffer
y
v1
v0
v2
v1
v0
z
v2
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 7/40
Algoritmo del pittore (depth sorting)
• Data una scena (composta da primitive)
– ordinare le primitive per profondità
– mandarle tutte (in ordine)
Sorting! Complessità
pesudolineare col
numero di primitive.

Una primitiva non
ha una sola profondità!
piuttosto ha una profondità
max e una min
in comp graph,
peggio di lineare vuol
dire MALE
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 8/40
Algoritmo del pittore (depth sorting)
• La primitiva A può essere
disegnata per prima
• Ma va prima C o D?
Profondità
• Ma poi,
esiste sempre
un "ordine giusto"?
A
zmax
zmin
E
B
C
D
Primitive
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 9/40
Algoritmo del pittore (depth sorting)
• La primitiva A può essere
disegnata per prima
• Ma va prima C o D?
• Ma poi,
esiste sempre
un "ordine giusto"?
– NO!
• intersezioni
– NO!
• cicli di sovrapposizioni
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 10/40
Algoritmo del pittore (depth sorting)
• Oneroso
– sorting: (n log (n))
– e nella parte software!
• Mal adattato allo schema HW
– deve lavorare in spazio occhio
...ma prima della proiezione HW ?!
– lavorare globalmente su tutta la scena prima di mandare
la prima primitiva
• Scomodo all'atto pratico
– le primitive sono già "ordinate" semanticamente (scene-graph)
• Test difficili
– in acluni casi (quando gli intervalli min z e max z non sono disgiunti)
• Bisogna comunque fare clipping
– in altri casi (intersezione, cicli)
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 11/40
Algoritmo del pittore (depth sorting)
• In pratica, viene usato solo quando e' facile
ordinare preventivamente le primitive
– in fase di preprocessing
• Esempio: terreno come campo di altezza
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 12/40
Rimozioni delle superfici nascoste
• Soluzione 3:
– rimuovere le superfici nascoste con un
TEST PER FRAMMENTO
– algoritmo dello "Z-buffer"
• o "Depth-buffer"
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 13/40
rasterizer
punti
setup
rasterizer
triangoli
setup
rasterizer
segmenti
computazioni
per frammento
setup
Frammenti
& attributi
interpolati
Vertici
& attributi
computati
computazioni
per vertice
Vertici
& loro attributi
Algoritmo dello z-buffer
RGB finale
per ogni frammento
Screen
buffer
Depth
buffer
profondità
per ogni frammento
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 14/40
Transform.
Metti la z
finale come
attributo
aggiuntivo
rasterizer
punti
setup
rasterizer
triangoli
setup
rasterizer
segmenti
Interpola
la z
(come tutti
gli attributi)
computazioni
per frammento
setup
Frammenti
& attributi
interpolati
Vertici
& attributi
computati
computazioni
per vertice
Vertici
& loro attributi
Algoritmo dello z-buffer
Screen
buffer
Depth
buffer
Frammento con screen coordinates (x,y)
e attributo interpolato z:
depth test
if ( z <= DepthBuffer[x,y] ) {
Scrivi frammento
DepthBuffer[x,y] = z
}
else scarta (KILL) frammento
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 15/40
rasterizer
punti
setup
rasterizer
triangoli
setup
rasterizer
segmenti
computazioni
per frammento
setup
Frammenti
& attributi
interpolati
Vertici
& attributi
computati
computazioni
per vertice
Vertici
& loro attributi
Algoritmo dello z-buffer
Screen
buffer
Depth
buffer
ho bisogno di precisione!
almeno 16 bits
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 16/40
Algoritmo dello z-buffer:
esempio
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
+
64 64 64 64 64 64 64 64
64 64 64 64 64 64 64 64
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5 5 5 5
5 5 5
5 5
5
=
64 64 64 64 64 64 64 64
5
5
5
5
5
5
5
64
5
5
5
5
5
5
64
64
5
5
5
5
5
64
64
64
5
5
5
5
64
64
64
64
5
5
5
64
64
64
64
64
5
5
64
64
64
64
64
64
5
64
64
64
64
64
64
64
64
64
64
64
64
64
64
64
7
6 7
+
5 6 7
4 5 6 7
3 4 5 6 7
2 3 4 5 6 7
=
5
5
5
5
5
5
5
64
5
5
5
5
5
5
64
64
5
5
5
5
4
3
2
64
5
5
5
5
5
64
64
64
5
5
5
5
5
4
3
64
5
5
5
5
64
64
64
64
5
5
5
5
5
5
4
64
5
5
5
64
64
64
64
64
5
5
5
5
7
6
5
64
5
5
64
64
64
64
64
64
5
5
5
64
64
7
6
64
5
64
64
64
64
64
64
64
5
5
64
64
64
64
7
64
64
64
64
64
64
64
64
64
5
64
64
64
64
64
64
64
64
64
64
64
64
64
64
64
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 17/40
Algoritmo dello z-buffer:
proprietà
• Non dipende dall'ordine delle primitive 
• Funziona su tutto
– anche su:
• Operazione per frammento
5
5
5
5
5
5
5 64
5
5
5
5
5
5 64 64
5
5
5
5
5 64 64 64
5
5
5
5 64 64 64 64
4
5
5
7 64 64 64 64
3
4
5
6
7 64 64 64
2
3
4
5
6
7 64 64
64 64 64 64 64 64 64 64
– Viene svolto nelle
"computazioni per frammento"
• Adatto all'implementazione HW
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 18/40
Algoritmo dello z-buffer:
difettucci
• Consumo memoria
– depth buffer = mezzo screen buffer
• Sia legge che scrive su dati condivisi
– (l'implementatore HW deve fare attenzione)
• Problemi di aliasing
– quando la precisione non e' sufficiente
– ad esempio, se si renderizzano due superfici
parallele molto vicine
• Male con le superfici semitrasparenti
– come vedremo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 19/40
In OpenGL
• Devo Abilitare il depth test:
manipolazioni di stato
(es. settare la matrice)
primitive
qui
glEnable(GL_DEPTH_TEST);
stato di OpenGL
tutto il pipeline
(proiezione, setup, rasterizzazione...)
Posso anche decidere le condizioni per
passare il test: GL_NEVER
GL_EQUAL
GL_LEQUAL
GL_GREATER
GL_NOTEQUAL
glDepthFunc( GL_LESS
GL_GEQUAL
GL_ALWAYS
)
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 20/40
pixels
In OpenGL e SDL
• Devo creare il depth buffer:
SDL_Init(SDL_INIT_VIDEO);
SDL_GL_SetAttribute( SDL_GL_DEPTH_SIZE, 16 );
SDL_SetVideoMode(640, 480, 0, SDL_OPENGL);
• Quando cancello lo schermo,
devo anche calcellare il depth buffer
...
glClear(
GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT
);
...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 21/40