Ottimizzazione della scena: culling (decimazione)Daniele Marini
Tipi di decimazione
• back face• view frustum culling• portali• detail• occlusion culling
2Programmazione grafica a.a. 2007/2008
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
3Programmazione grafica a.a. 2007/2008
La pipe line
4
Applic Geom Rast
Model and View
TransformLighting Projection Clipping
ScreenMapping
Programmazione grafica a.a. 2007/2008
Riassunto coordinate
5
Model and View
TransformLighting Projection Clipping
ScreenMapping
World Coord.3D
World Coord.4D (Omogenee)
Normalized DeviceCoord.
4D (Omogenee)
Window Coord.2D
(x’,y’) coordinate schermo+ coordinata z di profondità
mantenuta a parteProgrammazione grafica a.a. 2007/2008
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
6Programmazione grafica a.a. 2007/2008
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
7Programmazione grafica a.a. 2007/2008
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)
8Programmazione grafica a.a. 2007/2008
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
9Programmazione grafica a.a. 2007/2008
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
10Programmazione grafica a.a. 2007/2008
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
11Programmazione grafica a.a. 2007/2008
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
12Programmazione grafica a.a. 2007/2008
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
13Programmazione grafica a.a. 2007/2008
Portali
1. localizza la cella V dove si trova l’osservatore
2. inzializza un BB P rettangolare pari alla finestra di vista, allineato agli assi
3. renderizza la geometria della cella V con view frustum culling, definito da P e con vertice nell’osservatore
4. 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
14Programmazione grafica a.a. 2007/2008
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
15Programmazione grafica a.a. 2007/2008
16
eye
Programmazione grafica a.a. 2007/2008
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
17Programmazione grafica a.a. 2007/2008
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
18Programmazione grafica a.a. 2007/2008
Occlusion culling
19
eye
L’obiettivo è di evitare di spedire alla pipeline oggetti occlusi
Programmazione grafica a.a. 2007/2008
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
20Programmazione grafica a.a. 2007/2008
Occlusion cullingOR=emptyP=emptyfor each object g in G
if (isOccluded(g,OR)skip(g)
elserender(g)add(g,P)if(largeEnough(P))
update(OR,P)P=empty
endend
end
21Programmazione grafica a.a. 2007/2008
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
22Programmazione grafica a.a. 2007/2008