Marching Squares

1 min read•1 page

Marching Squares is the 2D precursor to Marching Cubes. It extracts continuous isolation lines (isolines) from a grid of scalar values. Each node in the grid has a scalar density. By comparing this density to a threshold isovalue, we classify the vertex as inside or outside the solid shape.

Scalar Thresholding:

1. Inside (Active): Node value is greater than or equal to the isovalue ($val \ge isovalue$). 2. Outside (Inactive): Node value is less than the isovalue ($val < isovalue$). 3. Intersection Boundary: The isoline boundary is located along the edges between inside and outside nodes.

python

1def classify_grid_node(node_value, isovalue):
2    # Returns 1 (Inside) or 0 (Outside)
3    return 1 if node_value >= isovalue else 0

Threshold Isovalue

50.00

5 min read•1 page

A square cell has 4 vertices. Since each vertex can be either inside or outside, there are exactly $2^4 = 16$ possible boundary configurations. We encode these into a binary index.

Binary Indexing:

1. Bitmasking: Construct a 4-bit integer where each bit represents the state of a vertex (V0, V1, V2, V3). 2. Lookups: Use the bitmask index to retrieve matching edge pairs from the precomputed lookup table. 3. Saddle Cases: Configurations 5 and 10 have diagonally opposite active corners, requiring two distinct isoline segments.

python

1# Marching Squares 16-case Lookup Table
2# Index represents binary code: (V3 << 3) | (V2 << 2) | (V1 << 1) | V0
3LINE_TABLE = [
4    [],             # 0 (0000) - All outside
5    [(3, 0)],       # 1 (0001) - V0 inside -> crosses Edge 3 & 0
6    [(0, 1)],       # 2 (0010) - V1 inside -> crosses Edge 0 & 1
7    [(3, 1)],       # 3 (0011) - V0, V1 inside
8    [(1, 2)],       # 4 (0100) - V2 inside -> crosses Edge 1 & 2
9    [(3, 0), (1, 2)], # 5 (0101) - Saddle case: V0, V2 inside
10    [(0, 2)],       # 6 (0110) - V1, V2 inside
11    [(3, 2)],       # 7 (0111) - V0, V1, V2 inside
12    [(2, 3)],       # 8 (1000) - V3 inside -> crosses Edge 2 & 3
13    [(2, 0)],       # 9 (1001) - V0, V3 inside
14    [(2, 3), (0, 1)], # 10 (1010) - Saddle case: V1, V3 inside
15    [(2, 1)],       # 11 (1011) - V0, V1, V3 inside
16    [(3, 1)],       # 12 (1100) - V2, V3 inside
17    [(0, 1)],       # 13 (1101) - V0, V2, V3 inside
18    [(3, 0)],       # 14 (1110) - V1, V2, V3 inside
19    []              # 15 (1111) - All inside
20]

Lookup Case Index

0.00

1 min read•1 page

Placing boundaries exactly in the middle of grid edges results in blocky, jagged contours. To construct smooth curves, we interpolate the exact intersection point along the cell edge based on the node values.

Interpolation Formula:

1. Vertex Values: Let $val_1$ and $val_2$ be the scalar values at the endpoints of the edge.2. Scale Ratio $t$: $t = \frac{isovalue - val_1}{val_2 - val_1}$, describing where the threshold falls along the span.3. Geometric Coordinate: The intersection point shifts dynamically according to $t$.

python

1def lerp_edge_intersection(pt1, pt2, val1, val2, isovalue):
2    # Linear interpolation factor
3    t = (isovalue - val1) / (val2 - val1)
4    
5    # Interpolated intersection coordinate
6    return pt1 + t * (pt2 - pt1)

Threshold Isovalue

50.00