Level of Detail: How Games Render Millions of Objects at 60 FPS

The Core Idea and Its Invariant

LOD rests on a perceptual observation: the number of pixels an object covers falls with the square of distance, but the triangle count needed to look correct falls roughly the same way. If a mesh with T triangles looks perfect at distance d, then at distance 2d it covers ¼ the pixels and can be replaced by a mesh with ≈ T⁄4 triangles with no visible loss. The renderer's job is to maintain one invariant:

• Screen-space error invariant: the geometric error introduced by simplification, when projected to the screen, stays below a threshold τ (typically 1–2 pixels). Formally, for object error ε (in world units) at distance d with a camera whose viewport is H pixels tall and vertical field of view φ, the projected error is ρ = ε · H ⁄ (2d · tan(φ⁄2)), and we require ρ ≤ τ.

Everything else — how many discrete meshes you build, whether you blend, how you cull — is machinery to keep ρ ≤ τ as cheaply as possible. Because ρ is monotonic in d, LOD selection reduces to comparing distances against precomputed thresholds, which is why the per-object decision is O(1).

Building the LOD Chain: Mesh Simplification

The offline half of LOD is mesh decimation: producing a chain LOD₀ ⊃ LOD₁ ⊃ … ⊃ LODₙ of progressively coarser meshes. The dominant algorithm is Garland & Heckbert's Quadric Error Metrics (QEM, 1997), which repeatedly collapses the edge whose removal adds the least geometric error.

• Each vertex v is assigned a 4×4 symmetric quadric matrix Q = Σ (over incident planes) of ppᵀ, where p = [a b c d]ᵀ is a plane's coefficients. The error of placing a vertex at position x̄ is the quadratic form x̄ᵀ Q x̄ — the sum of squared distances to those planes.
• For a candidate edge (v₁,v₂), the merged quadric is Q̄ = Q₁ + Q₂. The optimal contraction position solves a 3×3 linear system (∂/∂x of x̄ᵀQ̄x̄ = 0); if singular, fall back to the midpoint.
• Collapses are ordered in a priority queue keyed by error. Pop the cheapest edge, collapse it, recompute the quadrics and costs of affected neighbors, re-heapify.

With E edges and a binary heap, decimation runs in O(E log E) time and O(V + E) space. QEM preserves silhouettes and hard creases far better than naive vertex clustering, which is why it underpins meshoptimizer, Simplygon, and Blender's Decimate modifier. Recording each collapse as an inverse split yields a progressive mesh (Hoppe, 1996) — a single stream you can refine or coarsen one vertex at a time.

Discrete LOD: Selection at Runtime

The simplest and most widely shipped scheme is discrete LOD (DLOD): bake N meshes, pick one per frame. Selection is a tiny function evaluated per visible object:

lod = 0
for i in 1..n:                 # thresholds sorted ascending
    if dist2(cam, obj) > d2[i]:  # squared distance, no sqrt
        lod = i
draw(mesh[obj][lod])

Using squared distances avoids a per-object sqrt; the thresholds d2[i] are computed once from the screen-space-error bound. Selecting one of N meshes is O(N) in the worst case but N ≤ 4–5 in practice, so it is effectively O(1). Across M visible objects the pass is O(M) — trivial next to shading.

DLOD composes beautifully with instanced rendering: bucket all objects that resolve to the same (mesh, LOD) pair and issue one drawInstanced call per bucket. A forest of a million trees collapses to a handful of draw calls, each with a per-instance transform. This is how Unity's HLOD and Unreal's Hierarchical Instanced Static Mesh render vast fields at fixed CPU cost.

Complexity: Why LOD Turns O(scene) Into O(screen)

The payoff is asymptotic, not just a constant. Consider a uniform field of objects at density λ per unit area, each authored at T triangles, viewed to distance R.

• Without LOD: triangles drawn ≈ λ · π R² · T — quadratic in view distance, and it explodes as R grows. Doubling draw distance quadruples cost.
• With LOD: put objects in distance rings; ring k spans [kd, (k+1)d] with area ∝ k and triangle count per object ∝ 1⁄k² (from the screen-error law). Total ≈ Σ (2πk d² · λ) · (T⁄k²) = 2π d² λ T · Σ 1⁄k. That harmonic sum is Θ(log(R⁄d)).

LOD converts a Θ(R²) triangle load into a Θ(log R) one — the reason draw distance can grow to the horizon almost for free. Storage is the standard trade: a full chain that quarters each level sums to T·(1 + ¼ + 1⁄16 + …) → 4T⁄3 ≈ 1.33× the base mesh, a geometric series that never exceeds ⅓ overhead.

The Popping Problem and Continuous LOD

DLOD's failure mode is popping: crossing a threshold swaps meshes instantly, and the vertex snap is jarring — especially on silhouettes and on terrain, where adjacent tiles at different LODs leave T-junction cracks. Fixes range in cost and quality:

• Hysteresis: use different up/down thresholds so an object hovering at a boundary doesn't oscillate LODs every frame.
• Alpha/dithered cross-fade: render both levels for a short window and blend (Unreal's screen-door dithered LOD transition). Doubles cost during the transition only.
• Continuous LOD (CLOD) / geomorphing: a progressive mesh interpolates vertex positions along its collapse sequence, so refinement is a smooth geomorph rather than a snap. Terrain systems like ROAM (1997) and CDLOD geomorph heights per-vertex and stitch skirts to kill cracks.

CLOD costs O(k) edge operations per frame to track the target complexity (k = collapses/splits needed), versus DLOD's O(1). You pay CPU/animation cost for perceptual smoothness — worth it for a single hero mesh or terrain, rarely worth it for ten thousand background props.

Modern Practice: HLOD, Impostors, and Nanite

Real engines layer several LOD ideas because per-object LOD alone doesn't fix draw-call count when there are millions of objects. Three techniques dominate:

• Hierarchical LOD (HLOD): merge a whole neighborhood of distant objects into one baked proxy mesh + atlas texture, stored in a bounding-volume hierarchy or octree. Far away, a city block is a single mesh; up close, the BVH refines to individual buildings. Google Earth and Cesium's 3D Tiles stream exactly this kind of spatial hierarchy over the network.
• Impostors / billboards: at extreme distance, replace geometry with a camera-facing textured quad — the ultimate LOD, 2 triangles. Octahedral impostors bake many view angles so the flat card still looks 3D as you orbit.
• Virtualized geometry (Nanite, UE5, 2021): the mesh is a DAG of ~128-triangle clusters pre-simplified at many levels. Each frame the GPU walks the DAG and picks, per cluster, the coarsest level whose screen-space error ≤ 1 pixel — LOD selection at pixel granularity, streamed from disk. It effectively makes triangle count independent of scene complexity, bounded by screen resolution.

Pitfalls, Edge Cases, and Tuning

LOD is deceptively easy to get subtly wrong. The recurring failure modes:

• Distance-only metrics ignore FOV and silhouette. A sniper scope zoom shrinks φ, so the same object should use a higher LOD than raw distance suggests — always drive selection from projected screen-space error, not distance alone.
• UV/normal seams and skinning. Naive decimation welds vertices across UV seams (texture smearing) or breaks skin weights on animated meshes. Simplifiers must lock border edges and preserve attribute discontinuities.
• Terrain cracks and normal mismatch. Neighboring tiles at different LODs create gaps at shared edges; fix with vertex skirts, edge stitching, or restricted quadtrees (CDLOD) that constrain adjacent levels to differ by ≤ 1.
• Shadow LOD desync. Using a high LOD for the main view but a low LOD for the shadow pass makes the object and its shadow disagree in outline. Keep the shadow-caster LOD consistent or one step coarser at most.
• Thrashing. Without hysteresis, an object parked at a threshold flips LODs every frame — visible flicker and cache churn. Always separate up/down thresholds.

Rule of thumb: choose τ so the first transition happens where the object drops below ~1 pixel of error, add ~10–20% hysteresis, and instance aggressively so LOD selection stays the cheap part of your frame.

Discrete LOD vs. Continuous LOD vs. Nanite-style virtualized geometry

Property	Discrete LOD	Continuous LOD (CLOD)	Virtualized (Nanite)
Selection cost	O(1) per object	O(k) edge collapses/frame	O(clusters visible), GPU
Storage	Σ of N fixed meshes	1 progressive mesh (~1.33×)	cluster DAG, streamed
Transitions	Pop or alpha-blend	Smooth geomorph	Per-pixel, imperceptible
Authoring	Manual/auto-decimate	Edge-collapse sequence	Import raw high-poly
Best regime	Static props, instancing	Terrain, single hero mesh	Film-quality static geo