Bresenham's Line

The problem no one can avoid

Draw a line on paper and it goes exactly where you aim it. Draw a line on a raster grid and it cannot: a perfectly straight path between two points almost never passes cleanly through a column of pixel centres, so the display must choose, for each column it crosses, which row gets the lit pixel. Get that choice wrong and the line looks lumpy; get it right and the staircase is as even as the grid allows, which is the best any algorithm can promise.

In 1962, Jack Bresenham was a programmer at IBM on a cooperative placement with General Motors, working with pen plotters and early display hardware. He was trying to solve exactly this routing problem, and the solution he found was published in the IBM Systems Journal in 1965. The paper is short and entirely devoid of floating-point arithmetic, which is the point: the algorithm decides which pixel to light using nothing but integer addition and subtraction, plus one comparison. On the hardware of the early 1960s, a division or a multiplication could cost many times what an addition did. Bresenham's method avoided both entirely, and that is why it survived.

How the decision is made

Think of drawing a line from pixel (x₀, y₀) to pixel (x₁, y₁), where the slope is shallow — less than 45 degrees, so the line moves more in x than in y. As the algorithm steps one column to the right, it must decide whether to keep the same row or move one row up. The true line sits somewhere between those two options, and the question is simply which pixel centre it is closer to.

Bresenham reformulates the question as an error term — a running account of how far the ideal line has drifted from the centre of the pixel currently being drawn. Before each step the algorithm adds the line's rise to this accumulator. If the accumulated error exceeds half the line's run, the pixel moves up a row and the run is subtracted from the error to bring it back. The accumulator never holds a fraction; it is scaled at the start so that the half-run threshold is also an integer. The entire inner loop is: add, compare, conditionally subtract and increment, step. No division, no rounding, no floating-point register touched.

The error term is the insight. It is not approximating the line; it is tracking the exact sub-pixel position of the ideal line at each column, encoded as a scaled integer. The decision it makes — stay or step — is always the decision that keeps the drawn staircase closest to the true geometry. A formal proof of this optimality was given in later analyses of the algorithm, but the intuition is plain from the construction: the error term measures the real gap and the threshold is exactly the midpoint between the two candidate pixels.

The original paper handled lines in the first octant — positive slope, shallower than 45 degrees. Extension to all eight octants is mechanical: swap x and y for steep lines, negate increments for negative slope. Every real implementation carries this generalisation, and the core arithmetic stays identical across all cases.

Get that choice wrong and the line looks lumpy; get it right and the staircase is as even as the grid allows, which is the best any algorithm can promise.

From the plotter to every screen

Bresenham's algorithm was designed for a pen plotter, a device that moves a physical instrument in discrete steps. The transfer to raster displays was immediate and obvious: a pixel is just a discrete step that lights up instead of depositing ink. By the mid-1970s, when framebuffers became a practical component of graphics systems — Richard Shoup's SuperPaint system at Xerox PARC being a landmark — hardware line-drawing engines were implementing the Bresenham approach in dedicated silicon because its integer-only nature mapped directly to digital logic with no conversion overhead.

The algorithm also generalises beyond straight lines. Bresenham published a companion paper in 1977 on circle drawing that uses the same accumulated-error principle: step around the arc in one coordinate at a time, maintain an integer error term, and decide whether to step in the second coordinate based on whether the ideal circle has crossed the midpoint between candidates. The mechanism is structurally identical to the line algorithm, which is why it is sometimes called the midpoint circle algorithm in textbook treatments that derive it from the more general midpoint formulation. The midpoint perspective — choosing the pixel whose centre lies closer to the ideal curve — was made fully explicit by researchers building on Bresenham's framework in the 1970s and 1980s.

Understanding why the staircase is unavoidable in the first place requires only the sampling argument: a raster grid is a discrete measurement system, and a continuous line mapped onto it loses all information about where exactly it fell between pixel centres. Bresenham's algorithm does not eliminate the staircase; it produces the most faithful staircase possible given the grid. Softening that staircase is a separate problem — anti-aliasing — which works by lighting neighbouring pixels at partial intensity rather than making a binary choice, at the cost of more arithmetic and a blurred appearance at low resolution.

Why it still matters

Modern GPUs rasterise lines in hardware at rates that make the question of integer-versus-floating-point seem almost quaint, and the rasterisation pipelines in OpenGL and similar APIs follow specifications that describe line coverage in terms of a diamond-exit rule intended to avoid double-drawing shared pixels between adjoining primitives. These rules are more elaborate than Bresenham's original, but the underlying geometry — mapping a continuous line to a discrete grid by tracking a sub-pixel error — is the same idea.

What keeps Bresenham's algorithm relevant at the implementation level is embedded systems: microcontrollers driving small monochrome displays, CNC machines interpolating tool paths, laser cutters stepping galvo mirrors. In all of these, hardware multiplication may be absent or slow, memory is measured in kilobytes, and an algorithm that needs only an accumulator and a comparator is genuinely the right choice. Jack Bresenham's original paper, republished in the ACM digital library, is still cited in embedded graphics literature more than six decades after it was written.

The deeper lesson is about the relationship between geometry and its representation. A line in Euclidean space is a locus of points satisfying a linear equation — infinitely thin, infinitely precise. A line on a grid is a sequence of cells, and the question of which cells belong to it is genuinely a question of policy as much as mathematics. Bresenham's answer — track the error, stay closest to the ideal — is one principled answer, and its economy of means is why no one has substantially replaced it at the level of the pixel.