Crate axiolid_decompose

Convex decomposition: a solid as a set of convex parts.

Two strategies, one contract

There is no single right answer here, so the caller picks:

• Strategy::Exact splits at reflex features until every part is genuinely convex. The union reproduces the input exactly, and the part count can be large.
• Strategy::Approximate stops once each part is convex to within a stated concavity bound. Far fewer parts, and the union is close to but not identical to the input.

Both are legitimate. Collision detection and Minkowski sums usually want the approximate one; anything claiming to reproduce the original solid needs the exact one. What is NOT legitimate is returning an approximate decomposition that presents itself as exact, so Decomposition always reports which it is, and the approximate path reports the concavity it actually reached rather than the one that was requested.

Method

Both strategies share one loop: measure the worst concavity of a part, and if it exceeds the bound, split the part by a plane and recurse. They differ only in the bound – exact uses zero (to tolerance).

Concavity is measured as the largest distance from a vertex of the part to its own convex hull. That is a direct measurement of the property the caller cares about, rather than a proxy like volume ratio: a thin deep notch barely changes volume but is exactly what breaks a convexity assumption downstream.

The split plane is the plane of the face the reflex vertex sticks out past. Extending an existing face makes progress by definition, whereas a bounding-box axis through the same point need not separate the notch.

Capping a cut: measure, do not predict

Closing the cut is the hard part, and the first four attempts all failed in the same shape. Each tried to PREDICT the cross-section from the input mesh, deciding per triangle whether an edge bounded the cut. Measured on an L-shaped solid:

rule	boundary edges	non-manifold edges
strict sign changes only	5	0
plus vertices lying on the plane	0	3
plus a straddling filter	3	0
plus the two-vertices-on-plane case	1	3

Every rule fixed one defect and reintroduced the other, which is the signature of the wrong question rather than a missing case: whether a wall standing ON the cut plane bounds THIS part depends on which side the material lies, and a single triangle cannot see that.

The fix is to stop predicting. Clip first, then look at what the shell actually left open: in a closed mesh every undirected edge is used exactly twice, so the edges used ONCE are precisely the hole. The cap fills exactly that, and can be neither too generous nor too strict whatever the clipping did upstream.

Two splitters

The hand-rolled clipper above needs no boolean backend, which matters because this crate should be usable without one. A caller that already has a boolean provider can pass it instead, per call.

Because algorithms may not depend on providers – the architecture gate enforces it – the provider arrives through the mesh-boolean CONTRACT, which both layers may depend on. See split::Splitter. The two paths are independent implementations of the same contract, so each is evidence about the other, and the tests check they agree on the resulting solid rather than merely on their own claims.

Modules

split

Splitting a solid by a plane, either hand-rolled or via a boolean provider.

Structs

Decomposition

A solid expressed as convex parts, with the evidence to judge it.

Enums

DecomposeError

Why a decomposition could not be produced.

Fidelity

Whether the parts reproduce the input or merely approximate it.

Strategy

How hard to work at making each part convex.

Functions

convex_decompose

Decompose a closed two-manifold solid into convex parts.

convex_decompose_with

Decompose a solid, choosing how parts are cut.