Algoritmo DDA

Da Wikipedia, l'enciclopedia libera.

L'algoritmo DDA (digital differential analyzer) è un algoritmo di rasterizzazione di linea.

L'algoritmo DDA parte dall'osservazione che la pendenza di una retta passante per i punti p_1(x_1,y_1) e p_2(x_2,y_2) è esprimibile come:

m = \frac{y_2 - y_1}{x_2 - x_1} = \frac{\Delta y}{\Delta x}

e che

\Delta y = m * \Delta x

Da qui possiamo ricavare che per passare da un punto p_i(x_i,y_i) ad un punto p_{i+1}(x_{i+1},y_{i+1}) dove x_{i+1} = x_i +1, l'aumento di y_{i+1} rispetto a y_i dovrà essere \Delta y ovvero:

 y_{i+1} = y_i + \Delta y = y_i + (m * \Delta x) = y_i + (m * 1) = y_i + m

Algoritmo[modifica | modifica wikitesto]

Un esempio di algoritmo può essere il seguente:

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

Errori[modifica | modifica wikitesto]

Per grandi pendenze l'algoritmo produce uno spargimento di punti come in figura 1.

Figura 1.

Come vediamo è presente un'operazione di arrotondamento ( round(y) ) e le operazioni sono eseguite in virgola mobile per via del valore m; tutti elementi costosi dal punto di vista computazionale.


In questo caso infatti notiamo che m ha un valore di circa 4.2, quindi per ogni incremento sull'asse x di valore 1, sull'asse y incrementeremo di 4 pixels circa. Un arcogimento per correggere questo problema è quello di invertire i parametri, ovvero non ricercheremo più la y ma la x:

 x_{i+1} = x_i + \Delta x = y_i + (1/m * \Delta y) = y_i + (1/m * 1) = x_i + 1/m

In questo caso si ottiene il risultato in figura 2:

Figura 2.


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