The regions overlap and the parts never meet

The region a machine sweeps is the most convenient object this field has. It is computed once rather than at every configuration, it is a shape rather than a function, and two shapes either overlap or do not — so the obvious way to ask whether two parts of a machine can collide is to sweep each of them and intersect the answers.

That test is wrong in one direction, and the amount is large.

What the test gets right #

The region test is sound in one direction and it is worth stating the direction precisely, because that soundness is why anybody uses it.

If two parts collide at some configuration, then at that configuration each occupies the point where they touch. So that point is in both swept regions, and the regions intersect. Contrapositively: if the regions do not intersect, the parts never collide. A clear verdict from the region test is a proof.

That is a real guarantee and it is cheap. The four-bar’s crank and rocker sweep regions that share exactly nothing — 0.000000 square units, on a grid of fifty-seven thousand cells — and the two parts are never closer than 2.1212 units over the whole drive. One computation clears a pair for ever.

What it gets wrong, and by how much #

The converse fails, and it fails because a swept region has thrown away the only thing that distinguishes a collision from a near miss: when.

Two parts can both visit a patch of ground and visit it at different moments. The region test sees a patch in both sets and reports interference; the machine passes through the configuration space without either part ever meeting the other.

Chebyshev’s linkage is the clean example. Its two long arms cross on the drawing, which is the observation that gave this field an essay of its own, and their swept regions share 4.652 square units — thirty-six per cent of the smaller region. The arms’ actual closest approach over the drive is 0.3799, at 0.712 radians, and the gap is above a third of a unit everywhere.

Peaucellier’s cell is worse, and it is worse in a way that is characteristic rather than accidental.

The same statement in configuration space #

There is a second way to say all of this, and it is the one that makes the failure look inevitable rather than unlucky.

A one-freedom machine has a configuration space that is a circle: one number, the drive angle, and the machine is entirely determined by it. The set of configurations at which two given parts collide is a subset of that circle — possibly empty, as it is for every pair in Chebyshev’s linkage. That subset is what a collision check is about.

A swept region lives somewhere else entirely. It is a subset of the plane, obtained by taking the union over the configuration circle of the part’s body at that configuration — which is a projection that forgets the circle. Two such projections intersecting says that there exist a $\theta_1$ and a $\theta_2$ with the first part at $\theta_1$ and the second at $\theta_2$ occupying a common point. A collision says there exists one $\theta$ doing both.

$\exists\theta_1\,\exists\theta_2$ against $\exists\theta$. The region test is the first, the collision is the second, and the first is implied by the second and does not imply it. Everything above is that one line of logic, measured.

It also says immediately where the two coincide: when one of the two bodies does not depend on θ at all, the two quantifiers collapse into one. Which is the fixed-obstacle case, below, arrived at without any geometry.

Where the false alarm disappears completely #

The interesting part of this is not that the test is conservative. It is that the conservatism has a precise cause, and there is a whole class of questions where the cause is absent and the test is exact.

A fixed obstacle occupies its ground at every configuration. So “is the part ever where the obstacle is” and “does the part ever touch the obstacle” are not two questions related by an implication — they are the same question. There is no when to forget, because the obstacle’s when is always.

That is the sharp statement of the conservatism: it is about two things both moving. It has nothing to do with regions being a crude instrument, nothing to do with resolution, and nothing to do with the sweep being sampled. A machine’s clearance against its housing, its guards, its mountings and its neighbours can all be checked by one swept region and a set of polygons, exactly. Only the machine against itself needs configurations.

Why the false alarms are where they are #

Reading across the pairs, the share of ground two parts hold in common is not random.

Watt’s two arms share 9.9% of the smaller region and never come within 0.5409. Chebyshev’s share 35.9%. Peaucellier’s long arm and its far rhombus bar share 58.2%. The pattern is that parts adjacent in the kinematic chain, or nearly so, sweep overlapping regions almost always — they are pinned near each other and swing through overlapping arcs — and parts far apart in the chain do not.

That is the opposite of what a designer needs. The pairs the region test convicts most confidently are the ones most likely to be false alarms, because being near each other in the chain is exactly what makes two parts’ motions correlated — the reason they stay apart is that they move together.

So the test’s failures are not spread evenly over the pairs. They are concentrated on the pairs a machine has most of, which is why a region-based check on a linkage of any size comes back with a long list and why the list is usually ignored.

What the filter is worth, counted #

A machine with $n$ parts has $n(n-1)/2$ pairs, and the field’s catalogue runs from four parts to eight. Peaucellier’s cell has eight links and therefore twenty-eight pairs, of which the ones sharing a pin are excluded by construction — two links surrounding one pin overlap at that pin because that is what a pin is — leaving a list in the high teens.

The filter’s value is what fraction of that list it clears. On the four-bar it clears the crank–rocker pair and nothing else, because a four-bar’s other pairs all share pins or genuinely overlap. On Peaucellier’s it clears rather more, since the cell is long and its far ends really do stay apart.

The saving is real and it is bounded, and the bound is the interesting part: a filter that is wrong most often on the pairs a machine has most of does not scale. As a chain gets longer the number of pairs grows quadratically and the number of far-apart pairs grows quadratically too, so the filter keeps clearing a fixed fraction rather than a growing one. It does not turn a quadratic problem into a linear one; it divides the constant.

Two instruments that fail in opposite directions #

This field now carries two ways of asking whether a machine collides, and they are wrong in complementary ways.

A sampled sweep can miss. It looks at finitely many configurations of a machine that has infinitely many, and a crank passing a stud a tenth of a unit across is declared clear by a twelve-sample sweep while it is a hundredth of a unit inside the stud. Its error is a false negative, and the repair is a Lipschitz certificate that bounds what happens between samples.

A region intersection cannot miss. Its error is a false positive, and there is no repair at all, because the information it needs was discarded when the region was formed. Refining the grid does not help; sampling the drive more finely does not help; both make the regions more accurate and the regions are not the problem.

That is an unusually clean pair. One instrument is unsound and can be made sound by adding a bound; the other is sound and cannot be made complete by adding anything, because completeness would require un-projecting.

An arm is the same failure at higher dimension #

This field has already met the region test’s failure once without naming it, on an arm’s workspace, and the version there is worse for a reason worth stating.

A three-joint arm has a three-dimensional configuration space. Sweeping one of its links means taking a union over a volume of configurations rather than over an arc, and the resulting region is correspondingly larger — a link near the base of an arm sweeps almost the whole reachable disc, because the joints outboard of it do not move it and the joints inboard of it move it everywhere. So two links of an arm almost always have overlapping swept regions, and almost always do not collide.

The quantifier reading says exactly why. $\exists\theta_1\,\exists\theta_2$ over a three-dimensional space is a much weaker statement than $\exists\theta$, and it gets weaker as the dimension rises: the number of pairs of configurations grows as the square of the number of configurations, while the number of single configurations does not. The region test’s conservatism grows with the machine’s freedom, which is why it is nearly useless for an arm and merely lossy for a four-bar.

That is the general form of the result and it is the reason to state it as a fact about quantifiers rather than as a fact about linkages.

What the region is still the right instrument for #

Naming the failure should not cost the object its uses, and it has three that are unaffected.

Packaging. The area a machine needs is the union of its parts’ regions, and a union loses nothing: every point in it really is occupied at some moment. The box the material needs is a correct quantity computed this way.

Clearance against anything fixed. Exact, as above.

Clearing a pair. A disjoint verdict is a proof, and on the pairs that are far apart in the chain it comes back disjoint. So the region test is worth running first, as a filter: every pair it clears is cleared for ever, and only the pairs it convicts need a sweep. On the four-bar that removes the crank–rocker pair from the list at no cost.

That last use is the honest place for it, and it is a real saving. The expensive test is per pair per configuration; the cheap one is per pair. Using the cheap one to shorten the list the expensive one has to run is exactly what a conservative test is for.

What a designer should do with a convicted pair #

The practical question the result leaves is what to do when the region test convicts a pair, and the answer has three steps that cost increasing amounts.

First, look at the drive. If the two parts are adjacent in the chain, expect a false alarm and do not spend anything on it yet. The correlation that keeps them apart is the same correlation that made their regions overlap.

Second, take the pairwise gap curve. That is one sweep over one pair — much cheaper than the full check, since it tests one pair rather than all of them — and it answers the question outright, subject to the sampling caveat. The figures above are exactly that computation, and on Chebyshev’s arms it comes back with a comfortable third of a unit.

Third, certify it. If the margin is small, the sampled curve is not a proof and the Lipschitz bound is what turns it into one. That is the expensive end and it is rarely needed, because the pairs where it is needed are the ones with small margins and the pairs with small margins are the ones a designer has already noticed.

Stated that way the region test is the first of four instruments rather than a rival to any of them, and its place in the order is decided entirely by what it costs and what its verdicts mean: cheapest, sound one way, and therefore first.

What was measured, and how it could have gone wrong #

The two grids have to share a box. Each occupancy computation had always chosen its own bounds from the parts it was asked about, which is right for an area and useless for an intersection — two grids over two different boxes cannot be intersected cell by cell, and the answer would have been a plausible number computed from misaligned cells. The box is now computed once from both parts and passed to both.

The claim is checked in both directions. A pair whose regions overlap is required to have a positive closest approach, or it is not an example of anything; and a pair whose regions are disjoint is required never to collide, which is the sound direction and the one that would break if the grid were missing material.

One resolution limit is worth recording because it looks like a failure of the argument and is not. Against the stud at the field’s standard link width the coupler enters by 0.0099, and a grid of 240 cells over a six-unit sweep has cells of 0.025 — so the overlap is a sliver a third of a cell across, no cell centre falls inside it, and the grid reports no intersection where the configuration test reports a collision. The region test is exact about regions; a grid is an approximation to a region, and its resolution is the depth it can see. The figure above takes the collision at a link width where the penetration is four cells rather than a third of one.

Still open: the region of a pair, rather than two regions #

There is an object that would make the test exact and this field has not built it.

Instead of sweeping each part and intersecting the results, sweep the pair: for each configuration, form the set of points where the two parts are simultaneously, and take the union of those over the drive. That set is empty exactly when the parts never collide, so it is a complete test as well as a sound one — and it is a union over configurations of an intersection at each, which is the opposite order of operations from what the region test does.

The cost is that it is no longer one region per part but one computation per configuration, which is what the sampled sweep already is. So the exact version of the region test is the sweep, and the region test’s convenience was exactly the reordering that lost the information.

That is worth knowing before anybody tries to repair it. The two instruments are not two methods with different accuracies; they are one calculation with its quantifiers in two orders, and the cheaper order is the one that cannot answer the question.

The other thing left open is a partial reordering, which might be the useful object. Divide the drive into a handful of arcs, sweep each part over each arc separately, and intersect region against region only for the same arc. That is sound, it is still cheap — a few regions per part rather than one — and it is strictly less conservative than the whole-drive test, because two parts that visit the same ground half a turn apart are now compared arc by arc and never found together. How much of the false alarm it removes, and how the number of arcs trades against the work, is a measurement nobody here has made. On Chebyshev’s arms it would have to be enough arcs to separate 0.712 radians from wherever the other arm gets there, and that number is computable and is not computed above.