Marching Cubes

When a hospital MRI scanner finishes its work, the result is not a picture — it is a grid of numbers. Each tiny voxel (a 3D pixel) stores a density value: how much the tissue at that point resisted the magnetic field. Bone is dense; air is not; soft tissue lives somewhere between.

To make the scan useful, doctors need a surface: the boundary between one material and another. Draw a threshold value and ask — which voxels are above it and which are below? The surface you want is the shape that separates them.

That problem looks impossibly hard at first. A real scan has hundreds of millions of voxels; the surface can be any shape imaginable. But in 1987, William Lorensen and Harvey Cline discovered a beautiful shortcut: no matter how complicated the surface is, each individual cube of eight voxels can only be in one of 256 possible states. Pre-compute what triangles to draw for each state, store the answer in a lookup table, and then march through the grid one cube at a time — that is the Marching Cubes algorithm.

It is fast, it is simple, and it powered the very first real-time 3D reconstructions of medical scans. Today it still runs — in a slightly refined form — under nearly every 3D volume viewer in medicine, science, and game development.

The demo below shows a 2D version of the algorithm (called marching squares) on a small scalar field. Each cell in the grid stores a value; the color shows how large it is. Drag the threshold slider and watch the algorithm classify each cell, look up the right edge-crossing pattern, and stitch the contour together.

<div class="controls">
  <label for="thresh">{{label_threshold}}: <span id="thresh-val">0.5</span></label>
  <input type="range" id="thresh" min="0" max="1" step="0.01" value="0.5">
  <button id="animate" type="button">{{btn_animate}}</button>
  <button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="420" height="280"></canvas>
<div id="info" class="info">{{info_initial}}</div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: #fff; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem .8rem; margin-bottom: .6rem; }
label { font-size: .85rem; font-weight: 600; white-space: nowrap; }
input[type=range] { width: 140px; accent-color: #1d3557; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #d0d8e0; border-radius: 8px; max-width: 100%; }
.info { font-size: .82rem; color: #556; margin-top: .5rem; min-height: 1.3em; }

// Code not found

Notice two things. First, once the threshold is set, each cell is decided independently — the algorithm never backtracks or searches. Second, cells near the boundary flip between "inside" and "outside" as you drag the slider, instantly updating the contour. This is the lookup-table trick: a handful of pre-drawn cases, stamped onto the grid one cell at a time. The 3D version works the same way with 256 cases instead of 16.

Marching Cubes is one of the rare algorithms whose complexity is exactly as good as it can possibly be.

• Each cube is independent. The algorithm looks at the eight corner values of one cube, computes a single 8-bit index (0–255), fetches the pre-stored triangle list from a table, and moves on. No search, no backtracking, no communication with other cubes.
• $O(n)$ time, $O(1)$ per cube. If the volume has n voxels, the algorithm takes $O(n)$ time in total and constant time per cube. You cannot do better: you must at least look at every voxel once.
• The lookup table has exactly 256 entries — one per distinct combination of eight binary corner states (inside/outside). By symmetry, many are rotations or reflections of each other; Lorensen and Cline reduced them to 15 canonical cases in their original paper.
• Ambiguous faces are the only complication. When opposite corners of a face are inside and the other two are outside, two different triangle tilings are both valid, and choosing the wrong one can leave a hole in the surface. Several follow-up algorithms (Marching Tetrahedra, Dual Contouring) trade a small increase in complexity for a guaranteed hole-free result.
• Parallelism is trivial. Because cubes are independent, marching cubes is embarrassingly parallel — the entire volume can be split across GPU cores, which is why modern volume renderers run it in real time on medical-grade datasets.

Contrast this with problems like P vs NP where checking solutions is easy but finding them is expensive. Marching cubes is the opposite extreme: both finding and checking are linear. The hard part was realizing that 256 cases are enough.

The 256-case lookup table shows up in a surprisingly wide range of fields:

• Medical imaging: CT and MRI scanners produce voxel grids; marching cubes turns them into the smooth 3D organ models that surgeons use for pre-operative planning and that radiologists annotate on screen.
• Scientific visualization: weather simulations, computational fluid dynamics, and molecular dynamics all produce scalar fields — density, pressure, temperature — and marching cubes extracts the surface at any threshold in one linear pass.
• Video-game terrain and destruction: voxel-based games (Minecraft's smoother cousins, teardown simulations) store the world as a density grid and use marching cubes — or its variants — to generate renderable meshes in real time as terrain changes.
• Metaballs and implicit surfaces: 3D artists define objects as mathematical formulas ("the set of points closer than r to this skeleton"); marching cubes samples the formula on a grid and extracts the visible surface.
• 3D printing slicing: converting a solid model into printable layers requires intersecting the model with horizontal planes — essentially marching squares repeated per layer.

The algorithm is closely related to ideas in convex hull computation and mesh generation — anywhere a discrete sample must be turned into a geometric boundary.

Lorensen and Cline's key insight was deceptively simple: however wild the surface, each cube of eight voxels carries only one bit of information per corner, giving at most 256 distinct cases. Pre-tabulate the answer for all 256 and the rest is just iteration — march through the grid, stamp the right triangles, done.

That simplicity is the algorithm's superpower. It runs in linear time, parallelises perfectly, and can reconstruct a surface at any density threshold without ever searching or backtracking. Forty years after its publication, the same idea still drives the 3D models on every radiologist's screen.

The next time you see a smooth 3D scan of a brain or a lung, picture 256 tiny cookie-cutters stamping triangles across millions of cubes — one lookup per cube, no exceptions. That is marching cubes, and it is one of the cleanest algorithmic ideas in all of computer graphics.