A sweep that missed nothing

Everything this field measures is measured by sweeping: solve the mechanism at a sequence of driving angles, compute the gap at each, take the smallest. Every table in it is quoted with a sample count attached, and every one of those counts is a decision somebody made.

Here is why the decision is not a matter of taste.

The machine, built to be missed #

A four-bar with a stud bolted to its frame: a square a tenth of a unit across, at 1.28 units from the crank’s centre, at 2.0 radians. The crank turns at one unit of tip speed per radian and the stud is small, so the whole encounter occupies about a tenth of a radian of the turn.

Sweep it at eight samples and the smallest gap found is +0.081. At twelve, +0.007. At sixteen, −0.010. From sixteen on, every refinement returns −0.010: that is the true answer, and the crank is inside the stud by a tenth of a link width.

The twelve-sample answer is the dangerous one. Eight samples give a comfortable margin that somebody might question; twelve give a margin of 0.007 on links 0.16 wide, which reads exactly like a tight but successful design. The curve it draws is smooth. Its minimum is interior, not at an end. It behaves in every way the previous essay says a clearance function behaves. And it is wrong by more than its own value.

Why “sweep more finely” is not an answer #

The obvious response is to sample more, and it is not wrong so much as unanswerable: finely enough is not a property a sweep can report about itself.

Every sweep returns a smallest gap and no sweep returns a warning. There is no signal in the twelve-sample data that says a feature was stepped over — the samples either side of the stud are 0.5 radians apart, the crank was elsewhere at both, and the numbers at both are ordinary. Doubling the count and getting a different answer is evidence that the first was too coarse, but the same argument then applies to the second, and it never terminates.

The size of the feature is not knowable in advance either. It depends on the obstacle’s size, the link’s speed at that instant, and how nearly the two miss — and the last of those is precisely what is being measured. A design that misses by a lot leaves a wide, shallow dip that any sweep finds; a design that nearly touches leaves a narrow one, and the nearer it comes to failing the harder it is to see.

That is a bad property for a check to have. It is least reliable exactly where the answer matters most.

What the sampled curve looks like while it is wrong #

It is worth dwelling on the twelve-sample curve, because the argument above is easy to accept in principle and hard to act on in practice, and the reason is that the wrong answer is not ugly.

Twelve samples over a turn is one every thirty degrees. The crank’s tip moves 0.52 units between samples — three times the width of a link, five times the width of the stud. At the sample before the encounter the crank is well clear; at the sample after it, well clear again. The minimum of the sampled curve is not even at the encounter: it is at a different angle, where the coupler comes nearest the stud, and the encounter leaves no trace at all in the twelve numbers.

So there is no dip to notice, no asymmetry, no sample sitting suspiciously below its neighbours. The reported minimum belongs to a different pair of parts, at a different angle, and it happens to be small. Everything a reader would look at to judge whether a sweep is trustworthy — smoothness, an interior minimum, a sensible witness pair — is present and points the wrong way.

That is the general shape of the failure, and it is why the repair has to be arithmetic rather than judgement. Nothing in the output distinguishes a sweep that resolved the motion from one that stepped over it, so nothing but a bound can tell them apart.

What can be bounded #

The repair is to stop asking the samples what happens between them and start bounding it, and this field can state the bound exactly rather than assume it.

Every corner of every body is an affine function of its link’s two joints. A body is given in link coordinates, so a corner at (u, v) sits at p = a + u(b − a) + v·R₉₀(b − a), which is linear in the two joint positions with constant coefficients. Differentiate: the corner’s velocity is the same affine combination of the joint velocities,

$$\dot{\mathbf{p}} = \dot{\mathbf{a}} + u(\dot{\mathbf{b}} - \dot{\mathbf{a}}) + v\,R_{90}(\dot{\mathbf{b}} - \dot{\mathbf{a}}),$$

with no approximation anywhere. And the joint velocities are something this site has computed since its first field: they are the solution of the velocity problem, one linear solve against the same Jacobian the position solve uses.

So the largest speed any material point of the machine has, at any configuration, is available for the price of one extra linear solve per frame. Call the largest of those over the whole drive V.

The bound #

Distance between two point sets is 1-Lipschitz in the points: move every point of two shapes by at most ε and the distance between them changes by at most 2ε — and by at most ε if only one shape moves. So between two samples Δθ apart, the gap can fall by at most V·Δθ.

That gives a cone from each sample: from sample i, at a parameter s along the interval, the gap is at least gᵢ − V·s; from sample i+1 it is at least gᵢ₊₁ − V(Δθ − s). The guaranteed lower bound over the interval is where the two cones cross:

$$\frac{g_i + g_{i+1} - V\,\Delta\theta}{2}.$$

If that is positive at every adjacent pair, nothing was missed. A finite set of solves has become a statement about a continuum.

What it says about the two machines #

On the four-bar with a post, at sixty samples: V = 1.256 per radian, Δθ = 0.107, and the worst crossing height is +0.038. Positive, so the sweep is conclusive: that machine clears, and not merely at the sixty places it was looked at. At 150 samples the bound rises to +0.078, approaching the true minimum of 0.104 from below as the sample spacing shrinks.

On the crank and stud, at twelve samples: V = 1.256, Δθ = 0.571, and the worst crossing height is −0.281. The certificate refuses. It does not say the machine collides — it says this sweep proves nothing, which is the honest verdict and is exactly the verdict the twelve-sample sweep could not produce for itself.

That is the property worth having. The bound is not another estimate of the gap to be compared with the sampled one; it is a different kind of statement, and it fails safe. A sweep that missed something cannot pass it, because the thing that was missed is bounded by the same V that bounds everything else.

How many samples would do #

The bound can be run backwards. If the smallest sampled gap is g and the largest corner speed is V over a drive of length Θ, then the crossing height is positive as soon as

$$\Delta\theta < \frac{2g}{V} \quad\text{roughly, so}\quad N \gtrsim \frac{V\,\Theta}{g}.$$

For the four-bar with a post that is 1.256 × 6.283 ÷ 0.104 ≈ 77 samples, and the machine does in fact certify at sixty — the estimate is conservative, because it uses the worst gap at every step rather than the two that bracket the worst.

The formula says the useful thing plainly: the number of samples needed goes as one over the clearance. A machine with a comfortable margin certifies at a handful of positions; a machine that nearly touches needs an unbounded number, and one that touches exactly needs infinitely many. That is not a defect of the method. It is the geometry: at zero clearance there is nothing to certify, because the answer changes character.

For the stud machine the same formula returns 1,171 — which is what it would take to certify if the sampled gap were real. It is not, and sixteen samples find that out instead. Both readings are useful and they are different questions: how many samples to prove it clears, against how many to find that it does not.

What is assumed #

Two things, and they are stated rather than hidden.

V is measured, not bounded a priori. It is the largest corner speed found on a sweep six times denser than the one being certified. A genuine a priori bound would need a bound on the inverse of the constraint Jacobian over the whole drive, and near a singularity there is none: joint velocities grow without limit as a dead centre is approached, so no finite V exists on an arc that reaches one. On such an arc no sample count certifies anything, which is a fact about the mechanism rather than about the method — and a fair one, since a mechanism being driven through a dead centre is not a mechanism whose clearances are the interesting question.

On the machines here the crank is the input and turns at constant speed, so V is bounded and well behaved: 1.2556 on the four-bar, and it barely moves between sample densities, which is the evidence that the dense sweep has resolved it.

The bodies are rigid and the drive is one parameter. Both are true of everything on this site. A machine with two inputs has a two-dimensional drive and the same argument gives a bound over a grid rather than a sequence, with Δθ replaced by the grid’s diameter and the same V.

The same failure, one field over #

It is worth noticing where else this sampling error has already appeared, because it did not announce itself as one.

The width search bisects on link width, sweeping at each step, and it reports a positive maximum width of 0.0094 for a machine whose coupler crosses its driving pivot exactly. The true answer is zero. The bisection’s answer is positive only because the sweep steps over the instant of the crossing, and the same certificate refuses it: at that width the crossing height is negative and nothing is proved.

That is the same defect twice in one file, in two measurements that look nothing alike, and the second one was found by the first one’s machinery. It is also the reason the width table is reported with the crossing count beside it: a count of sign changes is a discrete quantity, and a discrete quantity computed on a fine sweep is robust in a way that a minimum distance is not.

What a certificate is not #

It is not a proof that the mechanism is safe. It is a proof that a sampled sweep did not miss anything, given a measured V, rigid bodies, and the shapes as specified. The tolerance essay takes up what happens when the lengths are ranges, and it is a wider statement than this one.

It is not free. Certifying needs the velocity solve at every frame and a denser sweep to measure V on, which is roughly seven times the work of the sweep it certifies. That is nothing on the machines here and would be the dominant cost on a machine of four hundred links.

And it is not a substitute for reading the picture. A bound of +0.038 says the sweep is conclusive. It says nothing about whether the shapes are the right shapes, whether the obstacle is where the drawing says it is, or whether the drive covers the motion the machine actually makes — which are the three ways this kind of check is usually wrong in practice, and none of them is a sampling problem.

The bound is exact where it could have been sloppy #

Two details of the derivation are worth stating, because both are places where a plausible version gives a weaker or a wrong bound.

The corner velocity is exact, not estimated. It would be natural to bound a body’s speed by the speed of its two joints, or by a joint speed plus an angular rate times a radius. Both are true and both are loose, and being loose costs sample count directly, since the required N goes as V. The affine identity gives the corner’s velocity as the same combination of joint velocities that gives its position from the joint positions — so V is the true maximum over corners, computed and not bounded, and the only slack left is that the maximum over corners bounds the maximum over the whole body. That last step is free: a convex body’s fastest material point is at a corner, because the velocity field is affine over the body and an affine function on a polygon attains its extremes at vertices.

The two cones are used, not one. A bound built from one sample — the gap can fall by at most V·Δθ from here — gives a floor of gᵢ − V·Δθ, which is worse than the crossing height by half of V·Δθ and therefore needs twice the samples. Using both ends is free and halves the cost, and it is the difference between certifying the four-bar at sixty samples and needing a hundred and twenty.

Neither is deep. Both are the kind of thing that gets left out of a first version and then quietly doubles or triples the work everything downstream does, which on this site means the difference between a figure that takes a second and one that takes ten.

What it would take to be wrong #

The certificate has exactly three assumptions, and it is worth asking what each one being false would look like, since a bound is only as good as the reasons it might not hold.

If V were understated, the cones would be too shallow and the bound too optimistic. That is the failure that matters, and the guard against it is that V is measured on a sweep six times denser than the one certified, and that it barely moves between densities — 1.2555 at 180 samples, 1.2557 at 900, on the same machine. A quantity that is stable to four figures under a fivefold refinement is a quantity that has been resolved.

If a body were not rigid, its corners would move relative to its joints and the affine identity would fail. Nothing here is flexible: this site’s strands are the one field with a member that is not rigid, and there are none in this catalogue.

And if the drive did not cover the motion, the bound would be a true statement about the wrong interval. That is not a sampling problem and no amount of density fixes it: it is the ordinary risk of measuring a machine over the arc somebody typed rather than the arc it has, and the guard is that every arc in this field is either a full turn or measured by workingArc rather than assumed.

The habit this belongs to #

Every field on this site produces its quantities twice. A mobility is counted and measured; a velocity is solved and differenced; a ratio is derived and swept. The second route is never the same computation done again — it is a different route to the same number, chosen so that the two fail differently.

A sampled minimum has no natural second route, because the obvious one is sample more, which fails in exactly the same way. The bound is the second route, and it is a different kind of object: it does not produce the gap, it produces a floor under it. Where the sampled minimum and the floor bracket the truth, the answer is known to lie between them; where the floor is negative, the sampled minimum is a number with no standing at all.

That is the shape the site’s habit takes when the quantity is a minimum over a continuum, and it is worth carrying to anything else measured the same way — a worst transmission angle, a peak acceleration, a maximum structural error. All of them are minima or maxima over a drive, all of them are computed by sampling, and none of them has been given a floor.