Marching Squares

Cellular Automata

How 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).

loading core…

Self-running demo — blobs merge and split under a traced contour.

Click the screen to focus, then watch. Tab away and it pauses.

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.