|
Graphics programmers are constantly looking for ways to improve the realism of the graphics in games. One of the simplest techniques employed to do this is texture mapping, and while texture mapping does add considerable realism to a scene, it also adds a number of new problems. The most obvious visual problems that appear when using textures in a scene are the aliasing artifacts that are visible when texture-mapped polygons are some distance from the viewpoint. If you're moving rapidly around your virtual world, these artifacts appear as flashing or sparkling on the surface of the texture. Or, if the viewpoint is fixed, the artifacts appear as unwanted patterns within the texture after it has been mapped to a polygon. This is clearly visible in Figure 1, where the checkered texture map becomes distorted as its distance from the viewpoint increases.
MIP-mapping helps alleviate this problem. The acronym MIP comes from the Latin phrase multum in parvo, meaning "many things in a small place." Researchers at the New York Institute of Technology adopted this term in 1979 to describe a technique whereby many pixels are filtered and compressed into a small place, known as the MIP-map. To see how MIP-maps improve visual clarity, see Figure 2, in which MIP-mapping with bilinear filtering has been used to smooth the texture.
 |
|
Figure 1. Checkerboard with
no MIP-mapping.
|
 |
|
Figure 2. Checkerboard with MIP-mapping and bilinear filtering.
|
In order to understand what is what's causing the problems in the Figure 1, you have to look within the texture-mapping renderer and understand how the process of sampling the texture maps affects what's displayed on the screen. Look at Figure 3A, in which a sine wave is being sampled at a much higher frequency than the wave itself. As you can see, a fairly good representation of the wave can be obtained from these samples. However, if the sampling frequency drops to exactly two times the frequency of the wave, as shown in Figure 3B, then it's possible that the sampling points will coincide with the zero crossing points of the sine wave, resulting in no information recovery. Sampling frequencies of less than twice that of the sine wave being sampled, as shown in Figure 3C, causes the information within the samples to appear as a sine wave of lower frequency than the original. From these figures, we can guess that for complete recovery of a sampled signal, the sampling frequency must be at least twice that of the signal being sampled. This is known as the Nyquist limit. So, from where does the seemingly magic value of twice the signal being sampled come? In order to answer, that we'll have to digress a bit further and take a stroll into the Fourier domain.
 |
|
Figure 3.
Sampling a sine wave with varying sampling intervals.
|
A complete discussion of Fourier theory could take up several books by itself, so for those of you who haven't suffered through a signal-processing course at college, I suggest that you take a look at the text by Bracewell that's mentioned at the end of this article. What follows is a very limited introduction to Fourier transforms and sampling, but it should be enough to demonstrate how the Nyquist limit is derived.
 |
Figure 4A. Fourier analysis of sampling.
|
Figure 4A shows a plot of the function h(t)=sinc2x and a plot of its Fourier transform, H(f). It's convenient to think of H(f) as being in the Fourier (or frequency) domain and of h(t) as being in the time domain. (If you're wondering why I chose to use sinc2x for this example, it's because it has a simple plot in the frequency domain.) To convert from the time domain to the frequency domain, the following transform is applied to h(t):
 |
|
Eq. 1
|
In this form of the Fourier transform, f defines the frequencies of the sine waves making up the signal, and  tells us that the exponential term is complex (that is, it has both real and imaginary parts). The operator É is often used to denote "has the Fourier transform," so we can write h(t)ÉH( f ). Figure 4B shows the train of impulses used for sampling and the Fourier transform of the impulses. An impulse, denoted as d(t), is a theoretical signal that is infinitely brief, infinitely powerful and has an area of one. An interesting property of an impulse train with a period of Ts is that its Fourier transform is an impulse train with a period of 1/Ts.
 |
|
Eq. 2
|
The effect of sampling h(t) with the sampling function s(t) is shown in Figure 4C. In the time domain, the sampling can be thought of as multiplying h(t) by s(t), and in the frequency domain, it can be thought of as the convolution of H(f) and S(f).
 |
|
Eq. 3
|
Convolution of any two functions f(x) and g(x) is given by
 |
|
Eq. 4
|
If the thought of plugging the Fourier transforms of both h(t) and s(t) into Equation 4 has you wanting to skip to the current Soapbox article (p.72 November issue of Game Developer), just hold on a second - it isn't as bad as it looks. The convolution of a single impulse located at t=t0, with h(t) is just the value of h(t) shifted to that location.
 |
|
Eq. 5
|
We can apply the result of Equation 5 to find the convolution of H(f) and S(f).
 |
|
Eq. 6
|
Equation 6 simply means that the result of the convolution of H(f) and S(f) is such that H(f) is duplicated at intervals of 1/Ts, as can be seen in Figure 4C. The sinc2x function is bandlimited (that is, its bandwidth is limited) to fmax, so the only requirement needed to ensure that there are no overlapping portions in the spectrum of the sampled signal is that fs>2fmax, where fs=1/Ts. So, this is from where the Nyquist limit comes. As you can see in Figure 4D, if the sampling frequency drops below 2fmax, adjacent spectra overlap at higher frequencies, and these frequencies are then lost in the resulting signal. However, instead of disappearing completely, these high-frequency signals reappear at lower frequencies as aliases; this is where the term aliasing originated. To prevent aliasing from occurring, either the signal being sampled must be bandlimited to less than 2fs or the sampling frequency must be set to be higher than 2fmax.
 |
|
|
Let's look at how MIP-mapping helps to reduce aliasing artifacts in our texture-mapped image. Remember that texture mapping is designed to increase the realism and detail in scenes. However, all of the fine details in the texture maps are effectively-high frequency components and they are the cause of our aliasing problems. Since we can't really modify our sampling frequency (1/DU and 1/DV in the texture-mapping portion of our renderer), we have to filter the textures to remove the high-frequency details.
 |
Figure 5. A MIP-Map Pyramid.
|
|
Printer-Friendly Version
