Algoritmo della linea di Bresenham

Da Wikipedia, l'enciclopedia libera.

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 linee, soprattutto per la sua bassa richiesta di risorse computazionali.

Per capire l'algoritmo, semplifichiamo il problema assumendo che m (m = \frac{\Delta y}{\Delta x}) sia compreso tra 0 ed 1 :  0 < m < 1 .

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

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

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.

Figura 1.

Nel caso A abbiamo y_2 = y_1 ;

Nel caso B abbiamo y_2 = y_1 + 1;

Prendiamo in considerazione il punto M(x_1 + 1, y_1 + 1/2) (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.

Figura 2.

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

y = \frac{\Delta y}{\Delta x} \cdot x + q

che può essere riscritta nella forma

-\Delta x \cdot y + \Delta y \cdot x + \Delta x \cdot q = 0

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.

Figura3.

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

d = -\Delta x \cdot y_M + \Delta y \cdot x_M + \Delta x \cdot q

il quale sarà:

  • d = 0 Se il punto giace sulla retta; in questo caso possiamo scegliere in modo indifferente il punto A o il punto B.
  • d < 0 Se il punto si trova sopra la retta; in questo caso prendiamo il punto A.
  • d > 0 Se il punto si trova sotto la retta; in questo caso prendiamo il punto B.

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

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

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

Proviamo a sottrarre al nuovo valore di d quello vecchio:

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)

Semplificando otteniamo:

d_{new} - d_{old} = \Delta y

Quindi abbiamo modo di ricavare il nuovo valore d 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:

  • p(x_1 + 1, y_1 +1) ;
  • M(x_1 + 2, y_1 + 1 + 1/2) = M(x_1 + 2, y_1 + 3/2) ;

e il nostro nuovo valore d:

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

Ripetiamo la sottrazione:

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)

Semplificando otteniamo:

d_{new} - d_{old} = - \Delta x + \Delta y

Riassumendo, dato un valore d_i:

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.

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

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)

Nel passaggio abbiamo portato fuori i valori 1/2 e +1. 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:

d_0 = -\frac{\Delta x}{2} + \Delta y

Algoritmo[modifica | modifica wikitesto]

Da tutte queste formule possiamo finalmente ricavare l'algoritmo: Dati due punti p1 e p2, con coordinate (x1,y1) e (x2,y2):

DX = x2 - x1
DY = y2 - y1

//il nostro valore d0
d = - 1/2 * DX + DY

//assegna le coordinate iniziali
x = x1
y = y1
disegna_il_punto(x, y)

while x < x2 {
       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 d:

DX = x2 - x1
DY = y2 - y1

//il nostro valore d0
d = - DX + 2 * DY

//assegna le coordinate iniziali
x = x1
y = y1
disegna_il_punto(x, y)

while x < x2 {
       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 numeri interi e semplice da implementare. Nel caso in cui avessimo x1>x2 allora al posto di aumentare x lo diminuiamo mentre i valori decisionali restano uguali, anche se y1>y2 i valori decisionali non variano, in quanto la retta assume pendenza di valore opposto a quello del caso y1<y2 e x1<x2, cambia solo l'incremento della y che invece di aumentare, diminuisce, e il valore decisionale resta invariato, in quanto trattiamo la retta sia se x1>x2 sia se y1>y2 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 = x2 - x1
DY = y2 - y1

//per non scrivere sempre i valori assoluti cambio DY e DX con altre variabili
a=abs(DY)
b=-abs(DX)

//il nostro valore d0
d = 2*a+b
//assegna le coordinate iniziali
x = x1
y = y1
disegna_il_punto(x, y)

//s e q sono gli incrementi di x e y
s=1
q=1
if (x1>x2) q=-1
if (y1>y2) s=-1

while x < x2 {
       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 |m|<1. Con valore di |m|>1 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 y, 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 d<0 in questo caso infatti dobbiamo decidere se aumentare solo x o solo y in base al caso che abbiamo. Nel caso normale si aumenta x, nel caso DY>DX si scambiano e si aumenta y, da questa logica possiamo ricavare l'algoritmo per linee generali che è il seguente:

swap = 0;
DX = x2 - x1;
DY = y2 - y1;

//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 = x1;
y = y1;

//il nostro valore d0
d = 2 * a + b;

//s e q sono gli incrementi/decrementi di x e y
q = 1;
s = 1;
if (x1 > x2) q = -1;
if (y1 > y2) s = -1;
disegna_punto(x, y);
disegna_punto(x2, y2);
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[modifica | modifica wikitesto]

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