Bresenham's Line Drawing Algorithm

Bresenham's algorithm is somewhat similar to the Simple DDA in that each iteration through the algorithm, one of the coordinate values is changed by 1 in some direction. The other coordinate may or may not change which is based on the accumulation of an error term measured perpendicular to the axis of greatest movement between the actual dots generated and the exact path of the line. The following example shows this measurement:

Once again, we are limiting our discussion to lines in the first octant. With this in mind, let's consider drawing a line from (0,0) to (19,4) as discussed in the text. The exact straight line is shown in Figure 2.27 on page 50. Given that this line is in the first octant, we know that the x coordinate will be incremented by one each time since deltax > deltay. Therefore, the error term will be measured perpendicular to the x-axis. In particular, the line crosses the vertical grid lines 18 times and we must decide which pixel, above the line or below the line, to set based on the error term.

We know that the slope of this line segment is: slope=(y2-y1)/(x2-x1)=(4-0)/(19-0)=4/19. With this in mind we have the following:

Because the value of 4/19 is less than 0.5, we choose the pixel which is below the exact line or in this case (1,0). Remember, x is always incremented and we are using the error term to determine which y term gets plotted. At x=2 we plot (2,0) and at x=3 we plot (3,1), since 12/19 > 0.5. We now move the decision to pixels at height 1 and 2, so 16/19 is less than 1.5 and so on.

Define:
1) elevation - the value of the y-coordinate on the exact line
2) midpoint - the value that is compared to when trying to decide whether to move vertically or not

So for the example from (0,0) to (19,4) we have the following:

(x,y);Midpoint;Elevation
(0,0);9.5/19=0.5;0/19
(1,0);0.5;4/19
(2,0);0.5;8/19
(3,1);28.5/19=1.5;12/19
(4,1);1.5;16/19
(5,1);1.5;20/19
(6,1);1.5,24/19
(7,1);1.5;28/19
(8,2);47.5/19=2.5;32/19 .......

This clearly is not very efficient since we are using division; therefore, we want to get rid of the denominator producing the following (Change #1):

(x,y);Midpoint;Elevation
(0,0);9.5;0
(1,0);9.5;4
(2,0);9.5;8
(3,1);28.5;12
(4,1);28.5;16
(5,1);28.5;20
(6,1);28.5,24
(7,1);28.5;28
(8,2);47.5=2.5;32 .......

Whenever the elevation becomes greater than 9.5 we know that a vertical step must take place, so instead of recalculating the next midpoint, we could simply subtract 19 from the elevation when the vertical step is taken as follows (Change #2):

(x,y);Midpoint;Elevation
(0,0);9.5;0
(1,0);9.5;4
(2,0);9.5;8
(3,1);9.5;12-19=-7
(4,1);9.5;-3
(5,1);9.5;1
(6,1);9.5,5
(7,1);9.5;9
(8,2);9.5;13-19=-6 .......

From here we can still make two major improvements:
(1) We can work with all numbers doubled which leads to pure integer arithmetic, so in the above example the number to add is 8 and the number to subtract is 38.
(2) If we double 9.5 we have 19. We can compare to 0 instead of 19 if we start the elevation at -19. We remember that comparison to 0 is faster in machine code than comparison to any other number. Why?

Problem: Using procedure bresline on page 53, generate a line from (0,0) to (4,3). Make a table of values for: xstart, ystart, xend, yend, sum, Dx, Dy, x, and y.