Reduces the number of triangles of a mesh to a ratio of the original while keeping its shape as closely as the method allows.
How the precision is kept
Arithmetic is 64-bit, but the result is an approximation by design: edges are collapsed in order of a quadric error, and a collapsed edge is replaced by its midpoint. The accuracy of the shape is set by the ratio asked for, not by the number type.
Calculations under this policy
4 calculations in 1 source file. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
Adds each triangle's plane to the error quadric of its three vertices.
n = unit((b − a) × (c − a)), d = −n·a; Q(v) += [a², ab, ac, ad, b², bc, bd, c², cd, d²]
Planes are unit normals with d = −n·a, added without area weighting into a Float64Array. A triangle of zero area gives a zero normal and adds nothing.
mesh/modifiers.js
lines 174 to 181
ModelCraft 0.8.1
const addQ = (v, a, b, c, d) => { const o = v * 10; Q[o] += a * a; Q[o + 1] += a * b; Q[o + 2] += a * c; Q[o + 3] += a * d; Q[o + 4] += b * b; Q[o + 5] += b * c; Q[o + 6] += b * d; Q[o + 7] += c * c; Q[o + 8] += c * d; Q[o + 9] += d * d; };
const vt = Array.from({ length: nv }, () => []);
for (let t = 0; t < nt; t++) {
const [a, b, c] = [tri[t * 3], tri[t * 3 + 1], tri[t * 3 + 2]];
const A = [P[a * 3], P[a * 3 + 1], P[a * 3 + 2]], n = norm(cross(sub([P[b * 3], P[b * 3 + 1], P[b * 3 + 2]], A), sub([P[c * 3], P[c * 3 + 1], P[c * 3 + 2]], A)));
const d = -dot(n, A);
for (const v of [a, b, c]) { addQ(v, n[0], n[1], n[2], d); vt[v].push(t); }
}
Border planes
64-bit
Adds a plane square to the face through each open border edge, so borders stay in place.
n = unit((B − A) × face normal), d = −n·A; added four times with n and d multiplied by 10
Each border plane is scaled by 10 before it is squared into the quadric and is added four times, so it weighs 400 times a face plane at each of the edge's two vertices.
mesh/modifiers.js
lines 182 to 191
ModelCraft 0.8.1
// open borders: a plane square to the face through the edge keeps them in place
const ek = new Map();
for (let t = 0; t < nt; t++) for (let k = 0; k < 3; k++) { const a = tri[t * 3 + k], b = tri[t * 3 + (k + 1) % 3]; const key = a < b ? a + ',' + b : b + ',' + a; ek.set(key, (ek.get(key) || 0) + 1); }
for (let t = 0; t < nt; t++) for (let k = 0; k < 3; k++) {
const a = tri[t * 3 + k], b = tri[t * 3 + (k + 1) % 3], key = a < b ? a + ',' + b : b + ',' + a;
if (ek.get(key) !== 1) continue;
const A = [P[a * 3], P[a * 3 + 1], P[a * 3 + 2]], B = [P[b * 3], P[b * 3 + 1], P[b * 3 + 2]], c = tri[t * 3 + (k + 2) % 3];
const fn = norm(cross(sub(B, A), sub([P[c * 3], P[c * 3 + 1], P[c * 3 + 2]], A))), n = norm(cross(sub(B, A), fn)), d = -dot(n, A);
for (const v of [a, b]) for (let r = 0; r < 4; r++) addQ(v, n[0] * 10, n[1] * 10, n[2] * 10, d * 10);
}
The ten terms are added in one expression. They are the expansion of squared plane distances about the origin and nearly cancel when the coordinates are large compared with the distances, so the cost loses digits for a mesh far from its origin; a negative sum is clamped to 0.
mesh/modifiers.js
lines 192 to 198
ModelCraft 0.8.1
const cost = (a, b) => {
const o = new Float64Array(10);
for (let i = 0; i < 10; i++) o[i] = Q[a * 10 + i] + Q[b * 10 + i];
const x = (P[a * 3] + P[b * 3]) / 2, y = (P[a * 3 + 1] + P[b * 3 + 1]) / 2, z = (P[a * 3 + 2] + P[b * 3 + 2]) / 2;
const e = o[0] * x * x + 2 * o[1] * x * y + 2 * o[2] * x * z + 2 * o[3] * x + o[4] * y * y + 2 * o[5] * y * z + 2 * o[6] * y + o[7] * z * z + 2 * o[8] * z + o[9];
return { e: Math.max(0, e), p: [x, y, z] };
};
Collapse test
64-bit
Decides whether the cheapest edge is collapsed now, put back with a new cost, or skipped.
put back when e > e₀·(1 + 1e-9) + 1e-18; skip when (new normal)·(old normal) ≤ 0 for any triangle that stays
The stale-entry test has a relative part of 1e-9 and an absolute part of 1e-18. The flip test compares unnormalized cross products of the triangle before and after the collapse; a product of exactly zero counts as a flip.
mesh/modifiers.js
lines 210 to 223
ModelCraft 0.8.1
// an entry made before its ends' quadrics grew is put back at today's cost
const { e, p } = cost(a, b);
if (e > e0 * (1 + 1e-9) + 1e-18) { push(e, a, b); continue; }
// the triangles that would flip are a reason to skip this collapse
let flips = false;
for (const v of [a, b]) for (const t of vt[v]) {
if (!alive[t]) continue;
const vs = [0, 1, 2].map((k) => find(tri[t * 3 + k]));
if (vs.includes(a) && vs.includes(b)) continue;
const q = vs.map((x) => (x === a || x === b ? p : [P[x * 3], P[x * 3 + 1], P[x * 3 + 2]]));
const before = vs.map((x) => [P[x * 3], P[x * 3 + 1], P[x * 3 + 2]]);
if (dot(cross(sub(q[1], q[0]), sub(q[2], q[0])), cross(sub(before[1], before[0]), sub(before[2], before[0]))) <= 0) { flips = true; break; }
}
if (flips) continue;
In detail
Method
Quadric edge collapse (Garland and Heckbert, Surface Simplification Using Quadric Error Metrics, 1997, as cited in the code), with the new vertex at the edge's midpoint and a lazy heap of candidate edges.
Number types
Quadrics in a Float64Array of 10 numbers per vertex; positions copied with slice from a Float64Array.
Tolerances
A heap entry is put back when today's cost exceeds its stored cost × (1 + 1e-9) + 1e-18. A collapse that would turn a triangle over (dot product of the old and new normals ≤ 0) is skipped. The target is at least 4 triangles.
Limits
The new vertex is the midpoint, not the point that minimizes the quadric error. The error is evaluated from plane coefficients about the mesh's origin, so its terms nearly cancel for a mesh far from the origin; a negative result is clamped to 0.
Approach: 64-bit, stated limit
The arithmetic is 64-bit, but the method or the data sets the accuracy: a solver tolerance, a mesh, a step size, a datum shift, a table. The limit is stated where the result is shown.