Ottimizzazione della scena:
culling (decimazione)
Daniele Marini
1
Tipi di decimazione
•
•
•
•
•
back face
view frustum culling
portali
detail
occlusion culling
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
3
La pipe line
Applic
Model and
View
Transform
Lighting
Geom
Projection
Rast
Clipping
Screen
Mapping
4
Riassunto coordinate
Model and
View
Transform
Lighting
World Coord.
4D (Omogenee)
World Coord.
3D
Projection
Clipping
Screen
Mapping
Normalized Device
Coord.
4D (Omogenee)
Window Coord.
2D
(x’,y’) coordinate schermo
5
+ coordinata z di profondità
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
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
7
Back face culling OGL
• disponibile la funzione
glCullFace(GL_FRONT|GL_BACK|GL_FRONT_BA
CK)
• 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)
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
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
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
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
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
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
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
15
eye
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
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
18
Occlusion culling
eye
L’obiettivo è di evitare di spedire alla pipeline
oggetti occlusi
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
20
Occlusion culling
OR=empty
P=empty
for each object g in G
if (isOccluded(g,OR)
skip(g)
else
render(g)
add(g,P)
if(largeEnough(P))
update(OR,P)
P=empty
end
end
end
21
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
22