Tricks of the Windows Game Programming Gurus:Advanced DirectDraw and Bitmapped Graphics

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

### Discrete Sampling Theory

This is going to be brief: I’ll turn your brain to mush with this stuff when you get to 3D texture mapping in Volume II, but for now, this is just a little teaser.

When you work with bitmaps, you’re really working with signals; it’s just that these signals are discrete 2D image data rather than continuous analog data like a radio signal. In either case, you can use signal processing, or more correctly digital signal processing concepts, on images. One of the areas of interest to us is data sampling and mapping.

Within the realm of 2D and 3D graphics, there will be numerous times when you want to sample a bitmap image and then perform some operation on it, such as scaling, rotation, or texture mapping. There are two types of general mappings: forward mappings and inverse mappings. Figures 7.32 and 7.33 show these graphically.

Figure 7.32 Sampling theory: forward mapping.

Figure 7.33 Sampling theory: inverse mapping.

In general, a forward mapping takes pixels from the source and maps them or deposits them on the destination. The only problem with this is that during the mapping, some pixels on the destination may not get mapped from the source due to the mapping function selected.

Inverse mapping, on the other hand, is much better. It takes every pixel on the destination and finds what its source pixel should have been. Of course, there’s a problem with this too—some pixels in the destination may have to be replicated because the source doesn’t have enough data to fill up the destination. This problem creates aliasing. In a case where there’s too much data, aliasing can also occur, but this can be minimized by averaging or using various mathematical filters. The point is, it’s better to have too much data than not enough.

Scaling is an operation that lends itself to either forward or inverse mapping, but inverse mapping is the way to go. Let me show you how to scale a one-dimensional bitmap, and then you can generalize the algorithm to two dimensions. This is an important point: Many image processing algorithms are separable, meaning that images can be processed in multiple dimensions simultaneously. The results of one axis don’t affect another—sort of.

  • Example 1: Let’s say you have a 1×4-pixel bitmap and you want to scale it to 1×8. Figure 7.34 shows the results. Basically, I just copied each pixel from the source to the destination twice.

  Figure 7.34 Scaling a 1×4-pixel bitmap to 1×8 pixels.

  • Example 2: Let’s say you have a 1×4-pixel bitmap and you want to scale it to 1×2. Figure 7.35 shows the results. Basically, I threw away two pixels from the source. This brings up a problem: You’ve thrown away information. Is this correct? Yes and no. “No” in the sense that data has been lost, but “yes” in the sense that it works and works quickly.

Figure 7.35 Scaling a 1×4-pixel bitmap to 1×2 pixels.

A better strategy in both examples would be to use a filter during the process. For example, in Example 1 you copied the pixels, but you could have taken the average of the two pixels above and below every extra pixel and used that value. This would have made the stretching look better. This is where the graphics term bi-linear filtering comes from; it’s based on this idea, but just in the 2D case. In Example 2, you could have used a filter also and done the same thing—average the pixel values so that even though you throw away two pixels, you accumulate some of their information into the remaining pixels to make the results look more natural.

I’m not going to show you how to do filtering until later in the book, so you’re just going to do scaling by brute force. Reviewing the examples, you should be able to pick up that we are sampling the source at some rate—call that the sample rate—and then, based on this sample rate, filling in the destination. Mathematically, this is what you’re doing:

    // the source height of the 1D bitmap.

    float source_height;

    // the destination height of the desired scaled 1D bitmap.

    float dest_height;

    // the sample rate

    float sample_rate = source_height/destination_height;

    // used to index source data

    float sample_index = 0;

    // generate scaled destination bitmap

    for (index = 0; index < dest_height; index++)

        {

        // write pixel

        dest_bitmap[index] =

        source_bitmap[(int)sample_index];

        // advance source index

        sample_index+=sample_rate;

    } // end for index

That’s all the code you need for scaling a bitmap. Of course, you have to add the other dimension, and I would lose the floating point math, but it works.

Given that the source bitmap is 1×4 and looks like this:

  1x4 Pixel Values
  source_bitmap[0] = 12
  source_bitmap[1] = 34
  source_bitmap[2] = 56
  source_bitmap[3] = 90

Now let’s scale the 1×4 image data to 1×8:

Set source_height | = 4
dest_height | = 8
sample_rate = 4/8 | = 0.5

Algorithm Run (with rounding)

index | sample_index | dest_bitmap[index]
0 | 0 | 12
1 | 0.5 | 12
2 | 1.0 | 34
3 | 1.5 | 34
4 | 2.0 | 56
5 | 2.5 | 56
6 | 3.0 | 90
7 | 3.5 | 90

Not bad—it exactly replicated each pixel twice. Now, try a compressive scale to three pixels high:

Set source_height | = 4
dest_height | = 3
sample_rate | = 4/3 = 1.333

Algorithm Run (with rounding)

index | sample_index | dest_bitmap[index]
0 | 0 | 12
1 | 1.333 | 34
2 | 2.666 | 56

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.