Bresenham's Algorithm

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.

Bresenham's algorithm is the algorithm almost universally used to plot a straight line on a raster [i.e. a pixel-based display, as opposed to a vector display]. It does not use the computationally-expensive operations of multiplication or division, in fact it does not even use floating-point variables, only integers. It is simple, and before optimisations it corresponds directly with a method any rational person would use to do the same thing. With a little work, it can be used with sub-pixel accuracy, and anti-aliasing. This algorithm has also inspired other algorithms for drawing circles and ellipses using only integer arithmetic.

Let's start with how a person would plot a straight line on graph paper. Imagine drawing a line from the point (0, 0) (positive x-axis pointing to the right, positive y-axis pointing up) to point (8, 3). [Any endpoint (x, y) could be chosen, for now with the restrictions that x ≥ y ≥ 0 - i.e. the line must make an angle of between 0 and 45 degrees inclusive anticlockwise from the positive-x direction. These restrictions help keep the essence of the algorithm clear, generalisations to cover every other possible endpoint are discussed later.] The boxes in the diagram below represent the pixels of a raster display, the stars represent the line to be drawn, the 'O's represent the centres of the pixels.

+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
|  O  |  O  |  O  |  O  |  O  |  O  |  O  |  O  | *O  |
|     |     |     |     |     |     |     |    ***    |
|     |     |     |     |     |     |     |  ** |     |
+-----+-----+-----+-----+-----+-----+-----***---+-----+
|     |     |     |     |     |     |  ***|     |     |
|     |     |     |     |     |     |**   |     |     |
|  O  |  O  |  O  |  O  |  O  |  O***  O  |  O  |  O  |
|     |     |     |     |     |***  |     |     |     |
|     |     |     |     |    **     |     |     |     |
+-----+-----+-----+-----+-***-+-----+-----+-----+-----+
|     |     |     |     **    |     |     |     |     |
|     |     |     |  ***|     |     |     |     |     |
|  O  |  O  |  O  ***O  |  O  |  O  |  O  |  O  |  O  |
|     |     |   **|     |     |     |     |     |     |
|     |     |***  |     |     |     |     |     |     |
+-----+---***-----+-----+-----+-----+-----+-----+-----+
|     | **  |     |     |     |     |     |     |     |
|    ***    |     |     |     |     |     |     |     |
|  O* |  O  |  O  |  O  |  O  |  O  |  O  |  O  |  O  |
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+

The first thing of note is that the line is drawn from the centres of the pixels on either end. In some cases, this is not the desired behaviour - if coordinates are calculated to a greater precision than pixel-resolution, a particular line should perhaps be drawn from near a corner of one pixel to the middle of the edge of another pixel. Those cases are discussed further down in the writeup, but for now concentrate on drawing lines from the middle of pixels.

The next decision that is made, is made almost without thought, but it is a decision that influences the shape of the algorithm and should be pointed out. A person will generally decide to plot exactly one pixel in each column. If there were a column without a pixel, the line would look broken. If there were one pixel in some columns but two pixels in other columns, the line would look jagged, or of uneven width. So, the most visually pleasing thin line has one pixel set per column.

Starting at the leftmost column, we start the line in the exact middle of the bottom pixel. That pixel obviously needs to be set.

The next column over, the line has risen; by (y/x) [in this case, 3/8], to be precise. This is less than a half, so the line is closer to the lowest pixel than the next one up. The bottom pixel in the second column is set.

In the third column, the line has risen again, by another (y/x) [total, in this case, 3/4]. It has moved vertically more than half a pixel, so it is closer to the centre of the pixel above the bottom one; so, the pixel above is set.

Each column is considered in the same way, and one pixel from each column is chosen to be set.

In the fifth column, the line goes exactly halfway between the pixels. A choice must be made: which of the two to fill? A person would just choose one without thinking and not worry about it, but for an algorithm there must be a well-defined procedure. More on this later.

So, the first attempt to make an algorithm would look like this. Let height be a real-valued [floating-point] variable [the distance from the line to the bottom edge of the bottom pixel in the middle of a column], intialise it to 0.5. Let n be an integer variable [the number of the column currently being worked on], initialised to 0. Plot the pixel (n, floor(height)). Increment n. Add (y / x) to height. Plot the pixel (n, floor(height)), loop until n = x.

In pseudo-code:
real height := 0.5
integer n := 0
while (n ≤ x)
  plot (n, floor(height))
  n := (n + 1)
  height := (height + (y / x))
end while

With such a logical procedure, you almost forget there's a choice that has been made [which of the two pixels to plot in the fifth column from the example]. If this algorithm were to be used to draw that line, the upper of the two pixels will be plotted. On the fifth iteration through the loop, height contains 0.5 [from the initialisation] + ((3/8) * 4) [incremented by 3/8 each of 4 previous passes through the loop] = 2.0 exactly. If height were initialised to just a tiny bit lower than 0.5 [or if rounding errors produce the same effect], then the lower of the two pixels is set - the smallest error could cause the floor function to round down to 1 rather than 2.

The first refinement is to get rid of the pesky floating-point variable, height [and the potential rounding errors always present when dealing with floating-point values]. By examining the code, it is clear to see that it is initialised with the value 0.5 and the only modification to it is increments of (y / x). This means that height can always be expressed as a fraction (because x is an integer), and further, it can always be expressed as an integer divided by the lowest common multiple of 2 and x. Let height1 be (height * 2 * x) [guaranteed to be an integer, whether x is odd or even], and the code can be rewritten:
integer height1 := x
integer n := 0
while (n ≤ x)
  plot (n, floor(height1 / (2 * x)))
  n := (n + 1)
  height1 := (height1 + (2 * y))
end while

Next, the division inside the loop can be eliminated. A precondition for the algorithm is (x ≥ y), so adding (2 * y) to height1 each iteration will either leave floor(height1 / (2 * x)) unchanged or will increment it by 1. Let o be floor(height1 / (2 * x)) [so that o is either unaffected or incremented by 1 each iteration], and let i1 be (height1 mod (2 * x)) [or (height1 - (2 * x * o))]. This gives the code:
integer o := 0
integer i1 := x
integer n := 0
while (n ≤ x)
  plot (n, o)
  n := (n + 1)
  i1 := (i1 + (2 * y))
  if (i1 ≥ (2 * x)) then
    i1 := (i1 - (2 * x))
    o := (o + 1)
  end if
end while

It is easy to see now that i1 either starts out as an odd number, and remains an odd number forever, or it starts out an even number and remains an even number forever [it is only ever modified by having an even number added to or subtracted from it]. Since the only other expression involving i1 involves comparing it with an even number (2 * x), it really doesn't matter if it starts out as an even number or the odd number one greater. Let i be floor(i1 / 2), and you get:
integer o := 0
integer i := floor(x / 2)
integer n := 0
while (n ≤ x)
  plot (n, o)
  n := (n + 1)
  i := (i + y)
  if (i ≥ x) then
    i := (i - x)
    o := (o + 1)
  end if
end while

But wait - there's still one division operation. Since it is in the expression floor(x / 2), an arithmetic shift right can be used (or even a logic shift right, since x is nonnegative). And since it's in the initialisation rather than the loop, it only gets executed once per line rather than once per pixel.

To plot a line between 45 degrees and 90 degrees, swap the x- and y- coordinates. To plot a line between 90° and 180°, invert the x-coordinate. To plot a line between 180° and 360°, invert the y-coordinate (or swap the endpoints). To plot a line somewhere other than the origin, add the offset of one endpoint to each of the coordinates before plotting.

That is Bresenham's Algorithm.

---

Returning to the issue of which pixel to set when the line goes exactly halfway between the pixels - in the algorithm described above, the pixel further from the origin gets set. This leads to the unfortunate conclusion that if an implementation were to choose to swap the endpoints rather than invert the y-coordinate in order to plot lines between 180° and 360°, the end result can look unbalanced. For instance, when plotting the square (0, 0) to (3, 6) to (9, 3) to (6, -3) back to (0, 0), inverting the y-coordinate (offset) where necessary would give:

   *
   ***
  *   **
  *     **
 *      *
 *      *
**     *
  **   *
    ***
      *

whereas swapping the endpoints would give:

   **
   * **
  *    **
  *      *
 *       *
 *      *
**      *
  **   *
    ** *
      *

Swapping the endpoints gives a visually asymmetrical shape, therefore, it is generally considered a better option to invert the y-coordinate offset to get lines between 180° and 360°.

If, for some reason, it would be preferable that the pixel nearer the start of the line be set rather than the pixel farther away, there are two options. First option, the endpoints could be swapped. Second option, the third pseudocode example could be used except with
if (i1 > (2 * x)) then
instead of
if (i1 ≥ (2 * x)) then

Setting the pixel nearer the start of the line with either of these modifications, the square example above would look like this:

   **
  *  **
  *    **
 *       *
 *       *
*       *
*       *
 **    *
   **  *
     **

This gives the same result as if the square had been plotted with the pixel further from the start set, and the lines were drawn in the opposite direction: (0, 0) to (6, -3) to (9, 3) to (3, 6) back to (0, 0). The square looks different, but is still symmetrical. In instances where it is possible to draw all polygons clockwise, or draw them all anticlockwise, without too much processing overhead, that is usually done so that identical shapes are drawn identically.

---

Finally, there is the matter of sub-pixel accuracy and anti-aliasing. The trick to sub-pixel accuracy is first to ensure that the centre of some sub-pixel is at the centre of a pixel [depending on how the sub-pixels line up with pixels, an even higher resolution may be required just for the purposes of drawing the line]. Then [assuming the line is between 0° and 45°], find out how far the line is from the bottom of the pixel halfway through the leftmost pixel - the units will be (1 pixel / (x * [number of subpixels per pixel])). Loop over pixels, not subpixels.

Reasonably good anti-aliasing can be accomplished by using i as a measure of how close the line gets to the centre of the pixel. (Actually, it measures how close the line comes to the centre of the pixel - as measured vertically when the line is closer to horizontal, and as measured horizontally when the line is closer to vertical.) The closer i1 is to x, the closer the line is to the centre of the pixel; therefore, the pixel should be darker and the neighbouring pixels should be affected very little. The further i1 is from x, the further the line is from the centre of the pixel, the pixel should be lightened by up to half the intensity and the neighbouring pixel on the appropriate side should be darkened by up to half the intensity. This is not a fully accurate anti-aliasing algorithm, but is good enough for many cases.