how it works

The four algorithms worth explaining

None of this is novel. It is the standard set of techniques for the job, written down so that you can predict the output instead of guessing, and so that a surprising result can be traced to a decision rather than to magic.

Quadric error edge collapse

Decimation removes one edge at a time. Collapsing the edge between two vertices merges them into a single vertex, which deletes the two triangles that shared the edge and rewires the rest of their neighbourhoods.

Each vertex carries a symmetric 4×4 matrix, its quadric, built by summing the outer product of the plane equation of every incident triangle with itself and weighting it by triangle area. The squared distance from a candidate point to all those planes is then one matrix product, which is the whole reason this representation is used: the cost of a collapse is evaluated without revisiting the geometry.

For a candidate edge the two quadrics are added. The optimal position is the solution of the 3×3 linear system taken from the summed matrix. We solve it by Cholesky factorisation with a condition check; when the matrix is close to singular - which happens on flat regions, where every point along a line is equally good - we fall back to the cheapest of the two endpoints and the midpoint. That fallback is the reason a decimated planar grid keeps its original vertices instead of drifting.

Candidates live in a binary heap keyed by cost. After a collapse, the costs of the edges around the new vertex change, so the heap would need deletions it cannot do. Instead each entry stores the version counter of its two endpoints; a popped entry whose counter is stale is discarded and the edge is re-pushed with a fresh cost. Roughly 2.4 entries are popped per accepted collapse on typical scan data, and that ratio is the main reason decimation is not faster.

What blocks a collapse

A collapse is rejected, regardless of cost, when any guard fires. Guards are checked in this order because that is the order of increasing expense:

Guard 3 is the classic link condition: the one-ring vertex sets of the two endpoints may intersect only in the vertices of the two shared faces. It is cheap, it is necessary, and it is why a decimator cannot be written as a simple loop over sorted edges.

Ridge detection and chaining

An edge is sharp when the angle between the normals of its two faces exceeds the threshold. The sign of that angle, measured against the edge direction, separates a convex ridge from a concave valley.

Detection is the easy half. Chaining is where the decisions are. Sharp edges form a graph on the mesh vertices; we walk it and emit maximal paths, splitting at any vertex of degree three or more, at any change of sign, and at any vertex where the angle leaves the band between min_angle_deg and max_angle_deg. Chains shorter than min_edges are dropped last, after splitting, which matters: a long chain cut by two junctions can produce fragments that the filter then removes.

The upper bound deserves a word. An edge whose faces fold back onto each other has a dihedral angle near 180°, and on scan data that nearly always means a zipper artefact rather than a feature. Keeping those edges produces polylines that zigzag across a flat region, so the default excludes them.

Boundary loops are not sharp edges at all - they have one face - but they are usually wanted in the same output, so they are emitted as RidgeKind::Boundary when asked for, after the sharp chains and with closed set where appropriate.

The hierarchy

Self-intersection search and surface projection both need a spatial index over triangles. Both use the same structure: a bounding-volume hierarchy over axis-aligned boxes, built top down by splitting at the median of the centroid along the widest axis, with eight triangles per leaf.

Construction is a single sort per level over an index array; the triangles themselves are never moved. For two million triangles the build takes 0.31 seconds single-threaded and the tree occupies about 24 MB, which is the dominant term in the peak memory figures on the benchmarks page.

The intersection search descends the tree against itself, which gives the pairs in a deterministic order, and skips any node pair whose boxes do not overlap. With ignore_adjacent on, pairs sharing a vertex are discarded at the leaf, not at the node, because adjacency is not a property of a box.

Filtered predicates

Deciding whether two triangles touch is a sign question, and signs computed in floating point are unreliable near zero. We use the usual two-stage approach: evaluate the determinant in double precision together with an error bound, and when the magnitude falls below that bound, recompute the same expression in exact arithmetic built from error-free transformations. No tolerance is exposed, because there is none - the answer is the true sign of the determinant of the input coordinates.

The exact path is taken on about 0.002 % of the tests on well-conditioned meshes and up to 4 % on meshes that have been welded with a large tolerance, which is the main reason an over-welded mesh searches slowly.

The remeshing loop

One iteration, in this order, with L the target edge length:

1. Split every edge longer than ⁴⁄₃ L at its midpoint.
2. Collapse every edge shorter than ⁴⁄₅ L, subject to the same link condition as decimation.
3. Flip interior edges when the flip brings the four incident valences closer to six.
4. Move each unlocked vertex to the area-weighted centroid of its neighbours, then remove the component of that motion along the vertex normal.
5. If project_to_input is set, project every moved vertex onto the nearest point of the original surface.

Those fractions are the conventional ones and are not configurable; they keep the edge-length histogram from oscillating between the split and collapse stages. Feature edges, meaning edges above feature_angle_deg, are excluded from steps 1 to 4, so a remeshed cube keeps twelve straight arrises and does not grow rounded corners.

Determinism

Two runs of the same version on the same input with the same options produce byte-identical output. That is a tested property, not an aspiration, and it holds because of four rules:

• Every container whose iteration order could reach the output is ordered. There is no unordered_map anywhere in the data path.
• Equal costs in the collapse heap are broken by the smaller vertex index, never by insertion order.
• Parallel sections only compute per-element values - quadrics, box bounds, candidate pairs - and the merge step sorts by index before anything is consumed.
• No floating-point reduction is parallelised, because summation order would change the last bits and with them the collapse order.

Determinism across versions is explicitly not promised: any change to the metric or the guards reorders collapses. The changelog marks the releases where output changed for unchanged input.