The classic algorithm for drawing a line on a
raster display. Bresenham's
Algorithm uses no
division or multiplication, and thus is very fast.
First, take the
major axis of the line - that is, the axis along which it is longer. The line's length along this axis becomes the "
denominator" (call it d). The length along the other axis (the
minor axis) is the "
numerator increment" (call it i). If the line is equally long along each axis, it doesn't matter which you call the
major axis
There are now 8 cases: the line can either have a start point at the top or at the bottom, and at either the left or the right. Additionally, it can have the x axis or the y axis as the
major axis. To simplify, switch the endpoints so that the line starts at the top - this reduces the number of cases to four.
Notes:
The minor coordinate is the
coordinate along the minor axis; the major coordinate is the coordinate along the major axis.
For this description, X is the major axis, and the line starts at the left and goes right. The other cases are a matter of replacing increment with decrement at certain
bolded locations
The Algorithm:
Start a counter for the "numerator" at 0 (call it n).
Now loop along the major axis.
At each step, increment the major coodinate.
Add i to n.
If n is greater than d, subtract d from n. Then increment the coordinate along the minor axis.
The reason why it works is that it
pretends to do division. N is like the numerator of a fraction representing error. As the difference between the pixel location and the actual line location grows, the
error term grows. When it gets above one pixel (n > d, so n / d > 1), the algorithm moves down one pixel, and the error term is corrected.
There's a variant of Bresenham's algorithm to draw
arcs and circles; the major
difference is that the error term isn't incremented by one, it's added to in some more complex fashion (I don't know it off the top of my head).
Update: I did define i - it's the "numerator increment". My description may be different from the one in your
computer graphics text book - that's because it's based on one from "
Tricks Of The Game Programming Gurus". It works the same, tho.