Culling e Sorting Giancarlo Todone Corso “Elementi di Grafica Digitale” Tabella dei contenuti • Sorting – Painter’s – Z-Buffer – BSPTree [nel disegnare] • Culling – – – – • Backface Frustum Occlusion PVS • Color coding Tecniche miste – Portal Rendering – BubbleTree Legenda: Verde: metodo naive Rosso: tecnica avanzata A B: B utilizza A A B: B può utilizzare A A B: tecniche integrate Introduzione • Una moderna “pipeline grafica” agisce nel seguente modo: La cosiddetta “zuppa Le geometrie di trasformateIlvengono processore frammenti ha l’ultima poligoni” viene “rasterizzate” preparata passando quindi parolada suuna come le “caselle” verranno dal software e fornita rappresentazione al interna scritte vettoriale nel framebuffer 3D processore vertici ad una rappresentazione casellare 2D Introduzione Introduzione • Quasi tutti gli algoritmi che vedremo operano sul “polygon soup”, prima che la geometria venga data in pasto alla pipeline, e quindi non dipendono dall’hardware grafico. Sorting: una definizione • Il sorting è l’operazione di ordinamento o categorizzazione su un set di dati • Nel campo della grafica per sorting si intende la sola operazione di ordinamento su un set di entità grafiche al fine della loro corretta visualizzazione • Il culling è categorizzazione delle entità tra quelle da considerare e quelle da ignorare Sorting e Culling • Il sorting è necessario per rappresentare correttamente su uno schermo bidimensionale una scena 3D • Il culling aiuta semplicemente a snellire il lavoro eliminando a priori entità grafiche che sarà inutile ordinare/trasformare/rasterizzare/… Entità grafiche • Mondo • Aree • Oggetti • Poligoni • Punti gerarchia L’algoritmo del pittore L’algoritmo del pittore • Disegnare poligoni dal più lontano al più vicino in modo che i più vicini coprano i più lontani L’algoritmo del pittore • Dispendioso: costringe a trasformare e rasterizzare comunque tutta la geometria della scena • In molti casi (quasi sempre) non funziona correttamente poiché opera su poligoni interi ordinandoli secondo la distanza di uno soltanto dei loro punti dal punto di vista • Se non fallisce per il punto precedente, riesce a disegnare correttamente superfici trasparenti Z buffer Z Buffer • Non opera ordinamento sulla geometria – Per ogni punto di ogni poligono esaminato, in fase di rasterizzazione viene fatto il depht-test (considero la coordinata Z del punto che devo scrivere in [X,Y]) – Se la coordinata Z del punto è minore del valore alle coordinate [X,Y] nello Z-buffer scrivo il colore del punto nel display buffer e il valore Z nello Z-buffer, in entrambi i casi alle coordinate [X,Y] – Altrimenti scarto il punto Z buffer Z=1 Z=2 Z=3 Z=4 Z buffer • Se provo a disegnare un punto più lontano sopra uno più vicino, il depht-test fallisce e la scena rimane invariata Z buffer Display buffer Z buffer Z buffer • Permette di fondere in tempo reale immagini già • • renderizzate Costringe a trasformare e rasterizzare tutta la scena prima di scartare dei punti poiché opera su raster Non permette di disegnare correttamente superfici trasparenti BSP Tree BSP: Binary Space Partition Tree • Opera in due tempi: – Il preprocessore trasforma una “zuppa di poligoni” non ordinabile in un set di poligoni ordinabile e strutturato, non coincidente ma geometricamente equivalente a quello originario – A run-time il motore attraversa la struttura di dati in modo da esaminarla in opportuno ordine a seconda del punto di vista BSP – algoritmo di preprocessamento Ripetere: • Scegliere un poligono candidato nel gruppo in esame (inizialmente l’intero set di poligoni) • Dividere il gruppo dei poligoni rimanenti in poligoni che stanno “sopra” e “sotto” al piano di appartenenza del candidato • I poligoni che vengono tagliati dal piano vengono suddivisi in più poligoni in modo che ognuno possa essere inserito in uno dei due insiemi sopraccitati • Per ognuno dei due insiemi si ripete l’operazione di selezione del candidato ecc… Finché ogni insieme contiene uno o nessun poligono BSP – algoritmo di preprocessamento sotto B C A (root) D E D F G sopra G sopra E A sopra B sotto F sotto C Scelgo un in candidato Suddivido sopra e per sottoil sottogruppo il(in Idem nuovamente pernuovamente i restanti sottogruppi Taglio Scelgo Suddivido Itero il i un procedimento poligoni nei candidato due di posizione gruppi sul gruppo ambigua “sotto” (e e lo segno a (e sinistra come root del sottogruppo sottogruppo segno nell’albero perché non posso questo caso solo “sopra”) “sotto” iterare assegno senzanuovamente) considerare i “brandelli” il sottogruppo ai rispettivi gruppi) “sopra” BSP – Attraversamento a run-time • Considero per primo il poligono root: • Il punto di vista è “sopra” o “sotto” al poligono • • in esame? Se sopra, allora considero il figlio “sotto”, poi disegno il poligono in esame, poi considero il figlio “sopra” Altrimenti, al contrario, considero davanti disegno poligono in esame – considero dietro F – E – G – A -– sotto C–B–D A (root) B C E D F G <-sotto sopra-> G D E A B F C Test: Considero Il La Analogamente punto sequenza sottosequenza il POV di prima vista sta è:per sopra èsopra il è:sotto SOPRA sopra: il sotto: o–sotto FA–E-ECsotto A? --sopra GB SOTTO -D F–E–G–A–C–B–D A (root) B C E G3 D7 D F G E2 B6 A 4 F 1 C5 Ricapitolando BSP: Binary Space Partition Tree • Opera in “precalcolo” facendo a compile-time le operazioni più • • • • • pesanti Opera sulla geometria: non occorre trasformarla/rasterizzarla/… per considerarne un’entità Produce un albero binario: alla geometria strutturata si può applicare la matematica degli alberi binari Può venire usato per risolvere molti altri problemi (culling, collision detection/response, ray casting, ray tracing …) Permette di disegnare correttamente le superfici trasparenti (sotto certe restrizioni) La sua efficacia dipende del tutto dal meccanismo di selezione dei candidati in fase di costruzione dell’albero BSP – Casi degeneri e bilanciamento A D A B B x x C C x D x x BSP – usi non grafici Esempio: collision detection con una sfera Normalmente: dovremmo effettuare il test di collisione tra un oggetto e ogni altro poligono del mondo Col BSP: • effettuare il test [sfera – poligono root del mondo] • Se la sfera sta tutta “sopra” al root, ignoro il “sotto” e viceversa, altrimenti continuo su entrambi i rami • Continuo analogamente coi parent dei sottogruppi non ignorati Culling Culling – metodi naive • Frustum Culling: se tutti i punti di un poligono stanno fuori dal FOV, possiamo ignorare il poligono perché invisibile Culling • Non incide sulla qualità del rendering • Aiuta ad effettuare il rendering più velocemente evitando • di considerare (trasformare, texturizzare, …) poligoni non visibili Necessario per la grafica realtime in scene complesse Si divide fondamentalmente in: • Algoritmi per ridurre il disegno di poligoni fuori dal FOV (Field Of View, campo visivo) • Algoritmi per ridurre l’overdraw (l’effetto pittore, il disegnare poligoni che verranno sovrascritti completamente) Culling – metodi naive • Backface Culling: se il volume degli tridimensionali è completamente contenuto in una superficie chiusa, è impossibile vedere la superficie “da dentro” -> se il prodotto vettoriale della normale di un poligono con il vettore di puntamento della telecamera è negativo possiamo ignorare il poligono perché invisibile Occlusion Culling • Meccanismo di selezione dei • • poligoni che con tutta probabilità occuperanno la maggiore area dello schermo una volta renderizzata la scena Una volta scelti gli oggetti/poligoni che fungono da “occluders”, la loro estrusione all’infinito crea un volume d’ombra Se un oggetto/poligono risiede all’interno di un volume, esso non viene considerato nella fase di rendering Occlusion Culling – generazione dei volumi d’ombra • Tenere un in-memory database che associa segmenti a poligoni • Marcare tutti quei segmenti che potrebbero essere spigoli (se • • • • l’angolo tra i versori dei poligoni che lo condividono è maggiore di 0) A runtime marcare tutti i segmenti potenzialmente “di silouette” quando si disegna il poligono come front-facing A runtime marcare tutti i segmenti potenzialmente “di silouette” quando si disegna il poligono come back-facing Tutti i segmenti che sono marcati in entrambi i modi, sono poligoni “di silouette” e basta estrudere la curva chiusa che essi descrivono per ottenere un volume d’ombra [stessa tecnica che per le stencil shadows…] front back Occlusion Culling • Algoritmo runtime (niente precalcolo qui) • Moooooolto time-consuming • Conviene solo se la scena è davvero molto • pesante e complessa (è da considerarsi il fatto che non è semplice scegliere dei buoni occlusori) Può essere “aiutato” con alcune estensioni hardware openGL (scarsamente usate nella pratica) PVS (Potentially Visible Sets) Culling - PVS PVS: Potentially Visible Sets • Suddividere il mondo in aree • Stabilire legame di appartenenza tra le aree e i poligoni contenuti in esse • Per ogni area segnare quali altre aree sono visibili in delle lookup tables • Rendering offline per creare le LUT Color Coding • Spegnere il lighting • Renderizzare la scena • assegnando ad ogni poligono un colore (“piatto”) diverso Per vedere se è presente un certo poligono controllo nella schermata se trovo un certo colore Color Coding • Performances davvero notevoli grazie all’utilizzo • dell’hardware grafico <<The color buffer isn't always 32 bit. 16 bit displays can seriously mess things up, because you can't guarantee that the color you specify will actually make it to the screen. This can be overcome with a few clever tricks though... (Exercise: find these clever tricks!) >> Tom Nuydens Color Coding -Idea: • Renderizzare più volte la stessa scena • In un fotogramma si renderizza la parte bassa (in bit) del codice-colore e nelle altre via via i bit in eccedenza dal passaggio precedente -In ogni caso il problema non dovrebbe più sussistere in seguito all’introduzione dell’estensione FBO (FrameBuffer Object) per il rendering offscreen Portal Rendering Portal rendering • Dividere il mondo da renderizzare in settori • Connettere i settori con dei “portali” Portal Rendering • Ogni volta che devo renderizzare una scena, parto dal settore in cui si trova il POV POV • Se nel mio FOV trovo un portale, portale alla fine del rendering corrente dovrò processare il settore cui esso conduce Portal Rendering • Quando devo considerare un settore che non è il mio, devo fare il clipping intorno a TUTTO il portale • Materialmente, prima di disegnare il settore più lontano, disegno il portale che vi conduce nello stencil-buffer • Causa comunque molto overdraw Portal Rendering - Clipping Portal rendering - PVS • Ad ogni settore associamo la lista dei settori • • • potenzialmente visibili (la reale visibilità dipende dalla posizione del POV nel settore) L’intero processo avviene in precalcolo A runtime consultiamo le tabelle di precalcolo per scartare a priori i settori MAI visibili dal settore in cui si trova il POV Rimane presente un po’ di overdraw BubbleTree BubbleTree Estensione dell’algoritmo BSP: • Per ogni poligono dell’albero, specifico anche il baricentro e il raggio della minima sfera che contiene – il poligono stesso – tutto il sotto-mondo “sopra” (fino alle foglie) – tutto il sotto-mondo “sotto” (fino alle foglie) BubbleTree BubbleTree • In fase di attraversamento dell’albero a scopo di • • • rendering, se una sfera sta completamente al di fuori del frustum posso scartarla interamente (early-stop) Riduce di molto il tempo di rendering di una scena Si può estendere in molti modi interessanti (posso occludere una intera sfera e il suo sottomondo, posso fare la collision detection prima sulle sfere e poi in caso di collisione tra di esse approfondire l’analisi della collisione sui poligoni, …) L’albero deve essere costruito in un certo modo (cioè -> ogni poligono candidato deve essere scelto in maniera da favorire la localizzazione spaziale dei suoi sottomondi) Bibliografia Tutte le informazioni sono disponibili in rete (per apprenderle ci si mette un po’ e si girano moooolti siti) Sito utilissimo per cominciare è www.delphi3d.net (nonostante il nome, la parte algoritmica non viene spiegata in alcun linguaggio specifico) Sito utile che purtroppo ha chiuso (ma se ne trovano copie-cache in giro per la rete) è www.flipcode.com Tutte le immagini ( tranne e i testi a cura di Giancarlo Todone e )