Mipmapping: The Prefiltered Pyramid That Kills Texture Shimmer

The problem: minification is a signal-processing bug

A texture is a discretely sampled 2D signal. When you draw it larger than its native size (magnification), you interpolate between texels and life is easy. The pain is minification: the surface recedes, and a single output pixel now projects onto a large quadrilateral in texture space — its footprint.

• A pixel whose footprint covers, say, 200 texels contains the average of all 200. That average is the correct answer.
• Point sampling reads one of those 200 texels. As the surface moves sub-pixel amounts, which texel gets hit jumps around chaotically.
• By the Nyquist–Shannon sampling theorem, sampling a signal below twice its highest frequency folds high frequencies down into low ones — aliasing. On a moving image this manifests as crawling moiré patterns and shimmer.

The only correct fix is to band-limit the texture — pre-average it — before sampling. Doing that per-pixel at render time means integrating over an arbitrary footprint every frame: expensive. Mipmapping's insight is that most footprints are roughly square and their sizes fall on a small set of scales, so you can precompute the averages once at power-of-two scales and interpolate.

The core idea: a prefiltered image pyramid

Given a base texture of size w × h (usually a power of two), build a chain of levels where each level is a half-resolution, box-filtered copy of the previous one. Level 0 is the original; each successive level is downsampled 2× in each dimension.

• Level 0: w × h (full detail).
• Level 1: w⁄2 × h⁄2, each texel = average of a 2×2 block of level 0.
• Level k: w⁄2ᵏ × h⁄2ᵏ.
• The chain ends at the 1×1 level — a single texel holding the average color of the entire texture.

The number of levels is ⌊log₂(max(w, h))⌋ + 1. For a 1024×1024 texture that's 11 levels (1024, 512, 256, …, 1). The invariant that makes it correct: texel(k, x, y) equals the average of the region of level 0 that it spatially covers, so reading from level k is equivalent to prefiltering the base image with a 2ᵏ × 2ᵏ box.

build_mip(src):            # src is level 0, w×h
  levels = [src]
  while w > 1 or h > 1:
    w, h = max(1, w/2), max(1, h/2)
    dst = new_image(w, h)
    for (x, y) in dst:      # average the 2×2 parent block
      dst[x,y] = 0.25 * (P[2x,2y] + P[2x+1,2y]
                       + P[2x,2y+1] + P[2x+1,2y+1])
    levels.append(dst); P = dst
  return levels

Choosing the level: LOD from the pixel footprint

At draw time the GPU must pick which mip level to read. It estimates how fast texture coordinates (u, v) change per screen pixel using screen-space partial derivatives ∂u/∂x, ∂u/∂y, ∂v/∂x, ∂v/∂y — computed cheaply because fragment shaders run in 2×2 quads, so neighboring pixels' UVs give finite differences for free.

• Compute the length of the longest UV-change vector: ρ = max(√((∂u/∂x)² + (∂v/∂x)²), √((∂u/∂y)² + (∂v/∂y)²)), scaled by texture dimensions.
• The ideal level of detail is λ = log₂(ρ). If one pixel spans 4 texels, ρ = 4 and λ = 2 — read level 2, where those 4 texels have already been averaged into one.
• λ is fractional. The integer floor ⌊λ⌋ selects a level; the fraction drives blending in trilinear filtering.

This is why mipmapping is O(1): the log₂ picks the level directly, no search. The whole thing is standardized — this ρ/λ formula is in the OpenGL and Vulkan specifications, and a shader-controllable LOD bias lets you nudge λ up (blurrier, cheaper, less aliasing) or down (sharper, risks shimmer).

Bilinear, trilinear, and the seam problem

Just picking ⌊λ⌋ and doing bilinear filtering (4 texels) inside that level produces a visible banding seam at every distance where λ crosses an integer — a sudden pop in sharpness sweeping across the floor.

• Trilinear filtering removes the seam by sampling both bracketing levels ⌊λ⌋ and ⌊λ⌋+1 (bilinear in each, 8 texels total) and linearly interpolating between them by the fraction λ − ⌊λ⌋.
• At λ = 2.7 you blend 30% of level 2 with 70% of level 3, so the transition is continuous. Cost: exactly 2× a bilinear fetch — still O(1), still 8 fixed texel reads.
• The residual defect is over-blurring at grazing angles. A footprint viewed edge-on is a long thin rectangle, but mip selection uses the longest axis, forcing an isotropically large level. The floor goes correctly un-shimmery but mushy.

Anisotropic filtering is the fix: it takes several trilinear samples along the long axis of the footprint (up to 16 taps → up to ~128 texels), keeping detail along the direction that isn't compressed. It's still built on the mip pyramid — anisotropy without mipmaps would re-introduce aliasing along the short axis.

Complexity and the ⅓ memory tax

Build time. Level k has n⁄4ᵏ texels (n = base texel count). Total work is n · Σₖ 4⁻ᵏ = n · 4⁄3 = Θ(n) — linear in the base size, dominated by level 0. Each output texel touches a constant number of parents, so there's no log factor.

Space. The pyramid stores n(1 + ¼ + ¹⁄₁₆ + …) = n · 4⁄3 texels. That geometric series is why the extra cost is exactly ⅓ regardless of texture size — a clean, memorable bound and a favorite interview question.

• Per-sample lookup: O(1). log₂ for level selection is a couple of hardware instructions; the fetch reads a fixed 4 (bilinear) or 8 (trilinear) texels.
• Bandwidth win: distant pixels read from tiny high levels that fit in the texture cache. Without mips, adjacent pixels scatter across a huge base texture, thrashing cache; with mips they hit the same small level — often a net speedup despite the extra memory.

So mipmapping trades a fixed 33% storage increase and a one-time Θ(n) preprocess for O(1) alias-free sampling and better cache behavior — a rare win on both quality and speed.

Real systems, generation, and where it lives

Mipmapping is not optional folklore — it is a hardware feature on every GPU shipped since the 1990s and a first-class object in every graphics API:

• OpenGL: glGenerateMipmap builds the chain; the sampler's GL_TEXTURE_MIN_FILTER selects GL_LINEAR_MIPMAP_LINEAR (trilinear) vs GL_NEAREST_MIPMAP_NEAREST, etc.
• Direct3D / Vulkan / Metal: mip levels are subresources of a texture; samplers expose minFilter, mipmapMode, maxAnisotropy, and LOD clamp/bias.
• Offline / assets: tools like NVIDIA Texture Tools, toktx, and Basis Universal bake mips into compressed formats (BC/ASTC/ETC) so they load prefiltered — you don't want to box-filter sRGB or normal maps naively.

Two production subtleties matter. sRGB/gamma: averaging must happen in linear light, not gamma-encoded values, or downsampled levels come out too dark. Normal maps: naive averaging of unit normals shortens them and flattens specular highlights; techniques like Toksvig or LEAN mapping fold the lost variance into a roughness term instead.

Pitfalls, edge cases, and variants

Mipmapping is simple to state and easy to misuse. The classic failure modes:

• Non-power-of-two textures: the 2× halving is exact only for powers of two. NPOT textures need rounding rules and can produce slightly misaligned averages; historically some hardware disabled mips for NPOT entirely.
• Bleeding across the last level: a texture atlas packs many sub-images into one texture. At high mip levels neighboring sub-images average together, so a distant grass tile leaks into a road tile. Fixes: padding/gutters, or per-region texture arrays instead of an atlas.
• Wrong LOD from procedural or dependent UVs: if you compute UVs with branches or a texture read, the 2×2-quad derivatives become garbage. Use explicit textureLod / textureGrad to supply λ or the gradients yourself.
• Over-blur vs under-sharpen: a positive LOD bias hides aliasing but muddies the image; a negative bias (common "sharpening" hack) re-introduces shimmer. Anisotropic filtering is the principled answer.

Notable variants extend the idea beyond square 2D: ripmaps and summed-area tables (Crow, 1984) support rectangular footprints directly; clipmaps stream only the visible window of enormous virtual textures; and the pyramid concept generalizes into level-of-detail systems for geometry and the Gaussian/Laplacian pyramids used throughout image processing.

Texture minification strategies compared: cost per sample and quality under heavy downscaling

Method	Texels read / pixel	Memory	Quality on distant surfaces
Nearest / point sampling	1	×1.00	Severe shimmer & moiré
Bilinear (no mips)	4	×1.00	Still aliases when minified
Bilinear mipmapping	4	×1.33	No shimmer, visible level seams
Trilinear mipmapping	8	×1.33	Smooth, but over-blurs at grazing angles
Anisotropic (16×) + mips	up to 128	×1.33	Sharp even at grazing angles