Algoritmo di rasterizzazione di linea

Da Wikipedia, l'enciclopedia libera.

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 pixels, o una stampa, con migliaia di punti. La rappresentazione su queste "superfici" richiede un aprossimazione, 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.

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

Figura 0.

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

[modifica] Un semplice algoritmo di rasterizzazione di linea

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 $x 2 > x 1$ e $y 2 > y 1$ . L'algoritmo funziona bene con $d x > = d y$ (figura 1.), ma diventa piuttosto lento nei computer, per via dei calcoli in virgola mobile.

Figura 1.

Se abbiamo $d x < d y$ , i punti della linea diventano "sparsi", come mostrato in figura 2.

Figura 2.

Nel caso limite di $d x = 0$ viene disegnato un solo punto.

[modifica] Elenco di algoritmi di rasterizzazione di linee

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

[modifica] Rasterizzazione di poligono

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: