﻿ Game Programming Gurus

Free JavaScript Editor     Ajax Editor ﻿

Main Page

### 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.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 1x4-pixel bitmap and you want to scale it to 1x8. Figure 7.34 shows the results. Basically, I just copied each pixel from the source to the destination twice.

##### Figure 7.34. Scaling a 1x4-pixel bitmap to 1x8 pixels.

• Example 2: Let's say you have a 1x4-pixel bitmap and you want to scale it to 1x2. 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 1x4-pixel bitmap to 1x2 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];

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 1x4 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 1x4 image data to 1x8:

 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

Notice that you missed the last pixel in the source—the 9—altogether. You may or may not like this; maybe you always want to see the top and bottom pixel in the scaling operation for scales 1x2 and greater and would rather throw away some in-between pixels. This is where rounding and biasing the sample_rate and sample_index come into play—think about it…

Now that you know how to scale an image, let DirectDraw do it for you. DEMO7_14.CPP|EXE is a remake of DEMO7_13.CPP|EXE, but I've added some code to arbitrarily scale the aliens so that they seem to be different sizes. If you have hardware scaling, the demo will run very smoothly, but if you don't, you may notice some degradation. Again, you'll see how to use IDIRECTDRAWSURFACE7::GetCaps() to detect this later in the chapter.

﻿

Ajax Editor     JavaScript Editor