VS: A surface-based system for topological analysis, quantization and visualization of voxel data

VS is a simple system consisting of several techniques for various volumetric problems. Based on the marching cubes algorithm, it operates with one space sweep through the voxels and extracts all topological information: detection of all isosurfaces, partitioning the data into connected components on the basis of surface connectivity, and association of surfaces with any internal surfaces to arbitrary levels of nesting. VS extends Baker's “Weaving Wall” method by associating topological cavities with their outer surface, and by using efficient data structures for the voxel traversal and for the connected component detection. Its runtime, on average, is only about 2% more than the speeded-up marching cubes algorithm. VS operates on the original voxels without using the contour tree required by other approaches. Using linear-time preprocessing, VS constructs a data structure which can be utilized for any isovalue or interval of isovalues. An accurate estimate of each component's volume is based on the volume enclosed by the outer surface, minus the volume of any internal cavities. VS enables noise reduction by eliminating components (and cavities) with a small volume. Different components can be rendered with different visual attributes, and cutaway views by arbitrary cut-planes are displayed as if the objects were solid, without adding any new surface patches to match the intersection.