Computational geometry
Why a Clearance Check Should Err Toward False Alarms
Exact distance between two oriented boxes is not free, and the cheap approximation is wrong in one specific direction. That direction turns out to be the one you want.
Two questions that look like one
A clearance check appears to ask a single question (how far apart are these two parts?) but it is really asking two, and they have different answers and different costs.
When two parts overlap, the useful number is penetration depth: how far one would have to move to stop intersecting the other. When they are apart, the useful number is separation: the shortest distance between their surfaces. A single function has to return both, and the algorithm that gives you one cheaply does not give you the other cheaply.
The separating-axis theorem, and what it actually returns
For two oriented bounding boxes, the standard tool is the separating-axis theorem. Two convex solids are disjoint if and only if some axis exists on which their projections do not overlap. For a pair of boxes it is enough to test fifteen candidate axes: the three face normals of each box, and the nine cross products of their edge directions.
Project both boxes onto each axis, measure the gap between the projected intervals, and take the largest value:
for each candidate axis:
gap = |distance between centres along axis|
- radius of A along axis
- radius of B along axis
result = max(gap over all axes)
A positive result means some axis separated them, so they are apart. A negative result means none did, so they overlap.
Where the asymmetry comes from
For the overlapping case, that maximum is exact. The least-negative axis is the axis of minimum translation, and its magnitude is the penetration depth. This is the standard result and it is why SAT is used for collision response.
For the disjoint case, it is only a lower bound. The fifteen axes catch the true distance whenever the closest features are face-to-face or edge-to-edge. When the closest features are a vertex and a face at an awkward angle, the true shortest distance runs along a direction that is not in the candidate set, and every tested axis reports something smaller than reality.
So the function is exact where parts collide and pessimistic where they do not. It never overestimates a gap.
Which way should a check be wrong?
Given that the approximation has to be wrong somewhere, the design question is which failure you would rather ship.
| Reports a violation that is not real | Reports a pass that is not real | |
|---|---|---|
| What the engineer does | Looks at the pair, measures it properly, dismisses it | Nothing: there is nothing to look at |
| Cost | Minutes, and some irritation | Found at integration, if you are lucky |
| Detectable? | Yes, immediately | No. Silence is indistinguishable from correctness |
A false alarm is a bounded cost paid by someone who is already looking at the model. A false pass is an unbounded cost paid by someone who has stopped looking. A lower bound on distance produces only the first kind, which is why it is worth accepting rather than engineering away.
This is the same reasoning behind a conservative static analyser or a coverage tool that refuses to claim a line was hit. The tool's job is not to be right about everything; it is to be wrong in a direction that stays visible.
The cylinder problem, stated plainly
The same principle covers a second approximation. A cylinder is bounded by its box for the separation test (radius, radius, half-height) while its volume is computed from the true solid, because density should not be a lie.
The consequence is worth being explicit about: two cylinders standing side by side read as tighter than they are, because the corners of their bounding boxes reach further than their walls do. A pair of 55 mm-radius sensor bodies 5 mm apart can report a violation against a 5 mm rule. That is the pessimism doing exactly what it was designed to do, and a reviewer resolves it in seconds.
What this costs, and when to fix it
The honest accounting: this design trades some noise for a guarantee. On a model of fifteen parts the noise is negligible. On a model of five hundred, a wall of near-miss pairs would start to hide the real ones, and at that point the fix is a true closest-feature distance for the disjoint case (GJK, or a direct feature-pair search) while keeping SAT for the overlap case where it is already exact.
What should not change is the direction of the error. Whatever replaces it should still be incapable of reporting a gap larger than the real one.
The general form
Most engineering checks admit this question, and most tools never ask it out loud. A mass roll-up that silently skips a part with no stated mass is optimistic. A trace matrix that counts a draft requirement as covered is optimistic. A thermal screen that ignores a pair because one of them has no declared dissipation is optimistic.
Optimism is the expensive default, because it is invisible. If a check cannot be exact, it should be pessimistic and say so, and it should say by how much, so the person reading it can decide whether the margin matters.
U.S. Provisional Patent App. No. 64/073,689. Patent Pending.