Marching Squares

1 min read•1 page

Scalar Thresholding:

1. Inside (Active): Node value is greater than or equal to the isovalue (val ≥ 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

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.

Threshold Isovalue

50.00

5 min read•1 page

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]

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.

Lookup Case Index

0.00

1 min read•1 page

Interpolation Formula:

1. Vertex Values: Let val_1 and val_2 be the scalar values at the endpoints of the edge.2. Scale Ratio <code>t</code>: <code>t = (isovalue - val_1 / val_2 - val_1)</code>, 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)

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.

Threshold Isovalue

50.00

Related Concepts

Principal Curvatures

The Weingarten shape operator, eigenvalues κ₁ and κ₂, orthogonal principal curvature directions, and quad-remeshing lines.

Explore concept →

Voxelization

3D Grids and Marching Cubes.

Explore concept →

Spatial Grids

Uniform 3D lattice discretization, coordinate quantization, Morton/prime spatial hashing, and voxel rasterization.

Explore concept →