The Line Carries an Error Ledger

A line on a screen is a negotiation.

The mathematical line can pass between pixels. The raster device cannot. It can only light cells, one after another, while trying not to drift too far from the ideal segment.

Bresenham’s line algorithm is the clean version of that negotiation. It keeps an integer error term, emits one adjacent pixel at a time, and updates the error by addition. No floating slope needs to be recomputed inside the loop.

Jack Bresenham’s 1965 IBM Systems Journal paper was written for a digital plotter whose head could move to any of eight neighboring mesh points. The paper gives an algorithm for controlling that plotter efficiently, with no multiplication or division in the step loop.¹ That hardware setting is old. The idea is still modern: carry the rounding debt explicitly.

The Midpoint Question

Start with the easy octant:

x increases by 1 every step
0 <= dy <= dx
y either stays put or increases by 1

At column x + 1, there are two candidates:

E   = (x + 1, y)
NE  = (x + 1, y + 1)

The real line crosses somewhere between them. The midpoint test asks whether the true line is above or below the halfway mark between E and NE. Instead of evaluating the line equation with fractions every time, scale the decision by 2*dx and keep an integer:

D0 = 2*dy - dx

if D >= 0:
    choose NE
    D += 2*(dy - dx)
else:
    choose E
    D += 2*dy

The recurrence is doing bookkeeping. If the line has been running above the chosen pixels, the debt grows until the next step must move in y. If the line has been running below, the debt shrinks.

For the other seven octants, swap axes and signs. The version in the lab uses the common symmetric form:

dx = abs(x1 - x0)
dy = abs(y1 - y0)
sx = sign(x1 - x0)
sy = sign(y1 - y0)
err = dx - dy

repeat:
    emit (x, y)
    e2 = 2*err
    if e2 > -dy:
        err -= dy
        x += sx
    if e2 < dx:
        err += dx
        y += sy

That code looks almost too small, but it is carrying the octant cases in sx, sy, and the two comparisons.

Lab: Watch The Debt Move

The lab draws the ideal real line in orange and the emitted raster pixels in blue. The red pixel is the current step. The error plot shows the minor-axis deviation staying inside half a cell. The ledger shows the integer err, the doubled decision variable 2e, and whether the next pulse moves in x, y, or both.

Segment shallow down steep up backward climb diagonal vertical Step

12

The lab uses integer endpoints on a small pixel grid. It visualizes aliased line rasterization, not antialiasing, coverage masks, joins, caps, clipping, or subpixel stroke rules.

What The Audit Checks

The exported Node audit runs five line segments: shallow, steep, backward, diagonal, and vertical. For each one it verifies:

the first pixel is the requested start
the final pixel is the requested end
successive pixels are adjacent on the 8-neighbor grid
the point count is max(abs(dx), abs(dy)) + 1
the decision trace stores integer err and 2*err values
the minor-axis deviation stays within half a cell

For the default segment (1,13) -> (25,5), the script reports:

points:      25
dx / dy:     24 / 8
max error:   0.333
audit:       pass

The vertical case is included for a boring reason: boring cases are where generalized octant code often leaks assumptions. The backward case forces a negative x direction. The steep case swaps the major axis. The exported audit reports 33 named checks: 30 segment-local invariants plus three cross-scenario guardrails for the shallow, vertical, and backward cases.

To reproduce those cases from the repository root:

node - <<'NODE'
const lab = require("./assets/js/bresenham-line-lab.js");
const EXPECTED_CASE_KEYS = [
  "shallow:1,13->25,5:24/8:1/-1:25",
  "steep:4,15->12,1:8/14:1/-1:15",
  "backward:25,3->3,15:22/12:-1/1:23",
  "diagonal:2,3->22,15:20/12:1/1:21",
  "vertical:14,1->14,16:0/15:0/1:16"
];
const EXPECTED_CASE_ROWS = [
  "shallow:1,13->25,5:dx=24:dy=8:sx=1:sy=-1:points=25/25:maxError=0.333:checks=6/6:passed=true",
  "steep:4,15->12,1:dx=8:dy=14:sx=1:sy=-1:points=15/15:maxError=0.429:checks=6/6:passed=true",
  "backward:25,3->3,15:dx=22:dy=12:sx=-1:sy=1:points=23/23:maxError=0.455:checks=6/6:passed=true",
  "diagonal:2,3->22,15:dx=20:dy=12:sx=1:sy=1:points=21/21:maxError=0.400:checks=6/6:passed=true",
  "vertical:14,1->14,16:dx=0:dy=15:sx=0:sy=1:points=16/16:maxError=0.000:checks=6/6:passed=true"
];
const EXPECTED_LOCAL_CHECKS = [
  { name: "starts at requested endpoint", ok: true },
  { name: "ends at requested endpoint", ok: true },
  { name: "one adjacent move per pulse", ok: true },
  { name: "point count is max delta + 1", ok: true },
  { name: "integer decision state", ok: true },
  { name: "half-cell error bound", ok: true }
];
const EXPECTED_CRITICAL_CHECKS = [
  { name: "shallow line advances x on step 1", ok: true },
  { name: "vertical x coordinate stays fixed", ok: true },
  { name: "backward scenario exercises negative x direction", ok: true }
];
const EXPECTED_CASES = EXPECTED_CASE_KEYS.length;
const EXPECTED_CHECKS =
  EXPECTED_CASES * EXPECTED_LOCAL_CHECKS.length +
  EXPECTED_CRITICAL_CHECKS.length;

function sameList(left, right) {
  return left.length === right.length &&
    left.every((value, index) => value === right[index]);
}

function sameJson(left, right) {
  return JSON.stringify(left) === JSON.stringify(right);
}

function rowDrifts(actual, expected) {
  const count = Math.max(actual.length, expected.length);
  const drift = [];
  for (let index = 0; index < count; index += 1) {
    if (actual[index] !== expected[index]) {
      drift.push({ index, actual: actual[index], expected: expected[index] });
    }
  }
  return drift;
}

function auditShape(audit) {
  return {
    cases: audit.cases.map(
      (row) => `${row.scenario}:${row.x0},${row.y0}->${row.x1},${row.y1}:` +
        `${row.dx}/${row.dy}:${row.sx}/${row.sy}:${row.points}`
    ),
    caseRows: audit.cases.map(
      (row) => `${row.scenario}:${row.x0},${row.y0}->${row.x1},${row.y1}:` +
        `dx=${row.dx}:dy=${row.dy}:sx=${row.sx}:sy=${row.sy}:` +
        `points=${row.points}/${row.expectedPoints}:` +
        `maxError=${row.maxAxisError.toFixed(3)}:` +
        `checks=${row.passedChecks}/${row.totalChecks}:passed=${row.passed}`
    ),
    localChecksByCase: audit.cases.map(
      (row) => row.checks.map((check) => ({
        name: check.name,
        ok: check.ok
      }))
    ),
    criticalChecks: audit.criticalChecks.map((row) => ({
      name: row.name,
      ok: row.ok
    }))
  };
}

const audit = lab.auditBresenhamLineLab();
const shape = auditShape(audit);
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const failedCriticalChecks = audit.criticalChecks.filter((row) => !row.ok);
const caseRowDrifts = rowDrifts(shape.caseRows, EXPECTED_CASE_ROWS);
const shapeErrors = [
  sameList(shape.cases, EXPECTED_CASE_KEYS) ? null : "cases",
  caseRowDrifts.length ? "caseRows" : null,
  shape.localChecksByCase.every((checks) => sameJson(checks, EXPECTED_LOCAL_CHECKS))
    ? null
    : "localChecksByCase",
  sameJson(shape.criticalChecks, EXPECTED_CRITICAL_CHECKS) ? null : "criticalChecks"
].filter(Boolean);
console.table(audit.cases.map((row) => ({
  scenario: row.scenario,
  dx: row.dx,
  dy: row.dy,
  points: `${row.points}/${row.expectedPoints}`,
  maxError: row.maxAxisError.toFixed(3),
  checks: `${row.passedChecks}/${row.totalChecks}`,
  passed: row.passed
})));
console.table(audit.criticalChecks.map((row) => ({
  check: row.name,
  passed: row.ok
})));
const summary =
  `${audit.passed}/${audit.total} cases and ` +
  `${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  shapeErrors.length ||
  audit.total !== EXPECTED_CASES ||
  audit.totalChecks !== EXPECTED_CHECKS ||
  failed.length ||
  failedCriticalChecks.length ||
  !audit.ok ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(JSON.stringify({
    summary,
    shapeErrors,
    shape,
    drifts: {
      caseRows: caseRowDrifts
    },
    failed,
    failedCriticalChecks,
    errors: audit.errors,
    expectedCases: EXPECTED_CASES,
    expectedChecks: EXPECTED_CHECKS,
    total: audit.total,
    totalChecks: audit.totalChecks
  }, null, 2));
}
console.log(summary);
NODE

Why This Is Not Just Rounding

You can draw a line by evaluating the real equation at every column and rounding. On modern hardware, that may be perfectly fine. But it hides the algorithmic shape.

Bresenham’s recurrence is not trying to rediscover the slope. It already knows the slope through dx and dy. The state variable only answers one local question:

has the accumulated rounding debt crossed the midpoint?

That is why the update is cheap. Each emitted pixel pays a fixed amount of debt or receives a fixed refund. In the first octant, choosing E adds 2*dy. Choosing NE adds 2*(dy-dx). The branch is a sign test.

The lesson generalizes beyond line drawing:

do not recompute the continuous object if a discrete error ledger is enough

You see the same flavor in incremental scan conversion, midpoint circle drawing, digital differential analyzers, and fixed-point timing loops. The object is continuous; the device is discrete; the algorithm survives by carrying the mismatch explicitly.

Where The Contract Ends

Bresenham chooses a one-pixel-wide aliased path. It does not know what a modern renderer means by a stroke. It does not compute pixel coverage. It does not antialias. It does not handle joins or caps. It does not decide whether a line endpoint should be inclusive in a graphics API’s fill convention.

Those are different contracts.

The small contract here is still valuable:

given integer endpoints,
emit a connected lattice path,
touch exactly one new major-axis position per pulse,
stay within half a cell of the ideal segment,
use only integer recurrence state in the loop

That is why the algorithm still feels sharp. It does not pretend pixels are real numbers. It keeps a ledger for the rounding error and pays it down one move at a time.

1. J. E. Bresenham, “Algorithm for computer control of a digital plotter”, IBM Systems Journal 4(1), 1965. A public PDF copy is hosted by Ohio State University Pressbooks: bresenham.pdf. ↩