A shape with a dent in it

Every body in the applied field is convex, and the code that measures them says so out loud: body() walks the corners, measures the worst turn, and refuses a polygon that turns the wrong way anywhere.

The refusal is right and it is also the whole problem, because the parts a reader owns are mostly not convex. A bell crank is two arms meeting at a pin, and it is the shape a rocker driving two outputs has to be. A rocker with an offset boss has a step in it. The four-bar hinge in the essay on where a hinge pin can go has arms that curve round the carcase, and that essay says in as many words that its arms are still lines and names the clearances that leaves unchecked.

So the field’s first job is to make a dented shape answerable, and the first thing to establish is that the obvious shortcut is not available.

The separating axis is not approximately right #

The separating-axis test rests on a theorem about convex sets: two of them are disjoint exactly when some line separates them, and testing the directions normal to their edges is enough. Neither half survives a dent.

A non-convex shape and a convex one can be disjoint with no separating line at all — which is a fact about convexity rather than about mechanisms, and is why the gap between two bars could be computed by a separating axis and this cannot — put a small block inside the notch of an L and no line has the block on one side and the whole L on the other. Run the test anyway and it finds an axis on which the projections overlap, concludes that the shapes overlap, and returns a depth. The number is a real number, computed correctly from a formula that does not apply.

That is a different failure from an approximation. An approximation is wrong by an amount that can be bounded and quoted; this is wrong in the sense that the quantity it computes is not the quantity it is named after. Nothing about the output says so: it has the right sign conventions, the right units, the right order of magnitude, and it moves smoothly as the parts move.

Which is why body() refuses rather than warns. A refusal at construction is the only place the mistake is cheap.

Cutting the shape up #

A polygon that is simple — an outline that does not cross itself — can be cut into convex pieces, and then the distance between two polygons is the best answer over the pairs of pieces. Two stages, because neither alone gives what is wanted.

Ear clipping cuts the outline into triangles. It walks the corners looking for an ear: three consecutive vertices whose triangle turns the right way and contains no other vertex. Cut it off, and the polygon has one fewer corner; repeat until three are left. Triangles are certainly convex — the same fact that makes a triangulated frame rigid — and there are certainly too many of them — a six-cornered bell crank becomes four, and the clearance test then costs sixteen piece pairs where four would do.

Hertel–Mehlhorn puts them back together. Take each diagonal the triangulation introduced and delete it if both sides stay convex without it. One pass, and the result is at worst four times the fewest pieces possible — a bound this file does not lean on, because the counts here are small enough to count by eye. On the bell crank it gives two quadrilaterals, which is what anybody would have drawn.

The merge is where the one real bug in this field lived, and it is worth recording because of how it presented. Both rings are anticlockwise, so the shared edge runs one way in the first piece and the other way in the second; the merged ring walks the first as far as the shared edge, crosses into the second, and comes back — taking the vertices strictly between the two shared endpoints, because those two are already in the first ring. Taking one of them as well leaves a repeated vertex. A repeated vertex is a zero-length edge. A zero-length edge has no normal, and the separating-axis loop divided by its length, got the fallback, projected everything onto the zero vector, and measured a penetration depth of exactly zero for every overlapping pair on the site.

Every gap in the catalogue read 0.0000. Not one figure was obviously wrong: the machines looked as though they just touched, which is a plausible thing for a mechanism to do, and the number was the same on every one of them, which reads as a shared convention rather than as a shared bug. What caught it was a check that the merged ring has as many vertices as the two pieces less two.

Checking a decomposition, three ways #

A decomposition can fail in three ways and only one of them shows up as a wrong picture, so it is checked in three ways.

The pieces tile the polygon. Their areas sum to its area, to 10⁻¹² relative, on every shape in the field. This catches a lost piece and an overlapping pair.

Every piece is convex. Not asserted by the code that made them but measured by body(), which is the code that depends on it. The decomposition’s own claim is checked by its consumer rather than by its author, which is the same discipline that makes the site’s mobility counts worth reading.

And a point is inside the pieces exactly when it is inside the polygon. Four thousand random points per shape, with the ones within a hair of an edge excluded because both answers are legitimate on a boundary. This is the check the areas cannot make: a decomposition that fills in the dent and loses a piece somewhere else has exactly the right total area. It comes back with zero mismatches on the field’s three shapes.

The decomposition happens once, in the link’s own coordinates, and not once per frame. A placement is affine — a rotation, a uniform scale by the link’s length, a translation — so it takes convex pieces to convex pieces, and the decomposition of a placed body is the placement of the decomposition. Running the clipper per frame would be three hundred and sixty identical answers, which on Peaucellier’s eight links is most of the cost of a sweep.

The shortcut, and what it costs #

The cheap alternative to all of this is the convex hull: take the smallest convex shape containing the part, use that as the body, and every test on the site works unchanged. It needs no decomposition, it is a dozen lines, and a great deal of collision code does exactly this.

It is also safe in the only direction people check, which is the direction the tolerance field’s worst case is careful about too. A hull contains the part, so it can only ever report interference that is not there — never the reverse. A design that passes on hulls certainly passes on the real shapes, and that is a genuine guarantee.

The question nobody asks is how much the guarantee costs, so here it is measured. On a right-angled bell crank with arms 1 and 0.7 and a half-width of 0.08, the hull is 105% more material than the crank: it is more than twice the part, and every bit of the difference is in the notch between the arms.

The notch is not a random place. It is exactly where a designer puts things — a stop, a spring anchor, an adjacent link’s boss, a cable — because it is the space the part deliberately leaves. A block in that notch clears the real crank by 0.020 and is 0.120 inside its hull. The hull says no to the one arrangement the shape was chosen to allow.

That is the shape of the argument against a conservative approximation in general, and it is not the usual one. The complaint is not that it is wrong — it is not — but that on the arrangements a designer actually tries, it is wrong by more than the quantity being measured. A test whose answer is dominated by its own conservatism is a test that has stopped depending on the design.

Simple, and measured rather than assumed #

Before a polygon can be cut up it has to have an inside, and an outline that crosses itself does not. Every question in this file would still return a number for a figure-of-eight: the ear clipper terminates, the pieces come out convex, the shoelace formula produces an area, and the area is the difference of the two lobes rather than their sum.

So simplicity is measured at construction, by testing every pair of non-adjacent edges for a crossing. On a six-cornered crank that is nine pairs, once, when the shape is made — and it is the kind of check whose value is entirely in the case that has not happened yet. The shapes in this field are generated from a handful of parameters, and a bell crank whose bend angle is pushed past π has an outline that crosses itself: the arms fold back through each other, the picture looks like a bow tie, and every downstream number is about a region with no interior.

The refusal is at the parameter, too, for the same reason. A bell crank asks that its bend be a real angle rather than something within a fifth of a radian of straight or of folded, because at those limits the inner corner runs off to infinity — the intersection of two nearly parallel lines — and a polygon with a corner ten thousand units away is simple, convex-checked, and useless.

What the pieces cost, and what they save #

The decomposition is done once per shape and the pieces are then placed per frame, so the arithmetic per configuration is proportional to the number of pieces, squared over a pair.

For a bar that is one piece and the pair cost is one. For a bell crank against a bar it is two. For two bell cranks it is four. The numbers stay small because Hertel–Mehlhorn gets close to the minimum, and the difference from ear clipping alone is the difference between four and sixteen on that last pair — enough to matter on a 360-position sweep and not enough to be interesting.

What the merge really buys is not speed. It is that the pieces are recognisable: two quadrilaterals that are visibly the two arms of the crank, rather than four triangles with a diagonal across the corner. Every figure in this field that shows a decomposition shows it because a reader can check it by eye, and a reader can only check a decomposition they would have drawn themselves.

What non-convexity does to the depth #

For shapes that are apart, decomposing changes nothing about the meaning: the distance between two polygons is the smallest distance between their pieces, and the minimum of minima is a minimum.

For shapes that overlap it does change the meaning, and the change is easy to get backwards. The pair has to be moved apart by enough to free the worst overlap, so the depth of a dented pair is the largest of the pieces’ depths. Taking the smallest — which is what the convex case does over its edge normals, and which is the code sitting immediately above — gives a number that shrinks as the decomposition gets finer, and eventually reports a deeply interfering pair as barely touching.

Both cases are in one function with one sign convention, and the branch between them is on whether any piece pair overlaps at all.

The shapes this field actually uses #

Three, and the restraint is deliberate.

A bar, which is an octagon: a rectangle of half-width w with its ends replaced by the tangents to two bosses of radius 1.35w. Convex, eight corners, one piece.

A bell crank, which is an L: two arms of half-width w meeting at a shared pin, with the inner corner where the near side of one meets the upper side of the other and the outer corner behind the pin where their far sides meet. Six corners, one of them reflex, two pieces.

A block, which is a rectangle carried at a joint rather than stretched along a link — the part that realises a prismatic pair — because a slider’s “link” is the line from the frame to the block and its length changes as the thing moves. Placed the way a bar is placed, the block grew and shrank through its own stroke, and the guide search converged on a guide exactly as long as the block.

That is the whole vocabulary. A real part is a casting with fillets, webs, lightening holes and a boss that is not concentric with anything, and none of that is here. What is here is the smallest set of shapes that makes the field’s questions well posed: something convex, something with a dent, and something that does not scale with its link.

The gap between those three shapes and a real part is the same gap this site has always had between a solved mechanism and a built one, and it is stated the same way. A number here is a statement about the geometry as dimensioned. What a foundry, a fillet radius or a lightening hole would do to it is a different subject.

What this buys the site #

Two things, and the second is bigger than it looks.

A bell crank can be a link. The catalogue’s fourth machine is the site’s own crank rocker with its rocker replaced by an L, and the only difference in the code is which shape the part carries. It gets the same treatment as everything else: the same gap, the same sweep, the same conflict graph, the same three planes.

And the hinge can be checked. That essay is careful about what it did not do — “the arms of the four-bar hinge are still lines here, and the essay says which clearances that leaves unchecked” — and the reason was that the arms are not convex and the machinery refused them. The refusal was right, the gap it left was recorded, and the shape of the repair was written down at the time: bodies for the arms and a test that survives a dent. That is what this essay is.

There is a second gap the decomposition closes, smaller and worth recording. The site’s own interference.js refuses a non-convex body, so any figure that wanted one had to either simplify the part until it was convex or leave the part out of the test. Both were done: the hinge arms were left as lines, and the cabinet door was drawn as a convex panel, which it genuinely is. What could not be done was to say how wrong the simplification was — and the hull measurement above is exactly that number, for the shape a hinge arm is. A hundred and five per cent, all of it in the notch.

The general rule it is an instance of is the one the site keeps rediscovering. A tool that refuses a case is not a tool with a hole in it; it is a tool that has said where its edge is. The failure mode to be afraid of is the other one — the routine that takes a dented polygon, applies a theorem about convex sets, and hands back a number with no complaint at all.

The shortcut adding a hundred per cent more material is the number that decides the practice, and it is worth stating what the trade actually is. A convex hull is cheap and conservative: one computation, one test, and a verdict that never misses an interference. A convex decomposition is expensive and exact: several pieces, several tests, and a verdict that is right. So the choice is between an answer that is fast and wrong in a known direction and one that is slow and correct — which is a perfectly ordinary engineering trade until the wrongness is measured, and at a hundred per cent it stops being ordinary. A hull that doubles the part is not a slightly conservative approximation; it is a different part. That is the argument for doing the decomposition, and it is an argument that could only be made by measuring the excess rather than reasoning about it, because conservative is a direction and says nothing at all about a size.