On-Line Computer Graphics Notes
BRESHENHAM'S ALGORITHM

Overview

The basic "line drawing" algorithm used in computer graphics is Bresenham's Algorithm. This algorithm was developed to draw lines on digital plotters, but has found wide-spread usage in computer graphics. The algorithm is fast - it can be implemented with integer calculations only - and very simple to describe.

Bresenham's Algorithm

Consider a line with initial point and terminal point in device space. If and , we define the driving axis ( DA) to be the -axis if , and the -axis if . The DA is used as the axis of control'' for the algorithm and is the axis of maximum movement. Within the main loop of the algorithm, the coordinate corresponding to the DA is incremented by one unit. The coordinate corresponding to the other axis (usually denoted the passive axis or PA) is only incremented as needed.

The best way to describe Bresenham's algorithm is to work through an example. Consider the following example, in which we wish to draw a line from to in device space.

Bresenham's algorithm begins with the point and illuminates'' that pixel. Since is the DA in this example, it then increments the coordinate by one. Rather than keeping track of the coordinate (which increases by , each time the increases by one), the algorithm keeps an error bound at each stage, which represents the negative of the distance from the point where the line exits the pixel to the top edge of the pixel (see the figure). This value is first set to , and is incremented by each time the coordinate is incremented by one. If becomes greater than zero, we know that the line has moved upwards one pixel, and that we must increment our coordinate and readjust the error to represent the distance from the top of the new pixel - which is done by subtracting one from .

The reader can examine the above illustration and the following table to see the complete operation of the algorithm on this example.

Assuming that the DA is the -axis, an algorithmic description of Bresenham's algorithm is as follows:

All algorithms presented in these notes assume that and are positive. If this is not the case, the algorithm is virtually the same except for the following:

• is calculated using .
• and are decremented (instead of incremented) by one if the sign of or is less than zero, respectively.

The Integer Bresenham's Algorithm

Bresenham's Algorithm, as given in the previous section, requires the use of floating point arithmetic to calculate the slope of the line and to evaluate the error term. We note that is initialized to

and is incremented by at each step. Since both and are integer quantities, we can convert to an all integer format by multiplying the operations through by . That is, we will consider the integer quantity , where is initialized to

and we will increment by at each step, and decrement it by when becomes positive.

Our example from the section above, which attempts to draw a line from to in screen space, can now be converted to an integer algorithm. Consider the figure and table below, where , and .

Thus the integer version of Bresenham's algorithm is constructed as follows:

Bresenham's Algorithm for Lines with Arbitrary Endpoints

Bresenham's algorithm, as described in the sections above, is limited by the fact that the lines to be drawn have endpoints with integer coordinates. In this section, we consider a version of Bresenham's algorithm for lines that have endpoints with real coordinates. The only problem to overcome is the initial setting of the error. Once this is done, the algorithm proceeds as before.

Consider a line with initial point and terminal point in device space, where we assume the points are not the same. To calculate the correct in this case, we refer to the following figure.

If we consider the lower-left-hand corner of the grid to be , then it is easily seen that the initial is

We now utilize this to modify Bresenham's algorithm accordingly.

Consider the following example, which attempts to draw a line from to in screen space,

Bresenham's algorithm calculates the new as

The algorithm begins with the point and then proceeds in exactly the same way as Bresenham's algorithm for lines having endpoints with integer coordinates.

The reader can examine the above illustration and the following table to see the complete operation of the algorithm on this example. In this case , and the lower left corner of the grid is .

Assuming that the DA is the -axis, the algorithmic description of Bresenham's algorithm for lines with arbitrary endpoints is as follows:

The Integer Bresenham's Algorithm for Lines with Arbitrary Endpoints

Bresenham's Algorithm, as given in the previous section, was adapted to lines that have endpoints with arbitrary real coordinates. This algorithm again requires the use of floating point arithmetic to calculate the slope of the line and to evaluate the error term. We note that is initialized to

and is incremented by at each step. However, we cannot do the same simplifications with this algorithm as we did with the integer algorithm above, since in this case both and are real - not integer.

If we multiply through by , we again obtain an approximation for that, at least, does not require division.

However, to bring this algorithm back to integer form we assume that our basic pixel element is no longer in size, but now it is in size, and utilize increments and decrements in the algorithm of and , respectively. The error term is first set to and the algorithm then proceeds as does the version with endpoints that have integer coordinates.

If we address the example, which attempts to draw a line from to in screen space.

and if we let , then we have that

and

and so we initialize the integer quantity , and the algorithm proceeds as follows:

Thus the integer version for Bresenham's algorithm with arbitrary endpoints is constructed as follows:

Specifying the Driving Axis

If is the driving axis, Bresenham's algorithm produces only one illuminated cell per column in the matrix of pixels. This feature allows the algorithm to be useful in the rasterization of polygons in image space. In this algorithm, we require only one illuminated pixel per row be produced - which is possible with Bresenham's algorithm by fixing the driving axis as the axis. This can be done by a simple change to the main loop of the algorithm.

Normally, within the main loop of the algorithm, the coordinate corresponding to the DA is incremented by one unit and the coordinate corresponding to the other axis need only be incremented occasionally. When we fix the driving axis, the coordinate on the DA is still incremented by one unit, however the coordinate on the other axis may be incremented several times. This is actually a simple change to the algorithm, and and can be implemented by replacing the statement

if
with
while
The algorithm now appears as follows (We note that we are using the non-integer form of the algorithm, which is clearer in its presentation. The conversion to the integer algorithm is straightforward.) We also note we have changed the algorithm to reflect that the axis is the driving axis. We note that , and that according to the following picture

we must consider two possible initial values for , one if (the left-hand illustration) and one if (the right-hand illustration). Referring to the illustration, we have either

in the first case, or

in the second. In general must be replaced by and by as the figure is drawn as if the lower-left-hand corner of the pixel is .

We also need to recognize that may be greater than zero immediately, as in the following figure. Therefore, we must move the illuminate'' step in our algorithm below the while'' statement. This will insure that we are at the correct boundary pixel for the trapezoid.

The algorithm now appears as follows:

This algorithm will continue to increment the value (and decrement ) as long as is greater than zero. It illuminates only one pixel per row on the line.

We are assuming that which is valid since we are only considering the non-horizontal edges of the trapezoids that we want to rasterize. It should also be mentioned that the above algorithm is written for the case where is positive. If , then and is never incremented. In this case, we have a vertical line, and the value will never need to be incremented. If , then we must decrement in the algorithm, and add to .

Summary

Bresenham's Algorithm is a fundamental algorithm in computer graphics. Its basic use it to draw lines on raster graphics devices, however it is useful as a driving engine for many other graphics routines.

This document maintained by Ken Joy