| Bresenham's Line Algorithm |
Website Links For Line |
Information AboutBresenham's Line Algorithm |
|
THE ALGORITHM The line is drawn between two points (''x''0, ''y''0) and (''x''1, ''y''1), 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''1-''x''0 exceeds the vertical distance ''y''1-''y''0 (that is, the line has a slope less than 1.) Our goal is, for each column ''x'' between ''x''0 and ''x''1, 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''0, and each time we add 1 to ''x'', we add the fixed value (''y''1-''y''0)/(''x''1-''x''0), 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 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''0 >= ''y''1; 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. 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 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
Bresenham also published a Run-Slice (as opposed to the Run-Length) computational algorithm. SEE ALSO
EXTERNAL LINKS
|
|
|