Marching squares

Method of generating contours for a 2D scalar field (a grid of individual numerical values), like turning elevation data into a banded topographical map. The scalar values get associated with vertices of the 2D grid, then lines are drawn across each cell in different ways based on the values of their four corner vertices.

There is only a finite number of lines possible, so they can be precomputed into a lookup table and referenced quickly later for faster performance. These lines can also be linearly interpolated to smoothly transition from cell to cell, resulting in very realistic blobby / fluid structures.

Key terms:

Illustration of algorithm:

Articles:

Code projects:

Videos:

Marching cubes

3D version of marching squares. Whereas marching squares uses lines and cells to trace the contours of a 2D scalar field, marching cubes uses polygons and voxels to trace the contours of a 3D scalar field, resulting in a mesh. Marching cubes can be thought of as a mesh conversion algorithm that produces meshes based on 3D scalar fields.

Originally developed by William Lorensen and Harvey Cline of General Electric in 1987 (see original paper in Articles section) for use in the medical imaging (MRI/CT) field, this algorithm has become widely used in many areas of computer graphics

TODO: add note on dual marching cubes

Algorithm [link]:

The algorithm proceeds through the scalar field, taking eight neighbor locations at a time (thus forming an imaginary cube), then determining the polygon(s) needed to represent the part of the isosurface that passes through this cube. The individual polygons are then fused into the desired surface.

  1. Choose a threshold (called an isovalue) to determine which level of values are considered inside or outside the mesh, thus setting where the mesh boundary is created.
  2. Pre-compute an array of all 256 (2^8) possible polygon configurations within a cube, where each entry is a set of IDs associated with edges of the cube (see Figure B below).
    • Note that of these 256 configurations, only 15 are unique due to repetition and symmetry (see Figure A below).
  3. For each set of 8 scalar values (forming a cube), compute an 8-bit integer where each bit corresponds to a unique scalar value (corner of the cube).
    • If the scalar value is higher than the isovalue (i.e. inside of mesh), set bit to 1
    • If lower, set bit to 0
  4. Generate polygons for each set of scalar values by drawing lines between the edges referenced in the polygon lookup table from step 2.
    • To do this, parse the 8 bits from step 3 into an integer, then use that integer as an index in the lookup table.
    • For example 00101001 = 41. Therefore the list of edges to draw lines between can be found in lookupTable[41].
  5. Each vertex of the generated polygons is placed on the appropriate position along the cube's edge by linearly interpolating the two scalar values that are connected by that edge.
  6. Calculate normals - TODO: how?
  7. Perform boolean union with all polygon fragments to form a mesh
(Figure A) diagram of 15 possible polygon configurations based on vertex bit values
(Figure B) diagram of edge and vertex numbering

Key terms:

Articles:

Videos: