janmr blog

Bresenham's Line Algorithm

In 1965 Jack Elton Bresenham published the paper Algorithm for computer control of a digital plotter in the IBM Systems Journal, volume 4, number 1. It explained how a line could be approximated on an integer grid. The algorithm is still used today as a rasterization technique for rendering lines on video displays or printers. As Bresenham's paper suggests, however, it was originally devised for a plotter, capable of moving from one grid point to one of the adjacent eight grid points.

We consider drawing a line from to on an integer grid by choosing the points that lie close to the true line. We also assume that and . The method is easily extended to the general case with arbitrary starting and ending points.

The line has the form

and we aim to sample the line at the grid points with for and .

We now associate with each step an error term,

The interpretation of this error term is important: It expresses the difference at between the line's true -coordinate, , and the midpoint between the previously chosen -coordinate, , and its successor, . The factor is there to make all quantities integral. The sign of is thus crucial:

  • If then lies closest to the line (it is a tie for ).
  • If then should be chosen.

Note how the magnitude of also tells exactly how far from the true line the chosen grid point is. It is straightforward to show that for .

Figure 1. Given that the previous point is at , the dashed lines indicate the two extreme cases for the line being approximated. will be negative if the line goes through the red area and positive if it goes through the blue area.

To determine the 's we start with the base case:

For we get

We now split into the two cases for and get

for .

These expressions determine all the 's which, in turn, determines all the 's.