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
)