Marching Cubes SDF to Mesh

mediumPROSurface RepresentationsCVCV: 3D Reconstruction

Implement a method to extract a mesh surface from a signed distance field (SDF) using the Marching Cubes algorithm. This technique is crucial in 3D reconstruction for converting implicit surface representations into explicit mesh models.

The SDF is a scalar field where each point's value represents its distance to the surface, with $d(x)$ being negative if $x$ is inside the surface, positive if outside, and zero if on the surface. The Marching Cubes algorithm works by discretizing the 3D space into cubes and checking the sign of the SDF values at each cube's vertices to determine the surface intersection.

Here are the key steps:

Discretize the 3D space into cubes.
Evaluate the SDF at each cube's vertices.
Determine the surface intersection based on the SDF values.

d(x) = \begin{cases} < 0, & \text{if }x\text{ is inside} \\ > 0, & \text{if }x\text{ is outside} \\ = 0, & \text{if }x\text{ is on the surface} \end{cases}

Return a tuple (vertices, faces): vertices are the 3D points where the surface crosses the grid (in grid-index coordinates), and faces are triangles given as triples of indices into vertices.

This technique is widely used in computer vision and 3D modeling applications.

Example

Input

3D SDF grid

Output

Mesh vertices and faces

Reasoning

Input: sdf is a 3D grid of signed distances, $d_{ijk}$ sampled at integer grid points $(i, j, k)$ . Take a tiny $2 \times 2 \times 2$ grid (a single cube) with $d_{000} = -0.2$ and the other seven corners at $0.6$ : one corner is inside the surface, the rest outside.
Where the surface crosses: only a cube edge whose two end values have opposite signs can contain a zero. Here that is the three edges leaving corner $(0,0,0)$ ; the other nine join two positive corners.
Locating the crossing: treat $d$ as linear along the edge and solve for the fraction $t$ where it hits zero: $t = \frac{0 - d_{\text{lo}}}{d_{\text{hi}} - d_{\text{lo}}} = \frac{0.2}{0.8} = 0.25$ .
Output (mesh vertices and faces): vertices $(0.25, 0, 0)$ , $(0, 0.25, 0)$ , $(0, 0, 0.25)$ in grid-index coordinates, and one face, the triangle $[0, 1, 2]$ , cutting off the inside corner.
Notice that a value closer to zero pulls the vertex toward that corner; at $d_{000} = -0.6$ every vertex would sit at the edge midpoint, $t = 0.5$ .

Constraints

Input SDF: 3D numpy array with shape (x, y, z) and dtype float32, representing the signed distance field
Valid SDF values: in the range [-inf, inf], where negative values indicate points inside the surface, positive values indicate points outside, and zero indicates points on the surface
Output mesh: list of vertices as 3D float32 numpy arrays and list of faces as integer numpy arrays, representing the extracted mesh surface
Grid size: x, y, z dimensions of the input SDF grid are in the range [1, 100]
Output precision: float32 for vertex coordinates and uint32 for face indices

Learn this in

3D ReconstructionCV Study Plan Introduction to 3D Computer Vision3D Computer Vision 3D Reconstruction Pipelines3D Computer Vision 3D Scene Understanding3D Computer Vision

More from CV: 3D Reconstruction

NeRF Ray Samplinghard Surface Integration from Normalsmedium ICP Point Cloud Alignmenthard NeRF Positional Encodingmedium Marching Cubes Configurationhard

Concept primerPREVIEW

Background Knowledge

A signed distance field (SDF) is a scalar function $f: \mathbb{R}^3 \to \mathbb{R}$ where each point stores the (signed) distance to the nearest surface: negative values are inside, positive are outside, and the zero level set $f(x)=0$ represents the surface you want to reconstruct. In discrete form, you have a 3D grid (voxel volume) of SDF samples $f(i,j,k)$ . The surface will generally cut through the cells between these grid points, not pass exactly through them.

The Marching Cubes algorithm is a classic method to extract a triangle mesh approximating an isosurface (here, the zero level set) from a scalar field. Each cube is formed by 8 neighboring grid samples (at the corners). By checking which corners are inside (negative) and which are outside (positive), you can determine how the isosurface intersects that cube. A precomputed lookup table maps each of the 256 possible inside/outside patterns to a set of edges that the surface intersects and to the triangles formed between those intersection points.

Conceptually, Marching Cubes does local interpolation: for each cube edge whose endpoints have opposite signs, the surface crosses that edge. The intersection position is found via linear interpolation between the two SDF values. Connecting these interpolated edge points according to the lookup table yields a set of triangles per cube; collecting them over all cubes yields the full mesh.

Algorithm / General Approach

At a high level, the approach is:

Treat the SDF grid as a 3D array of samples.
For each voxel cell (cube) between samples:
Classify its 8 corners as inside/outside relative to the isovalue (0).
Form an 8-bit cube index from these classifications.
Use the cube index to:
Look up which edges are intersected.
For each intersected edge, compute the exact intersection via interpolation.
Look up which triangles to emit using those edge points.
Aggregate all triangle vertices (and optionally deduplicate / index them) into a mesh.

This is a local, data-parallel algorithm: each cube can be processed independently, which is why it’s used widely in graphics and 3D reconstruction.

Step-by-Step Strategy
Define grid and indexing

Assume SDF values stored in sdf[z][y][x] (or similar).
A cube at integer index $(x, y, z)$ has 8 corners at:
$(x,y,z), (x+1,y,z), (x+1,y+1,z), (x,y+1,z)$
$(x,y,z+1), (x+1,y,z+1), (x+1,y+1,z+1), (x,y+1,z+1)$
Also know the world-space position of each grid point: e.g. p = origin + spacing * (x,y,z).

Loop over cubes

for z in range(nz-1):
for y in range(ny-1):
for x in range(nx-1):
process_cube(x, y, z)

Compute cube index (inside/outside pattern)

Sample the 8 corner SDF values v[0..7].
Initialize cubeIndex = 0.
For each corner i:
If v[i] < 0 (inside for isovalue 0), set bit i in cubeIndex.
Now cubeIndex is in [0, 255].

Early out for trivial cases

If cubeIndex == 0 or cubeIndex == 255, the surface does not pass through the cube (all outside or all inside) → skip.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results