Ottimizzazione della scena: culling (decimazione)

Daniele Marini

Corso di Programmazione Grafica per il Tempo Reale

Tipi di decimazione

• back face• view frustum culling• portali• detail• occlusion culling

2PGTR aa 2010/2011

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

3PGTR aa 2010/2011

La pipe line

4

Applic Geom Rast

Model and View

TransformLighting Projection Clipping

ScreenMapping

PGTR aa 2010/2011

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 partePGTR aa 2010/2011

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

6PGTR aa 2010/2011

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

7PGTR aa 2010/2011

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)

8PGTR aa 2010/2011

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

9PGTR aa 2010/2011

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

10PGTR aa 2010/2011

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

11PGTR aa 2010/2011

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

12PGTR aa 2010/2011

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

13PGTR aa 2010/2011

Portali

1. localizza la cella V dove si trova l’osservatore2. inzializza un BB P rettangolare pari alla finestra di

vista, allineato agli assi3. 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

14PGTR aa 2010/2011

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

15PGTR aa 2010/2011

16

eye

PGTR aa 2010/2011

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

17PGTR aa 2010/2011

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

18PGTR aa 2010/2011

Occlusion culling

19

eye

L’obiettivo è di evitare di spedire alla pipeline oggetti occlusi

PGTR aa 2010/2011

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

20PGTR aa 2010/2011

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

21PGTR aa 2010/2011