Computer Graphics

(1)

Computer Graphics

Marco Tarini Università dell’Insubria

Facoltà di Scienze MFN di Varese Corso di Laurea in Informatica Anno Accademico 2011/12

Lezione 6:

Lezione 6: 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 0 / 1 1 ‧ 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 le primitive le primitive le primitive che non cambiano la scena

• o, che non la cambiano abbastanza

– facciamolo il prima possibile! (nel pipeline) i triangoli triangoli triangoli! triangoli (o segmenti, o punti...)

chiaro?

Notazione

• Lo chiamiamo culling culling culling 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 clipping clipping clipping

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

testing per frammento testing per frammento testing per frammento

quale ci fa piu' gola?

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 presto presto presto e a gruppi ! a gruppi ! a gruppi ! 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

incongruenza nel renering, cioè un...

(2)

• 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

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 chiusa chiusa e opaca chiusa opaca opaca opaca…

non vedrò mai l'interno!

Backface Culling

• Un caso particolare (e facile) di Occlusion Culling

• Idea:

– ipotesi: superficie chiusa chiusa chiusa e opaca chiusa opaca opaca… 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

Concetto BASE di questo corso

• Vettore normale ortogonale ad un piano

o ad un un poligono – detto anche "vettore" normale

– detto anche NORMALE NORMALE NORMALE NORMALE (al/del piano)

• In pratica:

normale == orientamento normale == orientamento normale == orientamento normale == orientamento

Nota: a rigore di termini, vettore normale = vettore con norma 1 Nota: a rigore di termini, vettore normale = vettore con norma 1 Nota: a rigore di termini, vettore normale = vettore con norma 1 Nota: a rigore di termini, vettore normale = vettore con norma 1

n ^{^}

(3)

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 (c an di da ti pi xe 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 (c an di da ti pi xe 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 x2 x2 x2 ?

...ma solo da questo punto in poi!

(HW) Backface culling: quando?

• Non posso usarlo sempre sempre sempre 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:

glEnable( GL_CULL_FACE );

glDisable( GL_CULL_FACE );

• Decidere se scartare le front o le back - facing :

glCullFace(GL_FRONT );

glCullFace(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 normale geometrica normale geometrica” 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

(4)

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

(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 (c an di da ti pi xe 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

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)

(5)

Oltre al “un poligono alla volta”:

bounding volumes

bounding volume bounding volume bounding volume

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)?

Software View-frustum Culling

esempio 1/3: gerarchia di bounding spheres

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 Test effettuato con la Bounding sphere Test effettuato con la Bounding sphere Test effettuato con la Bounding sphere della della della della cella cella cella cella

• se se se se è TUTTA FUORI del VF è TUTTA FUORI del VF è TUTTA FUORI del VF è TUTTA FUORI del VF

→

→ CULL CULL CULL CULL

• sssse è TUTTA DENTRO il VF, e è TUTTA DENTRO il VF, e è TUTTA DENTRO il VF, e è TUTTA DENTRO il VF,

→ →

→ → RENDER RENDER RENDER RENDER tutta la cella tutta la cella tutta la cella tutta la cella

• sssse è PARZIALMENTE dentro il VF: e è PARZIALMENTE dentro il VF: e è PARZIALMENTE dentro il VF: e è PARZIALMENTE dentro il VF:

– Se siamo all’ultimo livello: Se siamo all’ultimo livello: Se siamo all’ultimo livello: Se siamo all’ultimo livello:

→

→ RENDER RENDER RENDER RENDER

– Altrimenti: Test sulle celle di livello inferiore Altrimenti: Test sulle celle di livello inferiore Altrimenti: Test sulle celle di livello inferiore 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

(6)

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 (c an di da ti pi xe 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 globali globali globali, su tutta la

scena

Cell-Based Occlusion-Culling (software) Idea base:

• Preprocessing:

– dividere il mondo in celle

• collegate da "portali"

– calcolare per ogni cella il "PVS PVS PVS PVS"

• PVS PVS PVS PVS = Potentially Visible Set

• cioe' la lista di celle che sono visiblili da quella cella

• Rendering:

– trova la cella xxxx dove è l'occhio – rendering solo delle celle

• nel PVS PVS PVS PVS di xxxx

• dentro il view frustum

di solito molto oneroso computazionalmente

vediamo degli esempi

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)

Quad-Tree

• esempio frame buffer

mondo

diviso con quad tree

• celle con bordo bianco sono nel view frustum ma non sono nel PVS:

CULLED CULLED CULLED CULLED

James Stewart, School of Computing, Queen's University, Kingston, Ontario

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