Voxel to Mesh Conversion: Marching Cube Algorithm
The ‘Marching Cubes’ is a simple iterative algorithm for creating triangular surfaces for a 3D function (in our case the 3D function is defined point wise and is called voxels).
It works by “Marching” over the whole 3D region which has been divided into cubes. The vertices of the cube are the voxels. The algorithm then computes whether a triangular surface passes through this cube or not. For a high level intuition say if the corners of the cube(the voxels) are all 1. This would mean that the cube will lie entirely inside the surface. Similarly if the voxels are all 0s then it would mean the cube lies outside the surface. In both the cases there would be no triangular surface passing through the cube. The main aim of the algorithm is to calculate the triangular surface (its intersection points, normals) in the cases where some voxels are 1 others are 0 (inside a cube). As there are 8 voxels in a cube which can have value 0 or 1 we have 2⁸ = 256 cube configurations.
The ingenuity of the algorithm is the way it handles the calculation of 256 configs by:
- Reducing the number of cases to 15 (taking redundancy due to rotational and mirror symmetry into account)
- Using a clever indexing table (a lookup table) that speeds up the whole process.
