Algoritmo DDA

Template:F 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{\mathrm{\Delta }y}{\mathrm{\Delta }x}$

e che

$\mathrm{\Delta }y=m*\mathrm{\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 $\mathrm{\Delta }y$ ovvero:

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

Algoritmo

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

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 accorgimento per correggere questo problema è quello di invertire i parametri, ovvero non ricercheremo più la y ma la x:

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

In questo caso si ottiene il risultato in figura 2:

Figura 2.