On-Line Computer Graphics Notes


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.

pdficonsmall.gif For a pdf version of these notes look here.

Bresenham's Algorithm

Consider a line with initial point $ (x_1, y_1)$ and terminal point $ (x_2,y_2)$ in device space. If $ \Delta x\: = \: x_2 - x_1$ and $ \Delta y\: = \: y_2 - y_1$, we define the driving axis ( DA) to be the $ x$-axis if $ \vert \Delta x\vert \, \geq \, \vert \Delta y\vert$, and the $ y$-axis if $ \vert \Delta y\vert \, > \, \vert \Delta x\vert$. 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 $ (0,0)$ to $ (5,3)$ in device space.

\includegraphics {figures/breshenham-1}

Bresenham's algorithm begins with the point $ (0,0)$ and ``illuminates'' that pixel. Since $ x$ is the DA in this example, it then increments the $ x$ coordinate by one. Rather than keeping track of the $ y$ coordinate (which increases by $ m=\Delta y/ \Delta x$, each time the $ x$ increases by one), the algorithm keeps an error bound $ \epsilon$ 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 $ m-1$, and is incremented by $ m$ each time the $ x$ coordinate is incremented by one. If $ \epsilon$ becomes greater than zero, we know that the line has moved upwards one pixel, and that we must increment our $ y$ coordinate and readjust the error to represent the distance from the top of the new pixel - which is done by subtracting one from $ \epsilon$.

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

\begin{tabular}{ \vert r \vert r \vert ...
...inate pixel $(4,2)$} \\ [.5em]

Assuming that the DA is the $ x$-axis, an algorithmic description of Bresenham's algorithm is as follows:
\hbox{\hspace{1in}} \= ...
...f next} i \\
\> \> {\bf finish}

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

Ken Joy