3D Game Design [Image] MIP Mapping ------------------------------------------------------------------------- What is MIP Mapping? "MIP mapping" refers to the technique of precomputing anti-aliased texture bitmaps as seen from far away, and using them in a texture mapped renderer. Each subsequent image in the MIP map is one quarter of the size of the previous (e.g. if the original image is 64x64, then the second image in the MIP map is 32x32, and the third 16x16, and so on). The word "MIP map" comes from the latin multum in parvo -- many things in a small place. A MIP mapped image requires 4/3 of the storage of the original (1 + 1/4 + 1/16 + ...). Why Use MIP Mapping? MIP mapping is used in texture mapped rendering as a short cut to improve both performance and image quality. Most 3D games do not use MIP mapping, and they suffer from artifacts and Moire patterns that reduce image quality. For example, take a close look at Doom sometime. In particular, pay close attention to the textures at the far end of a brightly lit room. Notice how they shift and sparkle as you move? That shifting is the result of aliasing -- erroneous images generated by sampling at too low a frequency. What is happening is that each screen pixel is much larger than a distant texture map pixel. So much larger that it covers dozens or hundreds of texture map pixels. In real life, the analog optics of your eyes will tend to blur images that are very far away so that the colors seem to blend together. But in a standard (non MIP mapped) texture mapper, a single texture pixel is used to color in each screen pixel, with the result that some colors are accentuated when they should softly fade away. Here is a sample scene rendered two ways, once without MIP mapping, and once with MIP mapping: [Image] [Image] No MIP Mapping With MIP Mapping The differences are subtle, but important. Aliasing is most notable in the silver tiled border along the floor and ceiling of the first image, particularly along the far wall. It gets even worse when the viewer moves. How Do You Generate MIP Maps? The idea is to precalculate each MIP map using a filtering process that mimics that of the human eye. For each MIP map image, iterate through the pixels of the original image, filtering groups of source pixels into single pixels in the destination: // Precalculate the 1/4 size MIP map void map2(BYTE* original, BYTE* destination, int w, int h) { int w1 = w/2; int h1 = h/2; BYTE* dst = destination; BYTE* src = original; for (int j = 0; j < h1; j++) { for (int i = 0; i < w1; i++) { src = original + w*j*2 + i*2; *dst++ = Filter(src, w, h, 2); } } } The Filter function can perform whatever kind of filtering you think gives an adequate result. Good results are usually obtained through a simple weighted average, or a Gaussian weighted average. ALPHA uses a simple unweighted mean value function called SumPix. Because ALPHA works with a palletized display mode, the filter function must first calculate the "ideal" color for the destination pixel, and then find the closest match in the current color palette. All filter calculations are done by first converting the RGB values of the source pixels to floating point numbers between 0.0 and 1.0. After the average is taken, the RGB values are rescaled up to 256. // +--------------------------------------------------------------------+ // Sum 'n' x 'n' pixels in a 'w' x 'h' image, starting at 'src' // +--------------------------------------------------------------------+ BYTE SumPix(BYTE* src, int w, int h, int n) { double r = 0.0; double g = 0.0; double b = 0.0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { BYTE* p = src + i*w + j; r += ape[*p].peRed / 256.0; g += ape[*p].peGreen / 256.0; b += ape[*p].peBlue / 256.0; } } double nsqr = n*n; r /= (nsqr); g /= (nsqr); b /= (nsqr); PALETTEENTRY rgb; rgb.peRed = (BYTE) (r * 256.0); rgb.peGreen = (BYTE) (g * 256.0); rgb.peBlue = (BYTE) (b * 256.0); return RGBtoIndex(rgb); } Sample MIP Map class code: MipMap.hpp and MipMap.cpp. How Do You Render With MIP Maps? The basic texture mapping process works the same with MIP maps as without: you simply need to calculate the correct indices into the source texture bitmap to select a color to place at the current screen pixel. The only difference is that the texture bitmap changes as the viewer gets farther away from a given polygon. The idea is to select the MIP map image for which the texel size most closely matches the screen pixel size for the current polygon. For example, if for a given polygon a single screen pixel covers five texels, you should select the 1/4 size MIP map image. In order to calculate which image to use, we must first calculate the size of a texel with respect to a screen pixel. Consider the 3D to 2D projection transform: i = scale * x / z; j = -scale * y / z; These equations tell us that one texel is the same size as one screen pixel when z == scale. This gives rise to the following MIP map selection code: if (z <= scale) polygon.mipnumber = 1; else if (z <= scale*2) polygon.mipnumber = 2; else if (z <= scale*3) polygon.mipnumber = 4; else polygon.mipnumber = 8; Now the only question is what value to use for z? Most polygons actuall cover a range of z values from their nearest vertex to their farthest vertex. Thus there are three obvious choices for z: the minimum z value; the maximum z value; or the average z value. Because the MIP map selection algorithm above selects a new MIP map at the moment z exceeds scale*n, ALPHA uses the minimum z value for the polygon. However, this can pose some problems with very large polygons seen nearly edge on (in which the range of z values for a single polygon is larger than scale). An even more accurate method for rendering with MIP maps is to select two MIP map images for each polygon and interpolate between the two images at each pixel. If you are writing a ray tracer you probably want to explore this technique, but it is too expensive for games without hardware support. The Nintendo Ultra 64 is reputed to support this feature in hardware. How About an Example? OK, here's an example: The left half of the image is the original texture bitmap. The right half of the image contains three interpolated views of the original, each one quarter of the size of the previous. Although this is a wasteful layout of the images in a single file (MIP maps require 1.333 times the original image, and this one uses 2.0), run length encoding compression in the PCX file format makes the wasted space almost negligible. [Image] One interesting side effect of MIP mapping that is visible in this example is the blurring of apparent light sources in the reduced images. As more and more pixels are averaged together, the "light bar" column in the center of this wall texture gets smeared with the color of the frame and the wall itself. In practice, it's not all that bad, but it doesn't look very realistic. In real life, light sources exhibit an effect called "halation" (from the word "halo") which makes them appear bigger than they really are. If desired, this effect can be approximated in the filter function by giving more weight to bright source texels than dark ones. ------------------------------------------------------------------------- back to milo's home page | qds home page | e-mail milo@qds.com This page is designed and implemented by John DiCamillo Copyright © 1995, 1996 John DiCamillo. All rights reserved.