Bresenham's line algorithm

From Free net encyclopedia

Bresenham's line algorithm is an algorithm that determines which points on a 2-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics.

1 The algorithm
2 Generalizing
3 Optimization
4 History
5 References
6 See also
7 External links

[edit]

The algorithm

Image:Bresenham.png The line is drawn between two points (x₀, y₀) and (x₁, y₁), where these pairs indicate column and row, respectively, increasing in the down and right directions. We will initially assume that our line goes down and to the right, and that the horizontal distance x₁-x₀ exceeds the vertical distance y₁-y₀ (that is, the line has a slope less than 1.) Our goal is, for each column x between x₀ and x₁, to identify the row y in that column which is closest to the line and plot a pixel at (x,y).

Now, how do we figure out which pixel is closest to the line for a given column? The general formula for the line between the two points is given by:

Since we know the column, x, the pixel's row, y, is given by rounding this quantity to the nearest integer:

However, explicitly calculating this value for each column, x, is silly; we need only note that y starts at y₀, and each time we add 1 to x, we add the fixed value (y₁-y₀)/(x₁-x₀), which we can precalculate, to the exact y. Moreover, since this is the slope of the line, by assumption it is between 0 and 1; in other words, after rounding, in each column we either use the same y as in the previous column, or we add one to it.

We can decide which of these to do by keeping track of an error value which denotes the vertical distance between the current y value and the exact y value of the line for the current x. Each time we increment x, we increase the error by the slope value above. Each time the error surpasses 0.5, the line has become closer to the next y value, so we add 1 to y, simultaneously decreasing the error by 1. The procedure looks like this, assuming plot(x,y) plots a point and abs takes absolute value:

Expressed in pseudo code, the naive implementation below uses comparatively expensive floating point arithmetic, but it can be easily tweaked (see optimization section) to use integer math:

 function line(x0, x1, y0, y1)
     int deltax := abs(x1 - x0)
     int deltay := abs(y1 - y0)
     real error := 0
     real deltaerr := deltay ÷ deltax
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         if error ≥ 0.5
             y := y + 1
             error := error - 1.0

[edit]

Generalizing

This first version only handles lines that descend to the right. We would of course like to be able to draw all lines. The first case is allowing us to draw lines that still slope downwards, but head in the opposite direction. This is a simple matter of swapping the initial points if x0 > x1. Trickier is determining how to draw lines that go up. To do this, we check if y₀ >= y₁; if so, we step y by -1 instead of 1. Lastly, We still need to generalize the algorithm to drawing lines in all directions. Up until now we have only been able to draw lines with a slope less than one. To be able to draw lines with a steeper slope, we take advantage of the fact that a steep line can be reflected across the line y=x to obtain a line with a small slope. The effect is to switch the x and y variables throughout, including switching the parameters to plot. The code looks like this:

 function line(x0, x1, y0, y1)
     boolean steep := abs(y1 - y0) > abs(x1 - x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     if x0 > x1 then
         swap(x0, x1)
         swap(y0, y1)
     int deltax := x1 - x0
     int deltay := abs(y1 - y0)
     real error := 0
     real deltaerr := deltay ÷ deltax
     int y := y0
     if y0 < y1 then ystep := 1 else ystep := -1
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error + deltaerr
         if error ≥ 0.5
             y := y + ystep
             error := error - 1.0

The function now handles all lines and implements the complete Bresenham's algorithm.

[edit]

Optimization

The problem with this approach is that computers operate relatively slowly on fractional numbers like error and deltaerr; moreover, error can accumulate over many floating-point additions. Working with integers will be both more accurate and faster. The trick we use is to multiply all the fractional numbers above by deltax, which enables us to express them as integers. The only problem remaining is the constant 0.5—to deal with this, we multiply both sides of the inequality by 2. The resulting multiplication by two can be implemented with a bit shift instead of a relatively expensive multiplication, further speeding up the algorithm. The new program looks like this:

 function line(x0, x1, y0, y1)
     boolean steep := abs(y1 - y0) > abs(x1 - x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     if x0 > x1 then
         swap(x0, x1)
         swap(y0, y1)
     int deltax := x1 - x0
     int deltay := abs(y1 - y0)
     int error := 0
     int y := y0
     if y0 < y1 then ystep := 1 else ystep := -1
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error + deltay
         if 2×error ≥ deltax
             y := y + ystep
             error := error - deltax

[edit]

History

The algorithm was developed by Jack E. Bresenham in 1962 at IBM. In 2001 Bresenham wrote:

"I was working in the computation lab at IBM's San Jose development lab. A Calcomp plotter had been attached to an IBM 1401 via the 1407 typewriter console. [The algorithm] was in production use by summer 1962, possibly a month or so earlier. Programs in those days were freely exchanged among corporations so Calcomp (Jim Newland and Calvin Hefte) had copies. When I returned to Stanford in Fall 1962, I put a copy in the Stanford comp center library.

A description of the line drawing routine was accepted for presentation at the 1963 ACM national convention in Denver, Colorado. It was a year in which no proceedings were published, only the agenda of speakers and topics in an issue of Communications of the ACM. A person from the IBM Systems Journal asked me after I made my presentation if they could publish the paper. I happily agreed, and they printed it in 1965."

Bresenham later modified his algorithm to produce circles.

[edit]