Answer to Question #268591 in 3D CAD Modeling for King

Question

Explain the marching squares algorithm

Answer 1

Marching squares is a computer graphics algorithm that generates contours for a two-dimensional scalar field (rectangular array of individual numerical values). A similar method can be used to contour 2D triangle meshes.

These contours can be of two kinds:

1) isolines – lines following a single data level, or isovalue.

2) usobands – filled areas between isolines.

The steps of the algorithm are:

Apply a threshold to the 2D field to make a binary image containing:

1 where the data value is above the isovalue

0 where the data value is below the isovalue

Every 2x2 block of pixels in the binary image forms a contouring cell, so the whole image is represented by a grid of such cells. Note that this contouring grid is one cell smaller in each direction than the original 2D field.

For each cell in the contouring grid:

Compose the 4 bits at the corners of the cell to build a binary index: walk around the cell in a clockwise direction appending the bit to the index, using bitwise OR and left-shift, from most significant bit at the top left, to least significant bit at the bottom left. The resulting 4-bit index can have 16 possible values in the range 0–15.

Use the cell index to access a pre-built lookup table with 16 entries listing the edges needed to represent the cell.

Apply linear interpolation between the original field data values to find the exact position of the contour line along the edges of the cell.