Jack Bresenham and the Line Algorithm That Made Raster Graphics Efficient
Jack Bresenham transformed line drawing into an incremental integer decision process, giving plotters and raster displays an efficient way to approximate continuous geometry.
Digital graphics made a straight line into a discrete decision problem
Mathematical lines are continuous, but a digital plotter or raster display moves among discrete positions. In the early 1960s, Jack E. Bresenham confronted that mismatch while working at IBM’s San Jose laboratory with an IBM 1401 driving a Calcomp plotter.[3]
The engineering question was deceptively simple: as the device advances along its major axis, which neighboring position should it choose on the minor axis so the plotted path stays closest to the ideal line? A practical answer had to be fast on hardware where multiplication and division were expensive.
Bresenham reduced line drawing to incremental error
Bresenham’s 1965 IBM Systems Journal paper described an algorithm that updates a decision quantity as each plotter step is taken, selecting between neighboring candidate points according to accumulated error.[1]
The key was incremental computation. Once the first decision value is known, the next one can be obtained from the previous value with additions and subtractions rather than recomputing geometric distance from scratch.
Integer arithmetic fit the machines of the time
The modern significance of the algorithm is often summarized as ‘no floating point,’ but the historical point is broader: Bresenham shaped the computation around operations that were cheap and predictable on the IBM 1401-class environment. NIST still characterizes the algorithm as incrementing the long dimension while accumulating fractional slope.[2]
Eight possible plotter moves shaped the original formulation
The Calcomp plotter could step in a small set of directions. Computer History Museum discussions of early CAD note that Bresenham’s method arose specifically in this stepping-plotter context rather than in a modern framebuffer.[4]
That device constraint explains the algorithm’s local nature. Each step chooses a neighboring location, and the decision variable keeps the resulting chain near the ideal geometric line.
Symmetry extended one derivation across different slopes
A basic derivation can focus on a line in one octant, for example with a positive slope between zero and one. Coordinate swaps, sign changes, and endpoint handling extend the method to the remaining directions.
This was an important software-economy technique. Instead of designing a separate numerical method for every direction, an implementation can normalize the case, run one incremental recurrence, and map the result back.
Rasterization turns geometry into a controlled approximation
No finite pixel grid can reproduce an arbitrary continuous line exactly. The algorithm’s task is therefore not exact geometric identity but a consistent choice of discrete samples with bounded visual error.
The 1963 presentation preceded the famous journal publication
Archival material preserved by the IBM 1401 community records Bresenham’s recollection that the line routine was in use by 1962 and that he presented it at the 1963 ACM national conference before IBM Systems Journal published the paper in 1965.[3]
This chronology matters because calling it a ‘1965 algorithm’ can misleadingly imply that the idea began with the printed article. The journal paper is the canonical publication, while surviving notes and recollections place the implementation earlier.
Practice came before publication
The algorithm’s path from working plotter code to conference presentation to journal article is a reminder that software history often begins in deployed programs before it appears in the archival literature.
The algorithm became a template for incremental raster geometry
Bresenham later developed related incremental methods for circles, and the name became attached to a family of raster techniques. His later reflections discuss ambiguities and design choices that arise when the same geometric object can be rasterized in more than one reasonable way.[5]
The deeper pattern is reusable: maintain a compact error state, advance one discrete step, and update the state using cheap arithmetic.
Efficiency and determinism made hardware implementation attractive
An algorithm built from predictable integer operations is suitable not only for software but also for dedicated hardware and firmware. That portability across implementation layers helped the approach survive changes from plotters to raster displays and graphics processors.
Line drawing became a foundation for larger graphics systems
Wireframe CAD, vector displays, plotters, and early raster graphics all depended on reliable primitive generation. A fast line routine therefore affected far more than one visual element: polygons, grids, diagrams, and engineering drawings could all build on it.[4]
Later graphics hardware moved much of rasterization away from application software, but the problem Bresenham formalized remains present inside the pipeline: continuous primitives still have to be converted into discrete samples.
Why Bresenham’s algorithm remains a graphics milestone
Bresenham did not invent the mathematical line or the digital plotter. His contribution was an exceptionally economical mapping from continuous geometry to discrete device steps, expressed as an incremental recurrence suited to real machines.[1][2]
The Computer History Museum’s CAD discussions still identify it as a fundamental enabling technique.[4] Its durability comes from a characteristic shared by many great graphics algorithms: it converts an expensive geometric idea into a small local decision that can be repeated very quickly.
Works Cited
- 01
- 02
- 03IBM 1401 / Computer History Museum community archive — Jack Bresenham's Line Drawing Algorithm ibm1401.computerhistory.org
- 04Computer History Museum — Computer Aided Design Pioneer Workshop (2023) archive.computerhistory.org
- 05Ray Tracing News — Jack Bresenham recollections on line and circle algorithms realtimerendering.com
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead