3 ) (punti in R 2 ) (punti in R (candidati pixels) 3 ) (punti in R 2 ) (punti in R (candidati pixels)

(1)

Computer Graphics

Marco Tarini

Università dell’Insubria

Facoltà di Scienze MFN di Varese Anno Accademico 2014/15

Lezione 9: culling:

se c’è ma non si vede!

M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 4 / 1 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Se non si vede, che non ci sia

• CULLING

– cioè: 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)

Notazione

• Lo chiamiamo culling se si scartano primitive intere

– o interi gruppi di primitive

• Se una primitiva viene spezzata in una parte visibile e una no, lo chiamiamo clipping

• Se è un frammento ad essere scartato, si tratta di testing per frammento

quale ci fa piu' gola?

Notazione

• Lo chiamiamo culling se si scartano primitive intere

– o interi gruppi di primitive

• 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

(principalmente) una ottimizzazione !

(principalmente) una necessità !

(principalmente)

una necessità !

(2)

Tipi 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

Il culling può essere

• Eseguito dall'hardware

– “in GPU”

– molto efficiente (overhead piccolo)

– ma scarta “tardi”, e una primitiva alla volta – spesso una funzionalità hard-wired

• Eseguito dall'applicazione (SW)

– richiede algoritmi e strutture dati appositi – ogni cull può essere oneroso (overhead) – ma scarta primitive presto e a gruppi !

quindi é chiaro che la scelta non é fra HW e SW,

ma fra solo HW ed entrambi

Il culling può essere

• Conservativo

– scarta solo se è sicuro che il risultato non cambia

• si accetta il rischio di processare anche cose che alla fine non saranno visibili

• Non Conservativi

– scartano seguendo un'euristica

• si accetta il rischio di NON disegnare qualcosa che (in parte) era visibile!

casomai, non succede nulla.

Si è solo spercato un po’ di calcolo GPU

quando succede, si produce un

• un difetto…

– di modelling: discrepanza fra quello che si intende modellare e il modello 3D usato

– di rendering: discrepanza fra modello 3D e immagini renderizzate

parentesi notazione parentesi notazione parentesi notazione

..."artefatto"!

es di Artefatto di modelling:

questo lago è modellato da un campo di altezza che…

presenta uno scalino :(

(3)

esempi di artefatti di rendering

parentesi notazione parentesi notazione parentesi notazione

..."artefatto"!

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

Backface Culling

• Un caso particolare di Occlusion Culling

• Idea:

– ipotesi: superficie chiusa e opaca…

non vedrò mai l'interno!

Backface Culling

• Un caso particolare (e facile) di Occlusion Culling

• Idea:

– ipotesi: superficie chiusa e opaca…

non vedrò mai l'interno!

qualunque faccia si veda “da dietro”

(back-facing triangles)

finirà per forza occlusa alla vista da (almeno) un layer di facce “viste da davanti”

(front-facing triangles)

posso scartare tutte i back-facing triangles

(4)

Concetto BASE di questo corso

• Vettore normale =

vettore unitario ortogonale

ad un a superficie in un dato punto

– detto anche la NORMALE

(di quel punto della supeficie)

• In pratica:

normale == orientamento

n ^{^}

nota:

triangolo =>

per forza planare =>

normale costante per ogni punto =>

normale “del triangolo”

Come si trova la normale di un triangolo?

• Traingolo front-facing

• Traingolo back-facing

– "che ci dà le spalle"

n ^{^}

v ₀ v ₂ v ₁

n ^{^}

v ₀ v ₂

v ₁

view dir

(HW) Backface Culling: dove?

fra m m en ti (ca nd id at i p ixe ls)

Ve rti ci (p un ti in R

3

) pixel

finali

(nello screen-buffer)

Ve rti ci pr oi et ta ti (p un ti in R

2

)

Z

rasterizer triangoli

co m pu ta zi on i pe r f ra m m en to set- up

rasterizer segmenti set- up

rasterizer punti set- up

co m pu ta zi on i pe r v er tic e

set- up

(nella fase di set-up che QUI.

precede la rasterizzazione dei triangoli)

(HW) Backface Culling: quanto?

fra m m en ti (ca nd id at i p ixe ls)

Ve rti ci (p un ti in R

3

) pixel

finali

Ve rti ci pr oi et ta ti (p un ti in R

2

)

Z

rasterizer triangoli

co m pu ta zi on i pe r f ra m m en to set- up

rasterizer segmenti set- up

rasterizer punti set- up

co m pu ta zi on i pe r v er tic e

set- up

scarto circa il 50% delle facce...

Lo speed-up? x2 ?

...ma solo da questo punto in poi!

(5)

(HW) Backface culling: quando?

• Non posso usarlo sempre!

– devo sapere a priori che l'oggetto è chiuso

primitive qui

pixels

tutto il pipeline HW di rendering (proiezione, setup, rasterizzazione...)

stato di OpenGL occlusion culling

ON / OFF

(HW) Backface culling: come?

• Attivare e disattivare:

gl.enable( gl.GL_CULL_FACE );

gl.disable( gl.GL_CULL_FACE );

• Decidere se scartare le front o le back - facing : gl.cullFace( gl.GL_FRONT );

gl.cullFace( gl.GL_BACK );

Tutti questi comandi cambiano solo lo stato.

"non fanno nulla sullo schermo" Quale sarà il default?

Quando è utile cambiarlo?

(HW) Backface culling: note

• Test conservativo

– se valgono le ipotesi

• Usa (implicitamente) la “normale geometrica”

– cioè la normale effettiva del triangolo – non: la normale che potremmo definire noi

(arbitrariamente) come attributo (dei vertici)

– in realtà, basta determinare in che ordine appaiono i tre vertici proiettati sullo schermo:

• es: orario backfacing

antiorario frontfacing default di OpenGL

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

(6)

(HW) View-frustum culling

• Dato una primitiva

– triangolo, segmento, punto

• E' dentro il view frustum?

– (o parzialmente dentro – conservativi!)

y

z

x

• Meglio fare il conto

nelle Normalized Device Coords [-1,+1] x [-1,+1] x [-1,+1]

(non a caso dette anche Clip Coords)

(HW) View-frustum Culling: dove?

fra m m en ti (ca nd id at i p ixe ls)

Ve rti ci (p un ti in R

3

) pixel

finali

Ve rti ci pr oi et ta ti (p un ti in R

2

)

Z

rasterizer triangoli

co m pu ta zi on i pe r f ra m m en to set- up

rasterizer segmenti set- up

rasterizer punti set- up

co m pu ta zi on i pe r v er tic e

...di nuovo, solo da questo punto in poi!

Ma ora possiamo agire dall'inizio!

Posso scartare moltissimo della scena!

set- up set- up

set- up

Software View-frustum Culling

• Idea: farlo prima di mandare triangoli nel pipeline di rendering

• Dividere la scena in blocchi

– è nata già divisa nella maggior parte dei casi (v. scenegraph )

• perché così sarà possibile scartare (= to cull ) interi blocchi alla volta!

left plane

near plane

bottom plane

Software View-frustum Culling

• Problema:

– bisogna fare culling prima delle proiezioni – come sono i piani? view frustum

top plane

far plane

right plane

(7)

Software View-frustum Culling:

test di un singolo poligono

• Nelle coordinate oggetto (o mondo)!

• 6 test con 6 piani del view frustum!

• Ripasso di geometria:

– i piani...

– …vettori (nx,ny,nz,k)

Oltre al “un poligono alla volta”:

bounding volumes

bounding volume dell’oggetto X

=

semplice forma che stima (per eccesso) il volume occupato da X

• Precomputato per ogni oggetto della scena

• Strumento molto utile in cg.

Esempi di applicazione:

– collision detection (in games, bounding volumes detti anche hit-box)

– ray-tracing

– … e, appunto, culling (view frustum, etc)

bounding volumes

• Tipi di bounding volumes:

– Axis Aligned Bounding Box (A.A.B.B.) – (generic) Bounding Box

– Discrete Oriented Polytope (D.O.P.) – Bounding sphere

– Bounding ellipsoids (axis aligned or not) – Bounding cylinders

• Difetti e pregi – …

– quanto sono onerosi da pre-computare ? – quanto sono aderenti ?

– sono robusti a rotazioni ^?

– quanto sono onerose le query (es.: di intersezione)?

M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 4 / 1 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 4 / 1 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Software View-frustum Culling

esempio 1/3: gerarchia di bounding spheres

(8)

Software View-frustum Culling

esempio 2/3: 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

Software View-frustum Culling esempio 3/3 : algoritmo finale

• Test effettuato con la Bounding sphere della cella

• se è TUTTA FUORI del VF

→ CULL

• se è TUTTA DENTRO il VF,

→ RENDER tutta la cella

• se è PARZIALMENTE dentro il VF:

– Se siamo all’ultimo livello:

→ RENDER

– Altrimenti: Test sulle celle di livello inferiore

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

Occlusion Culling

• Una forma molto importante di culling

• Scarta moltissimi poligoni

– tutti quelli che compongono il "mondo"

• Ma dove attuarla?

fra m m en ti (ca nd id at i p ixe ls)

Ve rti ci (p un ti in R

3

) pixel

finali

Ve rti ci pr oi et ta ti (p un ti in R

2

)

Z

rasterizer triangoli

co m pu ta zi on i pe r f ra m m en to set- up

rasterizer segmenti set- up

rasterizer punti set- up

co m pu ta zi on i pe r v er tic e

richiede info globali, su tutta la

scena

(9)

Cell-Based Occlusion-Culling (software)

Idea base:

• Preprocessing:

– dividere il mondo in celle

• collegate da "portali"

– calcolare per ogni cella il "PVS"

• PVS = Potentially Visible Set

• cioe' la lista di celle che 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

Struttura: BSP-tree

(Binary Spatial Partitioning tree)

il mondo

Obiettivo: circa stesso numero di primitive in ogni cella

Quad-Tree (in 2D, o 2.5D – es. campi d'altezza)

Oct-Tree (in 3D – partizione di un volume)

• stesso obiettivo

il mondo (2D)