Tim Kientzle works as a technical editor with Dr. Dobb's Journal. He has a Ph.D. in mathematics from the University of California at Berkeley. He is the author of The Working Programmer's Guide to Serial Protocols, and the forthcoming Internet File Formats (both published by Coriolis Group). He can be contacted at kientzle@netcom.com.
Introduction
Bresenham's classic line-drawing algorithm, also known as the "digital differential analyzer," is listed in most graphics textbooks and references, often with no explanation of why it works. After I puzzled it out for myself, I was able to adapt the basic ideas to a variety of other tasks. In this article I start by explaining Bresenham's line algorithm, then show how to adapt its ideas to create a fast algorithm for scaling bitmapped images.
Drawing lines
Drawing a line on a computer screen requires selecting a set of pixels. For example, drawing the line in Figure 1 requires selecting the pixels shown in gray. Bresenham's algorithm walks along the line picking out exact points, then rounds each one to choose a pixel.According to this algorithm, the fractions are the most important feature of Figure 1. Bresenham's algorithm uses simple arithmetic on fractions to track the exact point on the line. In the example, every time you move over one pixel, you move up by 1/3 of a pixel. Listing 1 shows one way to accomplish this.
In Listing 1, the exact y-coordinate of a point on the line is y + numerator/xDelta. Whenever the fraction is bigger than 1 (numerator > xDelta), the algorithm reduces the fraction and increments y. By storing the fraction explicitly as two numbers, this algorithm avoids any arithmetic more complex than integer addition and subtraction. Of course, this simple outline is only the start of a good library routine. In particular, you might want to consider why it's a good idea to initialize the numerator to xDelta/2 rather than zero. (Hint: Figure 1 is wrong in an interesting way.)
The same idea works for a variety of other purposes. When drawing a line such as shown in Figure 1, you need to move up by some fractional amount every time you move over by one. When shrinking a bitmap, you need to map each whole pixel in the original image to some fraction of a pixel in the result.
To simplify things a bit, I discuss only the scaling of a single row of pixels. To scale a two-dimensional bitmap, apply one of these algorithms twice, once to scale the bitmap horizontally and once to scale it vertically.
Non-Smooth Scaling
When drawing lines, you can arrange things so that the fraction numerator/xDelta never increases by more than one. In Figure 1, I increased x by one each time, and y by a fraction. If the slope were greater than 45 degrees, I would instead have increased y by one with each loop and increased x by some fraction.Bitmaps work a little differently. Keep in mind that the goal is to fill each pixel in the destination. So, whether you're scaling to make the bitmap larger or smaller, you still need to increment over the destination pixels. If you're scaling to make a smaller bitmap, you'll end up stepping over the source pixels by a fraction larger than 1.
Listing 2 shows one way to do the stepping. As in the simple Bresenham line drawer, this routine bumps the fraction (in this case numerator/destWidth) by srcWidth/destWidth. The biggest difference between this and the previous routine is that this one acknowledges the possibility that the fraction may increase by 2, 3, or more in the process. The inner while loop simply subtracts 1 from the fraction until the fraction is less than 1.
I leave the optimization to you. A lot will depend on your particular processor and compiler, the size of your images, and many other factors.
This approach is very fast, but you're probably familiar with its drawbacks: enlarging results in an irregular, blocky appearance; reducing generates unpleasant artifacts.
Smooth Bresenham Scaling
One way to avoid such problems is to perform "smooth" scaling, which entails averaging pixels to produce the result. This technique is especially helpful when reducing images, since it means you're actually preserving more of the original information.You might want to spend a while looking at Listing 3 carefully. It computes the correct weighted average of the source pixels to create each destination pixel. For example, this routine will scale the four pixels 12, 24, 36, and 48 to the three pixels 3/4 * 12 + 1/4 * 24, 1/2 * 24 + 1/2 * 36, and 1/4 * 36 + 3/4 * 48. The most complex part of this routine involves splitting one source pixel across more than one destination pixel.
Using this approach does require you to do arithmetic on pixels, however. In particular, you can't use it directly with palette images. You'll have to expand the image to a direct color format, scale, and then dither or quantize to produce the final image.