Algoritmo di rasterizzazione di linea: differenze tra le versioni

Versione delle 01:46, 9 giu 2008

Versione attuale delle 19:51, 19 feb 2019

(18 versioni intermedie di 14 utenti non mostrate)

Riga 1:

{{F|computer grafica|arg2=algoritmi|marzo 2013}}

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]]s, o una stampa, con migliaia di punti. La rappresentazione su queste "superfici" richiede un aprossimazione'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 [[Oscilloscopio#Oscilloscopio a tubo catodico|oscilloscopi a tubo catodico]].

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

[[ImmagineFile:Example_rastrExample rastr.png|frame|center|Figura 0.]]

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

==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:

<code>

dx = x2 - x1

dy = y2 - y1

Riga 18 ⟶ 19:

disegna_il_punto(x, y)

}

</code>

Nel nostro caso abbiamo semplificato l'operazione assumendo che i punti siano ordinati, ovvero che <math>x_2 > x_1</math> e <math>y_2 > y_1</math>.

L'algoritmo funziona bene con <math>dx >= dy</math> (figura 1.), ma diventa piuttosto lento nei computer, per via dei calcoli in virgola mobile.

[[ImmagineFile:esempio rasterizzazione linea 1.png|frame|center|Figura 1.]]

Se abbiamo <math>dx < dy</math>, i punti della linea diventano "sparsi", come mostrato in figura 2.

[[ImmagineFile:esempio rasterizzazione linea 2.png|frame|center|Figura 2.]]

Nel caso limite di <math>dx = 0</math> viene disegnato un solo punto.

Riga 33:

==Elenco di algoritmi di rasterizzazione di linee==

La lista non vuole essere completa:

*[[algoritmo DDA]] &mdash;—

*[[algoritmo della linea di Bresenham]] &mdash;— ottimizzato per usare solo le addizioni e per evitare l'uso di calcoli in virgola mobile.

*[[algoritmo della linea di Xiaolin Wu]] &mdash;— può realizzare l'[[antialiasing]]

==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:

[[ImmagineFile:esempio rasterizzazione poligono 1.png|frame|center|Figura 1.]]

In questi casi abbiamo a disposizione i seguenti algoritmi:

Riga 49:

*[[Algoritmo scan line]]

== Altri progetti ==

[[Categoria:Computer grafica]]

{{interprogetto}}

[[Categoria:Algoritmi geometrici]]

{{Link AdQ|de}}

{{Portale|matematica}}

[[Categoria:Computer grafica]]

[[bs:Algoritmi za crtanje linija]]

[[Categoria:Algoritmi geometrici|Rasterizzazione di linea]]

[[de:Rasterung von Linien]]

[[en:Line drawing algorithm]]

[[fr:Algorithme de tracé de segment]]

[[no:Linjetegningsalgoritme]]

[[ru:Алгоритмы построения отрезка]]

[[sr:Алгоритам за исцртавање линија]]