Introduction

Every line on a computer screen is a lie. A mathematical line is a continuous, infinitely thin ribbon of points. A screen is a grid of square pixels. Drawing a line means deciding which pixels to light up โ€” and making that choice so quickly that the result looks smooth.

In 1962, IBM engineer Jack Bresenham was working with a pen plotter at IBM's San Josรฉ Research Laboratory. Floating-point arithmetic was expensive โ€” or simply unavailable โ€” on the hardware of the day. He needed to trace a straight path across a grid using only the cheapest operation a digital circuit can do: integer addition.

The insight he found is almost embarrassing in its simplicity: instead of computing the exact y-coordinate for every x-step (which requires division), track the accumulated error between the true line and the chosen pixel row. Each step you just add a constant, then check whether the error has crossed a threshold. If it has, step up a row and subtract the threshold. No division, no floating point โ€” just addition and a sign check.

The result is an algorithm that is O(n)O(n) in the number of pixels and provably optimal: it touches exactly the pixels that best approximate the line, and nothing else.

Try It

Drag the endpoints on the pixel grid below. The algorithm updates instantly, lighting only the pixels Bresenham's integer-addition loop chooses.

<p class="hint">Drag the <b>green</b> (start) and <b>red</b> (end) dots to any cell. The lit pixels are chosen by Bresenham's integer-addition loop โ€” no division, no floating point.</p>
<div class="layout">
  <canvas id="grid" width="280" height="280"></canvas>
  <div class="panel">
    <div class="info-row"><span class="dot start-dot"></span> Start: <span id="p0"></span></div>
    <div class="info-row"><span class="dot end-dot"></span> End: <span id="p1"></span></div>
    <div class="info-row">Pixels lit: <span id="count"></span></div>
    <div class="divider"></div>
    <div class="label">Step log (first 8)</div>
    <div id="log" class="log"></div>
    <div class="divider"></div>
    <button id="toggle" type="button">Show naive float</button>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.layout { display: flex; gap: 1rem; align-items: flex-start; flex-wrap: wrap; }
canvas { border: 1px solid #cdd9e3; border-radius: 6px; cursor: crosshair; touch-action: none; }
.panel { flex: 1; min-width: 160px; font-size: .82rem; }
.info-row { display: flex; align-items: center; gap: .35rem; margin-bottom: .35rem; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.start-dot { background: #2e9e4f; }
.end-dot { background: #c92f3c; }
.divider { border-top: 1px solid #dde3ea; margin: .5rem 0; }
.label { font-weight: 600; font-size: .78rem; color: #555; margin-bottom: .25rem; }
.log { font-family: ui-monospace, monospace; font-size: .72rem; color: #333; line-height: 1.6; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; margin-top: .4rem; }
button.active { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Bresenham's line algorithm โ€” integer arithmetic only.
// Given endpoints (x0,y0) and (x1,y1), emit the pixels that best approximate
// the ideal line using only addition and comparisons (no division, no floats).
const COLS = 14, ROWS = 14, SZ = 20, PAD = 0;
const canvas = document.getElementById('grid');
const ctx = canvas.getContext('2d');
canvas.width = COLS * SZ;
canvas.height = ROWS * SZ;

let p0 = { x: 1, y: 2 }, p1 = { x: 12, y: 10 };
let showNaive = false;

// โ”€โ”€ Bresenham โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function bresenham(x0, y0, x1, y1) {
  const pts = [], log = [];
  let dx = Math.abs(x1 - x0), dy = Math.abs(y1 - y0);
  const sx = x0 < x1 ? 1 : -1, sy = y0 < y1 ? 1 : -1;
  let err = dx - dy;
  let x = x0, y = y0;
  for (let i = 0; i < 500; i++) {
    pts.push({ x, y });
    if (log.length < 8) log.push({ x, y, err });
    if (x === x1 && y === y1) break;
    const e2 = 2 * err;
    if (e2 > -dy) { err -= dy; x += sx; }
    if (e2 <  dx) { err += dx; y += sy; }
  }
  return { pts, log };
}

// โ”€โ”€ Naive float (for comparison) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function naiveFloat(x0, y0, x1, y1) {
  const pts = new Set();
  const dx = x1 - x0, dy = y1 - y0;
  const steps = Math.max(Math.abs(dx), Math.abs(dy));
  for (let i = 0; i <= steps; i++) {
    const t = steps === 0 ? 0 : i / steps;
    pts.add(Math.round(x0 + t * dx) + ',' + Math.round(y0 + t * dy));
  }
  return [...pts].map(k => { const [x, y] = k.split(',').map(Number); return { x, y }; });
}

function draw() {
  const { pts, log } = bresenham(p0.x, p0.y, p1.x, p1.y);
  const naive = showNaive ? naiveFloat(p0.x, p0.y, p1.x, p1.y) : [];
  const naiveSet = new Set(naive.map(p => p.x + ',' + p.y));

  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // grid lines
  ctx.strokeStyle = '#d8e0ea';
  ctx.lineWidth = 0.5;
  for (let i = 0; i <= COLS; i++) { ctx.beginPath(); ctx.moveTo(i*SZ,0); ctx.lineTo(i*SZ,ROWS*SZ); ctx.stroke(); }
  for (let j = 0; j <= ROWS; j++) { ctx.beginPath(); ctx.moveTo(0,j*SZ); ctx.lineTo(COLS*SZ,j*SZ); ctx.stroke(); }

  // naive pixels (behind Bresenham)
  if (showNaive) {
    naive.forEach(p => {
      ctx.fillStyle = 'rgba(220,150,50,0.35)';
      ctx.fillRect(p.x*SZ+1, p.y*SZ+1, SZ-2, SZ-2);
    });
  }

  // Bresenham pixels
  pts.forEach(p => {
    const isAlsoNaive = naiveSet.has(p.x + ',' + p.y);
    ctx.fillStyle = showNaive
      ? (isAlsoNaive ? '#6ab04c' : '#1d3557')
      : '#1d3557';
    ctx.fillRect(p.x*SZ+1, p.y*SZ+1, SZ-2, SZ-2);
  });

  // endpoints
  const endpts = [{ p: p0, color: '#2e9e4f' }, { p: p1, color: '#c92f3c' }];
  endpts.forEach(({ p, color }) => {
    ctx.fillStyle = color;
    ctx.beginPath();
    ctx.arc(p.x*SZ + SZ/2, p.y*SZ + SZ/2, SZ/2 - 2, 0, 2*Math.PI);
    ctx.fill();
  });

  // update panel
  document.getElementById('p0').textContent = `(${p0.x}, ${p0.y})`;
  document.getElementById('p1').textContent = `(${p1.x}, ${p1.y})`;
  document.getElementById('count').textContent = pts.length;
  const logEl = document.getElementById('log');
  logEl.innerHTML = log.map((s, i) =>
    fmt('step %i%: (%x%,%y%) err=%err%', { i: i, x: s.x, y: s.y, err: s.err })
  ).join('<br>');
}

// โ”€โ”€ Drag interaction โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let dragging = null;
function cellAt(e) {
  const r = canvas.getBoundingClientRect();
  const clientX = e.touches ? e.touches[0].clientX : e.clientX;
  const clientY = e.touches ? e.touches[0].clientY : e.clientY;
  const x = Math.floor((clientX - r.left) / SZ);
  const y = Math.floor((clientY - r.top) / SZ);
  return { x: Math.max(0, Math.min(COLS-1, x)), y: Math.max(0, Math.min(ROWS-1, y)) };
}
function nearestPoint(c) {
  const d0 = Math.hypot(c.x-p0.x, c.y-p0.y);
  const d1 = Math.hypot(c.x-p1.x, c.y-p1.y);
  return d0 <= d1 ? 'p0' : 'p1';
}
canvas.addEventListener('mousedown', e => { dragging = nearestPoint(cellAt(e)); });
canvas.addEventListener('mousemove', e => {
  if (!dragging) return;
  const c = cellAt(e);
  if (dragging === 'p0') p0 = c; else p1 = c;
  draw();
});
canvas.addEventListener('mouseup', () => { dragging = null; });
canvas.addEventListener('touchstart', e => { e.preventDefault(); dragging = nearestPoint(cellAt(e)); }, { passive: false });
canvas.addEventListener('touchmove', e => {
  e.preventDefault();
  if (!dragging) return;
  const c = cellAt(e);
  if (dragging === 'p0') p0 = c; else p1 = c;
  draw();
}, { passive: false });
canvas.addEventListener('touchend', () => { dragging = null; });

const toggleBtn = document.getElementById('toggle');
toggleBtn.addEventListener('click', () => {
  showNaive = !showNaive;
  toggleBtn.textContent = showNaive ? 'Hide naive float' : 'Show naive float';
  toggleBtn.classList.toggle('active', showNaive);
  draw();
});

draw();
// Self-test: verify Bresenham endpoints and pixel count for a known segment
(function selfTest() {
  const { pts } = bresenham(0, 0, 6, 4);
  console.assert(pts[0].x === 0 && pts[0].y === 0, 'start should be (0,0)');
  console.assert(pts[pts.length-1].x === 6 && pts[pts.length-1].y === 4, 'end should be (6,4)');
  console.assert(pts.length === 7, 'dx=6 means 7 pixels for (0,0)->(6,4)');
  // Verify no float variables are used: all err, dx, dy are integers
  const { pts: pts2 } = bresenham(0, 0, 0, 5);
  console.assert(pts2.length === 6, 'vertical line (0,0)-(0,5) = 6 pixels');
  console.log('Bresenham self-test: all assertions passed');
})();
Result
Console

Watch how the algorithm never revisits a column: it advances exactly one step in x each iteration, updating y only when the accumulated error demands it. The error variable is the heart of the trick โ€” it accumulates the slope and discharges in whole-pixel steps, keeping everything in the integer domain. Compare the Bresenham and naive float columns on the side panel: they agree on which pixels to light, but one does it with a single integer add per step.

The Real Complexity

How fast can you possibly draw a line on a pixel grid?

  • Lower bound: you must visit at least ฮ”x pixels (one per column, for a line with horizontal extent ฮ”x). Any correct algorithm is ฮฉ(n).
  • Bresenham: exactly ฮ”x iterations, each doing two integer additions and one comparison. Total work: O(n)O(n). It matches the lower bound.
  • Status: solved โ€” the algorithm is provably optimal in the number of arithmetic operations needed to rasterize a line segment under the standard pixel-grid model (Bresenham, 1965).

The deeper insight is what made it fast. The naive approach computes y = round(x * dy/dx) at every step โ€” requiring a multiplication and a division. Bresenham noticed that consecutive y-values differ by at most 1. So he replaced the exact computation with an incremental error accumulator:

error = 2*dy - dx
for each x from x0 to x1:
    plot(x, y)
    if error > 0:
        y += 1
        error -= 2*dx
    error += 2*dy

Every variable stays an integer. The multiplications by 2 are just left-shifts. On 1960s hardware โ€” and on modern CPUs where integer ops are faster than floating-point โ€” this is as lean as it gets.

Bresenham later generalized the same idea to circles and ellipses (the midpoint circle algorithm), and the error-accumulator pattern appears throughout computational geometry whenever you need to walk a curve on a grid efficiently. See also sorting lower bounds for another example of proving an algorithm optimal by matching a lower bound.

Where It Matters

"Convert a continuous line into discrete steps with no fractions" is a problem that appears everywhere coordinates meet a grid:

  • GPU rasterization pipelines: every triangle that reaches your screen is broken into horizontal spans using a variant of Bresenham's incremental method. The scan-line fill algorithm is a direct descendant.
  • Font rendering: TrueType and PostScript outlines are curved, but they are drawn onto a pixel grid. Rasterizers use Bresenham-style stepping along Bรฉzier curves to decide which pixels fall inside a glyph.
  • CNC machining and 3-D printing: a CNC mill moves a cutter from point A to point B in discrete motor steps. The stepper-motor controller runs a Bresenham variant to distribute horizontal and vertical steps evenly along the path โ€” exactly the same problem, just with motors instead of pixels.
  • Robotics path planning: differential-drive robots that step left/right motors independently use Bresenham to approximate a straight trajectory on a discrete step grid.
  • Medical imaging: drawing lines on CT or MRI voxel grids to measure distances, segment regions, or trace vessel centerlines relies on 3-D generalizations of the algorithm.

The unifying idea is incremental integer arithmetic: whenever you need to walk a geometric path across a discrete grid without accumulating floating-point error, you reach for the pattern Bresenham identified in 1962.

Conclusion

Bresenham's algorithm is a small masterpiece of algorithmic thinking: it took a problem that felt like it needed floating-point arithmetic, found the right invariant (the accumulated error), and reduced the whole computation to a single integer addition per pixel.

It is O(n)O(n) and provably optimal โ€” you cannot rasterize a line in fewer operations. It was fast on the hardware of 1962, and it is still the foundation of rasterization pipelines inside every GPU shipping today.

The lesson is not that integer arithmetic is always better. It is that the right abstraction โ€” tracking error instead of recomputing exact position โ€” can eliminate an entire class of expensive operations. See closest pair of points for another case where the right geometric insight collapses the apparent complexity.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bresenham/Content licensed under CC BY-NC 4.0.