Algoritmo DDA

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

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}+\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.