Marching Squares
Cellular AutomataHow do you draw the outline of a blob that has no outline — just a field of values? You
march: marching squares walks
a grid over the field, and in each cell reads the four corners as a 4-bit case, looks up which
edges the contour crosses, and interpolates where. The result is a clean iso-line traced around
merging, splitting metaballs — here on a Super Nintendo, all integer, so it's bit-exact. 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 — blobs merge and split under a traced contour.
Source msquares.cmsquares.h in wbniv/llvm-mos-65816
What it is
For each cell of the grid, the four corners are thresholded against the iso value into a 4-bit case, a 16-entry table gives the edges the contour crosses, and each crossing is interpolated:
case = (tl>=iso)<<3 | (tr>=iso)<<2 // 4 corner signs
| (br>=iso)<<1 | (bl>=iso); // -> a 4-bit index
edges = MS_SEG[case]; // which edges cross (16-case LUT)
t = (iso - va) / (vb - va); // crossing point on each edge Stitch those little segments together across the whole grid and you get the smooth iso-contour of the field — the yellow outline around the blobs. It's a case-table lookup plus a divide per crossing, identical across every codegen mode.
Compiler stress-test
| Item | What it exercises |
|---|---|
| the 4-bit case | Each grid cell has four corners; each is either inside the shape or outside. Those four yes/no bits make a number 0..15 — the case. A 16-entry table then says, for that case, which of the cell's edges the contour line crosses. |
| edge interpolation | A crossing is not snapped to the edge midpoint — it is placed by linear interpolation, t = (iso - a) / (b - a), so the contour is smooth. That divide, per crossing, is the heart of the inner loop. |
| contour extraction | The scalar field here is a sum of moving blobs; marching squares pulls out the single iso-line where the field equals a threshold. It is how contour maps, medical isosurfaces and metaball outlines are drawn. |
| integer, bit-exact | Coordinates are 16-bit and the field and interpolation are 32-bit integers, so the extracted contour is identical on the host and the 65816 — the build gate folds the case indices and crossing points and asserts a match. |
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 0x86A7 — a fold of the marching-squares case indices and
crossing points over two frames) live in this tab. No far pointers — the same source passes every
way: host == default == +mos-a16 == +mos-xy16 == bsnes-jg.