# A Comprehensive Survey of Isocontouring Methods: Applications, Limitations and Perspectives
## 2 Marching Squares and Marching Cubes Algorithms  
The marching cubes algorithm (MC) was introduced in [2] by [PERSON] and [PERSON] to find isovalues in medical imaging techniques such as magnetic resonance imaging (MRI), computed tomography scans (CT scan) and single-photon emission computed tomography (SPECT). Therefore, the initial data can be interpreted as pixels in a three-dimensional picture. A schematic representation of the data is shown in Figure 2. The \(k\) dimension represents the individual pictures, where the position of each pixel within one slice is represented by \(i\) and \(j\). Hence, the cube presented in Figure 2 is constructed by four opposing pixels in two neighboring slices. To be able to interpret the data in a medical context, points of equal value must be found. This value can represent a specific tissue density, for example, so that the result of the analysis yields the three-dimensional surface of individual parts of the scan. The marching cubes algorithm follows a divide-and-conquer approach, where each cube is analyzed individually, resulting in small triangles of the surface that, when put together, reconstruct the surface formed by the isovalue. The first step is to mark all vertices of the individual cubes that have a value smaller than, equal to or greater than the isovalue of interest. Since a cube has eight vertices, which themselves can have two states, 256 patterns are possible. Using the symmetries between the individual cases, only 14 different general cases are necessary according to [2]. Cubes where all vertices have values smaller or greater than the isovalue are outside or inside the surface, do not contribute to the surface itself and thus must not be considered in the further process. All other combinations do contribute and are investigated in the following steps. In Figure 3, the different combinations are shown. Here, the highlighted triangles in the individual cubes are part of the surface. Based on the values of the cube vertices, the position of the point of the isovalue on the edges of the cube can be determined by linear interpolation. The final step of the proposed algorithm uses the interpolated points, the vertices of the cube under investigation and the vertices of the neighboring cubes to calculate the unit normal used for Gourard-shaded images. This is not necessary for the interpolation itself but for the imaging and the subsequent medical analysis. To calculate the unit normal of the density \(D\) on each interpolated vertex, first, the normal at the cube vertices is calculated in the \(x\), \(y\) and \(z\) directions. For this purpose, the density gradient \(G\) is calculated, using the expressions presented in Equations (1)-(3). The distance between two pixels in the same slice is \(\Delta x\) and \(\Delta y\), while the distance between two slices is \(\Delta z\). Figure 2: Initial data structure for marching cubes algorithm based on [2]. \[G_{x}(i,j,k) =\frac{D(i+1,j,k)-D(i-1,j,k)}{\Delta x} \tag{1}\] \[G_{y}(i,j,k) =\frac{D(i+1,j,k)-D(i-1,j,k)}{\Delta y}\] (2) \[G_{z}(i,j,k) =\frac{D(i+1,j,k)-D(i-1,j,k)}{\Delta z} \tag{3}\]  
After calculating the gradient at the cube vertices, the gradient at the isovalue vertices can be determined using linear interpolation. Since the component of the gradient vector in the tangential direction of the isovalue surface is always zero, the gradient vector itself represents a normal vector of the respective vertex. In Figure 4, an example is depicted where the gradients of the cube vertices are known and yield the normal unit vectors at the vertices of the isovalue triangle. The original marching cubes algorithm is the subject of various other scientific works. Authors [PERSON] and [PERSON] propose, in [4], a method to decompose the cubes into tetrahedral cells before linearization, to increase the calculation efficiency. A problem in the  
Figure 4: Unit normal vector calculation at vertices of isovalue surfaces based on [3]. Figure 3: Basic types of triangulated cubes based on [2].