 # Improving the Marching Cubes Algorithm

In the previous Marching Cubes tutorial a basic Marching Cubes algorithm was shown and a sample C++ source code was provided. Here a couple of changes are made to the original code which improve the way the light is computed and increase its speed.

A screen shot of Marching Cubes in action in the previous tutorial shows the blocky appearance of the rendered object. This is due to the fact that the normals were computed as a cross product of two sides of a triangle. This gives a vector normal to each triangular face, but not a normal to the original surface, which is what is needed. To compute the normal to the surface rendered, gradient vectors are used. A gradient is computed at each vertex and then is linearly interpolated to the vertices on the edges, just like the vertices. This will give a normal vector orthogonal to the surface instead of a triangle, which is used to approximate the surface. Gradient vector at vertex (i, j, k) of a surface defined by function f is computed according to the formula: where , , are some factors by which x, y, z coordinates of are scaled respectively. These values are often the length of each side of a cube. This will increase the magnitude of a gradient vector with decreasing sides and will give more light for smaller subdivisions. Gradient vectors are then linearly interpolated using the value at the respective vertex. The only drawback is that gradient vectors can not be computed for the cubes on the edges of the defined space since the previous/next points don't exist. To go around this problem cubes on the edges are not looked at. They are just there to compute the gradient vectors of the "inside" cubes. The boundary volume is then decreased by 2 on each side. Here are two pictures comparing lighting computed first by the old method and then using the gradient vectors. Each has equal number of subdivisions:  Another aspect on which the original Marching Cubes algorithm can be improved is its speed. So far all the cubes in the defined space were "marched" through, with those being intersected by the surface subdivided into triangles. However, unless the surface is really complex or there are few subdivisions, most of the cubes are not intersected by the surface. To limit the amount of "empty" cubes that are looked at, a recursive Marching Cubes Algorithm is considered. Starting from a cube which is known to be intersected the algorithm tests cubes adjacent to its 6 surfaces. The cube is not considered by the algorithm if its on the bounday or has already been looked at. If the cube is not intersected then it returns to the previous one and does not launch recursive calls on its own 5 remaining faces. The algorithm stops when the cubes on all of its 6 faces have either been already "marched" through or are not considered. This way only the cubes on and adjacent to the surface are tested. The drawback of this algorithm comes up when multiple objects are drawn. Unless we know the intersecting cubes for each object, only one object can be drawn (objects are considered separate when they don't share an intersecting cube).

In my source code I pass other information from cube to cube, such as the vertices and gradient vectors at each vertex, interpolated vertices and gradient vectors on the adjacent edges. These values are passed as arrays of length four, since there are only four edges/vertices that two adjacent cubes can have. The face numbers and the way the indices of the passed values correspond to those of the current cube are shown in the figure below: I have a different function for each face of the cube, so that information can be passed without any if statements. I have also provided a function which searches the space for an intersecting cube and then launches the recursive Marching Cubes algorithm. The recursive algorithm itself accepts any number of intersecting cubes, allowing multiple objects to be drawn.

## Source Code

C++ source Code: MarchingCubes.cpp MarchingCubes.h MCTable.h
mpVector and mp4Vector C code used by Marching Cubes: mpVector.cpp mpVector.h

Please email me with suggestions and/or bugs at:
myp@andrew.cmu.edu or mikepolyakov@hotmail.com