Marching cubes

As explained in Geometry for Programmers

Marching cubes is an isosurface extraction algorithm that approximates a three-dimensional implicit surface with triangles from scalar samples on a grid.

Marching cubes converts an implicit shape into a triangle mesh by sampling a signed distance function (SDF) on a grid. Instead of seeking an exact smooth surface, it chooses a cell size as an acceptable error scale and approximates the surface locally with triangles. section 11.3.1

Each grid cell is classified from the signs at its corners: negative means inside, positive means outside. A configuration of inside and outside corners selects a small surface pattern; symmetric cases reduce the original set to 15 configurations. The 2D counterpart is marching squares, which produces contour segments rather than triangles. section 11.3.1 section 11.7

A practical contouring workflow is:

• Choose a grid resolution that balances tolerable geometric error against mesh size. section 11.3.1 section 11.3
• Sample the SDF at grid corners and identify where neighboring samples change sign. section 11.3.1
• Place the selected segments or triangles in each cell; linear interpolation can improve their positions along grid edges. section 11.3.1
• Use the resulting mesh when SDF-based Boolean operations, offsets, repair, or interpolation must return to a triangulated representation. section 11.3

From a circle to a contour

A circle sampled on a 2D grid becomes line segments that separate positive SDF values from negative ones. A coarse grid can satisfy a numerical error bound yet still look unlike a circle; finer sampling and interpolated edge positions make the contour more convincing. The same cell-by-cell idea extends from squares to 3D cubes and triangles. section 11.3.1

Marching cubes generally suits smooth surfaces. For sharp features, dual contouring is often preferable, though implementations can add sharp-feature restoration or optimize either family for different surface types. Resolution remains the central trade-off: increasing accuracy can sharply increase computation; a stated rule of thumb is that doubling accuracy makes the algorithm four times slower. section 11.3.4

Figure 11.11 Original configurations of triangles substituting the implicit surface in cells. Note that the symmetrical configurations are omitted; otherwise, there would have been 2⁸ = 256 combinations (Jmtrivial, GPL, via Wikimedia Commons).

Inspect the cube surface patterns to see how corner sign combinations become local triangle arrangements. section 11.3.1

How Geometry for Programmers covers it

How deep it goes

Explains grid cells, corner-sign configurations, 2D contouring, and interpolation, while treating full 3D patterns as a configuration set.

Examples

Uses a circle becoming a line-segment contour, plus sphere, metaballs, and rectangle reconstructions.

What it assumes

Assumes signed distance functions and introduces their negative-inside, positive-outside, zero-boundary interpretation.

What you can do after

Apply it to convert an SDF into an approximate triangle mesh or 2D contour while choosing a resolution trade-off.

How it connects

Connects signed distance functions, triangle meshes, marching squares, dual contouring, Boolean operations, and offsets.

liveBookmanning.com

Read Geometry for Programmers on liveBook Get the book at manning.com

Related concepts

• dual contouringcontrasts with · Dual contouring is an isosurface extraction algorithm that places one optimized vertex in each active grid cell and connects neighboring vertices across sign-changing edges.
• meshproduces · A mesh is a discrete geometric representation composed of interconnected vertices, edges, and faces or other elements covering a shape or region.
• signed distanceuses · A signed distance is a distance from a geometric boundary or separator assigned a positive or negative sign according to which side contains the point.
• marching squaresequivalent to · Marching squares is the two-dimensional counterpart of marching cubes that approximates an implicit curve with line segments by classifying the signs at the corners of grid cells.
• griduses · A grid is a regular arrangement of positions or cells organized by rows and columns or by fixed neighboring relationships.

This explainer was generated by Manning's knowledge graph from the text of Geometry for Programmers. The section links point to the parts of the book it draws on.