1Computer GraphicsMarco TariniUniversità dell’InsubriaCorso di Laurea in InformaticaAnno Accademico 2016/17Lezione08: occlusionie rimozionesuperficinascoste

(1)

Computer Graphics

Marco Tarini

Università dell’Insubria

Corso di Laurea in Informatica Anno Accademico 2016/17

Lezione 08: occlusioni e rimozione superfici nascoste

Rimozioni delle superfici nascoste

• Gli oggetti più vicini devono coprire quelli più lontani

– gli oggetti lontani sono "occlusi"

da quelli più vicini

Con raytracing era ovvio!

Con raserization?

(2)

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 6 / 1 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Rimozioni delle superfici nascoste

• Soluzione 1:

– dividere ogni triangolo parzialmente occluso

in parte visibile e parte occlusa?

• facendo una operazione di clipping

Come si trovano le coppie occluso/occlusore?

Clipping di un triangolo e un altro?

E dove, nel pipeline HW?

SOLUZIONE IMPROPONIBILE

Rimozioni delle superfici nascoste

• Soluzione 2:

– i poligoni disegnati dopo di sovrascrivono quelli precedenti – disegnare solo poligoni interi, ma nell' ordine giusto

• (back-to-front)

– noto come "algoritmo del pittore"

(3)

Algoritmo del pittore (depth sorting)

• Data una scena (composta da primitive) – ordinare le primitive per profondità

• (cioe’ in ordine di z… in spazio vista!)

– mandarle tutte (in ordine)

Sorting!

Complessità pesudolineare (n log(n))

col numero di primitive.

     in comp graph, peggio di lineare vuol

dire MALE

Una primitiva non ha una sola profondità!

piuttosto ha una profondità max e una min

Algoritmo del pittore (depth sorting)

Fr am m en ti & a ttr ib ut i in te rp ol at i Ve rti ci & lo ro a ttr ib ut i

Screen buffer

Ve rti ci p or ie tta ti & a ttr ib ut i co m pu ta ti

rasterizer triangoli

co m pu ta zi on i pe r f ra m m en to rasterizer

segmenti rasterizer

punti

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

DOVE?

x

y

z v

⁰

v

¹

v

⁰

v

¹

v

prima di mandare i triangoli.

Fatto dalla CPU ! 

(4)

Algoritmo del pittore (depth sorting)

• Ma va prima C o D?

• Ma poi,

esiste sempre

un "ordine giusto"? Pr of on di tà

z

min

Primitive B

z

max

A

E D

C

• La primitiva A può essere disegnata per prima

Algoritmo del pittore (depth sorting)

• La primitiva A può essere disegnata per prima

• Ma va prima C o D?

• Ma poi,

esiste sempre un "ordine giusto"?

– NO:

• intersezioni

– NO:

• cicli di sovrapposizioni

(5)

Algoritmo del pittore (depth sorting)

• Oneroso

– sorting: (n log (n)) – e nella parte software!

• Mal adattato allo schema HW

– deve lavorare in spazio occhio ...ma prima della proiezione HW ?!

– lavorare globalmente su tutta la scena prima di mandare la prima primitiva

• In alcuni casi

– Test difficili (quando gli intervalli min z e max z non sono disgiunti) – O addirittura nessun ordinamento corretto (allora, clipping?)

• Totale: usabile sse è

facile ordinare preventivamente le primitive

– in fase di preprocessing

Algoritmo del pittore (depth sorting)

• usabile sse è

facile ordinare preventivamente le primitive – in fase di preprocessing

• Esempio: terreno come campo di altezza

(6)

Rimozioni delle superfici nascoste

• Soluzione 3:

– Alcune assunzioni…

1. sto disegnando una superficie CHIUSA 2. rappresentata da una mesh ben orientata

Backface Culling

• Un caso particolare di Occlusion Culling

• Idea:

– ipotesi: superficie chiusa e opaca…

 non vedrò mai l'interno!

(7)

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

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”

(8)

Come si trova la normale di un triangolo?

• Cioe' il suo orientamento nello spazio

n ^{^}

v ₀

v ₂ v ₁

facile! é anche per questo che ci piacciono tanto i triangoli

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

(9)

(HW) Backface Culling: dove?

fra m m en ti (c an di da ti pi xe ls )

V er tic i (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

(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

scarto circa il 50% delle facce...

Lo speed-up? x2 ?

...ma solo da questo punto in poi!

(10)

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

(11)

(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

Rimozioni delle superfici nascoste

• Back-face culling non basta – esempio:

superfici

non back-facing,

non totalmente occluse

ma parzialemnte occluse

(12)

Rimozioni delle superfici nascoste

• Soluzione 4:

– rimuovere le superfici nascoste con un TEST PER FRAMMENTO

– algoritmo dello "Z-buffer"

• o "Depth-buffer"

Algoritmo dello z-buffer

Fr am m en ti & at tri bu ti in te rp ol at i

Ve rti ci & lo ro a ttr ib ut i Screen

buffer

Ve rti ci & at tri bu ti co m pu ta ti

rasterizer triangoli set- up

rasterizer segmenti set- up

rasterizer punti set- up

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

Depth buffer

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

profondità di ogni pixel

RGB finale

per ogni pixel

(13)

Algoritmo dello z-buffer

Fr am m en ti & at tri bu ti in te rp ol at i

V er tic i & lo ro a ttr ib ut i Screen

buffer

V er tic i & a ttr ib ut i co m pu ta ti

rasterizer triangoli set- up

rasterizer segmenti set- up

rasterizer punti set- up

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

Depth buffer

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

Transform.

Metti la z finale come

attributo aggiuntivo

Interpola (come tutti la z gli attributi)

per un frammento con

screen coordinates (x,y), colore (r,g,b) e profondità z:

if ( z <= DepthBuffer[x,y] ) {

ScreenBuffer[x,y] = (r , g , b) ; DepthBuffer[x,y] = z ;

} else scarta (“discard”, “kill”) frammento depth test

screento

RGBa +

Depth

Stencil +

Il pipeline: da più vicino

Fr am m en ti & a ttr ib ut i in te rp ol at i

RGBa buffer

rasterizer triangoli

computazioni programmabili per frammento rasterizer

segmenti rasterizer punti

Depth buffer Stencil

buffer

test automatici

per frammento

(14)

Algoritmo dello z-buffer

Fr am m en ti & at tri bu ti in te rp ol at i

V er tic i & lo ro a ttr ib ut i Screen

buffer

V er tic i & a ttr ib ut i co m pu ta ti

rasterizer triangoli set- up

rasterizer segmenti set- up

rasterizer punti set- up

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

Depth buffer

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

ho bisogno di precisione!

floats di almeno 16 o 24 bits

Rappresentazione reali in virgola fissa

• Rarppresento i numeri reali in un intervallo predefinito (es: da 0 a 1) come interi

• Es: se ho 32 bit, allora,

memorizzo l’intero x (da 0 a 2^32-1)

per rappresentare il razionale x / (2^32-1)

• Rispetto alla virgola mobile:

– intervallo limitato 

– niente esponente! solo mantissa  – distribuzione uniforme dei valori

rappresentabili 

(15)

Algoritmo dello z-buffer:

esempio (con depth buffer ipotetico di interi a 6 bit: valori da 0 a 63)

63 63 63 63 63 63 63 63

63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63

5 5

5

5 5 5 5 5 5 5 63 5 5 5 5 5 5 63 63 5 5 5 5 5 63 63 63 5 5 5 5 63 63 63 63 5 5 5 63 63 63 63 63 5 5 63 63 63 63 63 63 5 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63

+ =

5 5 5 5 5 5 5 63 5 5 5 5 5 5 63 63 5 5 5 5 5 63 63 63 5 5 5 5 63 63 63 63 5 5 5 63 63 63 63 63 5 5 63 63 63 63 63 63 5 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63

7

2 7

5 5 5 5 5 5 5 63 5 5 5 5 5 5 63 63 5 5 5 5 5 63 63 63 5 5 5 5 63 63 63 63 4 5 5 7 63 63 63 63 3 4 5 6 7 63 63 63 2 3 4 5 6 7 63 63 63 63 63 63 63 63 63 63

+ =

5 5

5 5 5

5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

7 6 7

5 7

4 7

3 7

2 7

7 6 7 5 6 7 4 5 6 7 3 4 5 6 7 2 3 4 5 6 7

Algoritmo dello z-buffer:

proprietà

• il rendering diventa “order independent” !!!

• Funziona su tutto 

– anche su:

• Operazione per frammento

– Viene svolto durante

"computazioni per frammento"

• Adatto all'implementazione HW 

5 5 5 5 5 5 5 63 5 5 5 5 5 5 63 63 5 5 5 5 5 63 63 63 5 5 5 5 63 63 63 63 4 5 5 7 63 63 63 63 3 4 5 6 7 63 63 63 2 3 4 5 6 7 63 63 63 63 63 63 63 63 63 63

(16)

Algoritmo dello z-buffer:

issues

• Costa un po’ di memoria (GPU)

– spesso: sizeof( depth buffer ) = sizeof(screen buffer ) / 2

• Problemi di aliasing sulla z

– causa problema detto: “z-fighting”

– avviene quando la precisione non è sufficiente

es., se si renderizzano due superfici parallele molto vicine

• Assume superfici del tutto opache

– problemi con le superfici semitrasparenti (come vedremo…)

• Dati condivisi in lettura e scrittura 

– complicazione per chi implementa HW

– efficienza ameno in parte impattata (ma test molto ottimizzato)

– è un test HardWired in GPU

Z-figthing

(17)

Z-figthing

Depth test, in OpenGL

• Devo abilitare il depth test:

glEnable(GL_DEPTH_TEST);

^primitive^qui

pixels tutto il pipeline

(proiezione, setup, rasterizzazione...) stato di OpenGL manipolazioni di stato (es. settare la matrice)

Posso anche decidere le condizioni per passare il test:

glDepthFunc( GL_LESS ) GL_NEVER

GL_EQUAL GL_LEQUAL GL_GREATER GL_NOTEQUAL GL_LESS GL_GEQUAL GL_ALWAYS

(dafault)

(18)

• Depth test: viene eseguito automaticamente alla fine del nostro fragment shader

– (se abilitato)

– motivo: è un op. critica, read/write su dati condiviso – motivo: HW deve poter fare le sue ottimizzazioni

• (es depth buffer gerarchico)

==> il fragment shader

dovrà determinare in output:

– un valore RGB, – un valore di depth

Depth test, in OpenGL

• Il rasterizzatore produce un valore di depth di default

– per ogni frammento prodotto

– interpolando la Z dei vertici proiettati in input

• Possiamo sovrascrivere questo valore se vogliamo nel fragment shader

// fragment shader void main() {

...

gl_FragColor = ... // un vec4 gl_FragDepth = ... // un float }

assegnamento opzionale.

(ha un costo grande

farlo! depth test

va rimandato e alcune

ottimizzazioni HW

disabilitate

(19)

Depth test, in OpenGL

• Quando si cancella lo schermo, cancellare il depth buffer

...

glClear(

GL_COLOR_BUFFER_BIT );

...

| GL_DEPTH_BUFFER_BIT

Altri per-fragment tests Tests automtici:

discard a fragment or pass it to the next step?

• Scissor test

discards fragments falling outside a scissor rectangle , used to specify rectangles inside the viewport

• Stencil buffer

is used as a mask to discard fragments

• Depth test , uses the z-buffer to discard

fragments that are not visible

(20)

screento

RGBa +

Depth

Stencil +

Il pipeline: da più vicino

Fr am m en ti & a ttr ib ut i in te rp ol at i

RGBa buffer

rasterizer triangoli

computazioni programmabili per frammento rasterizer

segmenti rasterizer punti

Depth buffer Stencil

buffer

Output combiner

Depth test in openGL: alcune regole hard-wired

• Il vertex shader produce le pos in clip coords

– Dove, se fuori da [-1..+1]  fuori da immagine!

– Vale sia per la X, che Y… che Z

(cioè: fuori anche cose troppo lontane oppure troppo vicine)

• Automaticamente (prima di rasterizzare):

clip coord convertite in viewport coords, con trasf. lineare:

– La X e Y: da [-1,+1] a [0..ResX]x[0..ResY]

– La Z: da [-1,+1] a [0,1]

• Per frammento: se non cambio esplicitamente la depth, eredito la Z del viewport coord (interpolata)

• Output combiner: depth test, hard-wired