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.