A Constraint Solver With No Equations

Someone authoring a virtual lab experiment does not want to type coordinates. They want to say what the scene is:

The compass sits five centimetres east of the bar magnet, resting on the desk, turned to face it.

Something has to turn that into position: [0.083, 0.0, 0.0] and rotation_euler_deg: [0, 0, 180] — numbers nobody typed, that must be right the first time, and must be identical every time the document is processed.

That something is the piece of this project I am proudest of. Not because it is large — the whole constraint layer is about seventeen hundred lines — but because of what it does not contain.

It contains no equations. Nothing is ever solved.

What people expect a constraint solver to be

Say "constraint solver" and most engineers picture the same thing. You collect the constraints into a system, you express them as residuals, and you hand the whole thing to something iterative — least squares, gradient descent, a physics relaxation loop. It runs until the error is small enough, and out comes a configuration that approximately satisfies everything at once.

That is the right architecture for CAD sketch solvers and inverse kinematics, and it was the wrong architecture here, for four reasons I only fully understood after choosing differently.

It can fail. Iterative solvers do not converge on over-constrained systems, and an author who writes two contradictory conditions deserves better than a spinner and a timeout.

It is approximate. "Close enough" is fine for a robot arm and not fine for a document that gets stored, re-processed, and compared against its previous output.

It is opaque. When a numerical solver produces a wrong answer, you cannot ask it why. There is no step at which the mistake was made; there is only a minimum in the wrong place.

And it is stochastic in the small. Floating-point iteration order, initial guesses, convergence thresholds. Two runs can differ in the last decimal, and I needed byte-identical output.

What it actually is

Sixteen pure functions.

Each one takes the pose accumulated so far and returns a modified pose. They are sorted by a priority number and applied in order, each seeing the output of the last. There is no system, no residual, no iteration, and no possibility of non-termination.

const acc = initialAccumulator(sceneState, objId);
const sorted = sortByPriority(constraints);

for (const c of sorted) {
    const handler = registry.get(c.type);
    applyConstraint(handler, c, objId, sceneState, acc, context);
}

That is the entire engine. Everything interesting is in the ordering and in what each function knows.

The priority ladder is the whole idea

Every constraint type declares a priority. Here they are, in the order they run:

Read that column top to bottom and it is a person's hands.

You pick the object up and turn it the right way round. If it clips onto something, you clip it. You set it down on the surface. You slide it to the right distance. You rotate it to face what it should face. You flip its switch. You step back and check you can see it.

That is not a coincidence and it is not decoration. The reason the ladder works — the reason sequential application produces correct results where you would expect a simultaneous system to be necessary — is that placement is genuinely sequential in the author's head too. Nobody holds six spatial conditions in mind at once and looks for a configuration satisfying all of them. They perform an ordered series of physical actions. The solver performs the same series.

The priority numbers are not a scheduling detail. They are a claim about how humans place objects, encoded as integers.

The trick that makes composition work

There is a subtlety that took me an embarrassingly long time to find, and it is six lines long.

Constraints frequently need to resolve an anchor — a named point on an object. The spout of a kettle. The top face of a ring stand. The north pole of a magnet. Anchor resolution reads the object's current pose from the scene state and transforms the local anchor point into world space.

Now consider two constraints on the same object. The first moves it. The second needs one of its anchors. If anchor resolution reads the scene state, it computes the anchor at the object's start-of-step pose — before the first constraint ran. The second constraint then places the object relative to a point that no longer exists.

The fix is to lie to the scene state, briefly:

let savedPos, savedRot;
if (state) {
    savedPos = state.position;  savedRot = state.rotation;
    state.position = acc.position;  state.rotation = acc.rotation;
}

applyConstraint(handler, c, objId, sceneState, registry, acc, context);

if (state) {
    state.position = savedPos;  state.rotation = savedRot;
}

Before each constraint, the object's entry in the scene is patched with the in-progress accumulator. After, it is restored. Every constraint therefore sees the object where it is right now, mid-solve, without any of them having to know that a solve is in progress.

The accumulator is also exposed on the shared context, so a constraint can read what earlier ones decided. The snap constraint uses this: it prefers the accumulated rotation over the start-of-step rotation, so an orientation applied before it correctly rotates the anchor before the snap is computed. Orient the bracket, then snap it on.

Six lines of save-patch-restore is what turns sixteen independent functions into something that composes.

The decision I would defend in any room

Here is the one that makes the language feel like it understands you.

When an author writes a radius of five centimetres, they do not mean five centimetres between two invisible origin points. They mean five centimetres of visible air between two objects. That is what "put the beaker 5 cm from the burner" means to every human who has ever said it.

So that is what it means to the solver:

// `radius` is a nearest-surface gap, not a centre-to-centre distance.
const centerExtent = isBareRef(constraint.around)
    ? xyHalfExtent(centerObjId, dirX, dirY, sceneState, registry)
    : 0;
const placedExtent = xyHalfExtent(objId, dirX, dirY, sceneState, registry);

const totalDist = Math.max(radius, MIN_SURFACE_GAP) + centerExtent + placedExtent;

The authored gap, plus how far each object sticks out along the direction between them.

That second part has to work for objects at arbitrary rotations, which is where it gets pleasing. The half-extent is a support function over an oriented bounding box:

const q = eulerToQuaternion(state.rotation);
const ax = q.rotateVector(new Vec3(hx, 0, 0));
const ay = q.rotateVector(new Vec3(0, hy, 0));
const az = q.rotateVector(new Vec3(0, 0, hz));

return Math.abs(ax.x * dirX + ax.y * dirY) +
       Math.abs(ay.x * dirX + ay.y * dirY) +
       Math.abs(az.x * dirX + az.y * dirY);

Rotate the three half-axes, project each onto the direction, sum the absolute values. That is exactly how far the box extends along that ray, for any rotation, exactly, in closed form. It is the same projection separating-axis collision tests use, borrowed for a friendlier purpose.

The consequence is that an author never thinks about object dimensions. They say five centimetres and get five centimetres of gap, whether the neighbour is a thermometer or a beaker, upright or tilted. Swap the object for a larger one and the scene stays correct, because the gap was the intent and the gap is what was stored.

Every constraint that talks about distance works this way. There is a floor of five millimetres so that a zero or sub-millimetre radius cannot resolve into interpenetrating surfaces.

The dot that changes the meaning

A detail I like more than its size warrants.

References come in two shapes. A bare one names an object: burner. A dotted one names a point on it: burner.top.

The solver treats them differently on purpose. A bare reference means the object, so the object's extent participates in the gap arithmetic. A dotted reference is an exact point, so it contributes nothing.

Place something five centimetres from burner and you get five centimetres from the burner's surface. Place it five centimetres from burner.top and you get five centimetres from that specific point.

One character of syntax selects between "keep clear of this thing" and "measure from this spot". Both are things authors want to say, they mean different things, and neither needs a flag or a mode. That is language design happening inside a geometry engine, and it is the sort of decision that makes a format feel considerate rather than merely capable.

The constraint that is a trap, documented as one

Not everything here is clean, and the one sharp edge is worth showing because of how it is handled.

One constraint places things in the viewer's frame — left, right, near, far. It resolves through the active camera's basis vectors:

const forward = q.rotateVector(new Vec3(0, 1, 0)).normalized();
const right = forward.cross(new Vec3(0, 0, 1)).normalized();

Which means the resulting world position depends on where the camera is. Move the camera and the placement rotates with it. Author "to the left of the burner" from a front view, switch to a side view, and "left" is now somewhere else entirely.

That is a feature when the intent is compositional — keep this out of the way of that, from wherever we are looking — and a trap when the geometry has to hold regardless. Two objects that must be coaxial cannot be placed this way.

Two things make it safe. The contract says so explicitly, in the guidance authors and language models read: use the viewer-relative constraint for composition that should track the camera; use the polar one, or explicit coordinates, when the geometry must hold regardless of camera.

And the solver freezes the camera pose it used onto the step's output. Re-processing the same document later, with a different camera, still reproduces the original placement, because the pose that produced it travelled with the result.

A camera-dependent constraint that records which camera it depended on is a very different thing from one that quietly re-resolves. The first is a documented tool. The second is a bug that appears months later.

Collision resolution is repair, not placement

After the constraints have had their say, two passes tidy up. One resolves overlapping bounding boxes. One enforces that everything sits above the surface it rests on.

The obvious design for the first is to compute the free region — the space nothing else occupies — and put the object somewhere inside it. That is the textbook approach and it is the wrong one here, for a reason that took me a while to articulate.

The constraints already decided where the object should be. Collision resolution is not being asked to find a position; it is being asked to correct one. "Anywhere valid" is a far weaker requirement than "as close as possible to what the author asked for, subject to not interpenetrating". An object placed five centimetres east of the magnet that ends up somewhere else entirely, because that is where the free space happened to be, has satisfied geometry and discarded intent.

So the pass moves the object minimally, along an axis that means something, and it only ever moves the object the step actually moved. Bystanders are never shoved — if something must sit elsewhere, its authored start position is the place to change it.

Most overlaps are legal

The deeper reason a free-region formulation does not fit is that in this domain, overlap is frequently the point.

A pH strip dipped into a beaker overlaps the beaker. A probe inserted into a holder overlaps the holder. A spacer resting on a platform shares a contact face. A thermometer in a cup is supposed to be inside the cup. A free-space computation would exclude precisely the positions the author asked for.

So the pass carries a semantic model of when overlap is intentional:

• Objects named together in the same step's match, close-distance or on_surface constraints are exempt from each other. Those constraints exist in order to co-locate them.
• Contact is not penetration. Two boxes whose smallest overlap is under a tenth of a millimetre are touching, and touching is left alone — which is what lets a spacer sit flush on a platform instead of being kicked sideways.
• Containers declare their cavities. When at least 80% of an object's horizontal footprint lies inside a container's declared interior volume, it is in the container, not colliding with it. The threshold earns its keep in both directions: a probe leaning against the rim stays exempt, while a cup parked beside a bucket with one corner overhanging the mouth does not.

None of that is expressible as a region. It is a set of judgements about what the author meant.

Some poses cannot be repaired at all

The strongest case against free placement is the snap constraint.

When an object's pose is determined by snapping its anchor onto another object's anchor, there is no acceptable alternative position. Displacement of any size breaks the coincidence — a thermometer whose focus anchor was aimed into a dish now reads ten centimetres beside it. Geometrically valid, semantically destroyed.

So a pose pinned by a snap is not nudged at all. The pass keeps it verbatim and logs the residual overlap instead:

Kept 'probe' on its anchor match despite overlap with 'beaker' — nudge would break the match

A loud, correct scene beats a quiet, wrong one. A free-region picker would have relocated it and said nothing.

The escape direction comes from the constraint

When a nudge is warranted, the direction is not derived from geometry alone.

For a distance constraint between two objects, the natural escape is along the line between them — the constraint's own axis. Without that hint the separator picks whichever bounding-box axis has the smallest overlap, and for two ring stands of equal width the X and Y overlaps are identical, so the tie-break sends one diagonally up the desk. Correct by the geometry, obviously wrong to look at.

So the pass reads the step's own constraints, builds a map of partner to escape axis, and separates along it.

And when minimal repair fails, it does search

The nudge loop is bounded and it watches itself. If the object returns to within a millimetre of a position it has already visited, it is oscillating between two obstacles, and the pass escalates: pick the axis with the most room, generate candidate positions a full object-width out on either side, and test each candidate for clearance against everything else in the scene.

That is the free-region idea, applied exactly where it earns its cost — after the cheap, intent-preserving method has demonstrably failed. Doing it first would pay for a search on every placement in order to handle the small fraction that need one.

Why the pipeline runs the pair twice

That leaves the shape of the pipeline: collision, surface, collision, surface.

The two passes repair on different axes and interfere with each other. Collision resolution moves objects laterally, in X and Y, leaving height alone. The surface pass corrects height. Slide an object sideways and it may no longer be over the surface it was resting on, so its correct height changes. Change its height and its three-dimensional overlap changes, so a new collision can appear.

Each pass is required to be idempotent: running it on a settled scene must change nothing. That is the property that makes the pipeline correct rather than merely repeated — a settled scene is a fixed point, and two rounds reach it for every scene we have.

Looping until nothing changes would add an iteration cap, a non-convergence path, and a decision about what to do when it is hit. Both of the inner loops already carry exactly that machinery, because they genuinely need it — twenty-five iterations for a step, up to two hundred sweeps for a scene's initial layout, with oscillation detection in between. The outer pipeline does not need it, because with idempotent passes and a coupling that only runs one way at a time, the settling depth is a small fixed number rather than an open question.

Why determinism was the requirement

Everything above serves one property: the same document always produces the same numbers.

That matters because these documents live a long life. They are stored, re-processed when the format version moves, diffed when someone edits them, reviewed by people comparing before and after, and covered by regression tests that assert on exact output.

A solver that lands within a millimetre would break every one of those. Not visibly — the scene would look fine — but the diff would be noise, the test suite would need tolerances, and "did my edit change anything else" would stop having an answer.

Sequential application of pure functions gives determinism for free. There is no iteration to vary, no initial guess, no threshold. The output is a function of the input in the ordinary mathematical sense.

What it gives up

It cannot satisfy genuinely simultaneous constraints, and it does not pretend to.

Two constraints that fight do not negotiate and do not error. The one with the higher priority number runs later and wins. Write a distance and a snap that disagree and you get the snap, silently.

For a general-purpose geometry kernel that would be disqualifying. Here it is correct, because of the thing the priority ladder is built on: authors do not write systems of simultaneous conditions. They write recipes. Put this here. Then that there. Then turn it around. The last instruction is meant to win — that is what "then" means.

The whole design rests on that observation, and if it were wrong the architecture would be wrong with it. Sixteen pure functions, one ordering, no equations, and a bet that placement is a sequence rather than a system.

Three years of authored scenes have not disproved the bet.