Octree-based decimation of marching cubes surfaces

The Marching Cubes (MC) algorithm is a commonly used method for generating isosurfaces. The MC algorithm also generates an excessively large number of triangles to represent an isosurface. Generating many triangles increases the rendering time which is directly proportional to the number of triangles. This paper presents a decimation method to reduce the number of triangles generated by the MC algorithm. Decimation is carried out within the framework of the MC algorithm before creating a large number of triangles. Four major steps comprise the reported implementation of the algorithm: a) surface tracking, b) merging, c) crack patching, and d) triangulation. Surface tracking is an enhanced implementation of the MC algorithm. Starling from a seed point, the surface tracker visits only those cells likely to compose part of the desired isosurface. This results in up to approximately 80% computational saving The cells making up the extracted surface are stored in an octree that is further processed. A bottom-up approach is taken in merging the cells containing a relatively flat approximating surface. The finer surface details are maintained. Cells are merged as long as the error due to such an operation is within a user-specified error parameter, or a cell acquires more than one connected surface component in it. A simple, yet general, crack patching method is described that forces edges of smaller cells to lie along those of the larger neighboring cells. Patching does not introduce new triangles. The overall saving in the number of triangles depends both on the specified error value and the nature of the data. We demonstrate savings of more than 90% for two artificial datasets and an MRI head dataset for an error value of less than half the minimum voxel dimension. Use of the hierarchical octree data structure also presents the potential of incremental representation of surfaces. We can generate a highly smoothed surface representation which can be progressively refined as the user-sepcified error value is decreased.