Bresenham's Line Algorithm

How Bresenham's algorithm works

You want to draw a line from pixel (x0, y0) to (x1, y1) on a grid where every pixel is either on or off. The mathematical line has a real-valued slope, but the screen only has integer cells. For every column the line crosses, you have to commit to exactly one row. Which one?

The naive answer computes y = y0 + slope · (x − x0) at each column and rounds. That works, but it drags a floating-point number through the inner loop and rounds it every step. In 1962, working on a Calcomp plotter at IBM, Jack Bresenham realized you never actually need the value of y — you only need to know, at each step, whether y should stay the same or tick up by one. That's a single yes/no decision, and you can make it with integers alone.

Assume the simple case first: a shallow line in the first octant, where x1 > x0, y1 > y0, and the slope is between 0 and 1. Let dx = x1 − x0 and dy = y1 − y0, so 0 ≤ dy ≤ dx. We step x one column at a time. At each column the true line sits somewhere between the current row y and the row above, y + 1. We pick whichever pixel center the line passes closer to — equivalently, we check whether the line passes above or below the midpoint between those two candidate pixels. That's why this is also called the midpoint line algorithm.

The running error term

Here is the trick that makes it integer-only. Instead of carrying y as a fraction, carry an error term d that accumulates how far the true line has drifted from the pixel we last chose. Each time we advance one column, the ideal y rises by dy/dx. We add that drift to the error. When the accumulated drift crosses one half — meaning the line has climbed past the midpoint — we step y up by one and subtract one off the error to keep it bounded.

Fractions like dy/dx and 1/2 would reintroduce floats. The fix is to multiply the entire decision through by 2·dx, which clears every denominator and leaves a purely integer recurrence. The classic formulation uses a decision variable initialized to:

d = 2·dy − dx

and then, at each step, applies one of two updates:

• If d < 0 — the line is still below the midpoint. Keep y the same (a horizontal step) and update d += 2·dy.
• If d ≥ 0 — the line has reached or passed the midpoint. Increment y (a diagonal step) and update d += 2·dy − 2·dx.

Both increments, 2·dy and 2·dy − 2·dx, are constants computed once before the loop. So the inner loop is: plot the pixel, compare d against zero, do one integer add (sometimes also bump y), repeat. No multiply, no divide, no float, no rounding ever happens inside the loop.

When to use it — and when not to

• Integer-only or no-FPU hardware — microcontrollers, retro consoles, CNC and laser-cutter controllers, pen plotters, e-paper and OLED display drivers. Bresenham is the canonical way to drive a stepper-motor head or a 1-bit framebuffer.
• Exact, deterministic pixel sets — when two adjacent draws must share pixels exactly with no rounding drift, the integer recurrence guarantees a reproducible result.
• Grid traversal in games — line-of-sight, fog-of-war reveal, and tile-based ray casting all walk a grid cell-by-cell. Bresenham (or its supercover variant) enumerates exactly the cells a ray crosses.
• Teaching — it's the cleanest example of trading an expensive operation (division) for a cheap incremental one, a pattern that recurs everywhere in graphics.

Skip it when you need anti-aliasing (use Xiaolin Wu's algorithm or a GPU), when you're drawing thick or textured lines (rasterize as a quad instead), or when you're already on a GPU — modern rasterizers evaluate edge functions across whole tiles in parallel, which beats Bresenham's strictly sequential recurrence.

Bresenham vs other line-drawing methods

	Bresenham	DDA	Naive y = mx + b	Xiaolin Wu	GPU edge function
Per-pixel math	1–2 int adds + compare	1 float add + round	1 float mul + add + round	2 int adds + fractional shade	2–3 int/fixed adds per pixel, parallel
Floating point	None	Yes (accumulator)	Yes (every pixel)	Yes (intensity)	Fixed-point, parallel
Division	None (deltas by subtraction)	Once, to find slope	Once, to find slope	Once	None in hot path
Anti-aliasing	No (hard edges)	No	No	Yes	Optional (MSAA)
Rounding drift	None (exact)	Can accumulate	Per-pixel	None	None
Parallelizable	Poorly (sequential recurrence)	Poorly	Yes (each pixel independent)	Poorly	Yes (designed for it)
Cost vs Bresenham	1×	≈ 2–4× on integer CPUs	≈ 5× on integer CPUs	≈ 2×	Different model entirely
Best for	CPU/embedded, exact lines	Quick float-friendly draw	Pedagogy only	Smooth CPU lines	Real-time 3D

The headline distinction is DDA (Digital Differential Analyzer) vs Bresenham. DDA also walks the line incrementally, but it stores the running y as a float and rounds it each step. Bresenham stores an integer error instead and never rounds. They light the same pixels; Bresenham just does it with cheaper instructions and no chance of float drift building up over a long line.

What the numbers actually say

• Per-pixel cost. The inner loop is one comparison, one conditional integer add, and on diagonal steps a second integer increment. On a 1980s 8-bit CPU an integer add was a single-cycle instruction while a floating-point divide could cost 50–100 cycles — which is exactly why a plotter or game console reached for Bresenham.
• A line from (0,0) to (1920,1080) plots 1921 pixels (one per column, since dx > dy). That's 1921 iterations of a 2–3 instruction loop: a few thousand integer operations to draw a full-screen diagonal, versus the same count of float operations plus rounding for DDA.
• Total work is O(max(dx, dy)) — linear in the longer projected axis, which is the number of pixels the line actually occupies. You cannot do better; every pixel on the line must be visited at least once.
• Memory is O(1). Three or four integer registers — x, y, the error term, and two precomputed increments. Nothing scales with line length.
• Error stays bounded. Because every diagonal step subtracts 2·dx back off the accumulator, d never overflows a normal int for any reasonable resolution — the deltas, not the cumulative path length, set its range.

JavaScript implementation

This is the general integer Bresenham — the form you'll actually paste into production. It handles all eight octants and the vertical, horizontal, and diagonal special cases without any branching on slope, by working with absolute deltas and per-axis sign steps. It's sometimes called the "error-doubling" or unified form.

function bresenham(x0, y0, x1, y1, plot) {
  let dx =  Math.abs(x1 - x0);
  let dy = -Math.abs(y1 - y0);   // note: kept negative
  const sx = x0 < x1 ? 1 : -1;
  const sy = y0 < y1 ? 1 : -1;
  let err = dx + dy;             // == dx - |dy|

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

// usage
const pixels = [];
bresenham(2, 1, 11, 6, (x, y) => pixels.push([x, y]));
// pixels === [[2,1],[3,2],[4,2],[5,3],[6,3],[7,4],[8,4],[9,5],[10,5],[11,6]]

Two details earn their keep. First, dy is stored as a negative number so the single accumulator err can drive both axes with one set of comparisons — that's what folds all eight octants into one branchless loop. Second, the two ifs are independent, not else if: a perfectly diagonal pixel satisfies both and steps in both axes in the same iteration, which is exactly what you want for a 45° line.

Python implementation

def bresenham(x0, y0, x1, y1):
    """Yield every integer pixel on the line from (x0,y0) to (x1,y1)."""
    dx =  abs(x1 - x0)
    dy = -abs(y1 - y0)
    sx = 1 if x0 < x1 else -1
    sy = 1 if y0 < y1 else -1
    err = dx + dy
    while True:
        yield (x0, y0)
        if x0 == x1 and y0 == y1:
            break
        e2 = 2 * err
        if e2 >= dy:
            err += dy
            x0 += sx
        if e2 <= dx:
            err += dx
            y0 += sy


# The "shallow first-octant" textbook form, for when you want to see the
# classic d = 2*dy - dx decision parameter explicitly:
def bresenham_shallow(x0, y0, x1, y1):
    dx, dy = x1 - x0, y1 - y0          # assumes dx > 0 and 0 <= dy <= dx
    d = 2 * dy - dx
    y = y0
    for x in range(x0, x1 + 1):
        yield (x, y)
        if d >= 0:
            y += 1
            d += 2 * (dy - dx)
        else:
            d += 2 * dy


print(list(bresenham(2, 1, 11, 6)))
# [(2, 1), (3, 2), (4, 2), (5, 3), (6, 3), (7, 4), (8, 4), (9, 5), (10, 5), (11, 6)]

The bresenham_shallow version exposes the famous d = 2·dy − dx initialization so you can match it against a textbook derivation. The general bresenham version is what you'd ship, because it silently handles steep, reversed, and degenerate lines that the shallow form would get wrong.

The famous sibling — midpoint circle

Bresenham's real legacy isn't lines, it's the technique: replace an expensive coordinate computation with a cheap integer error recurrence and a midpoint test. The most-searched application of that idea is drawing a circle. The midpoint circle algorithm applies the same decision-variable trick to the implicit equation x² + y² − r² = 0, and exploits 8-way symmetry so it only computes one 45° arc and mirrors it.

function midpointCircle(cx, cy, r, plot) {
  let x = r, y = 0;
  let d = 1 - r;                 // initial decision parameter
  while (x >= y) {
    // one computed point, eight mirrored octants
    for (const [px, py] of [
      [ x,  y], [ y,  x], [-y,  x], [-x,  y],
      [-x, -y], [-y, -x], [ y, -x], [ x, -y],
    ]) plot(cx + px, cy + py);

    y++;
    if (d <= 0) {
      d += 2 * y + 1;            // midpoint stays inside the circle
    } else {
      x--;
      d += 2 * (y - x) + 1;     // midpoint crossed outside; step x in
    }
  }
}

Same shape as the line algorithm: an integer d, two constant-ish increments, one compare per step, and zero trig or square roots. A full circle of radius r costs about r/√2 iterations of this loop, each producing eight pixels.

Variants worth knowing

Xiaolin Wu's line algorithm (1991). Keeps Bresenham's incremental error idea but lights the two pixels straddling the line each step, shading them by the fractional distance. The result is anti-aliased — smooth instead of stair-stepped — for roughly double the per-step cost.

Gupta–Sproull. Computes the true perpendicular distance from each pixel to the line and uses it to anti-alias more accurately than Wu's axis-aligned approximation, at higher cost. Used where edge quality matters more than speed.

Supercover / "all-cells" line. Standard Bresenham skips a cell when the line clips only its corner. The supercover variant plots every grid cell the line touches, including diagonal corner-crossings — essential for collision, line-of-sight, and conservative rasterization.

DDA on fixed-point. A middle ground: run DDA but store the accumulator in fixed-point integers (e.g. 16.16). You keep DDA's simplicity while avoiding true floats, which is how many embedded 2D libraries actually ship line drawing.

Bresenham's circle and ellipse. The midpoint circle above, plus the midpoint ellipse algorithm, which splits the arc into two regions where the slope crosses −1 and switches its decision rule between them. Same DNA, more bookkeeping.

Common bugs and edge cases

• Only handling one octant. The textbook shallow form assumes x increases and slope is in [0, 1]. Feed it a steep or right-to-left line and it draws garbage or an infinite loop. Ship the general absolute-delta form, or swap/sign-flip coordinates first.
• Using else if for the two axis steps. In the unified loop the two ifs must both be allowed to fire in the same iteration, otherwise 45° lines step only one axis and bend.
• Off-by-one at the endpoint. Decide once whether the line is inclusive of (x1, y1). The range(x0, x1 + 1) / break-on-match patterns above include it; drop the + 1 and you'll leave the last pixel dark, which shows up as a gap where two lines should meet.
• Forgetting the sign of stored dy. The compact form keeps dy negative on purpose. Make it positive and the comparisons against e2 invert and the line walks the wrong way.
• Integer overflow on huge coordinates. The doubling e2 = 2 * err can overflow a 16-bit accumulator on a large display. Size the error type to the resolution, or it wraps and the line jumps.
• Expecting anti-aliasing. Bresenham is exactly one pixel per major-axis step. If a reviewer complains the diagonal looks jagged, that's not a bug — switch to Wu's algorithm.