Bresenham’s line algorithm is an algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics. An extension to the original algorithm may be used for drawing circles.
While algorithms such as Wu’s algorithm are also frequently used in modern computer graphics because they can support antialiasing, the speed and simplicity of Bresenham’s line algorithm means that it is still important. The algorithm is used in hardware such as plotters and in the graphics chips of modern graphics cards. It can also be found in many software graphics libraries. Because the algorithm is very simple, it is often implemented in either the firmware or the graphics hardware of modern graphics cards.
The label “Bresenham” is used today for a family of algorithms extending or modifying Bresenham’s original algorithm.
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.
Bresenham’s algorithm was later extended to produce circles, the resulting algorithm being sometimes known as either Bresenham’s circle algorithm or midpoint circle algorithm.
Here is my implementation of Bresenham’s line algorithm by C++ and DirectX in 2012:
void DrawLine(D2D1_POINT_2F start, D2D1_POINT_2F end, int color = 0, int stroke = 5, int alpha = 255)
int x0 = (int)start.x, y0 = (int)start.y, x1 = (int)end.x, y1 = (int)end.y;
int dx = abs(x1 - x0), dy = abs(y1 - y0);
int sx = (x0 < x1) ? 1 : -1, sy = (y0 < y1) ? 1 : -1;
int err = dx - dy;
SetColor(y0, x0, color, stroke);
if (alpha != 255) SetAlpha(y0, x0, alpha, stroke);
if (x0 == x1 && y0 == y1) return;
int e2 = (err << 1);
if (e2 > -dy)
err -= dy;
x0 += sx;
if (e2 < dx)
err += dx;
y0 += sy;