MARCHING CUBES the isosurface, and the patent that shaped graphics
To turn a 3-D scalar field (a CT scan, a density) into a triangle mesh, march a cube through it: classify the 8 corners as inside/outside the surface into an 8-bit index, look up which edges the surface crosses in a 256-case table, and place vertices by interpolation. Simple, fast, and for 18 years patented — which is why a generation used clumsier alternatives.
THE TECHNIQUE 8 corners to a byte, a byte to triangles
Each corner is inside or outside (value below or above the isolevel) — eight bits, one byte, 256 cases. A precomputed table says which cube edges the surface crosses; each crossing vertex is placed by linear interpolation along its edge. Below: the 2-D sibling (marching squares) drawing a live contour; toggle a corner to see the case index. live demo
HISTORY & CREDIT a lookup table under patent
“Free since 1987” — it was freepatented until 2005, and the original table had a real bug (cracks). cited
1987 · Lorensen & Cline (General Electric) publish marching cubes at SIGGRAPH — and GE patents it (US 4,710,876). the bug · the original 15-case table handled ambiguous faces inconsistently, leaving holes in the mesh; Durst (1988) flagged it, Nielson & Hamann (1991) fixed it with the asymptotic decider. the workaround · because of the patent, many switched to marching tetrahedra, developed expressly to circumvent the claim — a whole era of clumsier code. (GE’s own dividing cubes was no escape — it was patented too, US 4,719,585.) 2005 · the patent expires; marching cubes becomes the free default it always should have been.
A 256-entry table that reshaped how a field’s surface is drawn — and how it was licensed. Lorensen-Cline 1987
RECOMMEND FOR I-13 bitwise index, lerp, bounded table
The corner test is bitwise, the vertex placement is f64 lerp, the case table is a bounded array — and the index comes out on the compiler:
$ i13 run mc.i13 # v0 inside, v1..v7 outside, iso=0.5
cubeindex = 1 edge-t = 0.5 # one triangle cutting corner v0 off
Recommend: the heart runs — the corner test shifts each value < iso into place and ORs the eight (& | <<, verified index 1), the vertex interpolation is a plain f64 lerp, and the case table is a bounded array lookup. The strain is the 256×16 integer triangulation table: I-13 arrays hold f64 only (and 2-D is a want, PS-004), so it flattens to a length-4096 f64 array with −1 sentinels — it works, the natural 2-D int table is the frontier. Note: the original table’s ambiguity bug is the corpus’s recurring lesson — an unstated invariant (consistent face resolution) that a checker never enforced.