|
|
Bresenham's Line AlgorithmBresenham'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. The algorithm The line is drawn between two points (x0, y0) and (x1, y1), 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 x1-x0 exceeds the vertical distance y1-y0 (that is, the line has a slope less than 1.) Our goal is, for each column x between x0 and x1, 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 y0, and each time we add 1 to x, we add the fixed value (y1-y0)/(x1-x0), 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 y0 < y1; if so, we step y by -1 instead of 1. Our function is now: function line(x0, x1, y0, y1) if x0 > x1 then swap(x0, x1) swap(y0, y1) boolean steep := abs(y1 - y0) > abs(x1 - x0) if steep then swap(x0, y0) swap(x1, 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 and can be easily 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. 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 See also External links
|
 |