Introduction

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×44 \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.

Try It: Watch Triangles Collapse

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.

<!-- Quadric mesh simplification demo: interactive 2-D mesh that sheds triangles -->
<div class="hint-box">Each edge is colored by its <b>quadric error score</b> — blue = cheap to collapse, red = expensive. The algorithm always collapses the cheapest edge first, merging its two endpoints.</div>
<canvas id="meshCanvas" width="480" height="260"></canvas>
<div class="stats" id="stats"></div>
<div class="btns">
  <button id="btnCollapse" type="button">Collapse cheapest edge</button>
  <button id="btnAuto" type="button">Auto-simplify</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status"></div>

/* Layout and colors for the mesh simplification demo */
* { 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; }

/* Garland-Heckbert quadric mesh simplification — 2-D demo */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Initial vertex positions [x, y] forming a wheel-like mesh */
const INIT_VERTS = [
  [240,20],[360,80],[440,160],[400,240],[280,250],
  [160,250],[80,160],[120,80],[200,60],
  [240,130]
];
/* Initial triangle list; each entry = [i0, i1, i2] vertex indices */
const INIT_TRIS = [
  [0,1,9],[1,2,9],[2,3,9],[3,4,9],[4,5,9],
  [5,6,9],[6,7,9],[7,8,9],[8,0,9]
];

/* Mutable state: vertex list, triangle list, auto-collapse timer */
let verts, tris, autoTimer;

/* Build a 4x4 quadric matrix Q = p*p^T from plane coefficients (a,b,c,d) */
function makeQ4(a, b, c, d) {
  /* Outer product of the plane normal vector with itself */
  return [
    a*a, a*b, a*c, a*d,
    a*b, b*b, b*c, b*d,
    a*c, b*c, c*c, c*d,
    a*d, b*d, c*d, d*d
  ];
}
function addQ(q1, q2) { return q1.map((v, i) => v + q2[i]); }
function zeroQ() { return new Array(16).fill(0); }

/* Compute 2-D plane (line) equation from two endpoints */
function planeFromPoints(ax, ay, bx, by) {
  /* Normal of the edge direction, normalized, then d = distance from origin */
  const nx = -(by - ay), ny = bx - ax;
  const len = Math.sqrt(nx*nx + ny*ny);
  if (len < 1e-10) return [0, 0, 1, 0];
  const a = nx / len, b = ny / len;
  const d = -(a * ax + b * ay);
  return [a, b, 0, d];
}

/* Accumulate per-vertex quadrics by summing contributions from adjacent edges */
function buildVertexQuadrics() {
  const Q = verts.map(() => zeroQ());
  for (const [i0, i1, i2] of tris) {
    /* Each triangle contributes three edge planes to its endpoint vertices */
    const edges = [[i0,i1],[i1,i2],[i2,i0]];
    for (const [a, b] of edges) {
      const [ax, ay] = verts[a], [bx, by] = verts[b];
      const p = planeFromPoints(ax, ay, bx, by);
      const q = makeQ4(...p);
      Q[a] = addQ(Q[a], q);
      Q[b] = addQ(Q[b], q);
    }
  }
  return Q;
}

/* Evaluate quadric error at position (x,y): v^T * Q * v */
function quadricError(Q, x, y) {
  /* 4-D homogeneous vector v=[x,y,0,1]; error = v^T Q v */
  const v = [x, y, 0, 1];
  let err = 0;
  for (let i = 0; i < 4; i++)
    for (let j = 0; j < 4; j++)
      err += v[i] * Q[i*4+j] * v[j];
  return Math.max(0, err);
}

/* Optimal contraction target for an edge — midpoint heuristic */
function optimalVertex(Qsum, ax, ay, bx, by) {
  /* Midpoint of the two endpoints (closed-form minimizer approximation) */
  return [(ax + bx) / 2, (ay + by) / 2];
}

/* Build a deduplicated edge list from the current triangle soup */
function buildEdgeList() {
  const edgeSet = new Map();
  for (const [i0, i1, i2] of tris) {
    const pairs = [[i0,i1],[i1,i2],[i2,i0]];
    for (let [a, b] of pairs) {
      if (a > b) [a, b] = [b, a];
      const key = a + '_' + b;
      if (!edgeSet.has(key)) edgeSet.set(key, [a, b]);
    }
  }
  return [...edgeSet.values()];
}

/* Score an edge: error at the optimal contraction target */
function edgeScore(Q, a, b) {
  const [ax, ay] = verts[a], [bx, by] = verts[b];
  const Qsum = addQ(Q[a], Q[b]);
  const [mx, my] = optimalVertex(Qsum, ax, ay, bx, by);
  return quadricError(Qsum, mx, my);
}

/* Collapse edge (a,b): move vertex a to midpoint, remove b, fix triangles */
function collapseEdge(a, b) {
  const Q = buildVertexQuadrics();
  const Qsum = addQ(Q[a], Q[b]);
  const [ax, ay] = verts[a], [bx, by] = verts[b];
  const [nx, ny] = optimalVertex(Qsum, ax, ay, bx, by);

  /* Remove degenerate triangles (those containing both a and b) */
  verts[a] = [nx, ny];
  tris = tris
    .filter(t => !(t.includes(a) && t.includes(b)))
    .map(t => t.map(i => i === b ? a : i))
    .filter(t => {
      /* After remapping b->a, reject any triangle with two equal indices */
      return t[0] !== t[1] && t[1] !== t[2] && t[0] !== t[2];
    });
}

/* Render the mesh onto the canvas */
function draw() {
  const canvas = document.getElementById('meshCanvas');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  /* Fill triangles with a light blue tint */
  ctx.fillStyle = 'rgba(29,53,87,0.08)';
  for (const [i0,i1,i2] of tris) {
    ctx.beginPath();
    ctx.moveTo(...verts[i0]); ctx.lineTo(...verts[i1]); ctx.lineTo(...verts[i2]);
    ctx.closePath(); ctx.fill();
  }

  /* Color edges by normalized score: blue=cheap (safe), red=expensive (important) */
  const Q = buildVertexQuadrics();
  const edges = buildEdgeList();
  if (edges.length === 0) return;
  const scores = edges.map(([a,b]) => edgeScore(Q,a,b));
  const minScore = Math.min(...scores);
  const maxScore = Math.max(...scores);
  const range = maxScore - minScore || 1;

  for (let i = 0; i < edges.length; i++) {
    const [a, b] = edges[i];
    const t = (scores[i] - minScore) / range;
    /* Interpolate from dark-blue (cheap) to dark-red (expensive) */
    const r = Math.round(29 + t * (200 - 29));
    const g = Math.round(53 + t * (30 - 53));
    const bl = Math.round(87 + t * (30 - 87));
    ctx.strokeStyle = `rgb(${r},${g},${bl})`;
    ctx.lineWidth = scores[i] === minScore ? 3 : 1.5;
    ctx.beginPath(); ctx.moveTo(...verts[a]); ctx.lineTo(...verts[b]); ctx.stroke();
  }

  /* Draw vertex dots */
  for (const [x, y] of verts) {
    ctx.beginPath(); ctx.arc(x, y, 4, 0, Math.PI*2);
    ctx.fillStyle = '#1d3557'; ctx.fill();
  }

  /* Label the cheapest edge with its score */
  const cheapIdx = scores.indexOf(minScore);
  const [ca, cb] = edges[cheapIdx];
  const mx = (verts[ca][0]+verts[cb][0])/2, my = (verts[ca][1]+verts[cb][1])/2;
  ctx.font = '11px system-ui'; ctx.fillStyle = '#c92f3c'; ctx.textAlign = 'center';
  ctx.fillText(i18nFmt(`cheapest (%score%)`, { score: minScore.toFixed(1) }), mx, my - 7);
}

function updateStats() {
  const Q = buildVertexQuadrics();
  const edges = buildEdgeList();
  const liveVerts = new Set(tris.flat()).size;
  document.getElementById('stats').textContent =
    i18nFmt(`Triangles: %t% · Vertices: %v% · Edges: %e%`, { t: tris.length, v: liveVerts, e: edges.length });
}

/* Find and collapse the single cheapest edge */
function doCollapse() {
  if (tris.length < 2) { setDone(); return; }
  const Q = buildVertexQuadrics();
  const edges = buildEdgeList();
  let best = Infinity, ba = -1, bb = -1;
  for (const [a, b] of edges) {
    const s = edgeScore(Q, a, b);
    if (s < best) { best = s; ba = a; bb = b; }
  }
  if (ba < 0) { setDone(); return; }
  collapseEdge(ba, bb);
  draw(); updateStats();
  setStatus(i18nFmt(`Collapsed edge with error %score%.`, { score: best.toFixed(1) }), 'info');
  if (tris.length < 2) setDone();
}

function setDone() {
  clearInterval(autoTimer); autoTimer = null;
  setStatus(`Mesh fully simplified.`, 'ok');
  document.getElementById('btnCollapse').disabled = true;
  document.getElementById('btnAuto').disabled = true;
}

function setStatus(t, cls) {
  const el = document.getElementById('status');
  el.textContent = t; el.className = 'status ' + cls;
}

/* Reset everything back to the initial mesh */
function init() {
  clearInterval(autoTimer); autoTimer = null;
  verts = INIT_VERTS.map(v => [...v]);
  tris = INIT_TRIS.map(t => [...t]);
  document.getElementById('btnCollapse').disabled = false;
  document.getElementById('btnAuto').disabled = false;
  setStatus(`Ready — press collapse or auto-simplify.`, 'info');
  draw(); updateStats();
}

document.getElementById('btnCollapse').addEventListener('click', doCollapse);
document.getElementById('btnAuto').addEventListener('click', () => {
  if (autoTimer) { clearInterval(autoTimer); autoTimer = null; return; }
  autoTimer = setInterval(() => {
    if (tris.length < 2) { setDone(); return; }
    doCollapse();
  }, 600);
});
document.getElementById('btnReset').addEventListener('click', init);
init();
Result
Console

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.

The Real Complexity

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)O(n) time.
  • Greedy collapses: each collapse extracts the minimum from a priority queue and re-inserts the updated neighbors — O(nlog⁡n)O(n \log n) total, where nn is the initial edge count.
  • Memory: one 4×44 \times 4 symmetric matrix per vertex, so O(v)O(v) where vv is the vertex count. Each matrix requires only 10 distinct numbers (upper triangle), making storage compact.
  • The quadric error formula: for a vertex v\mathbf{v}, the error contributed by plane p=(a,b,c,d)T\mathbf{p} = (a,b,c,d)^T (with a2+b2+c2=1a^2+b^2+c^2=1) is Δ(v)=vTQv\Delta(\mathbf{v}) = \mathbf{v}^T Q \mathbf{v}, where Q=ppTQ = \mathbf{p}\mathbf{p}^T. Summing QQ over all adjacent planes gives a vertex its full quadric, and the optimal contraction target for an edge (v1,v2)(v_1, v_2) minimises vT(Q1+Q2)v\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 kk 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(nlog⁡n)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.

Where It Matters

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×44 \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.

Conclusion

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×44 \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(nlog⁡n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quadric-mesh-simplification/Content licensed under CC BY-NC 4.0.