Part 2: Scan Conversion & Line Generation: DDA vs Bresenham's Integer Algorithm

1. The Differential Equation of a Line & Slope Dynamics

In Cartesian geometry, the slope-intercept form of a straight line is:

Where the slope $m$ and y-intercept $c$ are determined by the delta differentials $\Delta x = x_1 - x_0$ and $\Delta y = y_1 - y_0$:

Directly evaluating $y = m \cdot x + c$ for every integer $x$ requires floating-point multiplication and addition per step. More critically, when $|m| > 1$, incrementing $x$ by 1 produces $\Delta y > 1$, causing gaps and disconnected pixel holes along steep lines. Robust rasterization algorithms must dynamically adapt step increments according to the line's slope magnitude.

2. Digital Differential Analyzer (DDA) Algorithm

The DDA Algorithm is an incremental scan-conversion method based on calculating differential increments $\Delta x$ and $\Delta y$. Instead of computing full multiplications at each coordinate, DDA samples the line at unit intervals along the coordinate axis with the largest differential.

Weakness of DDA: Although DDA eliminates multiplication, it still relies on floating-point arithmetic and explicit rounding functions (round() or floor()) at every single step. In hardware graphics pipelines, floating-point roundoff errors accumulate over long lines, causing the line trajectory to drift away from the true mathematical path.

3. Bresenham's Integer Line Algorithm

In 1962, Jack Elton Bresenham developed an optimal scan-conversion algorithm that utilizes pure integer addition, subtraction, and bitwise arithmetic—completely eliminating floating-point math and division.

Consider a line in the first octant where $0 \le m \le 1$ with $x_0 < x_1$. At step $k$, having plotted $(x_k, y_k)$, the next candidate pixel must be either:

• East (E): $(x_k + 1, y_k)$
• North-East (NE): $(x_k + 1, y_k + 1)$

The true mathematical line at $x = x_k + 1$ has vertical coordinate $y = m(x_k + 1) + c$. The vertical distances from the true line to the lower candidate pixel ($d_1$) and upper candidate pixel ($d_2$) are:

Substituting $m = \Delta y / \Delta x$ and multiplying throughout by $\Delta x$ (which is strictly positive) produces the integer decision parameter $P_k$:

Initial Parameter & Incremental Recurrence

Evaluating at the origin endpoint $(x_0, y_0)$ yields the initial decision parameter $P_0$:

At each subsequent step $k$, the next parameter $P_{k+1}$ is computed incrementally from $P_k$:

• If $P_k < 0$: The true line is closer to pixel $E$ $(x_k + 1, y_k)$. Plot $(x_k + 1, y_k)$, and update:
  P_{k+1} = P_k + 2 \Delta y
• If $P_k \ge 0$: The true line is closer to pixel $NE$ $(x_k + 1, y_k + 1)$. Plot $(x_k + 1, y_k + 1)$, and update:
  P_{k+1} = P_k + 2 \Delta y - 2 \Delta x

4. C++ Reference Implementation

void drawLineBresenham(int x0, int y0, int x1, int y1) {
    int dx = std::abs(x1 - x0);
    int dy = std::abs(y1 - y0);
    int sx = (x0 < x1) ? 1 : -1;
    int sy = (y0 < y1) ? 1 : -1;
    int err = dx - dy;

    while (true) {
        setPixel(x0, y0);
        if (x0 == x1 && y0 == y1) break;
        int e2 = 2 * err;
        if (e2 > -dy) {
            err -= dy;
            x0 += sx;
        }
        if (e2 < dx) {
            err += dx;
            y0 += sy;
        }
    }
}

5. Performance & Hardware Efficiency Comparison