Low-Level Optimizations
Low-level optimizations are somewhat dubious, because they depend on understanding various machine details. Because machines vary, the accuracy of these low-level assumptions can sometimes be questioned. 

Typically, a set of general rules can be determined that are more-or-less consistent across machines. Here are some examples: 
- Addition and Subtraction are generally faster than Multiplication. 
-Multiplication is generally faster than Division. 
-Using tables to evaluate discrete functions is faster than computing them 
-Integer caluculations are faster than floating-point calculations. 
-Avoid unnecessary computation by testing for various special cases. 
-The intrinsic tests available to most machines are greater than, less than, greater than or equal, and less than or equal to zero (not an arbitrary value). 

None of these rules are etched in stone. Some of these rules are becoming less and less valid as time passes. We'll address these issues in more detail later. 

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 opertaion (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)

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. 



Note that the y variable is now an integer. Next we discuss how to retain the fraction as an integer. After we draw the first pixel (which happens outside our main loop) the correct fraction value is:

fraction = 1/2 + dy / dx

If we scale the fraction by 2*dx the following expression results:

scaledFraction = dx + 2*dy,

and the incremental update becomes:

scaledFraction += 2*dy,

and our test must be modified to reflect the new scaling



This test can be made a test against a value of zero if the inital value of scaledFraction has 2*dx subtracted from it. Giving outside the loop:

OffsetScaledFraction = dx + 2*dy - 2*dx = 2*dy - dx,

and the inner loop becomes

 

The net result is that we might as well double the values of dy and dx (this can be accomplished with either an add or a shift). The result ing method is known as Bresenham's line drawing algorithm. The code is shown below. 
[IMG]http://forum.vingrad.ru/index.php?act=module&module=vingradfaq&target=download_file&articleid=2037&attachid=1[/IMG]