Quadric Mesh Simplification

Every polygon mesh you see in a video game, a medical scan, or a CAD tool is a soup of triangles. A high-resolution scan of a human face might carry millions of triangles; a game character rendered fifty meters away needs perhaps a few hundred. Sending the full mesh to the GPU at every distance is wasteful — you want the right resolution at the right moment.

The naive idea — delete random triangles — destroys detail at sharp edges and leaves ugly holes. What you really want is to remove the least important geometry first: collapse the edges whose removal changes the surface as little as possible.

In 1997 Michael Garland and Paul Heckbert published Surface Simplification Using Quadric Error Metrics, which gave a clean answer. They showed that the error introduced by contracting an edge can be computed exactly from a $4 \times 4$ symmetric matrix (a quadric) stored at each vertex. Build the matrices in one linear pass, then greedily pick the cheapest edge again and again — and the resulting mesh keeps its silhouette, its creases, and its detail in the right places, all the way from the original count down to a handful of triangles.

The canvas below shows a simple 2-D polygon mesh (a ring of triangles). Each edge carries a quadric error score — the smaller the score, the safer it is to collapse that edge. Press Collapse cheapest edge to remove the edge with the lowest score, merging its two endpoints into one. Press Auto-simplify to keep collapsing until a target triangle count is reached.

<!-- {{c_html_intro}} -->
<div class="hint-box">{{hint_para}}</div>
<canvas id="meshCanvas" width="480" height="260"></canvas>
<div class="stats" id="stats"></div>
<div class="btns">
  <button id="btnCollapse" type="button">{{btn_collapse}}</button>
  <button id="btnAuto" type="button">{{btn_auto}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 8px; }
.hint-box { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f7f9fb;
         width: 100%; max-width: 480px; height: auto; }
.stats { font-size: .82rem; color: #555; margin: .4rem 0 .3rem; min-height: 1.3em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .92rem; font-weight: 600; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }

// Code not found

Notice how the algorithm instinctively protects corners and creases (high-error edges) while quickly consuming flat interior edges (low-error edges). The order in which edges are collapsed is the entire secret: random order ruins the shape, but error-guided order preserves it.

Garland-Heckbert is a solved algorithm (unlike the open problems studied elsewhere on this site), but it sits inside a rich complexity landscape:

• Building the quadrics: one pass over all faces, $O(n)$ time.
• Greedy collapses: each collapse extracts the minimum from a priority queue and re-inserts the updated neighbors — $O(n \log n)$ total, where $n$ is the initial edge count.
• Memory: one $4 \times 4$ symmetric matrix per vertex, so $O(v)$ where $v$ is the vertex count. Each matrix requires only 10 distinct numbers (upper triangle), making storage compact.
• The quadric error formula: for a vertex $\mathbf{v}$, the error contributed by plane $\mathbf{p} = (a,b,c,d)^T$ (with $a^2+b^2+c^2=1$) is $\Delta(\mathbf{v}) = \mathbf{v}^T Q \mathbf{v}$, where $Q = \mathbf{p}\mathbf{p}^T$. Summing $Q$ over all adjacent planes gives a vertex its full quadric, and the optimal contraction target for an edge $(v_1, v_2)$ minimises $\mathbf{v}^T (Q_1 + Q_2) \mathbf{v}$ — a closed-form linear system.
• Is greedy optimal? No. Finding the minimum-error simplification of a mesh to exactly $k$ triangles is NP-hard in the general case. Garland-Heckbert is a greedy heuristic that is near-optimal in practice because the quadric captures local geometry faithfully.

The gap between the $O(n \log n)$ heuristic and the NP-hard optimum is the same story you find in approximation algorithms: the best tractable solution is almost always good enough, and the truly optimal solution is out of reach.

Quadric mesh simplification (and its descendants) is one of the most-deployed algorithms in real-time 3-D:

• Game engines and real-time rendering: level-of-detail (LOD) pipelines pre-compute several versions of each asset at different polygon counts, then swap them based on distance. Garland-Heckbert is the standard tool for generating those LOD meshes.
• Medical imaging: CT and MRI scanners produce enormous volumetric meshes (bones, organs, vessels). Simplification makes them interactive without losing diagnostic detail at clinically important boundaries.
• 3-D printing and fabrication: watertight mesh repair and polygon-count reduction let high-resolution scans feed directly into slicers without overloading them.
• Web and mobile 3-D: glTF assets for browsers and AR/VR headsets must be tiny; automatic simplification at export time is now standard in tools like Blender, Maya, and Houdini.
• Point-cloud processing: the same quadric idea extends to collapsing point clouds and volumetric grids, showing up in systems for autonomous driving and robotics mapping.

The key insight that makes all of this work is that a $4 \times 4$ matrix can remember an entire set of planes destroyed during previous collapses, so later collapses still pay the accumulated cost — without storing the deleted triangles at all.

Quadric mesh simplification is one of those rare algorithms where the math is elegant, the implementation is compact, and the results are immediately visible. A $4 \times 4$ matrix accumulated at each vertex encodes the memory of every plane that has been collapsed away, and a priority queue turns that memory into the greedy order that keeps the surface faithful.

The algorithm is solved and fast — $O(n \log n)$ — yet it reminds us that "solved" and "optimal" are not the same thing. Globally optimal simplification remains out of reach, just as in so many other geometry and optimization problems. What Garland and Heckbert gave us in 1997 is something equally valuable: a heuristic so good that in practice you rarely need the optimum at all.