Visualizza wikitesto di Algoritmo della linea di Bresenham

{{F|computer grafica|arg2=algoritmi|marzo 2013}}
L''''algoritmo della linea di Bresenham''' (da alcuni chiamato ''algoritmo del punto medio'' o anche ''Cerchi di Bresenham'') è un [[algoritmo di rasterizzazione di linea]].
Allo stato attuale è l'algoritmo più usato per la [[rasterizzazione]] di [[linea|linee]], soprattutto per la sua bassa richiesta di risorse computazionali.

== Descrizione ==
Per capire l'[[algoritmo]], semplifichiamo il problema assumendo che <math>m = \frac{\Delta y}{\Delta x}</math> sia compreso tra <math>0 < m < 1</math>.

Immaginiamo di trovarci ad un passo <math>i</math> dell'algoritmo, cioè abbiamo appena determinato quale [[pixel]] "accendere", per esempio <math>p_1(x_1,y_1)</math>.

Ora dobbiamo determinare il prossimo pixel da "accendere", chiamiamolo <math>p_2(x_2,y_2)</math>, dove <math>x_2 = x_1 + 1</math>.

La situazione è quella riportata in figura 1, dove dal punto 1 (quello in verde) dobbiamo passare al punto 2 che si può trovare subito a destra, caso ''A'', o in alto a destra, caso ''B''.

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

*Nel caso ''A'' abbiamo <math>y_2 = y_1 </math>;
*Nel caso ''B'' abbiamo <math>y_2 = y_1 + 1</math>.

Prendiamo in considerazione il punto <math>M(x_1 + 1, y_1 + {1\over2})</math> (Figura 2), punto medio tra A e B.
Se la linea da rasterizzare passa sopra, illumineremo il pixel superiore B, altrimenti il pixel inferiore A.

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

Per determinare se <math>M</math> si trova sotto o sopra la retta, consideriamo la forma esplicita dell'equazione della retta:

<math>y = \frac{\Delta y}{\Delta x} \cdot x + q</math>

che può essere riscritta nella forma:

<math>-\Delta x \cdot y + \Delta y \cdot x + \Delta x \cdot q = 0 </math>

Tutti i punti appartenenti alla retta devono verificare l'equazione. Ma questa retta divide anche due semipiani, quello composto da tutti i punti per cui la formula precedente restituisce un valore positivo e quello per cui restituisce un valore negativo. Un esempio dei semipiani lo troviamo nella figura 3.

[[File:Esempio rasterizzazione linea bresenham 3mod.png|frame|center|Figura 3]]

Quindi dalla formula precedente possiamo ricavare il valore decisionale <math>d</math>, sostituendo ad <math>x</math> ed <math>y</math> le coordinate di <math>M(x_1 + 1, y_1 + 1/2) </math> (il punto medio tra A e B):

<math>d = -\Delta x \cdot y_M + \Delta y \cdot x_M + \Delta x \cdot q </math>

il quale sarà:
* <math>d = 0</math>, se il punto giace sulla retta; in questo caso possiamo scegliere in modo indifferente il punto A o il punto B;
* <math>d < 0</math>, se il punto si trova sopra la retta; in questo caso prendiamo il punto A;
* <math>d > 0</math>, se il punto si trova sotto la retta; in questo caso prendiamo il punto B.

Nell'algoritmo avremmo necessità ogni volta di sapere se <math>d</math> è positivo o negativo.

Ipotizziamo di aver scelto il punto A, in questo caso il nostro punto di partenza <math>p</math> è <math>p(x_1 + 1 , y_1)</math>, e il nostro nuovo punto medio M è <math>M(x_1 + 2 , y_1 + {1\over2})</math>.
Invece il nuovo valore di <math>d</math> è:

<math>d_{new} = -\Delta x \cdot y_M + \Delta y \cdot x_M + \Delta x \cdot q = -\Delta x \cdot \left(y_1 + \frac{1}{2}\right) + \Delta y \cdot (x_1 + 2) + \Delta x \cdot q </math>

Proviamo a sottrarre al nuovo valore di <math>d</math> quello vecchio:

<math>d_{new} - d_{old} = -\Delta x \cdot \left(y_1 + \frac{1}{2}\right) + \Delta y \cdot (x_1+2) + \Delta x \cdot q  -  \left(-\Delta x \cdot \left(y_1 + \frac{1}{2}\right) + \Delta y \cdot (x_1 + 1) + \Delta x \cdot q\right) </math>

Semplificando otteniamo:

<math>d_{new} - d_{old} = \Delta y </math>

Quindi abbiamo modo di ricavare il nuovo valore <math>d</math> in modo più semplice dal vecchio, senza ogni volta rifare tutti i calcoli.

Ora dobbiamo fare l'ipotesi per il caso in cui si sia scelto il punto B.
Abbiamo i nostri nuovi punti:
* <math>p(x_1 + 1, y_1 +1) </math>;
*<math>M(x_1 + 2, y_1 + 1+{1\over2}) = M(x_1 + 2, y_1 + {3\over2}) </math>;

e il nostro nuovo valore <math>d</math>:

<math>d_{new} = -\Delta x \cdot \left(y_1 + \frac{3}{2}\right) + \Delta y \cdot (x_1+2) + \Delta x \cdot q </math>

Ripetiamo la sottrazione:

<math>d_{new} - d_{old} = -\Delta x \cdot \left(y_1 + \frac{3}{2}\right) + \Delta y \cdot (x_1 + 2) + \Delta x \cdot q  -  \left(-\Delta x \cdot \left(y_1 + \frac{1}{2}\right) + \Delta y \cdot (x_1 + 1) + \Delta x \cdot q\right) </math>

Semplificando otteniamo:

<math>d_{new} - d_{old} = - \Delta x + \Delta y </math>

Riassumendo, dato un valore <math>d_i</math>:

<math>d_{i+1}=
\left\{\begin{matrix} d_i - \Delta x + \Delta y, & \mbox{se }d_i > 0 \\ d_i + \Delta y, & \mbox{se }d_i<0 \end{matrix}\right. </math>

Non ci rimane che conoscere il valore <math>d_0</math>; ricordandoci la formula per calcolare <math>d</math> e prendendo come punto <math>p</math>, <math>p_0(x_0, y_0)</math> ovvero un estremo della retta, abbiamo:

<math>d = -\Delta x \cdot \left(y_0 + \frac{1}{2}\right) + \Delta y \cdot (x_0 + 1) + \Delta x \cdot q = -\Delta x \cdot y_0 + \Delta y \cdot x_0 + \Delta x \cdot q + \left(-\frac{\Delta x}{2} + \Delta y\right) </math>

Nel passaggio abbiamo portato fuori i valori <math>+1/2</math> e <math>+1</math>. La prima parte della formula corrisponde all'equazione della retta applicata ad un punto della retta, quindi sappiamo che sarà uguale a zero. Infine ci rimane:

<math>d_0 = -\frac{\Delta x}{2} + \Delta y </math>

==Algoritmo==
Da tutte queste formule possiamo finalmente ricavare l'algoritmo:
Dati due punti <math>p_1</math> e <math>p_2</math>, con coordinate (x<sub>1</sub>,y<sub>1</sub>) e (x<sub>2</sub>,y<sub>2</sub>):

 DX = x<sub>2</sub> - x<sub>1</sub>
 DY = y<sub>2</sub> - y<sub>1</sub>
 
 //il nostro valore d<sub>0</sub>
 d = - 1/2 * DX + DY
 
 //assegna le coordinate iniziali
 x = x<sub>1</sub>
 y = y<sub>1</sub>
 disegna_il_punto(x, y)
 
 '''while''' x '''<''' x<sub>2</sub> {
        '''if''' (d >= 0) {
         d = d -DX + DY;
         y = y + 1;
         x = x + 1;
        }
        '''else''' {
         d = d + DY;
         x = x + 1;
        }
        disegna_il_punto(x, y)
 }

Notiamo che l'algoritmo presenta dei numeri in virgola mobile, i quali richiedono risorse computazionali, un'idea per evitare questa precisione è quella di raddoppiare i valori di <math>d</math>:

 DX = x<sub>2</sub> - x<sub>1</sub>
 DY = y<sub>2</sub> - y<sub>1</sub>
 
 //il nostro valore d<sub>0</sub>
 d = - DX + 2 * DY
 
 //assegna le coordinate iniziali
 x = x<sub>1</sub>
 y = y<sub>1</sub>
 disegna_il_punto(x, y)
 
 '''while''' x '''<''' x<sub>2</sub> {
        '''if''' (d >= 0) {
         d = d -2 * DX + 2 * DY;
         y = y + 1;
         x = x + 1;
        }
        '''else''' {
         d = d + 2 * DY;
         x = x + 1;
        }
        disegna_il_punto(x, y)
 }

Abbiamo quindi ottenuto un algoritmo che lavora con [[numero|numeri]] interi e semplice da implementare.
Nel caso in cui avessimo x<sub>1</sub>>x<sub>2</sub> allora al posto di aumentare <math>x</math> lo diminuiamo mentre i valori decisionali restano uguali, anche se y<sub>1</sub>>y<sub>2</sub> i valori decisionali non variano, in quanto la retta assume pendenza di valore opposto a quello del caso y<sub>1</sub><y<sub>2</sub> e x<sub>1</sub><x<sub>2</sub>, cambia solo l'incremento della <math>y</math> che invece di aumentare, diminuisce, e il valore decisionale resta invariato, in quanto trattiamo la retta sia se x<sub>1</sub>>x<sub>2</sub> sia se y<sub>1</sub>>y<sub>2</sub> come se fosse nel primo caso studiato, nel primo caso sia DX che DY sono maggiori di zero allora prenderemo il valore assoluto, di seguito ricaviamo l'algoritmo:

 DX = x<sub>2</sub> - x<sub>1</sub>
 DY = y<sub>2</sub> - y<sub>1</sub>
 
 //per non scrivere sempre i valori assoluti cambio DY e DX con altre variabili
 a=abs(DY)
 b=-abs(DX)
 
 //il nostro valore d<sub>0</sub>
 d = 2*a+b
 //assegna le coordinate iniziali
 x = x<sub>1</sub>
 y = y<sub>1</sub>
 disegna_il_punto(x, y)
 
 //s e q sono gli incrementi di x e y
 s=1
 q=1
 if (x<sub>1</sub>>x<sub>2</sub>) q=-1
 if (y<sub>1</sub>>y<sub>2</sub>) s=-1
 
 '''while''' x '''<''' x<sub>2</sub> {
        '''if''' (d >= 0) {
         d = 2 * (a + b) + d
         y = y + s;
         x = x + q;
        }
        '''else''' {
         d = 2 * a + d;
         x = x + q;
        }
        disegna_il_punto(x, y)
 }

Con questo abbiamo ottenuto le rette con valore di <math>|m|<1</math>. Con valore di <math>|m|>1</math> dobbiamo fare delle modifiche perché |DY/DX|>1 e questo accade quando DY>DX in questo caso l'approssimazione della linea con l'algoritmo che abbiamo trovato è pessima, visto che viene trattato solo DX come loop, dobbiamo generalizzare l'algoritmo nei casi in cui possiamo avere DY>DX.
Se ruotiamo la retta di 90 gradi possiamo notare che è come se dovessimo applicare lo stesso algoritmo precedente con la coordinata dei due punti da scegliere x invece che <math>y</math>, allora in questo caso trattiamo DY come DX e DY come DX, basta quindi scambiare DX e DY e rimanere i valori decisionali invariati, nel loop possiamo avere DX>DY oppure DY>DX ma siccome scambiamo sarà sempre DX>DY, poi nel caso in cui d>=0 avremo che entrambe le coordinate aumentano o diminuiscono di 1, quindi questo caso rimane uguale, cambia invece il caso in cui <math>d<0</math> in questo caso infatti dobbiamo decidere se aumentare solo <math>x</math> o solo <math>y</math> in base al caso che abbiamo. Nel caso normale si aumenta <math>x</math>, nel caso DY>DX si scambiano e si aumenta <math>y</math>, da questa logica possiamo ricavare l'algoritmo per linee generali che è il seguente:

 swap = 0;
 DX = x<sub>2</sub> - x<sub>1</sub>;
 DY = y<sub>2</sub> - y<sub>1</sub>;
 
 //siccome scambio DY e DX ho sempre DX>=DY allora per sapere quale coordinata occorre cambiare uso una variabile
 '''if''' (abs(DX) '''<''' abs(DY)) {
    swap(DX, DY);
    swap = 1;
 }
 
 //per non scrivere sempre i valori assoluti cambio DY e DX con altre variabili
 a = abs(DY);
 b = -abs(DX);
 
 //assegna le coordinate iniziali
 x = x<sub>1</sub>;
 y = y<sub>1</sub>;
 
 //il nostro valore d<sub>0</sub>
 d = 2 * a + b;
 
 //s e q sono gli incrementi/decrementi di x e y
 q = 1;
 s = 1;
 '''if''' (x<sub>1</sub> > x<sub>2</sub>) q = -1;
 '''if''' (y<sub>1</sub> > y<sub>2</sub>) s = -1;
 disegna_punto(x, y);
 disegna_punto(x<sub>2</sub>, y<sub>2</sub>);
 '''for''' (k = 0; k '''<''' -b; k+=1) {
    '''if''' (d > 0) {
        x= x + q; y= y + s;
        d= d + 2 * (a + b);
    }
    '''else''' {
        x = x + q;
        '''if''' (swap==1) { y = y + s; x = x - q; }
        d = d + 2 * a;
    }
    disegna_punto(x, y);
 }

== Altri progetti ==
{{interprogetto|preposizione=sull'}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Computer grafica]]
[[Categoria:Algoritmi geometrici|Bresenham]]