Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 50 ยท Line and Circle Algorithms

Bresenham's Line Algorithm

Learn Bresenham's line algorithm: the decision parameter, integer-only arithmetic, how to handle all octants, and how it compares with DDA, with a live step-through.

In 1962 Jack Bresenham, working at IBM, devised a way to draw lines for a plotter using only integer addition and subtraction. No floating point, no multiplication in the loop, no rounding. More than sixty years later, his idea is still the textbook method for drawing lines on a pixel grid, and its core trick, tracking a small integer error or decision parameter, appears again in circle, ellipse and polygon algorithms.

This lesson derives the algorithm for one octant, shows how to extend it to every direction, and lets you step through it pixel by pixel. If you have not read the DDA algorithm, do so first; Bresenham solves the same problem better.

The problem DDA left open

DDA computes a floating-point y for every x and rounds it. But all we really need is a yes-or-no answer per column: should the next pixel stay on the same row, or move up one row? Bresenham answers that with a number that is always an integer.

Start with the simplest case, the first octant: a line with 0 <= slope <= 1 going right. Then x increases by exactly 1 every step, and y either stays or increases by 1. Let dx = x1 - x0 and dy = y1 - y0 (both non-negative here).

Suppose we have just plotted pixel (x, y). For the next column x + 1 there are two candidates: (x + 1, y) and (x + 1, y + 1). The true line passes between them. We choose the candidate that is closer to the line.

flowchart LR
  A["Plotted pixel<br/>(x, y)"] --> B{"Which is closer to the true line?"}
  B -->|"lower is closer"| C["next pixel (x + 1, y)"]
  B -->|"upper is closer"| D["next pixel (x + 1, y + 1)"]

Every step is a choice between two neighboring pixels in the next column.

The decision parameter

Let d_low be the vertical distance from the line down to the lower candidate and d_up the distance up to the upper candidate. At column x + 1 the line is at height y_line = m * (x + 1) + b, so:

  • d_low = y_line - y
  • d_up = (y + 1) - y_line

The lower pixel is closer when d_low - d_up < 0. Multiply that difference by dx (positive, so the sign does not change) to remove the fraction in m = dy / dx. The result is the decision parameter:

TEXT
p = dx * (d_low - d_up)  =  2*dy*x - 2*dx*y + c      (c is a constant)

Because p is built from integers, it is an integer. The rule is:

  • if p < 0, plot (x + 1, y) (stay on the same row);
  • otherwise, plot (x + 1, y + 1) (step up).

Now the clever part: we do not recompute p from scratch. Compare it with the next value p':

  • After staying on the row (y unchanged): p' = p + 2*dy.
  • After stepping up (y + 1): p' = p + 2*dy - 2*dx.

The starting value, evaluated at the first point (which lies exactly on the line), simplifies to p0 = 2*dy - dx.

So the whole algorithm is:

  1. p = 2*dy - dx.
  2. For each x from x0 to x1: plot (x, y); if p < 0 then p += 2*dy, otherwise y += 1 and p += 2*dy - 2*dx.

The values 2*dy and 2*dy - 2*dx are computed once, so the inner loop contains only additions, subtractions and a comparison with zero. That is why Bresenham was so much faster than DDA on early hardware, and why hardware line drawers still use it.

Worked example

Draw from (2, 3) to (9, 7), the same line as in the DDA lesson. Here dx = 7, dy = 4, 2*dy = 8, 2*dy - 2*dx = -6, and p0 = 8 - 7 = 1.

x y plotted p next
2 3 1 p >= 0: y up, p = 1 - 6 = -5
3 4 -5 p < 0: same y, p = -5 + 8 = 3
4 4 3 p >= 0: y up, p = 3 - 6 = -3
5 5 -3 p < 0: same y, p = 5
6 5 5 y up, p = -1
7 6 -1 same y, p = 7
8 6 7 y up, p = 1
9 7 1 done

The pixels are (2,3) (3,4) (4,4) (5,5) (6,5) (7,6) (8,6) (9,7), the same as DDA produced, but without a single fraction.

Handling every direction

The derivation assumed a shallow line going to the right with y increasing. Real lines can go in eight directions, or octants. There are two standard ways to cover them.

Reflect into the first octant. Before the loop:

  • if the line is steep (|dy| > |dx|), swap the roles of x and y everywhere, and swap back when plotting;
  • if it goes right-to-left, swap the two endpoints;
  • if y decreases, use a step of -1 instead of +1 and take dy as its absolute value.

Use the symmetric error form. The version below keeps a single error term and works in all octants without any swapping. It tracks err = dx + dy where dy is stored as a negative number, and each loop iteration decides independently whether to advance x, y or both:

JavaScript
function bresenham(x0, y0, x1, y1) {
  const points = [];
  const dx = Math.abs(x1 - x0);
  const dy = -Math.abs(y1 - y0);
  const sx = x0 < x1 ? 1 : -1;
  const sy = y0 < y1 ? 1 : -1;
  let err = dx + dy;

  while (true) {
    points.push({ x: x0, y: y0 });
    if (x0 === x1 && y0 === y1) break;
    const e2 = 2 * err;
    if (e2 >= dy) { err += dy; x0 += sx; }  // time to step in x
    if (e2 <= dx) { err += dx; y0 += sy; }  // time to step in y
  }
  return points;
}

It is the same idea (accumulate an integer error, step when it crosses a threshold), written so that either axis can be the fast one. Both forms use only integer arithmetic.

Step through it

The first demo below uses the "reflect into the first octant" version, so the decision parameter p stays visible. Press Step to plot one pixel and see the value of p that chose it; Run plays the rest, and Reset starts over. Change the endpoints to try steep lines, left-going lines and lines going up. The faint red line is the ideal line.

Bresenham, one step at a time

When you try a steep line, remember what the code does: it swaps x and y, runs the first-octant algorithm, and swaps back when plotting. "Stay on the same row/column" in the log therefore means "the slow axis does not move this step".

Bresenham versus DDA

How do the two compare in practice? The next console draws thousands of pseudo-random lines with both algorithms (a fixed random seed makes the result repeatable) and counts how many lines get a different pixel set.

JS DDA versus Bresenham on random lines

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

No output.

You should see that every pair of lines has the same number of pixels (both light exactly one pixel per step along the long axis), and that roughly four lines in five are identical. The rest differ at the pixels where the true line passes exactly halfway between two candidates, which happens over and over on lines such as slope 1/2. There DDA's rounding rule (Math.round goes up) and Bresenham's tie rule may disagree, and a tie decided differently can shift a whole run of pixels by one row. Both answers are equally good approximations; they are just different conventions.

In summary:

DDA Bresenham
Arithmetic floating point add + round integer add/subtract only
Error can accumulate none (exact integer decisions)
Speed on simple hardware slower faster
Ease of understanding easiest needs the decision parameter idea
Generalizes to circles no yes (midpoint circle, next lesson)

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the decision parameter p decide in Bresenham's algorithm?

    p is the scaled difference of the two distances between the line and the candidate pixels. Its sign tells which candidate is closer.
  2. 2. For a line from (0, 0) to (8, 3), what is the initial decision parameter p0 = 2*dy - dx?

    dx = 8 and dy = 3, so p0 = 6 - 8 = -2. It is negative, so the second pixel stays on row 0.
  3. 3. Which operations does Bresenham's inner loop need?

    The constants 2dy and 2dy - 2*dx are computed once. Each step just adds one of them to p and tests the sign.
  4. 4. How does the basic first-octant algorithm handle a steep line (|dy| > |dx|)?

    By exchanging x and y the steep line becomes shallow, so the same decision logic applies. The plotted coordinates are swapped back.

Summary

  • Bresenham's algorithm chooses, for each step along the long axis, between two neighboring pixels using an integer decision parameter.
  • In the first octant: p0 = 2*dy - dx; if p < 0 then p += 2*dy, otherwise move diagonally and p += 2*dy - 2*dx.
  • Only integer addition, subtraction and sign tests are needed, so it is fast and has no accumulating error.
  • Other octants are handled by swapping x and y for steep lines, swapping endpoints for leftward lines and negating the step for downward ones, or by the symmetric error form.
  • DDA and Bresenham agree except where the true line passes exactly halfway between pixels.

Next: The Midpoint Circle Algorithm.