DDA algorithm with advantages

The Digital Differential Analyzer (DDA) is a scan-conversion algorithm that draws a line by computing the pixel positions at unit intervals along one axis, using the line's slope. The other coordinate is calculated by adding a constant increment and rounding.

Principle

For a line from (x1, y1) to (x2, y2): dx = x2 − x1, dy = y2 − y1, slope m = dy/dx. Number of steps = max(|dx|, |dy|). The increments are

xinc = dx / steps,   yinc = dy / steps
(one of them is ±1)

• If |m| ≤ 1: x changes by 1, y by m: x_k+1 = x_k + 1, y_k+1 = y_k + m.
• If |m| > 1: y changes by 1, x by 1/m: y_k+1 = y_k + 1, x_k+1 = x_k + 1/m.

Algorithm

1. Input (x1, y1), (x2, y2).
2. dx = x2 − x1; dy = y2 − y1.
3. steps = max(|dx|, |dy|).
4. xinc = dx / steps; yinc = dy / steps.
5. x = x1; y = y1; plot (round(x), round(y)).
6. Repeat steps times:
      x = x + xinc; y = y + yinc;
      plot (round(x), round(y)).

void dda(int x1,int y1,int x2,int y2){
    int dx=x2-x1, dy=y2-y1, steps, k;
    float x=x1, y=y1, xinc, yinc;
    steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);
    xinc = (float)dx/steps;  yinc = (float)dy/steps;
    putpixel(round(x), round(y), WHITE);
    for(k=0;k<steps;k++){
        x += xinc;  y += yinc;
        putpixel(round(x), round(y), WHITE);
    }
}

Example: (2,3) to (7,6): dx=5, dy=3, steps=5, xinc=1, yinc=0.6. Points: (2,3), (3,3.6→4), (4,4.2→4), (5,4.8→5), (6,5.4→5), (7,6).

Advantages

• Simple to understand and implement.
• Faster than the direct equation y = mx + b, because no multiplication is used per step.
• Works for lines of any slope and direction.

Disadvantages

• Uses floating-point arithmetic and a rounding operation at every step, which is slow.
• Round-off error accumulates for long lines, so pixels may drift from the true line.
• Not suitable for direct hardware implementation.
• Division is needed to find the increments.