A gap is a number

A collision test is usually a predicate. Two shapes go in, true or false comes out, and the caller either proceeds or does not.

That is the wrong shape of answer for this site and it is worth being precise about why. A predicate cannot be plotted against a crank angle. It cannot be minimised over a sweep, bisected on a width, or bounded between samples. It cannot say whether a design missed by a hair or by a hand. And it cannot be checked against a second route, because there is nothing to compare — two implementations agreeing on false have agreed about almost nothing.

So the quantity here is a signed clearance: one number, positive when the parts are apart and negative when they are not, and in both cases a distance.

Two regimes, and only one of them is obvious #

Apart. The distance between two convex polygons is the smallest distance between an edge of one and an edge of the other. That is exact — no approximation, no iteration, no tolerance — and it is a loop over pairs of segments with a point-to-segment distance inside it. For an octagon against an octagon it is sixty-four segment pairs, which is nothing, and the answer comes with a witness pair: the two points, one on each shape, that realise it.

The witness is not a detail. It is what gets drawn in every figure in this field, and it is what makes the number checkable by eye: a reader can see whether the segment goes where the caption says the parts are closest, which is a test no printed number passes on its own. It is also the thing whose identity changes as a mechanism moves, and that identity is where the gap function gets its corners.

Together. When the parts overlap there is no distance between their boundaries to report — the boundaries cross — and the number wanted is a penetration depth: how far the pair would have to be moved apart to separate them. For convex shapes the separating-axis theorem answers it. Two convex sets are apart exactly when some line separates them, and it is enough to test the directions normal to the edges of both. If every one of those directions has the two projections overlapping, the shapes overlap; and the smallest of those overlaps is the least translation that separates them.

That smallest is the load-bearing word and it is the easiest thing in the file to get wrong. Taking the largest overlap gives a plausible number with the wrong meaning, taking the first gives a number that depends on the order the edges were listed in, and both draw a perfectly convincing picture.

Why a depth rather than a flag #

A designer asked to fix an interference wants to know how much material has to go. That is the depth, and it is directly actionable: move the post four millimetres, thin the coupler by two, shorten the boss.

There is a second reason and it matters more to this site. A depth makes the quantity continuous through zero, and a continuous quantity can be searched. The width search bisects on the link width because the worst gap falls monotonically as every body grows, and the crossing is a single well-defined point rather than the edge of a plateau of false. The tolerance study reports an interval of gaps over a box of lengths, and the interesting fact about that interval is where it sits relative to zero — which needs the number to exist on both sides.

The calibration, because this machinery looks obviously right #

The separating-axis code is about forty lines and every one of them is plausible. It was checked against closed forms rather than against itself, on three cases whose answers can be written down:

• Two axis-aligned squares a known distance apart. The gap is that distance, and the witness pair is the two facing edges.
• A square and a point outside it. The gap is the point-to-edge distance, and this case catches a version that only ever compares edge to edge.
• A pair overlapped by a known amount. The depth is the overlap, and this case is the one that catches the smallest against the largest.

There are three things a plausible version gets wrong: the winding of a polygon, the sign of the outward normal, and the choice among the overlaps. Each of them produces a number of the right order of magnitude on the case it is wrong about, which is why the calibration is against arithmetic somebody can do by hand rather than against a second implementation of the same idea.

The one it did not catch #

The three cases above are the calibration the applied field wrote when it first needed bodies, for a cabinet door against its carcase and a wheel in its arch. They are correct and they are not complete, and the gap in them is a good example of how a test suite inherits the shape of the problem it was written for.

A door and a carcase meet edge first. So do a wheel and an arch, a coupler and a post, a crank and a stud. In every one of those, two shapes that do not overlap have a positive smallest edge-to-edge distance, and two that overlap have crossing edges and a distance of zero, so the branch on is the edge distance greater than nothing separates the cases perfectly.

It separates them perfectly for every pair of shapes except one arrangement: nested. A small shape entirely inside a large one crosses none of its edges. The smallest edge-to-edge distance is positive — it is the distance from the small shape to the wall of the large one — and the code returned it as a clearance.

The case turned up in this field’s first hour, in a figure comparing a bell crank against its own convex hull. A probe placed in the crank’s notch clears the crank and is buried in the hull, and the routine reported that it cleared the hull by 0.18. Every gate on the site was green; the picture showed a block inside a shape with a comfortable number printed beside it.

The repair is one line and one point: if either polygon’s first vertex is inside the other, the shapes are nested, and the depth branch has to run whatever the edge distance says. One point of each is enough, because containment without crossing edges is total — if any vertex of one is inside the other, all of them are.

The fix belongs in interference.js, where the bug is, and not in this field’s own code, because the same routine draws the cabinet door and the wheel arch and would have gone on being wrong about them the first time either was drawn inside something. The nested case had never come up there. It was going to.

Where the closest pair is, and why it keeps moving #

The witness pair carries more information than the number does, and the site had no use for it until this field.

At any configuration the witness is a pair of features — an edge of one part and a vertex of the other, or two edges — and as the mechanism moves that pair changes discretely while the number changes continuously. On the four-bar with a post bolted to its frame, swept through a whole turn at 360 solved positions, the closest pair changes four times: the coupler approaches the post, hands over to the rocker, hands back, and hands over again as the crank comes round. Between changes the gap is a smooth function of the crank angle. At a change it has a corner.

That is a fact about the geometry rather than about the sampling, and it survives any refinement: at 3,600 samples there are still four changes, in the same four places. The reason is that each pair of features contributes its own smooth distance function of the configuration, and the gap is the minimum over all of them — and a minimum of smooth functions is smooth except where the argmin changes hands.

Every figure in this field draws the witness for that reason. A plot of the gap alone shows the corners and cannot say what they are; a plot with the witness pair as the colour of the curve says that this corner is the coupler handing over to the rocker, which is a sentence about the machine.

What the number costs #

A gap is not free, and the cost has a shape worth knowing before a sweep is designed.

At one configuration, testing one pair of octagons is sixty-four segment-to-segment distances if they are apart, plus sixteen axis projections if they are not. The pair count is the part that grows: n links give n(n − 1)/2 pairs, less the joined ones, so a four-bar has two pairs to test and Peaucellier’s eight links have fourteen. Add an obstacle bolted to the frame and every moving part is tested against it.

Over a sweep the configuration count multiplies that, and the configuration count is not free either: each one is a Newton solve, marched from the position before it rather than jumped to, because a solver asked for a distant configuration converges to a different assembly with every bar satisfied and the picture wrong. So a 360-sample sweep of Peaucellier’s cell is 360 solves and 5,040 pair tests, which is a second of arithmetic and is the reason the tables in this field are quoted with their sample counts attached.

None of that is expensive by any standard. What it is, is avoidable — and the temptation to avoid it, by sweeping coarsely, is the subject of the two essays after the next one.

There is one place where the cost is not negligible and it is worth naming, because it decides how the rest of this field is written. A search over a design parameter re-runs the whole sweep at every step: the width search rebuilds the machine and sweeps it once per bisection step, which is a dozen sweeps for four significant figures, and the tolerance study sweeps sixteen corners of a box and then two dozen interior draws. Those are the figures in this field that take a second rather than a millisecond, and they are the ones whose sample counts are chosen rather than inherited.

What the number is not #

It is not a force, a pressure or a stress. A depth of 0.4 says the parts are 0.4 into each other in the geometry as dimensioned. It says nothing about what would happen if somebody built them and turned the crank, and this site does not model what would happen.

It is not a contact. The holding field is about parts held by contact, where a touching pair is a constraint that shapes the motion — an inequality on velocities, with a cone of admissible directions and a rank. Here a touching pair is a failure of the design: the mechanism is meant to move freely and the material is meant to keep out of the way. The two fields use the same word for contact and mean opposite things by it, and the difference is whether the touching is intended.

It is not symmetric in what it costs to compute. The apart branch is exact and cheap. The depth branch is exact for convex shapes and, for shapes with a dent in them, needs the decomposition of the next essay — where the depth of a pair is the largest of the pieces’ depths rather than the smallest, since the pair has to be moved by enough to free the worst overlap.

Reading the number on a real machine #

Peaucellier’s cell is the densest planar loop on the site: eight links, ten pins, and an exact straight line. It has twenty-eight pairs of links, fourteen of them joined at a pin and therefore not tested, and fourteen that are.

Swept over its working arc at 0.16 width, the smallest gap is −0.432, between a long arm and the crank — two links at opposite ends of the chain with no joint and no equation in common. The number is exactly the same as the four-bar’s, and the repetition is informative rather than suspicious: two long bars fully crossed have to be moved apart by the whole of one width, so the depth saturates once the crossing is complete and stops carrying information about how badly.

That is the honest limit of the depth as a design number. It is precise and useful near zero, where a designer is deciding whether to thin a link or move a pivot, and it is merely a diagnosis of fully crossed when it is large. Which is exactly the regime where the answer is not to move anything but to build the two links in different planes — and that is a decision about the third dimension, which the layers essay takes up.

The witness on a machine that clears #

It is worth reading one machine where the answer is positive, since almost everything in the catalogue is not.

Take the same four-bar and bolt a post to its frame at (1.35, 2.5), a third of a unit wide and a little over a unit tall, standing in the region the coupler sweeps. Over a full turn the smallest gap is +0.104, at a crank angle of 2.11 radians, between the coupler and the post. The machine runs, with a clearance of about two thirds of one link width at its worst instant.

Refining that minimum off the sample grid by golden section — the gap has corners, so a derivative is the wrong instrument and a bracketing search is the right one — moves it by 1.5 × 10⁻⁵. That is a smooth minimum found on a fine enough grid, and it is the exception rather than the rule in this field: at a corner, refinement moves the answer by much more than the sampling error, because the true minimum sits at a kink the samples straddle.

The same machine with the post moved a quarter of a unit outward, to (1.7, 2.5), reads −0.071. A quarter of a unit of post position is the difference between a working machine and an impossible one, and no quantity anywhere else on this site changes character over that distance.

One number, four uses #

Everything in this field is this number, read in a different way.

Minimised over a drive, it is whether the machine runs, and where the worst instant is. Minimised over a drive and then over a width, it is how thick the links may be. Watched for its sign at each angle, it partitions the drive into free arcs. Taken over a tolerance box, it becomes an interval, and the question stops being how large and becomes which side of zero it reaches. Bounded between samples, it becomes a certificate that a finite sweep proves something about a continuum.

None of that is available from a predicate, and all of it comes from insisting that the answer be a distance with a sign on it.

The signed depth is a single number and it is worth naming precisely what makes it worth more than a flag: it is differentiable, almost everywhere. A yes-or-no answer has no derivative, so it cannot be optimised, cannot be used in a search that improves, and cannot say which way to move. A signed depth can be handed to any of those: perturb a dimension, watch the depth, and the sensitivity says which change buys clearance and how fast. That is the difference between a check and a design tool, and it is why every quantity this site prefers is a number rather than a verdict. The exception is the place where the differentiability fails, and it is worth knowing where: the depth’s derivative jumps when the closest pair changes — when a different pair of features becomes the nearest — which is exactly the configuration the essay reports as moving. So the honest use of the number is with its witness attached, and a search that ignores a change of witness is fitting across a kink, which is the same trap a strand’s contact boundary sets.