Instead of averaging out texels during scan conversion, one can pre-compute averaged images. Here's a series of such images.

In practice, there is a very efficient scheme for storing pre-filtered bitmaps that takes up only 1/3 more space than the original bitmap. We start with a square image whose side is a power of two. Each next level-of-detail (LOD) map is the result of averaging out the previous image using a 2x2 box filter. The maps are split into RGB components and arranged in the following way in an array.

This data structure is called a mip-map (Latin: *multum in parvo*, multitude in a small place).

In order to decide which LOD to use, we have to calculate the compression factor. Calculating the compression factor per pixel is expensive, so instead we'll do it per-polygon. Right before scan converting a polygon, we can calculate its span in x, y as well as its span in u, v. The square of the compression factor is the area of the bounding rectangle in texture space divided by the area of the bounding rectangle in pixel space.

void Viewport::FillPoly (PolygonFace & poly, Vector<3> const & normal) { PolygonFace::iterator it = poly.begin (); double w = it->GetParam (ParamW); double minX = it->x (), minY = it->y (); double maxX = minX, maxY = minY; double minU = it->GetParam (ParamU) / w; double minV = it->GetParam (ParamV) / w; double maxU = minU, maxV = minV; for (++it; it != poly.end (); ++it) { if (it->x () < minX) minX = it->x (); else if (it-.x () > maxX) maxX = it->x (); if (it->y () , minY) minY = it->y (); else if (it->y () > maxY) maxY = it->y (); w = it->GetParam (ParamW); double u = it->GetParam (ParamU) / w; if ( u < minU) minU = u; else if (u > maxU) maxU = u; double v = it->GetParam (ParamV) / w; if ( v < minV) minV = v; else if (v > maxV) maxV = v; } double dx = maxX - minX; double dy = maxY - minY; double d = sqrt ((maxU - minU) * (maxV - minV) / (dx * dy)); Shader shader (normal, _lightDir, _eye, _ambient, poly.GetTexture (), d); ... }

The compression factor tells us how many texel lengths fall into one pixel length, on average. When accessing a MIP map, we perform the following calculation.

If d <= 1, we have less than one texel per pixel, there's nothing to average out. Return the top-level (full detail) pixel corresponding to u, v.

If d >= size of the bitmap, we have the whole bitmap squeezed inside a single pixel. Return the color from the lower right corner of the MIP map (the whole bitmap averaged out to a single texel).

Otherwise, find the nearest powers of two between which *d* falls. These will be the sizes of the compressed bitmaps used in calculating the color of the pixel. One of them has too much detail, the other too little. Given u and v, calculate the two colors given by the two maps. Interpolate between these two colors in proportion to where d falls between the sizes of the two bitmaps.

To calculate the color at a particular LOD, we do a double interpolation. The point (u, v) falls between the centers of four texels. We interpolate between the upper two texels, based on the actual value of u, between the lower two texels, also using u; and finally interpolate between these two using the actual value of v.

This sophisticated blending scheme is especially important when doing animation, since we want the texture to smoothly change from one level of detail to the next level of detail as the distance to the object changes.

Color MipMap::GetTexel (double u, double v, double d) const { assert (u >= 0 && u <= 1); assert (v >= 0 && v <= 1); // u or v may be equal to 1, so let's subtract epsilon u = u * (MAP_SIZE - 0.001); v = v * (MAP_SIZE - 0.001); d *= MAP_SIZE; // how many texel lengths per pixel length int mapOff = 0; int mapSize = MAP_SIZE; bool biLevel = true; if (d <= 1) { // less than one texel per pixel // no averaging biLevel = false; } else if (d >= MAP_SIZE) { // the whole map in one pixel biLevel = false; u = 0; v = 0; mapOff = 2 * MAP_SIZE - 1; mapSize = 1; } else { while (d > 2.0) { d /= 2.0; mapOff += mapSize; mapSize /= 2; u /= 2.0; v /= 2.0; } d -= 1.0; // 0 < d <= 1 } int x = static_cast<int> (u); int y = static_cast<int> (v); double mixU = u - x; double mixV = v - y; // (1 - mixU) * color1 + mixU * color2; Mapper mapper (_texels, mapOff, mapSize); Color color1 = mapper.GetColor (x, y); color1 *= (1 - mixU); Color color2 = mapper.GetColor (x + 1, y); color2 *= mixU; Color colorUp = color1; colorUp += color2; // same thing for y + 1 color1 = mapper.GetColor (x, y + 1); color1 *= (1 - mixU); color2 = mapper.GetColor (x + 1, y + 1); color2 *= mixU; Color colorDn = color1; colorDn += color2; // mix up and down colorUp *= (1 - mixV); colorDn *= mixV; Color color = colorUp; color += colorDn; if (biLevel) { // add lower level of detail u /= 2.0; v /= 2.0; int x = static_cast<int> (u); int y = static_cast<int> (v); double mixU = u - x; double mixV = v - y; Mapper mapper (_texels, mapOff + mapSize, mapSize / 2); Color color1 = mapper.GetColor (x, y); color1 *= (1 - mixU); Color color2 = mapper.GetColor (x + 1, y); color2 *= mixU; Color colorUp = color1; colorUp += color2; // same thing for y + 1 color1 = mapper.GetColor (x, y + 1); color1 *= (1 - mixU); color2 = mapper.GetColor (x + 1, y + 1); color2 *= mixU; Color colorDn = color1; colorDn += color2; // mix up and down colorUp *= (1 - mixV); colorDn *= mixV; Color colorLo = colorUp; colorLo += colorDn; // mix two levels of detail colorLo *= d; color *= (1 - d); color += colorLo; } return color; }