Convex Hull
Algorithms & Data
The convex hull is the shape a rubber band
makes when you snap it around a set of pins — the smallest convex outline that contains them all.
This one wraps a drifting cloud of points, recomputed every frame by
gift-wrapping, which is built
from a single geometric question — left turn or right turn? — answered by the sign of a
2-D cross product. Runs on its own; no joypad needed. Written in C and compiled with the
llvm-mos-based 65816 toolchain
(+mos-a16, 16-bit accumulator mode).
Self-running demo — the hull rubber-bands around the drifting points.
Click the screen to focus, then watch. Tab away and it pauses.
What it is
Gift-wrapping finds the hull the way you'd wrap a present with string: from the leftmost point, keep turning to the point that leaves everything else on one side. Each turn is an orientation test:
cross(O, A, B) = (A.x-O.x)*(B.y-O.y) - (A.y-O.y)*(B.x-O.x); // > 0 : B is to the LEFT of O->A (a left turn) // < 0 : B is to the RIGHT (a right turn) // = 0 : O, A, B are collinear
No trigonometry, no distances — just the sign of a cross product, computed in 32-bit so it can't overflow. As the points drift, the rubber band flexes to stay taut, and the whole thing stays bit-exact across every codegen mode.
Compiler stress-test
| Item | What it exercises |
|---|---|
| orientation test | The whole hull is built from one question: turning from one point toward another, is a third point to the left or the right? The sign of a 2-D cross product answers it — no angles, no square roots, just multiplies and subtracts. |
| gift-wrapping | Start at the leftmost point and repeatedly pick the point that everyone else is to the left of — like pulling a rubber band taut around a set of pins. Each step is a sweep of orientation tests. |
| int32 to avoid overflow | The cross product multiplies coordinate differences, which can exceed 16 bits, so it is computed in 32-bit with an explicit cast — making the host (32-bit int) and the 65816 (16-bit int) agree exactly. |
| cross-checked | The build gate verifies every result is a genuine convex hull — every edge has all points on its left — so a slip in the orientation sign is caught at once. |
Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg
(and MAME where the SPC700 IPL is present). Hit Verify fidelity to reproduce the build
gate's WRAM assert (gate CRC 0x84E3 — the hulls of many random point clouds, each
checked for validity) live in this tab. No far pointers — the same source passes every way:
host == default == +mos-a16 == +mos-xy16 == bsnes-jg,
-verify clean.