Apparently I have forgotten some of Bresenham's algorithm. I cannot remember it being that smart, but I may have forgotten. Alexfru's explanation about the use of exact integer arithmetic for fractional slopes is spot on, but I want to add a little explanation for the error part. Unfortunately, it does involve some math.
First, the algorithm as you can see uses sx and sy to transform the result to the necessary "quadrant". I am going to assume that dx and dy are positive as well. I am going to treat only the case for the line starting at the origin, because the starting point has no significant impact on the computations.
You may want to skip parts of the following if you feel that it is unhelpful. Anyway. We are at a pixel with centerpoint (x0, y0). If this is not the final pixel, adjacent pixel must be selected in the direction of the line slope. There are three choices - with centerpoints (x0+1,y0), (x0,y0+1), (x0+1,y0+1). It is senseless to explain without illustration the argument, but let's assume for the moment that if (x0+0.5,y0+1) (midpoint between (x0,y0+1) and (x0+1,y0+1)) lies between the line and (x0+1,y0+1), then we must choose (x0,y0+1). This geometrically means that the line falls away from (x0+1,y0+1) and closer to (x0,y0+1) and is expressed in the slope (x0+0.5)/(y0+1) being greater then dx/dy. Similarly, when (x0+1,y0+0.5) (midpoint between (x0+1,y0) and (x0+1,y0+1)) lies between the line and the (x0+1,y0+1), then we must choose (x0+1,y0). Again, this means that the line falls away from (x0+1,y0+1) and closer to (x0+1,y0), and is the same as the slope (y0+0.5)/(x0+1) being greater then dy/dx. If neither of these conditions are satisfied, we must choose (x0+1,y0+1). The verbiage can be summarized as follows:
Code:
(x0+0.5)/(y0+1) > dx/dy choose (x0,y0+1)
(y0+0.5)/(x0+1) > dy/dx choose (x0+1,y0)
otherwise choose (x0+1,y0+1)
We can decouple the choice for x0 and y0 from above:
Code:
(x0+0.5)/(y0+1) <= dx/dy choose x0+1
(y0+0.5)/(x0+1) <= dy/dx choose y0+1
We can multiply each side by the denominator of the other side in both inequalities:
Code:
(x0+0.5) * dy <= (y0+1) * dx
(y0+0.5) * dx <= (x0+1) * dy
We can add and subtract 0.5 * dy and 0.5 * dx respectively:
Code:
(x0+1) * dy - 0.5 * dy <= (y0+1) * dx
(y0+1) * dx - 0.5 * dx <= (x0+1) * dy
We can move terms:
Code:
(y0+1) * dx - (x0+1) * dy >= - 0.5 * dy
(y0+1) * dx - (x0+1) * dy <= 0.5 * dx
Multiply by two both sides:
Code:
2 * ((y0+1) * dx - (x0+1) * dy) >= -dy (choose x0+1)
2 * ((y0+1) * dx - (x0+1) * dy) <= dx (choose y0+1)
We need efficient way to compute (y0+1) * dx - (x0+1) * dy. We start with dx - dy for (0, 0), and add dx when incrementing y0, subtract dy when incrementing x0.