I’ve been continually amazed at how many game programmers don’t know this algorithm.  I’ve also been amazed at how many programmers think that’s it’s useless.  It’s true that there are faster algorithms.  It’s also true that it’s not as important in modern CPU’s to avoid using divide.  But it’s still a handy algorithm not only for lines but for dynamic scaling, and other related things. 

Integer line algorithms came about a long long time ago, in a galaxy far far away.  Back when the CPU’s didn’t have a divide instruction.  Anytime you wanted to do a divide (and multiply for that matter) you had to do it algorithmically.  So, many strange and wonderful algorithms were invented to avoid the necessity for dividing.  The integer line algorithm is one of those.  It allows you to draw a line from any point to any other point with having to use divides to calculate the slope.  It’s also based on integer math, making it fairly fast, especially on pre-Pentium processors. 

The concept is fairly simple, figure out how many steps you need to take both horizontally and vertically, and spread the steps evenly so that the line looks sloped.  A line drawn with this algorithm looks like this: 

This is done by keeping track of how many steps you’ve made in the largest delta direction, and making sure the number of steps in the smaller delta direction are correct.  Here’s a bit of code in C++ that does this: 

drawline(int x1,int y1,int x2,int y2)
{
        int dx=x2-x1;   // dx is the delta for x
        int dy=y2-y1;   // dy is the delta for y
        int StepVal=0;  // variable for figuring out when to 
                        // increment the other axis.
        int x,y;        // where is the current pixel.
        if(dx>dy)       // The slope is less than 45 degres
        {
                y=y1;
                for(x=x1; x<=x2; x++)
                {
                        StepVal+=dy;
                        if(StepVal>=dx) // Increment y if enough x steps
                                        // have been taken.
                        {
                                y++;
                                StepVal-=dx;    // Reset StepVal, but  
                                                // not to 0.  This 
                                                // gives even slopes.
                        }
                        DrawPixel(x,y); // Call your function to draw a
                                        // pixel here.
                }
        }
        else    // The slope is greater than 45 degrees, just like 
                // above, but with y instead of x.
        {
                x=x1;
                for(y=y1; y<=y2; y++)
                {
                        StepVal+=dx;
                        if(StepVal>=dy)
                        {
                                x++;
                                StepVal-=dy;
                        }
                        DrawPixel(x,y); // Call your function to 
                                        //draw a pixel here.
                }
        }
}

But, how is this algorithm useful in anything else but line drawing.  This part requires a little imagination.  There isn’t really anything that says that the input values have to correspond to x and y offsets.  What if they represented original width, and desired width of an image.  Then instead of having x and y, you’d have OldX and NewX.  And if you draw you’re pixels in the color of OldX at the position of NewX then you have yourself a scaling routine.  Of course you’d have to do this with both axis, but that is left as an exercise to the reader.