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)That’s it, that’s all there is to it. The incrementing based on StepVal being larger than the largest delta is what keep the line on track. By adding the smaller delta to the StepVal each iteration, it’s basically calculating SmallDelta/LargeDelta without doing a divide. The above code works only for slopes that extend from upper left to lower right. It’s not a perfect algorithm, but it does work, and it is fast. It’s extremely close to Bresenham’s Line Algorithm. But I’m not very good at following established methods. :) You can find examples of Bresenham’s Line Algorithm in several books including Zen of Computer Graphics by Michael Abrash, which I highly recommend. That book also includes fast algorithms for other drawing functions as well.
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.
Last revised: August 12, 1997