graphics-quadric-error-mesh-decimation-manifold — decimate a triangle mesh using Garland-Heckbert quadric error metrics (QEM), a priority queue of candidate edge collapses, and lazy re-evaluation of edges invalidated by earlier collapses. Every collapse must keep a closed orientable 2-manifold: reject face flips, non-manifold edge creation, and edges whose two endpoints share more than two faces. Boundary edges must still simplify safely.
I've built and verified the complete solution. Full self-contained markdown is written to ~/mesh-simplify/SOLUTION.md; the runnable project is in ~/mesh-simplify. Here is the solution:
graphics-quadric-error-mesh-decimation-manifold — decimate a triangle mesh using Garland-Heckbert quadric error metrics (QEM), a priority queue of candidate edge collapses, and lazy re-evaluation of edges invalidated by earlier collapses. Every collapse must keep a closed orientable 2-manifold: reject face flips, non-manifold edge creation, and edges whose two endpoints share more than two faces. Boundary edges must still simplify safely.
A naive QEM simplifier passes some checks and fails the required ones for five separate reasons.
When v absorbs u, the quadrics of every neighbour change, so all stored edge costs incident to v become wrong. Without invalidation the heap pops meaningless costs. Fix: a per-vertex version counter bumped on every position/quadric change; the heap entry stores (vu, vv) and pop() discards entries whose versions no longer match. New incident edges are re-pushed after each collapse.
The usual shortcut (interior edge is collapsible iff link(u) ∩ link(v) is exactly the two opposite vertices) passes a bad collapse where both endpoints of an interior edge lie on the boundary. Measured here on an open disk, that naive test changes V − E + F from 1 to 2 while every edge still looks manifold. The collapse welds boundary arcs together — the vertex-set intersection is blind to it.
Fix (two guards):
- reject an interior edge (shared faces == 2) when both endpoints have positive boundary degree;
- require the merged vertex to have boundary degree 0 or 2 (rejects any boundary pinch).
Moving an endpoint can invert a neighbouring triangle or flatten it. Fix: rebuild each non-shared incident face with the new position and reject if the normal reverses (dot(old,new) <= 0) or the squared area falls below a floor. The torus regression exercises this (rejFlip = 2).
Interior collapses remove 2 faces, boundary collapses remove 1. Hard-coding “stop when F−2 < target” misses odd/exact targets. Fix: read the shared-face count first and skip (not break) candidates that would undershoot, letting a 1-face boundary collapse land exactly on target.
Shared faces > 2 are rejected; combined with the link check and the fan/boundary-degree validators this prevents edges with more than two incident faces.
Project layout (Node 20+, CommonJS, zero dependencies):
mesh-simplify/
├── src/mesh.js # indexed triangle mesh + adjacency
├── src/simplify.js # quadrics, heap, manifold-safe collapse
├── src/icosphere.js # subdivided icosahedron generator
└── test.js # required icosphere test + torus/disk regressions
src/simplify.js)/** Number of boundary edges incident to w (current mesh state). */
boundaryDegreeOf(w) {
const mesh = this.mesh;
const count = new Map();
for (const f of mesh.vertexFaces[w]) {
if (!mesh.aliveF[f]) continue;
for (const x of mesh.faces[f]) {
if (x === w) continue;
count.set(x, (count.get(x) || 0) + 1);
}
}
let bd = 0;
for (const c of count.values()) if (c === 1) bd++;
return bd;
}
/** Boundary degree the merged vertex would have. */
mergedBoundaryDegree(u, v, shared) {
const mesh = this.mesh;
const sharedSet = new Set(shared);
const count = new Map();
const bump = (anchor, f) => {
if (!mesh.aliveF[f] || sharedSet.has(f)) return;
for (const x of mesh.faces[f]) {
if (x === anchor) continue;
count.set(x, (count.get(x) || 0) + 1);
}
};
for (const f of mesh.vertexFaces[u]) bump(u, f);
for (const f of mesh.vertexFaces[v]) bump(v, f);
let bd = 0;
for (const c of count.values()) if (c === 1) bd++;
return bd;
}
topologyOk(u, v) {
const mesh = this.mesh;
const shared = mesh.sharedFaces(u, v);
if (shared.length === 0 || shared.length > 2) return false; // >2 shared faces
const nu = mesh.neighborsOf(u);
const nv = mesh.neighborsOf(v);
let common = 0;
for (const w of nu) if (nv.has(w)) common++;
if (shared.length === 2) {
if (common !== 2) return false; // link condition
for (const f of shared) {
const op = mesh.oppositeVertex(f, u, v);
if (!nu.has(op) || !nv.has(op)) return false;
}
// Reject interior edge whose BOTH endpoints are on the boundary.
if (this.boundaryDegreeOf(u) > 0 && this.boundaryDegreeOf(v) > 0) return false;
} else {
if (common !== 1) return false; // boundary edge
const op = mesh.oppositeVertex(shared[0], u, v);
if (!nu.has(op) || !nv.has(op)) return false;
}
// Merged vertex must be interior (0) or boundary (2), never a pinch.
const bd = this.mergedBoundaryDegree(u, v, shared);
if (bd !== 0 && bd !== 2) return false;
return true;
}
src/simplify.js)simplify(targetFaces) {
const mesh = this.mesh;
while (mesh.faceCount() > targetFaces) {
const e = this.heap.pop();
if (!e) break;
// Lazy re-evaluation: drop stale / dead candidates.
if (!mesh.aliveV[e.u] || !mesh.aliveV[e.v] ||
this.version[e.u] !== e.vu || this.version[e.v] !== e.vv) {
this.stale++;
continue;
}
if (!this.topologyOk(e.u, e.v)) { this.rejectedTopology++; continue; }
const shared = mesh.sharedFaces(e.u, e.v);
// Skip (don't break) overshoots: 1-face boundary collapses can hit odd targets.
if (mesh.faceCount() - shared.length < targetFaces) continue;
if (!this.geometryOk(e.u, e.v, e.pos, shared)) { this.rejectedFlip++; continue; }
this.applyCollapse(e.u, e.v, e.pos);
}
mesh.refreshFaceNormals();
return mesh;
}
applyCollapse deletes the 1–2 shared faces, re-points u’s remaining faces to v, merges Q[v] += Q[u], sets v to the optimal position, bumps both versions, and re-pushes all survivor edges. geometryOk rejects normals with dot(old,new) <= 0 and area below areaEps. Quadrics are the 10 independent coefficients of p·pᵀ; optimal placement solves the 3×3 system from Q_u + Q_v, falling back to the lower-error endpoint when singular.
The full runnable sources (mesh.js, icosphere.js, simplify.js, test.js) are embedded verbatim in SOLUTION.md.
$ cd ~/mesh-simplify && node test.js
[icosphere] collapses=576 stale=8409 rejTop=0 rejFlip=0
[icosphere] V=66 E=192 F=128 chi=2
[icosphere] one-sided Hausdorff=3.8427e-2 limit=6.9282e-2 (1.1093% of diag)
[icosphere] PASS
[torus] F=102 (target 102) chi=0 rejFlip=2
[torus] PASS
[disk] F=115 (target 115) chi=1 rejTop=8
[disk] PASS
ALL TESTS PASSED
Level-4 stress test (F0 = 5120):
$ node /tmp/stress.js
{"F0":5120,"target":512,"F":512,"chi":2,"collapses":2304,
"stale":33897,"rejTop":0,"rejFlip":0,
"minArea":0.009363397517460481,"ms":266}
| Requirement | Result |
|---|---|
| Exactly 10% of original triangles | 1280 → 128 ✅ |
Euler characteristic V − E + F = 2 |
66 − 192 + 128 = 2 ✅ |
| Closed orientable 2-manifold (every edge 1×/2×, single fan per vertex, boundary degree 0/2) | ✅ |
| No degenerate / zero-area triangles | min area > 1e-12 ✅ |
One-sided Hausdorff < 2% of bbox diagonal |
1.1093% ✅ |
Regressions in the same run: torus (χ=0, rejFlip=2 proves the flip guard is live) and open wavy disk (χ=1, rejTop=8 proves the boundary-pinch fix — without it χ jumps to 2/4). All geometry is generated analytically, so the test is deterministic and dependency-free.
# Evidence - Problem class: graphics-quadric-error-mesh-decimation-manifold - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-11T22:51:26.916Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement mesh simplification by edge collapse using Garland-Heckbert quadric error metrics, with a priority queue over candidate collapses and lazy re-evaluation of edges whose costs were invalidated by earlier collapses. Every collapse must preserve a closed orientable 2-manifold: reject face flips, non-manifold edge creation, and collapsing edges whose two endpoints share more than two faces, while still simplifying boundary edges safely. Include a test that decimates an icosphere to exactly 10% of its original triangle count and verifies the Euler characteristic V - E + F = 2 is preserved, no degenerate or zero-area triangles remain, and the one-sided Hausdorff distance to the original surface stays under 2% of the bounding-box diagonal.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "graphics-quadric-error-mesh-decimation-manifold", "provider": "openrouter", "solved_at": "2026-09-11T22:51:26.916Z", "version": "20"}I've built and verified the complete solution. Full self-contained markdown is written to ~/mesh-simplify/SOLUTION.md; the runnable project is in ~/mesh-simplify. Here is the solution:
graphics-quadric-error-mesh-decimation-manifold — decimate a triangle mesh using Garland-Heckbert quadric error metrics (QEM), a priority queue of candidate edge collapses, and lazy re-evaluation of edges invalidated by earlier collapses. Every collapse must keep a closed orientable 2-manifold: reject face flips, non-manifold edge creation, and edges whose two endpoints share more than two faces. Boundary edges must still simplify safely.
A naive QEM simplifier passes some checks and fails the required ones for five separate reasons.
When v absorbs u, the quadrics of every neighbour change, so all stored edge costs incident to v become wrong. Without invalidation the heap pops meaningless costs. Fix: a per-vertex version counter bumped on every position/quadric change; the heap entry stores (vu, vv) and pop() discards entries whose versions no longer match. New incident edges are re-pushed after each collapse.
The usual shortcut (interior edge is collapsible iff link(u) ∩ link(v) is exactly the two opposite vertices) passes a bad collapse where both endpoints of an interior edge lie on the boundary. Measured here on an open disk, that naive test changes V − E + F from 1 to 2 while every edge still looks manifold. The collapse welds boundary arcs together — the vertex-set intersection is blind to it.
Fix (two guards):
- reject an interior edge (shared faces == 2) when both endpoints have positive boundary degree;
- require the merged vertex to have boundary degree 0 or 2 (rejects any boundary pinch).
Moving an endpoint can invert a neighbouring triangle or flatten it. Fix: rebuild each non-shared incident face with the new position and reject if the normal reverses (dot(old,new) <= 0) or the squared area falls below a floor. The torus regression exercises this (rejFlip = 2).
Interior collapses remove 2 faces, boundary collapses remove 1. Hard-coding “stop when F−2 < target” misses odd/exact targets. Fix: read the shared-face count first and skip (not break) candidates that would undershoot, letting a 1-face boundary collapse land exactly on target.
Shared faces > 2 are rejected; combined with the link check and the fan/boundary-degree validators this prevents edges with more than two incident faces.
Project layout (Node 20+, CommonJS, zero dependencies):
mesh-simplify/
├── src/mesh.js # indexed triangle mesh + adjacency
├── src/simplify.js # quadrics, heap, manifold-safe collapse
├── src/icosphere.js # subdivided icosahedron generator
└── test.js # required icosphere test + torus/disk regressions
src/simplify.js)/** Number of boundary edges incident to w (current mesh state). */
boundaryDegreeOf(w) {
const mesh = this.mesh;
const count = new Map();
for (const f of mesh.vertexFaces[w]) {
if (!mesh.aliveF[f]) continue;
for (const x of mesh.faces[f]) {
if (x === w) continue;
count.set(x, (count.get(x) || 0) + 1);
}
}
let bd = 0;
for (const c of count.values()) if (c === 1) bd++;
return bd;
}
/** Boundary degree the merged vertex would have. */
mergedBoundaryDegree(u, v, shared) {
const mesh = this.mesh;
const sharedSet = new Set(shared);
const count = new Map();
const bump = (anchor, f) => {
if (!mesh.aliveF[f] || sharedSet.has(f)) return;
for (const x of mesh.faces[f]) {
if (x === anchor) continue;
count.set(x, (count.get(x) || 0) + 1);
}
};
for (const f of mesh.vertexFaces[u]) bump(u, f);
for (const f of mesh.vertexFaces[v]) bump(v, f);
let bd = 0;
for (const c of count.values()) if (c === 1) bd++;
return bd;
}
topologyOk(u, v) {
const mesh = this.mesh;
const shared = mesh.sharedFaces(u, v);
if (shared.length === 0 || shared.length > 2) return false; // >2 shared faces
const nu = mesh.neighborsOf(u);
const nv = mesh.neighborsOf(v);
let common = 0;
for (const w of nu) if (nv.has(w)) common++;
if (shared.length === 2) {
if (common !== 2) return false; // link condition
for (const f of shared) {
const op = mesh.oppositeVertex(f, u, v);
if (!nu.has(op) || !nv.has(op)) return false;
}
// Reject interior edge whose BOTH endpoints are on the boundary.
if (this.boundaryDegreeOf(u) > 0 && this.boundaryDegreeOf(v) > 0) return false;
} else {
if (common !== 1) return false; // boundary edge
const op = mesh.oppositeVertex(shared[0], u, v);
if (!nu.has(op) || !nv.has(op)) return false;
}
// Merged vertex must be interior (0) or boundary (2), never a pinch.
const bd = this.mergedBoundaryDegree(u, v, shared);
if (bd !== 0 && bd !== 2) return false;
return true;
}
src/simplify.js)simplify(targetFaces) {
const mesh = this.mesh;
while (mesh.faceCount() > targetFaces) {
const e = this.heap.pop();
if (!e) break;
// Lazy re-evaluation: drop stale / dead candidates.
if (!mesh.aliveV[e.u] || !mesh.aliveV[e.v] ||
this.version[e.u] !== e.vu || this.version[e.v] !== e.vv) {
this.stale++;
continue;
}
if (!this.topologyOk(e.u, e.v)) { this.rejectedTopology++; continue; }
const shared = mesh.sharedFaces(e.u, e.v);
// Skip (don't break) overshoots: 1-face boundary collapses can hit odd targets.
if (mesh.faceCount() - shared.length < targetFaces) continue;
if (!this.geometryOk(e.u, e.v, e.pos, shared)) { this.rejectedFlip++; continue; }
this.applyCollapse(e.u, e.v, e.pos);
}
mesh.refreshFaceNormals();
return mesh;
}
applyCollapse deletes the 1–2 shared faces, re-points u’s remaining faces to v, merges Q[v] += Q[u], sets v to the optimal position, bumps both versions, and re-pushes all survivor edges. geometryOk rejects normals with dot(old,new) <= 0 and area below areaEps. Quadrics are the 10 independent coefficients of p·pᵀ; optimal placement solves the 3×3 system from Q_u + Q_v, falling back to the lower-error endpoint when singular.
The full runnable sources (mesh.js, icosphere.js, simplify.js, test.js) are embedded verbatim in SOLUTION.md.
$ cd ~/mesh-simplify && node test.js
[icosphere] collapses=576 stale=8409 rejTop=0 rejFlip=0
[icosphere] V=66 E=192 F=128 chi=2
[icosphere] one-sided Hausdorff=3.8427e-2 limit=6.9282e-2 (1.1093% of diag)
[icosphere] PASS
[torus] F=102 (target 102) chi=0 rejFlip=2
[torus] PASS
[disk] F=115 (target 115) chi=1 rejTop=8
[disk] PASS
ALL TESTS PASSED
Level-4 stress test (F0 = 5120):
$ node /tmp/stress.js
{"F0":5120,"target":512,"F":512,"chi":2,"collapses":2304,
"stale":33897,"rejTop":0,"rejFlip":0,
"minArea":0.009363397517460481,"ms":266}
| Requirement | Result |
|---|---|
| Exactly 10% of original triangles | 1280 → 128 ✅ |
Euler characteristic V − E + F = 2 |
66 − 192 + 128 = 2 ✅ |
| Closed orientable 2-manifold (every edge 1×/2×, single fan per vertex, boundary degree 0/2) | ✅ |
| No degenerate / zero-area triangles | min area > 1e-12 ✅ |
One-sided Hausdorff < 2% of bbox diagonal |
1.1093% ✅ |
Regressions in the same run: torus (χ=0, rejFlip=2 proves the flip guard is live) and open wavy disk (χ=1, rejTop=8 proves the boundary-pinch fix — without it χ jumps to 2/4). All geometry is generated analytically, so the test is deterministic and dependency-free.
# Evidence - Problem class: graphics-quadric-error-mesh-decimation-manifold - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-11T22:51:26.916Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement mesh simplification by edge collapse using Garland-Heckbert quadric error metrics, with a priority queue over candidate collapses and lazy re-evaluation of edges whose costs were invalidated by earlier collapses. Every collapse must preserve a closed orientable 2-manifold: reject face flips, non-manifold edge creation, and collapsing edges whose two endpoints share more than two faces, while still simplifying boundary edges safely. Include a test that decimates an icosphere to exactly 10% of its original triangle count and verifies the Euler characteristic V - E + F = 2 is preserved, no degenerate or zero-area triangles remain, and the one-sided Hausdorff distance to the original surface stays under 2% of the bounding-box diagonal.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "graphics-quadric-error-mesh-decimation-manifold", "provider": "openrouter", "solved_at": "2026-09-11T22:51:26.916Z", "version": "20"}