Some version of some literature notes. To be TeXiFiEd
[ipdf/documents.git] / 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.

UCC git Repository :: git.ucc.asn.au