Applications of Low-level Optimizations

For our line drawing algorithm we'll investigate applying several of these optimizations. The incremental calculation effectively removed multiplications in favor of additions. Our next optimization will use three of the mentioned methods. It will remove floating-point calculations in favor of integer operations, and it will remove the single divide operation (it makes a difference on short lines), and it will normalize the tests to tests for zero.

Notice that the slope is always rational (a ratio of two integers).

m = (y1 - y0) / (x1 - x0)

Note that the incremental part of the algorthim never generates a new y that is more than one unit away from the old one (because the slope is always less than one)

yi+1 = yi + m


Thus, if we maintained only the fractional part of y we could still draw a line by noting when this fraction exceeded one. If we initialize fraction with 0.5, then we will also handle the rounding correctly as in our DDA routine. 

fraction += m; 
if (fraction >= 1) { 
	y = y + 1; fraction -= 1; 
}


Notice that the slope is always rational (a ratio of two integers).

m = (y1 - y0) / (x1 - x0)

Also note that the incremental part of the algorthim never generates a new y value that is more than one unit away from the old one, because the slope is always less than one (this assured by our improved algorithm).

y[i+1] = y[i] + m

Thus, if we maintained the only the only fractional part of y we could still draw a line by noting when this fraction exceeded one. If we initialize fraction with 0.5, then we will also handle the rounding correctly as in our DDA routine.