Quadric Error Metrics: The Mathematics Behind Mesh Decimation

Quadric error metrics, or QEM, give a mesh simplifier a fast estimate of how much an edge contraction moves the surface away from its accumulated local planes. Michael Garland and Paul Heckbert introduced the method in 1997. Its combination of compact state, inexpensive evaluation, and good practical results made it a foundation of many modern decimators.

QEM is not a visual truth oracle. The classic metric approximates geometric plane distance. It needs topology checks, boundary handling, feature constraints, attribute treatment, and final image validation to become a production pipeline.

From a triangle to a plane#

Take a nondegenerate triangle with a normalized plane equation:

ax + by + cz + d = 0

The vector (a, b, c) is the unit normal and d positions the plane. For any point v = (x, y, z), the signed distance to this normalized plane is ax + by + cz + d. Squaring it removes the sign and penalizes larger deviations:

(ax + by + cz + d)²

Write the point in homogeneous form as [x, y, z, 1] and the plane as p = [a, b, c, d]. The squared expression becomes v-transpose × (p × p-transpose) × v. The outer product p × p-transpose is a symmetric 4 × 4 matrix called a fundamental quadric for that plane.

A symmetric 4 × 4 matrix has 10 unique components rather than 16 because values mirror across the diagonal. That compact representation matters when every vertex carries a quadric.

The normalization of (a, b, c) matters. If one face plane uses a normal 10 times longer, its squared distance contribution becomes 100 times stronger. Normalize unless a deliberate area or feature weighting says otherwise.

Accumulating planes at a vertex#

For each original vertex, sum the quadrics of its incident face planes. Evaluating the sum at a candidate point gives the sum of squared distances to those planes.

On a broad flat region, all incident faces have nearly the same plane. Moving within that plane costs little; moving away costs more. Near a corner where several distinct planes meet, a candidate must stay close to all of them, so the quadric strongly prefers the intersection. This is why basic QEM often preserves hard geometric structure better than a shortest-edge rule.

Face quadrics can be weighted by triangle area. Without weighting, a cluster of many tiny noisy triangles can dominate one large face because each plane contributes equally. With area weighting, each plane contributes in proportion to represented surface area. Neither choice is universally correct: tiny triangles might encode a real sharp feature that area weighting suppresses.

Record the weighting policy. “Uses QEM” is not enough to reproduce a result.

Combining two vertices#

For a proposed contraction of vertices u and v into replacement position w, add their accumulated quadrics:

Q = Q-u + Q-v

Then evaluate w-transpose × Q × w. This scalar is the candidate contraction cost under the classic metric.

The addition is what makes QEM efficient and history-aware. The new vertex carries the combined quadric, which represents planes accumulated from both contraction histories. The simplifier does not need to keep every original triangle around for basic cost evaluation.

Repeated addition can count some plane evidence more than once depending on the contraction history and formulation. The original work discusses the approximation. In practice, the compact metric is valuable because it predicts useful local damage at low cost, not because it computes exact Hausdorff distance.

Finding the optimal replacement position#

The best unconstrained w minimizes the quadratic form while its homogeneous fourth coordinate remains 1. This yields a 3 × 3 linear system derived from the upper-left part of Q and the terms involving d.

If that system is invertible and well-conditioned, solve it for x, y, and z. The solution can lie somewhere along the edge or elsewhere in local space depending on the metric and allowed contraction.

The system can be singular. On a perfectly flat patch, distance to one plane does not constrain movement within the plane, leaving infinitely many equal solutions. Implementations need fallback candidates, commonly:

endpoint u;
endpoint v;
edge midpoint;
the lowest-cost of those three;
a constrained point along the edge segment;
a regularized solve;
a feature-line intersection when specialized constraints exist.

Evaluate fallback costs with the same combined quadric. A robust method does not emit NaN coordinates because a matrix inversion failed.

Placement policy affects shape. Restricting w to an endpoint preserves original samples but can produce worse approximation. Allowing an unconstrained optimum improves geometric fit but may cross boundaries, leave the local neighborhood, or change attributes more severely. Add validity filters.

Candidate ordering#

At initialization, compute a cost and placement for every eligible edge, then place candidates in a priority queue ordered by cost. Pop the lowest candidate, confirm that it is still current and valid, collapse it, and update edges in the affected one-ring neighborhood.

A mesh with 100,000 vertices can have roughly 300,000 edges for a large closed triangular manifold, following Euler relationships with local variation. Recomputing every edge after each collapse would be wasteful. Local updates and a heap give practical performance, though stale queue entries need versioning or replacement.

One sequence is:

build connectivity and incident face planes;
accumulate one quadric per vertex;
create eligible edge candidates;
solve or choose replacement positions;
queue candidates by cost;
pop the cheapest current candidate;
run topology and geometry filters;
perform the contraction and add quadrics;
update the local neighborhood;
stop at count, error, or validity limit.

Deterministic tie breaking is important for build reproducibility. Equal or nearly equal costs occur on regular surfaces. Sort by stable vertex identifiers after cost, or document nondeterminism.

Edge collapse versus arbitrary pair contraction#

The original QEM paper discusses contracting vertex pairs, including unconnected pairs within a threshold. Pair contraction can join separate surface regions and close small gaps, producing stronger reduction or repair-like behavior. It can also create non-manifold topology and bridge parts that should remain separate.

Many production simplifiers restrict candidates to actual edges. CGAL's surface-mesh simplification framework collapses edges and requires suitable manifold graph concepts. This makes topology behavior easier to constrain.

Choose deliberately:

edge-only contraction preserves connectivity more predictably;
arbitrary pairs can join disconnected components;
a proximity threshold must be expressed in asset-scale units;
semantic components may need permanent separation;
watertightness and genus policies must be explicit.

For a product model with a 0.5-millimeter designed gap, pair contraction at 1 millimeter can weld moving parts. For noisy scan fragments, that same behavior may be desirable.

Boundary quadrics#

Classic face planes may not strongly resist movement along or across an open boundary. Add virtual constraint planes for boundary edges. One common construction creates a plane through the boundary edge and perpendicular to its adjacent face, then applies a configurable weight.

Higher boundary weight keeps the edge near its original line. Infinite locking preserves it completely but may prevent a target. Low weight permits smoother reduction but can shrink openings and alter silhouettes.

Distinguish boundaries:

intentional outer silhouette;
designed hole or opening;
modular seam hidden by another part;
accidental scan hole;
UV seam with no geometric opening;
material border on a continuous surface.

Only the first four are geometric boundary cases, and they may need different policies. A UV seam often duplicates rendered vertices while geometric connectivity can remain conceptually continuous.

Sharp features and line constraints#

Two faces meeting at a strong dihedral angle define a crease. Plane quadrics already penalize leaving both planes, but aggressive contraction can shorten or erase the feature. Add line quadrics, feature-plane weights, or lock selected edges and corner vertices.

Automatic feature detection uses a dihedral threshold such as 45 degrees, but thresholds have failure modes. A designed 30-degree crease can be important; a noisy scan can contain thousands of accidental 50-degree changes. Feature tags from CAD or artists are stronger when available.

Use a hierarchy:

locked semantic landmarks;
protected boundary and material features;
weighted detected creases;
ordinary curvature handled by base quadrics.

If every edge is protected, simplification stops. Report constraint saturation and route the asset for review.

Topology validity is separate from error#

A contraction with near-zero quadric cost can still create invalid topology. Flat overlapping regions are a classic risk. Before collapse, test the link condition or equivalent topology rule for the mesh type. Reject operations that create non-manifold vertices or edges when the output requires a manifold surface.

Geometry filters should also reject:

flipped incident triangles;
zero or near-zero triangle area;
self-intersection beyond policy;
replacement outside a permitted envelope;
excessive normal change;
component joins or splits that are forbidden;
inverted local volume.

These filters alter the greedy path. Rejecting one cheap edge makes the next candidate win, which changes later quadrics and output. Validation cannot simply repair everything after reaching the count.

Attribute-aware quadrics#

The surface is more than XYZ. Garland and Heckbert extended quadric ideas to color and texture. Modern implementations may add attribute deviation terms or use separate weighted penalties.

For a vertex carrying two UV components, three normal components, and four color components, an extended representation has many more dimensions. Direct high-dimensional quadrics increase storage and computation. Practical tools use specialized formulations, attribute gradients, wedge handling, or independent penalties.

Normalize scales. A 1-meter position change, a UV change of 1, and an 8-bit color change of 1 have different perceptual meanings. Define weights using maximum acceptable errors:

1 millimeter position deviation;
0.25 texel UV shift at a 2048 map;
1 degree normal change in a highlight-critical region;
a color-space difference tied to display review;
a skin-weight change tested in motion.

UV seams create multiple attribute values at one geometric position. A wedge-aware simplifier can treat corner attributes independently while sharing geometry. A naive weld corrupts the seam.

Error units and normalization#

QEM cost is typically a squared-distance-like quantity, accumulated and weighted. It is not automatically “millimeters of maximum surface error.” A cost of 0.0001 has meaning only with model units, weighting, normalization, and formulation.

Tools may report a relative error normalized by mesh extent. Meshoptimizer documentation, for example, distinguishes relative error and scaling to absolute error in its simplification API. Read the tool's contract before setting a threshold.

For acceptance, calculate independent distances against the source:

vertex-to-surface or sampled point-to-surface distance;
symmetric Hausdorff approximation;
normal deviation;
silhouette displacement in pixels;
rendered image differences.

QEM chooses contractions; independent metrics verify the completed result.

A small numerical intuition#

Imagine two perpendicular infinite planes x = 0 and y = 0. A point w = (x, y, z) has summed squared distance x² + y². Any point on their intersection line, where x = 0 and y = 0, has zero cost regardless of z. The system is singular along that line.

Add a third plane z = 0 and the cost becomes x² + y² + z². The unique minimum is the corner at (0, 0, 0). This is why corners constrain optimal placement more fully than planar or crease regions.

With weights 10 for x = 0 and 1 for y = 0, cost is 10x² + y². Movement away from the first plane is penalized 10 times more. Boundary and feature weights use this principle, though real meshes accumulate many non-axis-aligned planes.

Implementation diagnostics#

Log more than final triangles:

initial and final vertices, edges, and faces;
accepted and rejected contractions;
rejection reasons;
cost distribution over time;
singular solves and fallback choice counts;
maximum and accumulated reported error;
number of locked or constrained edges;
processing time and peak memory;
deterministic output hash;
independent post-simplification errors.

If 70% of popped candidates fail a normal-flip test, the input or placement policy may need attention. If most solves use endpoints on a smooth mesh, the system may be singular, poorly conditioned, or implemented incorrectly.

Visualize contraction cost as a heat map. Unexpected low costs along a critical boundary or high costs on a flat plane expose weighting and topology issues.

QEM production workflow#

Validate triangulation and connectivity.
Classify boundaries, creases, components, and semantic landmarks.
Choose plane weighting and pair eligibility.
Define placement and singular fallback policy.
Add topology, flip, envelope, and attribute filters.
Generate several count and error candidates.
Export with final normals, tangents, UVs, and materials.
Measure independent object- and screen-space error.
Test animation and runtime where applicable.
store configuration, logs, and reference images.

QEM review checklist#

Face normals used for planes are valid and intentionally weighted.
Symmetric quadrics use stable numeric precision.
Singular placement has deterministic fallbacks.
Candidate queue entries cannot apply stale topology.
Pair contraction cannot join components unless explicitly allowed.
Boundary and crease weights correspond to feature policy.
Link and geometric validity tests run before every contraction.
Attribute scales and weights have perceptual justification.
Reported QEM cost is not mislabeled as exact surface distance.
Independent distance and image metrics validate the output.
Constraint saturation is reported when the target cannot be reached.
Output is reproducible from source, tool version, and settings.

Sources and further reading#

QEM turns local plane evidence into a compact quadratic cost that can guide millions of contraction decisions. Its power comes from that efficient approximation; its reliability comes from the constraints, attribute policies, and independent validation built around it.