La RasterizzazioneMattias Cibien

Cos’è la Rasterizzazione?

La rasterizzazione è il processo che consente di rappresentare un immagine su una periferica di un computer. Consiste nel convertire un immagine reale, in una detta raster o bitmap, ovvero formata da pixel. Il problema principale è di doversi spostare da una descrizione lineare ad una discreta, ovvero i pixel.

Algoritmi

Esistono due principali categorie di algoritmi di rasterizzazione, che permettono di rappresentare tutti gli oggetti bidimensionali. Algoritmi di rasterizzazione di linea Algoritmi di rasterizzazione di poligono

Rasterizzazione di una linea

Algoritmo DDA (Listato 1) Algoritmo di Bresenham (Listato 2) Algoritmo di Xiaolin Wu

DDA Questo algoritmo parte dall'osservazione

che la pendenza (o coefficiente angolare) di una retta passante per due punti è esprimibile come: m = Δy/Δx

e che: Δy = m*Δx

In sostanza, l'algoritmo incrementa x di un'unità (corrispondente ad un pixel) e calcola il nuovo valore di y.

Svantaggi del DDA

m < 1 ( sinistra) m > 1 (a destra)

Se lo applichiamo a pendenze maggiori di 1, otterremo un segmento sgranato perché, per pendenze alte aumenta maggiormente y rispetto ad x e si creano inevitabilmente dei vuoti, poiché y “salta” di un valore maggiore di 1 di pixel, facendo così perdere l'effetto di continuità. Per ovviare a questo problema basta invertire le due variabili: calcolare x partendo da y (basta infatti aggiungere un’istruzione condizionale all’algoritmo presentato).Nonostante tutto, questo algoritmo è scarsamente efficiente poiché, ad ogni iterazione, sono richieste operazioni in virgola mobile come la somma (riga 9) e l'arrotondamento (riga 10).

Algoritmo Di Bresenham

La matematica dell’algoritmo di Bresenham

-Δx*y + Δy*x + Δx*q = 0 (Equazione di una retta)

M(x1+1; y1+ ½) (coordinate di M) d = -Δx*yM + Δy*xM + Δx*q (Valore

decisionale)

Il valore decisionale

Se d = 0, M giace sulla retta, quindi si sceglie indifferentemente uno dei punti (per comodità A).

Se d > 0, M si trova sopra la retta, quindi si sceglie A.

Se d < 0, M si trova sotto la retta, quindi si sceglie B.

Scegliendo il punto A

In questo caso il nostro punto di partenza P è P(x1 + 1,y1), e il nostro nuovo punto medio M è M(x1 + 2,y1 + ½).

Invece il nuovo valore di d è:dnew = -Δx(y1 + ½) + Δy(x1 + ½) + Δxq

Sottraendo quindi il vecchio valore:dnew – d = Δy

Scegliendo il punto B

Effettuando ora lo stesso ragionamento:dnew – d = -Δx+Δy

Riassumendo

0,0,

1ii

iii dyd

dyxdd

yxd 21

0

Antialiasing

L'antialiasing (abbreviato con AA) è una tecnica per ridurre l'effetto aliasing (tradotto: scalettatura o gradinatura) che si presenta quando un segnale a bassa risoluzione viene mostrato ad alta risoluzione. L'antialiasing ammorbidisce le linee allisciando i bordi e omogeneizzando l'immagine.

Antialiasing su Testo

Antialiasing su Immagine 3D

Immagine tratta dal Videogame Half-Life® 2. Fornita da Tweakguides.com

Rasterizzazione di un poligono L'algoritmo di rasterizzazione di poligono si occupa di convertire un

poligono definito attraverso i suoi vertici in un'immagine bitmap.Disegnare un poligono vuoto, ovvero nel quale sono definiti solo i lati, è semplice. In questo caso si può fare un uso ricorsivo di un algoritmo di rasterizzazione di linea, per ogni lato del poligono.Nel caso di poligoni pieni risulta più complicato. Per riuscire in questo intento esistono due algoritmi principali detti Flood Fill e Scanline.

Algoritmo Flood-Fill L'algoritmo Flood Fill individua un punto all'interno dell'area e, a partire da

quel punto, colora tutto quello che ha intorno fermandosi solo quando incontra un confine, ovvero un pixel di colore differente (alcuni programmi di grafica permettono di definire quanto/come differente), in pratica si basa sullo stesso principio dell’acqua versata in una vasca con un secchiello. L’implementazione di questo algoritmo è estremamente semplice ed esente da difetti; d’altro canto deve solamente colorare tutto quello che trova di diverso da quello che gli viene assegnato.

Flood-Fill (specifica) Flood-fill (pixel, colore_prima, colore_nuovo):

1. Se il colore di pixel è diverso da colore_prima, termina.

2. Imposta il colore di pixel a colore_nuovo.3. Esegui Flood-fill (pixel ad ovest di pixel,

colore_prima, colore_nuovo).Esegui Flood-fill (pixel a nord di pixel, colore_prima, colore_nuovo).Esegui Flood-fill (pixel ad est di pixel, colore_prima, colore_nuovo). colore_nuovo).Esegui Flood-fill (pixel a sud di pixel, colore_prima, colore_nuovo).

4. Termina.

E se si introduce un’ulteriore dimensione?

Immagine tratta dal Videogame Devil May Cry® 4. Fornita da CAPCOM

La rasterizzazioneGrazie dell’attenzione