General Minkowski sum and difference

[GeneralPawz]

Problem

#78 delivered constant-distance offset and shelling, and explicitly narrowed
general Minkowski sum out of scope with the reasoning recorded: offset by a
sphere is the special case worth having, the general operation is
substantially heavier, and "CGAL has it" is not by itself a product
requirement.

That narrowing was right at the time. This issue exists so the gap is
tracked rather than forgotten, and so it is picked up when a consumer needs
it — not before.

Manifold has MinkowskiSum / MinkowskiDifference; CGAL has
minkowski_sum_3.

Why it matters

The named consumer, when it appears, is clearance and tool-path work:
sweeping a cutter profile along a path, or growing an obstacle by a robot's
footprint to test reachability. Both are Minkowski sums with a non-spherical
structuring solid, which #78's miter offset cannot express.

Blocked on

A named consumer. This is deliberately not scheduled. Do not implement it
speculatively — the v0.9 offset work covers the cases we currently have, and
this issue should stay open until something concrete needs it.

Scope (when unblocked)

• Minkowski sum of two convex planar-faced solids, which is the tractable
  case: the sum of two convex polyhedra is the convex hull of the pairwise
  vertex sums, and Convex hull provider over point sets and meshes #76's hull already provides that.
• Non-convex operands by convex decomposition, summing pairwise and unioning
  through General exact boolean over planar-faced solids #77's exact boolean.
• Refusal by name for curved operands, matching the rest of v0.9.

Not in scope

• Minkowski on meshes with attributes.
• Any GPU path.

Verification

• bash scripts/gate.sh
• The Minkowski sum of two boxes is a box with summed extents, volume-checked
  against the closed form.
• A convex sum agrees with the convex hull of pairwise vertex sums.
• A non-convex sum agrees with the union of its per-part sums.
• Every result passes v0.7 diagnosis.
• Mutation probe: skip the convex decomposition and treat a non-convex
  operand as convex; the non-convex volume test must fail.

[GeneralPawz]

Blocked on #96 (convex decomposition), filed as the prerequisite.

The Minkowski sum of two CONVEX polyhedra is the convex hull of the pairwise vertex sums — tractable and exact. For non-convex operands the standard construction needs both operands decomposed into convex pieces first. Without #96 this issue has only two honest options: silently narrow the published capability to convex-only, or ship something exponential in the non-convexity of the inputs.

Sequence agreed with @GeneralPawz: #84 (done, 349b7ff) -> #86 -> #87 -> #96 -> #88.

[GeneralPawz]

Landed in 93b1280.

Scope note

This issue was gated on "blocked on a named consumer — do not implement speculatively." That gate was waived on explicit direction, not overlooked. Recording it here so the reasoning in the issue body isn't silently contradicted by the commit history: the consumer named in the issue (clearance / tool-path work) still does not exist in-tree.

What shipped

minkowski_sum(&a, &b, tol)                          // convex operands, no backend needed
minkowski_sum_with(&a, &b, tol, &provider)          // arbitrary, via decomposition + union
minkowski_difference_with(&a, &b, tol, &provider)   // erosion

The convex sum is the convex hull of pairwise vertex sums — exact, and needs no boolean solver. Non-convex operands decompose through #96, sum pairwise, and union through the provider (reached via the contract, since algorithms may not depend on providers).

The difference is not the sum run backwards

Worth stating because computing it as one is a silent error. A ⊖ B is the set of translations keeping B inside A:

A ⊖ B = ⋂ᵢ (A − vᵢ)   over the vertices vᵢ of B

That reduction to vertices is only valid when A is convex — a non-convex A can contain every translated vertex while missing the material between them. So a non-convex subject is refused by name rather than answered with a result that is too large.

Verification

Against closed forms, not against another implementation:

criterion	status
scripts/gate.sh	PASSED
two boxes sum to a box with summed extents	met — volume and per-axis span
convex sum agrees with hull of pairwise vertex sums	met
non-convex sum agrees with union of per-part sums	met — strictly smaller than the convex-hull sum
every result passes v0.7 diagnosis	met
mutation probe: skip decomposition, treat operand as convex	kills the non-convex volume test

Also: erosion of a 4-cube by a unit cube leaves a 3-cube; an oversized tool leaves nothing; the sum is commutative and contains the original.

A mutation that survived first

Flipping the erosion's translation sign survived. My box test used a tool anchored at the origin, and negating a symmetric offset set changes nothing — so the test proved less than it appeared to. Added erosion_places_the_result_where_the_tool_actually_fits, using a tool deliberately off the origin and asserting the eroded extent per axis. Both sign mutants now fail.

Cost is visible

Work is the product of the two part counts, so it is budgeted up front and refused with the pair count rather than discovered by running out of time. MinkowskiEvidence reports part counts, pairwise sums, and boolean operations.

Not in scope, as specified

Attributes and any GPU path remain out. Curved operands are refused.

Workspace: 1195 passed, 0 failed.