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

Computer Graphics

Marco Tarini

la rasterizzazione from vertex to pixels

Università dell’Insubria Corso di Laurea in Informatica Anno Accademico 2014/15

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

Rasterizer: “lines” (segmenti)

fra m m en ti

Ve rti ci

pixel

finali

(nello screen-buffer)

Ve rti ci pr oi et 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

rasterizer triangoli rasterizer segmenti rasterizer punti rasterizer

triangoli rasterizer

punti

Rasterizzazione: “lines” (segmenti)

• Produrre i frammenti il più vicino possibile alla linea ideale

v ₀

v ₁

lavoriamo con coord intere.

Arrotondarle prima.

Attenzione agli estremi!

Rasterizzazione: “lines” (segmenti)

• Vogliamo avere la sequenza di frammenti che

– approssimi al meglio il segmento

• e quindi

– sia il più in linea retta

possibile

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

Rasterizzazione: “lines” (segmenti)

coefficienti angolari | a ^|≤ 1

→

1 frammento per colonna

dx=9

d y = 7

Considerando approx di segmenti di circa un pixel di spessore

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

Rasterizzazione: “lines” (segmenti)

dx=3

d y = 1 0

coefficienti angolari | m ^| >1

→

1 frammento per riga

Consideriamo i due casi separatemente.

Ne vediamo uno.

(l'altro è simile)

Scrivo la retta come:

) 1 a (

b a

≤ +

= x y

Rasterizzazione di segmenti:

algoritmo analitico

dx=9

d y = 7

m=dy/dx=7/9

Rasterizziamo da ( x ₀ ,y ₀ ) a ( x ₁ ,y ₁ )

Rasterizzazione di segmenti:

algoritmo analitico

P ₀

P ₁

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

Algoritmo analitico (caso |A|<1)

Calcola a,b t.c. y = a x + b Per x che va da x

a x

1. y ← ax + b 2. arrotondare y

3. produrre frammento ( x , y ) 4. x ++

Algoritmo di Bresenham:

verisone ottimizzata di quanto sopra :

• evita la moltiplicaz in 1.

• usa solo interi (no float)

ad ogni iter, sceglie se y++ o no

• ogni caso gestito separato:

|dx|>|dy? dx>0? dy>0? otto casi!

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

Algoritmo analitico

• seleziona sempre il frammento più vicino alla linea ideale

• per trovarlo bastano:

– un’addizione – una moltiplicazione – un arrotondamento

Segmenti con spessore diverso da un pixel

es: spessore 3

Segmenti con spessore diverso da un pixel

Chiaramente è solo una approssimazione

Aliasing and antialiasing

• Aliasing =

errore introdotto nel passare dal continuo al discreto

– “Valori diversi del continuo (infiniti!) mappati nello stesso valore discreto”

– (o anche: dal discreto hi-res al discreto low-res )

• Antialiasing (AA) =

tecniche per ridurne l’impatto visivo – Es: area-averaging techniques

interpolare i colori usando le sotto aree come peso – Modo semplice di approssimarlo:

Super Sampling , (aka SSAA o FSAA)

1 screen pixel = KxK frame buffer pixel (es 2x2)

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

Antialiasing

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

Rasterizer: triangoli

fra m m en ti

Ve rti ci

pixel

finali

(nello screen-buffer)

Ve rti ci pr oi et 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

Rasterizziamo triangoli: algoritmi a scanline

Algoritmo scan-line Idea Base:

1. ordiniamo per y

2. per ogni righa ^{da y}

a y

1. trova primo framm dentro 2. trova primo framm fuori 3. produci frammenti da da

A incluso a B escluso

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

Rasterizziamo triangoli: algoritmi a scanline

Algoritmo scan-line Idea Base:

1. ordiniamo vertici per y 2. per ogni riga da y

a y

1. trova primo framm dentro 2. trova primo framm fuori 3. produci frammenti da

primo dentro a primo fuori (escluso)

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

Rasterizziamo triangoli: algoritmi a scanline

• In ogni riga:

– trovare il primo-dentro e primo-fuori è simile a Bresenham, ma:

• un caso solo (sempre per riga, sempre verso l'alto)

• arrotondiamo per eccesso

(sia per “il primo dentro” che per “il primo fuori”)

• passiamo all'altro segmento quando siamo arrivati alla riga del vertice intermedio

• "Scan-Conversion" = Rasterization

(Rasterizzazione)

• "to scan-convert" = to Rasterize

• "Span" = intervallo da primo-dentro a primo-fuori

• "Line-scan" = una riga processata

• "Active edges" = i 2 lati attuali

• "Edge table " = i 3 lati (precalcolati) Terminologia della

rasterizzazione a scanline

3 2

Problemi con rasterizzazione di poligoni usando scan-line

• I frammenti vengono prodotti uno alla volta

• Non adatto per implementazione parallela

– il rasterizzatore deve produrre frammenti molto

velocemente (e molti alla volta) se non vogliamo

tenere disoccupato (“to starve”, lett.: affamare) il

processore di frammenti

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

Soluzione

• Produrre frammenti a gruppi

– ad es, a gruppi di 2x2 , 4x4 , 4x1 , 8x1...

– non necessariamente tutti i frammenti in un gruppo sono interni al triangolo!

• Dato un gruppo:

– scartare tutto se completamente fuori – produrre tutto se completamente dentro – se a cavallo:

• testare ogni frammento:

• se esterno, scartare. Else, produrre frammento

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

Rasterizzazione

basata sul bounding box e edge functions

1. Trovo il bounding box del triangolo Come si trova il

bounding box di un triangolo?

Rasterizzazione

basata sul bounding box e edge functions

1. Trovo il bounding box del triangolo 1. arrotondato agli interi...

2. ...divisibili per N (es. 2)

Rasterizzazione

basata sul bounding box e edge functions

1. Trovo il bounding box del triangolo 1. arrotondato agli interi…

2. …divisibili per N (es. 2) 2. Processo ogni blocco NxN (es. 2x2)

1. Testo ogni frammento nel blocco

(magari: solo per I blocchi misti) 2. Se interno al triangolo

produco frammento

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

Rasterizzazione

basata sul bounding box e edge functions

1. Trovo il bounding box del triangolo 1. arrotondato agli interi…

2. …divisibili per N (es. 2) 2. Processo ogni blocco NxN (es. 2x2)

1. Testo ogni frammento nel blocco

(magari: solo per I blocchi misti) 2. Se interno al triangolo

produco frammento

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

Test di appartenenza ad un triangolo

• Triangolo=interesezione di 3 semipiani

v 0

v ₂

v 1 SI NO

SI

SI SI

NO

NO SI SI

SI

NO NO

SI

NO SI NO

NO

SI NO

SI

SI

Test di appartenenza ad un triangolo

• Triangolo=interesezione di 3 semipiani

NO

v 0 SI

NO

SI

SI SI

NO

v 1

v 2 SI SI

SI

SI

NO NO

SI NO

NO

SI NO

SI

• Triangolo front-facing (senso anti-orario)

Test di appartenenza ad un triangolo

• Scambio v ₁ ^con v ₂

v 2

v 1

v 0

• Triangolo BACK-facing (senso anti-orario)

SI NO SI

NO

NO NO

SI NO NO NO

NO

SI SI

NO SI

SI

NO SI

NO

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

Test di appartenenza ad un triangolo Tre Edge Functions: (una per lato)

• Tutte SI (negative) :

– frammento interno a triangolo front-facing

• Tutte NO (positive):

– frammento interno a triangolo back-facing

• Miste:

– frammento esterno (scartare sempre)

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

Test di appartenenza ad un triangolo

• Test di appartenenza ad un semipiano:

SI

NO

p n

x

k n x

n p x

<

•

<

•

− ) 0

(

n p k = •

con TEST:

retta definita

da punto appartenente p e vettore ortognoale n

SI

NO

Test di appartenenza ad un semipiano

• Il semipiano e' definito da un lato:

v ₀ =( x _0, y ₀ ) d

v 1= ( x 1, y 1 )

q funzione

detta EDGE FUNCTION

(Edge = Lato, Bordo)

d’ = ( y ₁ -y ₀ , - ( x ₁ -x ₀ ) ) d = ( y ₀ , x ₀ )

f(q) = (q - y 0 ‧ d’ )

Test di appartenenza ad un semipiano

bool edge_function( vec2 v0, vec2 v1, vec2 p) {

vec2 d = v1 – v0;

d = vec2( -d.y, d.x ); // (ruota 90 gradi senso anti-orario) return ( dot( d , p-v0 ) > 0 );

}

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

Clipping

• Clipping!

Tutto fuori:

CULLED !

☺ no prob.

Screen

Tutto dentro:

Rasterizzo ! (benissimo)

Qualche vertice fuori, ma non tutto il triangolo Clipping.

AHI!

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

Clipping: la vecchia scuola

• Clipping!

Screen

1. Trovo intersezioni 2. Unisco intersezioni A

B

3. Divido poligono in triangoli 4. Rasterizzo ogni triangolo

A poi B

Clipping: la vecchia scuola

• Clipping!

Screen

1. Trovo intersezioni 2. Unisco intersezioni 3. Divido poligono in triangoli 4. Rasterizzo ogni triangolo B

C A

Clipping: la vecchia scuola

• Clipping!

Screen

2. Unisco intersezioni 3. Divido poligono in triangoli 4. Rasterizzo ogni triangolo B

C

A

D

1. Trovo intersezioni Caso pessimo molto complicato Malissimo per implementazione HW

L'HW deve prevedere il

caso pessimo, anche se è raro

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

Clipping: come si fa ora

• Clipping!

Screen

1. Trovo bounding box

3. Rasterizzo nel bounding box come normale

Come si interseca un bounding box con lo schermo (cioe' col rettangolo definito dal ViewPort)?

2. Interseco bounding box con schermo

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

Un momento!

• E il clipping contro il far e il near plane?

– detti anche "far plane clipping"

e "near plane clipping"

left plane

near plane

bottom plane

view frustum

top plane

far plane right plane

Soluz: si fa testando la Z di ogni frammento

prodotto dalla rasteizzazione.

(TEST x FRAMMENTO)

Rasterizzazione triangoli:

• Il metodo basato su bounding box e test di appartenenza (edge functions):

– Vantaggi

• fortemente parallelizzabile – (es: gruppi 4x4)

• clipping diventa facile facile

– per i planes UP, DOWN, LEFT e RIGHT

– Svantaggi

• Overhead grandini

– Si testano molti frammenti inutilmente – Specialmente quando...

Un caso sfortunato

Screen

Triangoli:

• lunghi e stretti

• messi lungo la direzione diagonale

Sinonimo di MALE in computer graphics ^:

(anche per questo, ma non solo)

lunghi e stretti = male

molti algoritmi portano ad artefatti (come vedremo)

circa equilateri = bene

robusti con praticamente tutti gli algoritmi