Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 50 ยท Line and Circle Algorithms

The DDA Line Algorithm

Learn how the DDA (digital differential analyzer) algorithm draws a line on a pixel grid with incremental steps, rounding, and its limitations.

A straight line is the simplest shape, and yet drawing one on a screen is not trivial. A mathematical line is infinitely thin and continuous, but a screen has only a grid of pixels. We have to pick, for each column or row, the pixel that best approximates the line. Doing this quickly, millions of times per second, was one of the first problems of computer graphics.

The DDA algorithm (digital differential analyzer) is the most direct solution. It walks along the line in equal steps and rounds each position to the nearest pixel. It is easy to understand, and it is the stepping stone to Bresenham's faster integer algorithm in the next lesson.

The idea: walk along the slope

Take two endpoints, (x0, y0) and (x1, y1). The line between them has these properties:

  • dx = x1 - x0 and dy = y1 - y0 are how far the line goes horizontally and vertically.
  • The slope is m = dy / dx: for every one step right, the line rises by m.

The line equation is y = m * x + b. A naive way to draw it is: for each integer x from x0 to x1, compute y = m * x + b, round it, and light the pixel. That works, but it multiplies and adds a floating-point number for every pixel. Multiplication was slow on early computers.

DDA replaces the multiplication with addition. If x increases by 1, then y increases by exactly m. So we start at (x0, y0) and repeatedly add a constant step to both coordinates.

Choosing the step size

There is one catch. If the slope is steep (|m| greater than 1), stepping x by 1 would make y jump by more than 1 and leave gaps in the line. So the larger of the two differences decides the number of steps:

TEXT
steps = max(|dx|, |dy|)
x_increment = dx / steps
y_increment = dy / steps

The longer axis always advances by exactly 1 pixel per step, and the shorter axis by a fraction between 0 and 1. This handles every direction: shallow lines, steep lines, diagonals, horizontal, vertical, and lines that run right-to-left or bottom-to-top (the increments just become negative).

The whole algorithm:

  1. Compute dx, dy and steps.
  2. Compute x_increment and y_increment.
  3. Start with x = x0, y = y0.
  4. Repeat steps + 1 times: plot (round(x), round(y)), then x += x_increment, y += y_increment.
flowchart TD
  A["Start: x = x0, y = y0"] --> B["steps = max(|dx|, |dy|)"]
  B --> C["xinc = dx / steps<br/>yinc = dy / steps"]
  C --> D["plot round(x), round(y)"]
  D --> E["x += xinc, y += yinc"]
  E --> F{"steps done?"}
  F -->|"no"| D
  F -->|"yes"| G["Finish"]

The DDA loop: plot, advance both coordinates by a constant increment, repeat.

In JavaScript:

JavaScript
function dda(x0, y0, x1, y1) {
  const dx = x1 - x0;
  const dy = y1 - y0;
  const steps = Math.max(Math.abs(dx), Math.abs(dy));
  const points = [];

  if (steps === 0) {                 // both endpoints are the same pixel
    return [{ x: x0, y: y0 }];
  }

  const xInc = dx / steps;
  const yInc = dy / steps;
  let x = x0;
  let y = y0;
  for (let i = 0; i <= steps; i++) {
    points.push({ x: Math.round(x), y: Math.round(y) });
    x += xInc;
    y += yInc;
  }
  return points;
}

A worked example

Draw from (2, 3) to (9, 7). Here dx = 7, dy = 4, so steps = 7. The increments are xInc = 1 and yInc = 4/7, about 0.571:

i x y (exact) pixel
0 2 3.000 (2, 3)
1 3 3.571 (3, 4)
2 4 4.143 (4, 4)
3 5 4.714 (5, 5)
4 6 5.286 (6, 5)
5 7 5.857 (7, 6)
6 8 6.429 (8, 6)
7 9 7.000 (9, 7)

Exactly one pixel is lit in each column, because x is the long axis. The y value is rounded to the nearest integer.

See it on a pixel grid

The demo below draws a grid of big "pixels". Type any endpoints (the grid is 32 columns by 20 rows, with the origin at the top-left like a real screen) and the DDA pixels are filled in. The thin blue line is the ideal mathematical line through the pixel centers, so you can judge the approximation. The list underneath shows each step.

DDA on a pixel grid

Try (2, 3) to (9, 7) to reproduce the table above, then a steep line such as (5, 1) to (9, 18). Notice that the line is thin and has exactly one pixel per row there, because y is now the long axis.

Strengths and limitations

DDA is simple and handles all slopes with one loop. But it has real weaknesses:

  • Floating-point arithmetic. Each step adds floats and rounds. On hardware without a floating-point unit this was slow, which is why Bresenham's integer method took over.
  • Accumulated rounding error. The increment dy / steps cannot usually be stored exactly in binary. Adding it again and again lets tiny errors accumulate, so on a very long line a pixel may eventually round the wrong way. The next example measures this.
  • Rounding cost. Calling round() for every pixel is an extra operation.
  • Rounding rules matter. At exact halves (such as y = 4.5) the result depends on the rounding rule. Math.round(4.5) gives 5 but Math.round(-4.5) gives -4. For screen coordinates that are never negative this is harmless, but a line that must look the same when drawn from either end needs care.

The console below draws a long line two ways. One uses the accumulate-and-add approach of DDA. The other computes each y directly from the line equation, y = y0 + (x - x0) * dy / dx, which has no accumulation. Then it counts how many pixels differ.

JS Accumulated error in DDA

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The last line is the root cause: ten additions of 0.1 do not give exactly 1. The few differences you see appear where the exact y is a tie such as 166.5, so a tiny error decides which way it rounds. For ordinary screen-sized lines this is rare and invisible, but they show why the next algorithm avoids floating point altogether.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does DDA use steps = max(|dx|, |dy|) instead of always stepping x by 1?

    The axis with the larger change advances by exactly 1 per step. If x always advanced by 1 on a steep line, y would skip pixels.
  2. 2. A line goes from (0, 0) to (10, 4). How many pixels does DDA plot and what is yInc?

    steps = max(10, 4) = 10, so the loop plots 11 points (including both ends). yInc = 4 / 10 = 0.4.
  3. 3. What is the main drawback of DDA compared with integer algorithms?

    Each step adds a non-exact float and rounds. That is slower on simple hardware and lets error build up on very long lines.
  4. 4. For the line (3, 3) to (3, 9), what does DDA compute?

    dx = 0 and dy = 6, so steps = 6; x never changes and y advances by 1.

Summary

  • A line from (x0, y0) to (x1, y1) has dx, dy and slope dy / dx.
  • DDA walks the line with constant increments: steps = max(|dx|, |dy|), then xInc = dx / steps and yInc = dy / steps.
  • The longer axis moves one pixel per step; the other axis is rounded, so each column (or row) gets exactly one pixel.
  • It is simple and works in every direction, but uses floating point, rounding and can accumulate small errors.

Next: Bresenham's Line Algorithm, which does the same job with integers only.