Sistemi Multimediali II
Lezione 6:
culling:
se c'e' ma non si vede!
Università dell’Insubria
Facoltà di Scienze MFN di Varese
Corso di Laurea in Informatica
Anno Accademico 2004/05
Marco Tarini
Se non si vede, che non ci sia
• CULLING
– cioe': non perdiamo tempo a renderizzare ciò che
non si vede
– buttiamo via le primitive che non cambiano la scena
• o, che non la cambiano abbastanza
– facciamolo il prima possibile! (nel pipeline)
i tiangoli! (o segmenti, o punti...)
chiaro?
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 2/40
Notazione
• Lo chiamiamo culling se si scartano primitive intere
– o interi gruppi di primive
• Se una primitiva viene spezzata in una parte visibile e
una no, lo chiamiamo clipping
• Se e' un frammento ad essere scartato, si tratta di
testing per frammento
quale ci fa piu' gola?
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 3/40
Notazione
(principalmente)
una ottimizzazione !
• Lo chiamiamo culling se si scartano primitive intere
– o interi gruppi di primive
• Se una primitiva viene spezzata in una parte visibile e
una no, lo chiamiamo clipping (principalmente)
una necessità !
• Se e' un frammento ad essere scartato, si tratta di
testing per frammento
(principalmente)
una necessità !
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 4/40
Metodologie di Culling
• Occlusion culling
– non si vede... perchè coperto da qualcos'altro
• View-frustum culling
– non si vede... perchè é fuori dal frustum di vista
• Backface culling
– non si vede... perchè é la parte interna di una
superficie chiusa
• Importance culling
– (quasi) non si vede... perchè é la sua proiezione è
troppo piccola rispetto alla scena
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 5/40
Tipi di culling
• Eseguiti dall'hardware
quindi é chiaro che
la scelta non é fra HW e SW,
ma fra solo HW ed entrambi
– automatici
– molto efficienti (overhead minuscolo)
– ma scartano tardi, e una primitiva alla volta
• Eseguiti dall'applicazione (SW)
– richiedono algoritmi e strutture dati
– meno efficienti (overhead anche grandino)
– ma scartano presto, e a gruppi
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 6/40
Tipi di culling
• Conservativi
– scartano solo se sono sicuri
– piuttosto, rischiano di diesgnare anche cose che poi
non si vedranno
casomai, non succede nulla.
Si è solo spercato un po di calcolo GPU
• Non Conservativi
– scartano seguendo un'euristica
– rischiano di NON disegnare qualcosa che (in parte)
era visibile!
se succede, si è creato un
errore nel renering, cioè un...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 7/40
parentesi notazione parentesi notazione parentesi notazione
..."artefatto"!
• Dicasi artefatto un difetto di rendering,
– una discrepanza fra modello e immagine
– o fra realtà e modello
– tipicamente, piazzare sullo schermo un dettaglio
che non c'era
parentesi notazione parentesi notazione parentesi notazione
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 8/40
parentesi notazione parentesi notazione parentesi notazione
..."artefatto"!
• Dicasi artefatto un difetto di rendering,
– una discrepanza fra modello e immagine
– o fra realtà e modello
– tipicamente, piazzare sullo schermo un dettaglio
che non c'era
parentesi notazione parentesi notazione parentesi notazione
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 9/40
Metodologie di Culling
• Occlusion culling
– non si vede... perchè coperto da qualcos'altro
• View-frustum culling
– non si vede... perchè é fuori dal frustum di vista
• Backface culling
– non si vede... perchè é la parte interna di una
superficie chiusa
• Importance culling
– (quasi) non si vede... perchè é la sua proiezione è
troppo piccola rispetto allo schermo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 10/40
Backface Culling
• Concetto:
– superficie di oggetto chiuso...
– non vedro' mai l'interno
– cioè non vedrò mai
il "dietro delle faccie"
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 11/40
Concetto BASE di questo corso
• Vettore normale ortogonale ad un piano
o ad un un poligono
– Detto anche "vettore" normale
– Detto anche NORMALE (al/del piano)
n^
• In pratica:
normale == orientamento
Nota: a rigore di termini, vettore normale = vettore con norma 1
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 12/40
Come si trova la normale di un triangolo?
• Cioe' il suo orientamento nello spazio
v1
n^
v2
v0
facile! e' anche per questo che ci
piacciono tanto i triangoli
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 13/40
Come si trova la normale di un triangolo?
• Traingolo front-facing
n^
view dir
v2
v1
v0
• Traingolo back-facing
– "che ci da le spalle"
v2
view dir
n^
v1
v0
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 14/40
setup
rasterizer
triangoli
setup
rasterizer
segmenti
computazioni
per frammento
rasterizer
punti
frammenti
(punti in R2)
setup
(candidati pixels)
Z
Vertici
proiettati
computazioni
per vertice
Vertici
(punti in R3)
(HW) Backface Culling: dove?
pixel
finali
(nello
screen-buffer)
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 15/40
setup
rasterizer
triangoli
setup
rasterizer
segmenti
computazioni
per frammento
rasterizer
punti
frammenti
(punti in R2)
setup
(candidati pixels)
Z
Vertici
proiettati
computazioni
per vertice
Vertici
(punti in R3)
(HW) Backface Culling: quanto?
pixel
finali
(nello
screen-buffer)
...ma solo da questo punto in poi!
scarto circa il 50% delle faccie...
Lo speed-up? x2 ?
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 16/40
(HW) Backface culling: quando?
• Non posso usarlo sempre!
– devo sapere a priori che l'oggetto é chiusi
occlusion culling
ON / OFF
primitive
qui
stato di OpenGL
tutto il pipeline HW di rendering
(proiezione, setup, rasterizzazione...)
pixels
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 17/40
(HW) Backface culling: come?
• Accendere e spengere:
glEnable( GL_CULL_FACE );
glDisable( GL_CULL_FACE );
Tutti questi comandi cambiano solo lo stato.
"non fanno nulla sullo schermo"
Quale sarà il default?
Quando è utile cambiarlo?
• Decidere se scartare le front o le back-facing :
glCullFace(GL_FRONT );
glCullFace(GL_BACK );
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 18/40
Metodologie di Culling
• Occlusion culling
– non si vede... perchè coperto da qualcos'altro
• View-frustum culling
– non si vede... perchè é fuori dal frustum di vista
• Backface culling
– non si vede... perchè é la parte interna di una
superficie chiusa
• Importance culling
– (quasi) non si vede... perchè é la sua proiezione è
troppo piccola rispetto allo schermo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 19/40
(HW) View-frustum culling
• Dato una primitiva
– triangolo, segmento, punto
• E' dentro il view frustum?
– (o parzialmente dentro – conservativi!)
y
• Meglio fare il conto
nelle Normalized Device Coords
x
[-1,+1] x [-1,+1] x [-1,+1]
z
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 20/40
setup
rasterizer
triangoli
setup
rasterizer
segmenti
computazioni
per frammento
rasterizer
punti
frammenti
(punti in R2)
setup
(candidati pixels)
Z
Vertici
proiettati
computazioni
per vertice
Vertici
(punti in R3)
(HW) View-frustum Culling: dove?
pixel
finali
(nello
screen-buffer)
...di nuovo, solo da questo punto in poi!
Ma ora possiamo agire dall'inizio!
Posso scartare moltissimo della scena!
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 21/40
Software View-frustum Culling
• Idea: farlo prima di mandare triangoli nel
pipeline di rendering
• Dividere la scena in blocchi
– è nata gia divisa la maggior parte delle volte
• perchè così sarà possibile scartare (=to cull)
interi blocchi alla volta!
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 22/40
Software View-frustum Culling
• Problema:
– bisogna fare culling prima delle proiezioni
– come sono i piani?
view frustum
top plane
left plane
near plane
right plane
far plane
bottom plane
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 23/40
Software View-frustum Culling
Parte 1/4: test di un singolo poligono
• Nelle coordinate oggetto o mondo!
• 6 test con 6 piani del view frustum!
• Ripasso di geometrica:
– i piani...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 24/40
Software View-frustum Culling
Parte 2 /4 : Gerarchia di bounding spheres
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 25/40
Software View-frustum Culling
Parte 3 /4 : intersezione sfera view frustum
• Sfera centro c raggio r
• Test con un piano p (con normale normalizzata)
• Facile!
– pc > r
• sfera tutta “al di qua” del piano
– pc < -r
• sfera tutta “al di là” del piano
– altrimenti: sfera mezza dentro e mezza fuori
• Test contro view frustum:
– testare tutti e 6 i piani
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 26/40
Software View-frustum Culling
Parte 4 /4 : algoritmo finale
• Test effettuato con la Bounding sphere della cella
• se è TUTTA FUORI del VF
 CULLED
• se è TUTTA DENTRO il VF,
 RENDERED tutta la cella
• se è PARZIALMENTE dentro il VF:
– Se siamo all’ultimo livello:
 RENDERED
– Altrimenti: Test sulle celle di livello inferiore
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 27/40
Metodologie di Culling
• Occlusion culling
– non si vede... perchè coperto da qualcos'altro
• View-frustum culling
– non si vede... perchè é fuori dal frustum di vista
• Backface culling
– non si vede... perchè é la parte interna di una
superficie chiusa
• Importance culling
– (quasi) non si vede... perchè é la sua proiezione è
troppo piccola rispetto allo schermo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 28/40
Occlusion Culling
• Una forma molto importante di culling
• Scarta moltissimi poligoni
– soprattutto quelli che compongono il "mondo"
setup
rasterizer
triangoli
setup
rasterizer
segmenti
computazioni
per frammento
rasterizer
punti
frammenti
(punti in R2)
setup
(candidati pixels)
Z
Vertici
proiettati
computazioni
per vertice
Vertici
(punti in R3)
• Ma dove attuarla?
pixel
finali
(nello
screen-buffer)
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 29/40
Cell-Based Occlusion-Culling (software)
Idea base:
• Preprocessing:
– dividere il mondo in celle
di solito
molto oneroso
computazionalmente
vediamo degli esempi
• collegate da "portali"
– calcolare per ogni cella il "PVS"
• PVS = Potentially Visible Set
• cioe' la lista di celle sono visiblili da quella cella
• Rendering:
– trova la cella x dove è l'occhio
– rendering solo delle celle
• nel PVS di x
• dentro il view frustum
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 30/40
Struttura: BSP-tree
Obiettivo: circa stesso numero di primitive in ogni cella
il mondo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 31/40
Quad-Tree
• stesso obiettivo
il mondo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 32/40
Quad-Tree
• esempio
frame buffer
mondo
James Stewart, School of Computing, Queen's University, Kingston, Ontario
diviso con quad tree
• celle con bordo bianco
sono nel view frustum
ma non sono nel PVS:
CULLED
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 33/40
Metodologie di Culling
• Occlusion culling
– non si vede... perchè coperto da qualcos'altro
• View-frustum culling
– non si vede... perchè é fuori dal frustum di vista
• Backface culling
– non si vede... perchè é la parte interna di una
superficie chiusa
• Importance culling
– (quasi) non si vede... perchè é la sua proiezione è
troppo piccola rispetto allo schermo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 34/40