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.
For a pdf version of these notes look here.
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:
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
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
Consider the following example, which attempts to draw a line from to in screen space,
Bresenham's algorithm calculates the new as
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
If we multiply through by , we again obtain an approximation for that, at least, does not require division.
If we address the example, which attempts to draw a line from to in screen space.
and if we let , then we have that
Thus the integer version for Bresenham's algorithm with arbitrary
endpoints is constructed as follows:
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
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
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.
Return to
the Graphics Notes Home Page
Return
to the Geometric Modeling Notes Home Page
Return
to the UC Davis Visualization and Graphics Group Home Page
This document maintained by Ken Joy
All contents copyright (c) 1996, 1997, 1998,
1999
Computer Science Department
University of California, Davis
All rights reserved.