Bresenham's line algorithm (1962)

Bresenham's line algorithm decides which points of a grid a machine should step through to draw a straight line, using only whole numbers. Jack Bresenham wrote it at IBM in 1962 for a pen plotter and published it in 1965 in the IBM Systems Journal as "Algorithm for computer control of a digital plotter".^1, 2 On a screen the grid points are pixels, and the same rule picks which pixels to fill.²

The problem

The plotter in Bresenham's paper answers each electrical pulse with one of eight moves: one step left, right, up or down, or one step along a diagonal. In his words, "the plotter can move linearly from a point on a mesh to any adjacent point on the mesh". A drawing is given as points on that mesh, joined by straight segments.¹

A segment that is not horizontal, vertical or at 45 degrees can only be drawn as a staircase of these moves, and before every step the computer must choose the next one. Bresenham's rule is to take, each time, "the mesh point nearest the desired line segment".¹

How it works

Take a line from D1 to D2 that rises less steeply than 45 degrees, the paper's "first octant". Let Δa be the number of mesh steps across and Δb the number up. Every move is then either one step across (M1) or one step diagonally across and up (M2).¹ The program keeps a single whole number, the decision value ∇:

1. Start with ∇ = 2Δb − Δa.
2. If ∇ is negative, move one step across and add 2Δb.
3. Otherwise, move diagonally and add 2Δb − 2Δa.
4. Repeat until the pen has made Δa moves.

Bresenham shows that ∇ always has the same sign as the difference between the distances from the line to the two possible next points, so its sign alone tells which point is nearer.¹ Lines in the other seven directions are handled by swapping the axes or reversing the direction.²

Inside the loop there is only addition, subtraction and a comparison. The algorithm, the paper says, "may be programmed without multiplication or division instructions and is efficient with respect to speed of execution and memory utilization".¹ A 1962 description of the program states that 333 core memory locations were enough.³

New drawing

The machines

In an account from 2001, Bresenham said he was working in the computation lab at IBM's San Jose development lab, where "a Calcomp plotter had been attached to an IBM 1401 via the 1407 typewriter console", and that the algorithm was in production use by the summer of 1962.² The volunteers who restore IBM 1401 computers at the Computer History Museum have since gathered 1962 documents. One describes "an IBM 1401 program (used to control an IBM 1627)", the name under which IBM sold CalComp's drum plotters; Robert Garner reports that the lab used the 11-inch CalComp 565. The same page lists what is still uncertain, among it whether the program listing that survives is complete.³

Still a plotter problem

A pen plotter is still told to draw straight segments between points, in a language such as HP-GL, and the machine has to turn each one into movement. Every drawing in Olof Broström's Unverified Air at JAEV is stored as such a file for a pen plotter, in black, red and blue ink.⁴ See also Plotter art and Plotter path optimisation.

Amit Patel of Red Blob Games, whose copy of Bresenham's paper we first used, pointed us in October 2026 to the open-access version from the ACM (source 5).