Algoritmi di rasterizzazione

La rasterizzazione e un processo che dato un poligono in coordinate schermo colora i pixel di quel dato poligono con un colore, esistono due processi principali:

rasterizzazione per mezzo di coordinate baricentriche
rasterizzazione per mezzo di scan conversion

Inoltre queste vengono differenziate in base a come il colore del pixel viene determinato

colore omogeneo
texture (immagine bidimensionale da applicare sull’oggetto)

Sistema di riferimento baricentrico
#

Dato un poligono in coordinate schermo definito come segue

allora e possible definire un nuovo sistema di riferimento basato sui vertici del poligono

$$ O' = p_1,u = p_2 - p_1,v = p_3 - p_1 $$

in questo sistema di riferimento tutti i punti vengono rappresentati da combinazioni affini dei 3 vertici del poligono

$$ p = \alpha p_1 +\beta p_2 +\gamma p_3, \space con $$

$$ 1= \alpha + \beta + \gamma $$

In coordinate baricentriche si ha che se un punto fa parte del poligono allora e vero che $\alpha,\beta,\gamma \geq 0$ di conseguenza determinare se un punto fa parte del poligono si riduce a un confronto

if(a >=0 && b >=0 && c >= 0){
	console.log("punto del poligono")
}else{
	console.log("punto non del poligono")
}

Inoltre questo approccio può essere implementato in parallelo per mezzo di architetture SIMD

Recupero dell’informazione colore
#

Inoltre le coordinate baricentriche possono essere utilizzate per recuperare anche l’informazione del colore di un dato punto, date le coordinate baricentriche $\alpha,\beta,\gamma$ l’informazione colore può essere recuperata dallo spazio RGB dei colori

Scan conversion
#

L’idea base di questo algoritmo consiste nell’identificare le sequenze orizzontali di pixel che fanno parte del triangolo, l’algoritmo si divide in due fasi

identificazione delle intersezioni della linea con i lati del triangolo
colorazione dei pixel fra le due intersezioni

Per identificare il prossimo pixel sulla linea si utilizza l’algoritmo di linea incrementale

Texture mapping
#

Il processo di texture mapping si occupa di applicare a un dato poligono un immagine sulla sua superficie, sfruttando un mapping tra i vertici di un poligono 3D e un immagine

Di conseguenza il problema si riduce ad assegnare a ogni pixel il corretto punto della texture in questione, questo può essere fatto per mezzo delle coordinate baricentriche, costruendo un mapping fra le coordinate del poligono e le coordinate in spazio texture

Tuttavia non e detta che dato un punto del poligono ci sia una corrispondenza con un pixel esatta della texture

E necessario quindi determinare il colore da assegnare a un dato punto del triangolo,ci sono diverse strategie disponibili:

Nearest neighbor
#

Il colore di un dato punto e dato dal pixel della texture più vicino alle coordinate del punto $p$

Bilinear interpolation
#

Vengono considerati i 4 punti più vicini al punto $p$ Le cui componenti colore vengono pesate per determinare il colore del punto $p$

data la seguente interpolazione lineare in una dimensione come segue

$$ P(x) = f_0(1-x) + f_1x $$

la interpolazione bilineare e di conseguenza realizzata come un interpolazione lineare di due interpolazioni lineari

di conseguenza si ha che:

$$ f_P= f_E(1-y)+ f_Fy $$

con:

$$ f_E= f_A(1-x)+ f_Bx $$

$$ f_F= f_D(1-x)+ f_Cx $$

ℹ️ Note

nel caso in cui il punto si trovi al centro dei 4 pixel piu vicini l’interpolazione bilineare si riduce a una media dei 4 pixel $f_P = \frac{f_A +f_B +f_C +f_D}{4}$

Bi-cubic interpolation
#

Metodologia che prende in considerazione i $16$ pixel più vicini al punto in questione, le cui componenti vengono pesate per mezzo dell’interpolazione colore