LitNotes/BresenhamLineDrawing

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