(algorithm)
Definition: An efficient algorithm to render a line with pixels. The long dimension is incremented for each pixel, and the fractional slope is accumulated.
Note:
Bresenham discusses implementation issues and design choices, such as arise drawing lines beginning at either end point of a line or approximating a circle with a polygon, in
Jack Bresenham, Ambiguities in incremental line rastering, IEEE Computer Graphics and Applications, 7(5):31-43, May, 1987.
Author: PEB
An explanation.
Eugen Dedu's implementation of a Bresenham-based supercover line algorithm. It marks all the squares a line passes through, not just the least error squares. It may help with dithered lines or checking for obstacles.
Jack E. Bresenham, Algorithm for Computer Control of a Digital Plotter, IBM Systems Journal, 4(1):25-30, 1965.
Reprinted in Interactive Computer Graphics, Herbert Freeman ed., 1980, and Seminal Graphics: Pioneering Efforts That Shaped The Field, Rosalee Wolfe ed., ACM SIGGRAPH, 1998.
Historical Note
In November 2001 Jack E. Bresenham wrote, "I was working in the computation lab at IBM's San Jose development lab. A Calcomp plotter had been attached to an IBM 1401 via the 1407 typewriter console. [The algorithm] was in production use by summer 1962, possibly a month or so earlier. Programs in those days were freely exchanged among corporations so Calcomp (Jim Newland and Calvin Hefte) had copies. When I returned to Stanford in Fall 1962, I put a copy in the Stanford comp center library.
A description of the line drawing routine was accepted for presentation at the 1963 ACM national convention in Denver, Colorado. It was a year in which no proceedings were published, only the agenda of speakers and topics in an issue of Communications of the ACM. A person from the IBM Systems Journal asked me after I made my presentation if they could publish the paper. I happily agreed, and they printed it in 1965."
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 14 April 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "Bresenham's algorithm", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 April 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bresenham.html