Algoritmo di rasterizzazione di linea

Questa voce o sezione sugli argomenti computer grafica e algoritmi non cita le fonti necessarie o quelle presenti sono insufficienti.

Un algoritmo di rasterizzazione di linea è un algoritmo grafico che si occupa di approssimare una linea o un segmento in una rappresentazione grafica discreta. Esempi di rappresentazioni grafiche discrete possono essere il monitor, composto da migliaia di pixel, o una stampa, con migliaia di punti. La rappresentazione su queste "superfici" richiede un'approssimazione, naturalmente in casi non banali.

In rappresentazioni non discrete, e quindi continue, questo lavoro non si presenta. Esempi di rappresentazioni grafiche continue sono gli oscilloscopi a tubo catodico.

Un esempio del problema si può vedere nella figura 0:

Nello sfondo si vede una griglia, che rappresenta i pixel di un'immagine. Il segmento rosso (dal punto p1 al punto p2) è il segmento che noi vorremmo rasterizzare. Nel lato destro vediamo un esempio di rasterizzazione. Abbiamo evidenziato in nero i pixel che si dovrebbero illuminare per visualizzare il segmento dal punto p1 al punto p2.

Dati due punti p1 e p2, con coordinate (x₁,y₁) e (x₂,y₂), possiamo usare il seguente algoritmo:

dx = x2 - x1
dy = y2 - y1
for x from x1 to x2 {
	y = y1 + (y2 - y1) * (x - x1)/(x2 - x1)
	disegna_il_punto(x, y)
}

Nel nostro caso abbiamo semplificato l'operazione assumendo che i punti siano ordinati, ovvero che ${\displaystyle x_{2}>x_{1}}$ e ${\displaystyle y_{2}>y_{1}}$. L'algoritmo funziona bene con ${\displaystyle dx>=dy}$ (figura 1.), ma diventa piuttosto lento nei computer, per via dei calcoli in virgola mobile.

Se abbiamo ${\displaystyle dx<dy}$, i punti della linea diventano "sparsi", come mostrato in figura 2.

Nel caso limite di ${\displaystyle dx=0}$ viene disegnato un solo punto.

La lista non vuole essere completa:

• algoritmo DDA —
• algoritmo della linea di Bresenham — ottimizzato per usare solo le addizioni e per evitare l'uso di calcoli in virgola mobile.
• algoritmo della linea di Xiaolin Wu — può realizzare l'antialiasing

L'algoritmo di rasterizzazione di poligono è un algoritmo di rasterizzazione che si occupa di convertire un poligono definito attraverso i suoi vertici in un'immagine raster (o bitmap).

Il problema più semplice è quello di convertire un poligono vuoto, ovvero nel quale sono definiti solo i lati. In questo caso si può fare un uso ricorsivo di un algoritmo di rasterizzazione di linea, per ogni lato del poligono.

Il problema si complica nel caso di poligoni pieni. Nella figura 1 possiamo vedere alcuni esempi di poligono:

In questi casi abbiamo a disposizione i seguenti algoritmi:

• Algoritmo flood fill
• Algoritmo scan line

• Wikimedia Commons contiene immagini o altri file su Algoritmo di rasterizzazione di linea

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica