The computer is also time-efficient when performing integer multiplication by powers of 2. Therefore, it is an efficient method for scan-converting straight lines. To accomplish this, the algorithm always increments either x or y by one unit depending on the slope of line. The increment in the other variable is determined by examining the distance between the actual line location and the nearest pixel.
|Published (Last):||4 March 2006|
|PDF File Size:||12.40 Mb|
|ePub File Size:||15.31 Mb|
|Price:||Free* [*Free Regsitration Required]|
This algorithm was developed by Jack E. Bresenham in at IBM. And then show you the complete line drawing function. Before we begin on this topic, a revision of the concepts developed earlier like scan conversion methods and rasterization may be helpful.
Once we finish this aspect, we will proceed towards exposition of items listed in the synopsis. One thing to note here is that it is impossible to draw the true line that we want because of the pixel spacing. The true line is indicated in bright color, and its approximation is indicated in black pixels. In this example the starting point of the line is located exactly at 0, 0 and the ending point of the line is located exactly at 9, 6. Now let discuss the way in which this algorithm works. First it decides which axis is the major axis and which is the minor axis.
The major axis is longer than the minor axis. On this picture illustrated above the major axis is the X axis. Each iteration progresses the current value of the major axis starting from the original position , by exactly one pixel. Then it decides which pixel on the minor axis is appropriate for the current pixel of the major axis. Now how can you approximate the right pixel on the minor axis that matches the pixel on the major axis? Now you take a closer look at the picture.
The center of each pixel is marked with a dot. The algorithm takes the coordinates of that dot and compares it to the true line. If the span from the center of the pixel to the true line is less or equal to 0.
That span is more generally known as the error term. You might think of using floating variables but you can see that the whole algorithm is done in straight integer math with no multiplication or division in the main loops no fixed point math either. Now how is it possible?
Basically, during each iteration through the main drawing loop the error term is tossed around to identify the right pixel as close as possible to the true line. Why do you scale the deltas? Finally the scaled values must be subtracted by either dx or dy the original, non-scaled delta values depending on what the major axis is either x or y.
Line Generation Algorithm
Multiplication by 2 can be implemented by left-shift. This version limited to slopes in the first octant,. This is an all-integer function, employs left shift for multiplication and eliminates redundant operations by tricky use of the eps variable. A real implementation should do this.
Bresenham’s Circle Drawing Algorithm