Bresenham's line algorithm

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, and is one of the earliest algorithms discovered in the field of computer graphics.

Contents

1 The algorithm 2 History 3 References 4 See also 5 External links

The algorithm

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:

<math>y - y_0 = \frac{y_1-y_0}{x_1-x_0}(x-x_0).<math>

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

<math>\frac{y_1-y_0}{x_1-x_0}(x-x_0) + y_0.<math>

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:

 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

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. It is better to work on integers. The trick we use is to multiply all the fractional numbers above by deltax, which changes them into integers. The only problem is the constant 0.5 — to deal with this, we multiply both sides of the inequality by 2. The new program looks like this:

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

The multiplication by two can be implemented with a bit shift. Now we can quickly draw lines down and to the right with slope less than 1. We still need to generalize the algorithm to drawing lines in all directions. First, let's draw lines with larger slopes. To do this, we take advantage of the fact that a steep line, one with a large slope, 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)
     int deltax := abs(x1 - x0)
     int deltay := abs(y1 - y0)
     int error := 0
     int deltaerr := deltay
     int y := y0
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error + deltaerr
         if 2×error ≥ deltax
             y := y + 1
             error := error - deltax

We'd also like to draw lines that go down and to the left. Enabling 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. Our function is now:

 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 deltaerr := deltay
     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 2×error ≥ deltax
             y := y + ystep
             error := error - deltax

, or alternatively:

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

The function now handles all lines, and implements the complete Bresenham's algorithm. It can easily be updated to support line styles correctly.

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.

References

• "The Bresenham Line-Drawing Algorithm" (http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html), by Colin Flanagan

Bresenham also published a Run-Slice (as opposed to the Run-Length) computational algorithm.

See also

• Xiaolin Wu's line algorithm, a similarly fast method of drawing lines with antialiasing.

External links

• The Bresenham Line-Drawing Algorithm by Colin Flanagan (http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html)
• National Institute of Standards and Technology page on Bresenham's algorithm (http://www.nist.gov/dads/HTML/bresenham.html)
• Calcomp 563 Incremental Plotter Information (http://www.pdp8.net/563/563.shtml)de:Bresenham-Algorithmus