Algorithm for computer control of a digital plotter
J. E. Bresenham
Bresenham's line drawing algorithm is a fast, high quality line rasterization
algorithm which is still the basis for most (aliased) line drawing today. The
paper, while originally written to describe how to control a particular plotter,
is uniquely suited to rasterizing lines for display on a pixel grid.
Lines drawn with Bresenham's algorithm must begin and end at integer pixel
coordinates, though one can round or truncate the fractional part. In order to
avoid multiplication or division in the algorithm's inner loop,
The algorithm works by scanning along the long axis of the line, moving along
the short axis when the error along that axis exceeds 0.5px. Because error
accumulates linearly, this can be achieved by simply adding the per-pixel
error (equal to (short axis/long axis)) until it exceeds 0.5, then incrementing
the position along the short axis and subtracting 1 from the error accumulator.
As this requires nothing but addition, it is very fast, particularly on the
older CPUs used in Bresenham's time. Modern graphics systems will often use Wu's
line-drawing algorithm instead, as it produces antialiased lines, taking
sub-pixel coverage into account. Bresenham himself extended this algorithm to
produce Bresenham's circle algorithm. The principles behind the algorithm have
also been used to rasterize other shapes, including Bézier curves.