Convex decomposition of an arbitrary solid

[GeneralPawz]

Problem

axiolid has no convex decomposition: no way to take an arbitrary
(possibly non-convex, possibly multi-component) TriMesh and produce a set
of convex pieces whose union is the original solid.

Why it matters

This is the missing prerequisite for #88 (general Minkowski sum and
difference). The Minkowski sum of two CONVEX polyhedra is the convex hull of
the pairwise vertex sums, which is tractable and exact. For non-convex
operands there is no such shortcut: the standard construction decomposes both
operands into convex pieces, takes the pairwise sums, and unions the results.

Without decomposition, #88 has only two honest options, and both are bad:

• restrict to convex operands, which silently narrows the published
  capability to a case most real geometry does not satisfy, or
• attempt a general implementation whose cost is exponential in the
  non-convexity of the inputs.

convex_hull already exists (crates/algorithms/construction/construct),
so the convex end of this is solved. The decomposition itself is not.

Scope

• Decompose a closed, two-manifold TriMesh into convex parts.
• Report the decomposition rather than asserting it: part count, and whether
  the result is an exact decomposition or an approximate one within a stated
  bound. An approximate decomposition is legitimate and widely used, but it
  must be labelled, not passed off as exact.
• Bounded refusal for inputs that are not closed or not two-manifold, rather
  than producing parts whose union is not the input.
• Deterministic part ordering, matching the discipline decimate established.

Done when

• an arbitrary closed two-manifold solid decomposes into convex parts
• the union of the parts reproduces the input within a stated tolerance,
  verified by a volume-conservation test rather than by index comparison
• exact vs approximate decomposition is reported, never implied
• a non-manifold or open input is refused by name
• part ordering is deterministic across runs

Blocks

#88

[GeneralPawz]

Work in progress on branch wip/96-convex-decompose (e31808f). Not on main — it does not yet meet its own acceptance criteria, and I would rather report that than merge something that decomposes a solid into parts which are not solids.

Design, as agreed

Both strategies behind one contract, so the caller switches per need:

convex_decompose(&mesh, Strategy::Exact, tolerance)
convex_decompose(&mesh, Strategy::Approximate { max_concavity }, tolerance)
    -> Result<Decomposition, DecomposeError>

Decomposition { parts: Vec<TriMesh>, fidelity: Fidelity, splits: usize }
Fidelity::Exact
Fidelity::Approximate { requested, achieved }

achieved is reported separately from requested so the ask can never be mistaken for the outcome — a caller that asked for 10mm and got 2mm can see that.

What works (8 of 9 tests)

• convex input yields exactly one part, zero splits, Fidelity::Exact
• volume conservation — parts sum to 3.0 on an L-shape whose true volume is 3.0
• open surface refused by name with its boundary-edge count
• ragged indices, out-of-range indices, non-positive bound all refused
• deterministic part ordering across runs
• approximate strategy never reports Fidelity::Exact

Two design errors found by the tests

Concavity measured against the hull surface reports zero. A reflex vertex generally lies exactly on its own convex hull — the hull spans the notch with a face passing through that vertex. The L-shape never split. Now measured against the solid's own face planes: a solid is convex exactly when every vertex lies behind every face plane, and the distance in front is the notch depth. Finds depth 1.0 on the L-shape.

Parts built as hulls of point subsets inflate the volume. Hulling a subset fills in any notch that subset still spans; the parts summed to 3.5 against a true 3.0. Parts are now produced by clipping the actual solid, and volume is conserved.

The blocker

Clipping produces the correct sides, but the cap over the cut is not watertight. Cut edges arrive one triangle at a time in arbitrary order; capping needs them stitched into ordered loops, then triangulated in the cut plane.

I implemented loop stitching on a tolerance lattice and reused axiolid_reference::polygon::triangulate_simple (ear clipping, already in-tree, refuses partial fans) rather than writing a second triangulator. That took the L-shape's parts from 8 unmatched boundary edges to 5 — real progress, still open.

Remaining causes, not yet isolated:

• a cut cross-section that stitches into more than one loop, where one loop is a hole rather than an outer ring
• loops whose endpoints straddle the quantisation lattice and fail to chain
• ear clipping refusing a loop that is not simple after projection

Recommendation

Robust mesh clipping with watertight caps is the hard part of this issue, and it is a well-known hard part. I would rather land it correctly than iterate on the cap heuristically. The clean options are to finish the loop stitching properly with a dedicated test suite for the capper alone (it deserves its own tests, independent of decomposition), or to build the cap on the existing boolean provider, which already solves half-space clipping robustly — that is worth checking before writing more geometry code.

main is unaffected and gates green.

[GeneralPawz]

Landed in 4a7ba77. Both the switchable splitter and the decomposition itself are working.

The switch you asked about

algorithms may not depend on providers — the gate enforces it:

"algorithms" => matches!(to, "foundation"|"representations"|"contracts"|"algorithms")

So the provider arrives through the mesh-boolean contract, which both layers may depend on. That makes the switch a per-call parameter rather than a build-time flag:

convex_decompose(&mesh, strategy, tol)                              // hand-rolled, no backend
convex_decompose_with(&mesh, strategy, tol, &Splitter::HandRolled)
convex_decompose_with(&mesh, strategy, tol, &Splitter::Provider(&boolmesh))

Same Decomposition type either way. The two are independent implementations of the same contract, so each is evidence about the other — both_splitters_produce_the_same_solid compares the resulting solid, not each path's own claims.

The cap: four wrong attempts and why

Each of the first four tried to PREDICT the cut cross-section from the input, deciding per triangle whether an edge bounded the cut:

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

Every rule fixed one defect and reintroduced the other. That is the signature of the wrong question, not 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 measure 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 other design errors, both caught by tests

• Concavity vs. the convex hull reports zero. A reflex vertex lies on its own hull — the hull spans the notch with a face through that vertex — so the L-shape never split. Now measured against the solid's own face planes.
• Parts as hulls of point subsets inflate volume (3.5 against a true 3.0), because hulling a subset fills the notch it spans. Parts are clipped from the actual solid.

Done-when checklist

criterion	status
arbitrary closed two-manifold solid decomposes into convex parts	met
union reproduces input, verified by volume not index comparison	met — L-shape and a 4-reflex-corner cross, both splitters
exact vs approximate reported, never implied	met — Fidelity carries requested and achieved
non-manifold or open input refused by name	met — NotASolid { boundary, non_manifold }
deterministic part ordering	met

Mutation evidence:

• capping from predicted edges rather than open ones — 7 failures
• coplanar faces kept by both sides — 13 failures
• skipping reflex detection — 3 failures

Workspace 1183 passed, 0 failed. Gate green. #88 is now unblocked.