Skip to content
Computational Lab.

Marching Squares

Contours from a sixteen-case lookup.

Intermediate / contours / implicit-surfaces

Marching squares turns an implicit field into line segments: classify each grid cell by which corners sit above the iso value, then place the crossing edges - with interpolation for smoothness and the standard resolution for the ambiguous saddle cases. The metaballs move; the contours follow.

Tagged: iso-contour, metaballs, interpolation, saddle case

Live simulation

The iso slider retightens the contour around the moving blobs.

Speed

The iso slider retightens the contour around the moving blobs.

Mathematics

Marching squares turns a scalar field into an iso-contour: each grid cell is classified by a 4-bit code (which corners exceed the threshold), and a 16-case lookup returns the line segments crossing that cell. Linear interpolation positions each crossing along the edges for sub-cell smoothness.

cell code: bit_i = 1 when f(corner_i) > iso

edge crossing: t = (iso - f_a) / (f_b - f_a)

saddle cases (5, 10): resolved by the cell-center average

The two ambiguous cases (codes 5 and 10) are where topology is decided: the center average chooses whether opposite corners connect as one region or two - the standard resolution, and the only place the algorithm makes a judgment call. Everything else is lookup and interpolation.

How it works

Three metaballs move on seeded paths; the field is their inverse-square sum sampled on a 70x70 grid. Below-threshold cells are shaded faintly, contour segments are drawn in accent, and the segment counter lets you see the contour complexity respond to the iso slider.

Drag the iso value across a blob and watch the contour tighten around it - the implicit surface's shape was always in the field; marching squares just extracts it.

Implementation

src/engine/experiments/marching-squares.ts · 191 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4/**
5 * Marching squares over a field of moving metaballs: the classic 16-case
6 * table turns the implicit surface f(x, y) = threshold into line segments.
7 * The contour you see is computed in the tick, not drawn by hand.
8 */
9export class MarchingSquaresExperiment extends BaseExperiment {
10 readonly id = "marching-squares";
11
12 private blobs = [
13 { cx: 0.3, cy: 0.3, vx: 34, vy: 26 },
14 { cx: 0.7, cy: 0.6, vx: -28, vy: 31 },
15 { cx: 0.45, cy: 0.75, vx: 22, vy: -33 },
16 ];
17 private threshold = 1;
18 private segments = 0;
19 private segmentList: number[] = [];
20
21 protected params(): ParameterDef[] {
22 return [
23 { key: "threshold", label: "Iso value", min: 0.5, max: 2.2, step: 0.05, defaultValue: 1 },
24 { key: "speed", label: "Blob speed", min: 0, max: 3, step: 0.1, defaultValue: 1 },
25 { key: "grid", label: "Sample grid", min: 40, max: 110, step: 5, defaultValue: 70 },
26 ];
27 }
28
29 protected onReset(): void {
30 this.threshold = this.num("threshold");
31 }
32
33 protected onParameterChange(key: string): void {
34 if (key === "threshold") this.threshold = this.num("threshold");
35 void key;
36 }
37
38 private field(gx: number, gy: number, cols: number, rows: number): number {
39 let sum = 0;
40 for (const blob of this.blobs) {
41 const bx = blob.cx * cols;
42 const by = blob.cy * rows;
43 const d2 = ((gx - bx) / (cols / 3)) ** 2 + ((gy - by) / (rows / 3)) ** 2;
44 sum += 1 / (d2 + 0.05);
45 }
46 return sum;
47 }
48
49 private computeSegments(): void {
50 const cols = this.num("grid");
51 const rows = this.num("grid");
52 const cw = this.width / cols;
53 const ch = this.height / rows;
54 this.segmentList = [];
55 this.segments = 0;
56 const interp = (f1: number, f2: number) => (this.threshold - f1) / (f2 - f1 || 1e-9);
57 for (let gy = 0; gy < rows - 1; gy++) {
58 for (let gx = 0; gx < cols - 1; gx++) {
59 const f00 = this.field(gx, gy, cols, rows);
60 const f10 = this.field(gx + 1, gy, cols, rows);
61 const f01 = this.field(gx, gy + 1, cols, rows);
62 const f11 = this.field(gx + 1, gy + 1, cols, rows);
63 let code = 0;
64 if (f00 > this.threshold) code |= 8;
65 if (f10 > this.threshold) code |= 4;
66 if (f11 > this.threshold) code |= 2;
67 if (f01 > this.threshold) code |= 1;
68 if (code === 0 || code === 15) continue;
69 const topX = (gx + interp(f00, f10)) * cw;
70 const bottomX = (gx + interp(f01, f11)) * cw;
71 const leftY = (gy + interp(f00, f01)) * ch;
72 const rightY = (gy + interp(f10, f11)) * ch;
73 const midX = (gx + 0.5) * cw;
74 const midY = (gy + 0.5) * ch;
75 const seg = (x1: number, y1: number, x2: number, y2: number) => {
76 this.segmentList.push(x1, y1, x2, y2);
77 this.segments += 1;
78 };
79 const leftX = gx * cw;
80 switch (code) {
81 case 1: seg(leftX, leftY, bottomX, (gy + 1) * ch); break;
82 case 2: seg(bottomX, (gy + 1) * ch, (gx + 1) * cw, rightY); break;
83 case 3: seg(leftX, leftY, (gx + 1) * cw, rightY); break;
84 case 4: seg(topX, gy * ch, (gx + 1) * cw, rightY); break;
85 case 5: {
86 const centerHigh = (f00 + f10 + f01 + f11) / 4 > this.threshold;
87 if (centerHigh) {
88 seg(leftX, leftY, midX, midY);
89 seg(midX, midY, topX, gy * ch);
90 seg((gx + 1) * cw, rightY, midX, midY);
91 seg(midX, midY, bottomX, (gy + 1) * ch);
92 } else {
93 seg(leftX, leftY, midX, midY);
94 seg(midX, midY, bottomX, (gy + 1) * ch);
95 seg((gx + 1) * cw, rightY, midX, midY);
96 seg(midX, midY, topX, gy * ch);
97 }
98 break;
99 }
100 case 6: seg(topX, gy * ch, bottomX, (gy + 1) * ch); break;
101 case 7: seg(leftX, leftY, topX, gy * ch); break;
102 case 8: seg(leftX, leftY, topX, gy * ch); break;
103 case 9: seg(topX, gy * ch, bottomX, (gy + 1) * ch); break;
104 case 10: {
105 const centerHigh = (f00 + f10 + f01 + f11) / 4 > this.threshold;
106 if (centerHigh) {
107 seg(topX, gy * ch, midX, midY);
108 seg(midX, midY, (gx + 1) * cw, rightY);
109 seg(bottomX, (gy + 1) * ch, midX, midY);
110 seg(midX, midY, leftX, leftY);
111 } else {
112 seg(topX, gy * ch, midX, midY);
113 seg(midX, midY, leftX, leftY);
114 seg(bottomX, (gy + 1) * ch, midX, midY);
115 seg(midX, midY, (gx + 1) * cw, rightY);
116 }
117 break;
118 }
119 case 11: seg(topX, gy * ch, (gx + 1) * cw, rightY); break;
120 case 12: seg(leftX, leftY, (gx + 1) * cw, rightY); break;
121 case 13: seg(bottomX, (gy + 1) * ch, (gx + 1) * cw, rightY); break;
122 case 14: seg(leftX, leftY, bottomX, (gy + 1) * ch); break;
123 }
124 }
125 }
126 }
127
128 protected onUpdate(dt: number): void {
129 this.threshold = this.num("threshold");
130 const speed = this.num("speed");
131 for (const blob of this.blobs) {
132 blob.cx += (blob.vx * dt * speed) / 100;
133 blob.cy += (blob.vy * dt * speed) / 100;
134 if (blob.cx < 0.12 || blob.cx > 0.88) blob.vx *= -1;
135 if (blob.cy < 0.12 || blob.cy > 0.88) blob.vy *= -1;
136 blob.cx = Math.min(0.88, Math.max(0.12, blob.cx));
137 blob.cy = Math.min(0.88, Math.max(0.12, blob.cy));
138 }
139 this.computeSegments();
140 }
141
142 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
143 ctx.fillStyle = theme.bg;
144 ctx.fillRect(0, 0, this.width, this.height);
145 const cols = this.num("grid");
146 const rows = this.num("grid");
147 const cw = this.width / cols;
148 const ch = this.height / rows;
149 // Faint above-threshold field
150 ctx.fillStyle = theme.raised;
151 for (let gy = 0; gy < rows; gy++) {
152 for (let gx = 0; gx < cols; gx++) {
153 if (this.field(gx + 0.5, gy + 0.5, cols, rows) > this.threshold) {
154 ctx.fillRect(gx * cw, gy * ch, cw, ch);
155 }
156 }
157 }
158 // Contours from the cached segment list
159 ctx.strokeStyle = theme.accent;
160 ctx.lineWidth = 2;
161 ctx.lineCap = "round";
162 ctx.beginPath();
163 for (let i = 0; i < this.segmentList.length; i += 4) {
164 ctx.moveTo(this.segmentList[i], this.segmentList[i + 1]);
165 ctx.lineTo(this.segmentList[i + 2], this.segmentList[i + 3]);
166 }
167 ctx.stroke();
168 ctx.lineWidth = 1;
169 ctx.font = "11px ui-monospace, monospace";
170 ctx.fillStyle = theme.fgTertiary;
171 ctx.fillText(`${this.segments} contour segments`, 10, 16);
172 }
173
174 getMetrics() {
175 return {
176 isoValue: this.threshold.toFixed(2),
177 segments: this.segments,
178 blobs: this.blobs.length,
179 grid: `${this.num("grid")}^2`,
180 };
181 }
182
183 describe(): string {
184 return `Marching squares extracting the iso-contour of three moving metaballs: ${this.segments} segments at iso value ${this.threshold.toFixed(2)}.`;
185 }
186
187 entities(): number {
188 return this.num("grid") ** 2;
189 }
190}
191

Performance

Time per tick
O(cells) field evaluation plus O(cells) classification
Space
None beyond the sampled field
Notes
The same 16-case table, run per cell, is the algorithm behind every iso-line in every medical imaging package.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.