Corso di Programmazione Grafica per il Tempo Reale
Ottimizzazione della scena:
culling (decimazione)
Daniele Marini
Tipi di decimazione
• back face
• view frustum culling
• portali
• detail
• occlusion culling
PGTR aa 2010/2011
2
Quando farlo
• per un pieno controllo: nella applicazione
• si può anche sfruttare info contenute nel
frame buffer e includerlo nella pipe line
• il metodo ideale spedisce alla pipe line solo
EVS exact visibility set, primitive parzialmente
o totalmente visibili
– complessità alta O(n2)
• alternativa PVS potentially visible set, e deve
comprendere EVS (conservativo), pena
errori nelle immagini (approssimato)
– sfrutta z-buffer per la visibilità finale
PGTR aa 2010/2011
3
La pipe line
Applic
Model and
View
Transform
Lighting
Geom
Projection
PGTR aa 2010/2011
Rast
Clipping
Screen
Mapping
4
Riassunto coordinate
Model and
View
Transform
Lighting
World Coord.
4D (Omogenee)
Projection
Clipping
Screen
Mapping
Normalized Device
Coord.
4D (Omogenee)
World Coord.
3D
PGTR aa 2010/2011
Window Coord.
2D
(x’,y’) coordinate schermo
+ coordinata z di profondità
5
mantenuta a parte
Back face culling
• sono le facce autonascoste, orientate in
senso opposto all’osservatore
• si calcola la normale al poligono proiettato
sul piano immagine: n=(v1-v0)x(v2-v0), vi
vertici poligono; la normale ha la forma
(0,0,a) o (0,0,-a) con a>0; se asse z punta
verso lo schermo (0,0,a) indica un poligono
orientato verso l’osservatore
• il risparmio consiste nell’evitare la scan
conversione dei poligoni esclusi
• accresce la complessità nella fase di
geometria
PGTR aa 2010/2011
6
Back face culling
• si può eseguire prima nello stadio
geometrico, lavorando nello spazio
“vista”
– In tal caso si testa la normale rispetto alla
direzione di vista
• è meglio eseguirlo nello spazio
schermo NDC: errori di
arrotondamento possono modificare
lievemente l’orientamento di un
poligono
PGTR aa 2010/2011
7
Back face culling OGL
• disponibile la funzione
glCullFace(GL_FRONT|GL_BACK|GL_FRONT_BACK)
• da chiamare dopo aver abilitato il culling con:
glEnable(GL_CULL_FACE)
• OGL permette di riorientare le facce di un poliedro
con glFrontFace(GL_CCW|GL_CW)
PGTR aa 2010/2011
8
Clustered Back face culling
• Lo spazio delle normali viene suddiviso in
frustum chiamati cluster
• Sono definiti 6 frusta, orientati come le
facce di un cubo, con il vertice al centro
• Ogni cluster contiene i poligoni che hanno
la normale compresa nell’intervallo del
frustum corrispondente
• Questa classificazione si esegue in fase di
preprocessing, in esecuzione si trattano solo
i poligoni che appartengono a cluster visibili
PGTR aa 2010/2011
9
View frustum culling
• valutare il BV rispetto al frustum di visione
• se il BV è gerarchico anche il culling è
gerarchico
• Se un BV è esterno al frustum non viene
spedito alla pipe-line
• Se un BV è (parzialmente) interno a un
frustum le primitive interne al BV vengono
spedite alla pipe line ed elaborate
• Se si utilizza un scene graph i BV possono
essere organizzati gerarchicamente
PGTR aa 2010/2011
10
View frustum culling
• si sfrutta anche la coerenza tra frame: se un
BV è esterno lo è probabilmente anche nel
frame successivo
• se i movimenti sono vincolati (traslazioni o
rotazioni attorno un solo asse) al frame
successivo il test può essere accelerato,
memorizzando la distanza dal piano del
frustum e aggiornandola
PGTR aa 2010/2011
11
Portali
• adatto a scenari architettonici, una
parete svolge un ruolo di occlusore
• si considera un frustum limitato da
finestre o porte
• quando si attraversa una finestra o
una porta il frustum viene aggiornato
PGTR aa 2010/2011
12
Portali
• si esegue un pre-processing
suddividendo lo scenario in celle (una
per ogni stanza o corridoio)
• porte, finestre e pareti della cella
formano la struttura dati
• le celle si organizzano in un grafo di
adiacenza per descrivere la topologia
della scena
PGTR aa 2010/2011
13
Portali
1.
2.
3.
4.
localizza la cella V dove si trova l’osservatore
inzializza un BB P rettangolare pari alla finestra
di vista, allineato agli assi
renderizza la geometria della cella V con view
frustum culling, definito da P e con vertice
nell’osservatore
ripeti ricorsivamente per le celle adiacenti
seguendo il grafo di adiacenza; per ciascun
portale della cella corrente proietta il portale
sullo schermo e trova il rettangolo AABB della
proiezione; calcola l’intersezione logica di P e
del rettangolo AABB proiettato
PGTR aa 2010/2011
14
Portali
5. per ciascuna intersezione logica: se è vuota
allora la cella adiacente non è visibile e si
scarta, se non è vuota esegui il culling
rispetto al frustum che va dall’osservatore al
rettangolo proiettato dall’intersezione
rettangolare
6. se l’intersezione logica non era vuota le
celle adiacenti successive possono essere
visibili e si ripete ricorsivamente da 3. con un
nuovo P generato dalla intersezione
precedente; ogni oggetto già esaminato va
etichettato per evitare di ripassarci
PGTR aa 2010/2011
15
eye
PGTR aa 2010/2011
16
Dettagli (detail culling)
• Chiamato anche screen size culling
• si stima l’area in pixel del BV sul piano di
proiezione
• se è sotto una soglia non si rende
• quando l’osservatore è fermo viene
disabilitato e si rende tutto
• è simile a un LOD semplificato a due soli
livelli
• Presenta difetti di pop up
PGTR aa 2010/2011
17
Occlusion culling
• evitare di rendere più volte oggetti che si
occludono lavorando sempre sugli stessi
pixel nello z-buffer (paesaggi, alberi, edifici,
...)
• occlusion culling è simile a un test di ombra
• molte soluzioni: spazio immagine, spazio
oggetti, spazio raggi
• altra classificazione: basati su un punto,
basati su una cella
PGTR aa 2010/2011
18
Occlusion culling
eye
L’obiettivo è di evitare di spedire alla pipeline
oggetti occlusi
PGTR aa 2010/2011
19
Occlusion culling
• richiede un test di visibilità, basato su
ordinamento tra oggetti
• G insieme di oggetti da rendere
• OR insieme che rappresenta le
occlusioni
• P insieme di occlusori potenziali
PGTR aa 2010/2011
20
Occlusion culling
• è costoso
• una buona strategia consiste nel
creare una rappresentazione degli
occlusori iniziali e aggiornarla frame
per frame
• si può accelerare ordinando gli
oggetti secondo la distanza
PGTR aa 2010/2011
21