Mipmapping

Look at a checkerboard floor stretching away from you in a 3-D game. Up close the squares are crisp. In the distance, where dozens of texels map onto a single screen pixel, the pattern dissolves into a dancing, strobing noise — aliasing. Scroll the camera and the shimmer chases you.

The fix, invented by Lance Williams in 1983, is elegant: precompute the texture at half resolution, then quarter, then eighth — a pyramid of progressively smaller images. When the GPU shades a distant pixel it reaches not for the original full-resolution image, but for whichever level in the pyramid best matches how many texels project onto that pixel. No more averaging a crowd of high-frequency detail into a single noisy sample.

The name comes from the Latin multum in parvo — "much in little." Each level is a mip level, and the complete pyramid is a mipmap. The storage overhead is modest: the levels at $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, … of the original size form a geometric series that sums to exactly one third of the original texture's area — so the full mipmap costs only $\frac{4}{3}$ times the original.

This article is about the idea behind mipmapping and the elegant math that makes it work. For a broader look at how rendering pipelines eliminate jagged edges see the article on antialiasing — or explore how dynamic shortest paths shows that precomputation is a recurring theme across algorithms.

The canvas below renders a checkerboard floor receding into the distance — the classic aliasing stress-test. Toggle the switch to turn mipmapping on and off and watch what happens to the distant squares.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label class="toggle-label">
    <span class="label-text">{{label_mips}}</span>
    <span class="switch">
      <input type="checkbox" id="mip-toggle" checked>
      <span class="slider"></span>
    </span>
  </label>
  <span id="mip-level-display" class="level-badge"></span>
</div>
<canvas id="canvas" width="560" height="320" title="{{canvas_title}}"></canvas>
<p class="hint">{{hint_para}}</p>

/* {{c_css_intro}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; background: #111; color: #eee; padding: .6rem; }
.controls { display: flex; align-items: center; gap: 1rem; margin-bottom: .6rem; flex-wrap: wrap; }
.label-text { font-size: .95rem; font-weight: 600; }
.switch { position: relative; display: inline-block; width: 44px; height: 24px; }
.switch input { opacity: 0; width: 0; height: 0; }
.slider { position: absolute; inset: 0; background: #555; border-radius: 24px; transition: .25s; cursor: pointer; }
.slider::before { content: ''; position: absolute; width: 18px; height: 18px; left: 3px; top: 3px;
                  background: #fff; border-radius: 50%; transition: .25s; }
input:checked + .slider { background: #3b82f6; }
input:checked + .slider::before { transform: translateX(20px); }
.level-badge { font-size: .8rem; background: #1e293b; border: 1px solid #334155;
               border-radius: 6px; padding: .15rem .55rem; min-width: 7rem; text-align: center; }
canvas { display: block; width: 100%; max-width: 560px; border-radius: 8px; image-rendering: pixelated; }
.hint { font-size: .82rem; color: #aaa; margin-top: .5rem; line-height: 1.5; }

// Code not found

With mips off, the renderer samples the full-resolution texture for every pixel regardless of distance. Far away, dozens of high-contrast texels collapse into one pixel and you get the characteristic shimmer. With mips on, the renderer picks a pre-blurred level where roughly one texel maps to one pixel — the floor stays smooth all the way to the horizon.

The key decision is: which mip level do I sample? The GPU estimates how much the texture stretches or shrinks in screen space using the texture derivative — how many texels does a one-pixel step in screen space correspond to?

If that ratio is $\rho$ (texels-per-pixel), the ideal level is:

$$d = \log_{2}(\rho)$$

At $d = 0$ you use the original full-resolution image. At $d = 1$ you use the half-size level. At $d = 2$ the quarter-size level, and so on.

Filtering strategies vary by quality and cost:

• Nearest-level (point): snap $d$ to the nearest integer level. Fast, but introduces a visible pop when you cross level boundaries.
• Bilinear on one level: sample the chosen level with bilinear interpolation of its four nearest texels. Smooth within a level, still pops at boundaries.
• Trilinear filtering: blend between the two nearest mip levels ($\lfloor d \rfloor$ and $\lceil d \rceil$) each sampled bilinearly. Eight texture reads per pixel, no visible seams. The standard quality setting in almost every game since the mid-1990s.
• Anisotropic filtering: the $\log_{2}$ formula assumes the pixel footprint is square. When the surface is at a steep angle the footprint is an elongated ellipse, and a square mip level under-samples one axis. Anisotropic filtering takes multiple samples along the elongated axis, recovering sharpness on slanted surfaces.

Storage cost. The mip chain is $1 + \frac{1}{4} + \frac{1}{16} + \cdots = \frac{1}{1 - 1/4} = \frac{4}{3}$ of the base level. For a $1024 \times 1024$ texture the mipmap adds roughly 33 % more memory — a bargain for the quality gain.

Build time. Generating the chain is a cascade of box-filter (or higher-quality Lanczos) downsamples: each level is $O(n)$ in the number of texels of the level above it, and the total work is $O\!\left(\frac{4}{3} n\right)$ — essentially one extra pass over the original texture.

The mipmap idea — precompute a coarser version and pick it at the right time — resurfaces across computing:

• Real-time 3-D rendering: every GPU since the late 1980s has hardware mipmap support. Without it, textured surfaces at oblique angles shimmer on every frame. Modern engines also use mips for environment maps, shadow maps, and light probes.
• Satellite and map imagery: tile pyramids (the "zoom levels" of Google Maps or OpenStreetMap) are geographic mipmaps. When you zoom out, the server serves a pre-averaged tile instead of sub-sampling thousands of high-resolution tiles on the fly.
• Image compression: formats such as DXT/BC and ASTC store mip chains as part of the compressed file. Decompressing a distant object's texture at full resolution and then discarding most of the information would waste bandwidth; the right mip level is decompressed directly.
• Machine learning — feature pyramids: modern object-detection networks (Feature Pyramid Networks, FPN) build explicit multi-scale feature maps, essentially mipmaps of learned features. The network detects small objects in high-resolution feature maps and large objects in coarse ones.
• Procedural and virtual textures: streaming texture systems (id Software's MegaTexture, Unreal's Virtual Textures) load only the mip levels actually visible — a direct application of the LOD idea to texture memory management.

The core insight is always the same: precompute the work at every scale, then choose the scale that matches the query. That is precisely the idea behind the halting problem's undecidability proofs — knowing in advance which cases are hard and which are easy.

Mipmapping is one of the most cost-effective algorithmic ideas in computer graphics: spend 33 % more storage to precompute every coarser version of a texture, and in exchange eliminate an entire class of visual artifacts in real time, at negligible runtime cost.

Lance Williams described the pyramid in 1983. Every GPU sold since the early 1990s implements it in silicon. The formula $d = \log_{2}(\rho)$ has not changed; only the filtering layers on top — bilinear, trilinear, anisotropic — have grown more sophisticated.

The next time you drive through a game world with a crisp, stable floor texture receding to the horizon, remember: the GPU is not sampling the original high-resolution image. It is plucking the right pre-blurred level from a quietly maintained pyramid, one that was computed the moment the texture was loaded — and whose total cost is just $\frac{4}{3}$ of the original.