IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Isosurface extraction generalized adaptive marching cubes

  • Sept. 9, 2009

Abstract

Marching cubes is an algorithm for rendering isosurfaces in volumetric data. It was first designed and published by Lorensen and Cline (SIGGRAPH 1987) to create triangle models of constant density surfaces from 3D medical data. The basic principle behind the marching cubes algorithm is to subdi-vide space into a series of small cubes. By the values at the eight vertices of a cube we can determine which edges are intersected by the isosurface. Since at each vertex the value can be greater or smaller than the user specified isovalue, we have 256 different configurations. Two of these are trivial and if we account for symmetries, there are only 14 different configurations in the remaining 254 possibilities. But in many cases the topology of the isosurface is not unique. In a first step we will show that even in the discrete case (no underlying scalar function is given) the number of different configurations can be reduced to two by subdivision. If an underlying function is given, in most cases the topology of the isosurface becomes unique. Another advantage of adaptation is that the starting grid size can be kept larger without loosing precision. Nevertheless, in some cases small isolated parts of the isosurfaces may be totally missed or we might get the wrong topology. Thus in a second step we will improve the algorithm by taking derivatives into account. This might be done numerically by finite differences, analytically for special classes of functions, e.g. Splines or algebraic functions or by automatic differentiation (AD). Under the assumption that the first derivative can be computed and we know or can compute bounds for the second one, we will show that this algorithm is watertight. That means, up to a given threshold it will find all parts and the right topology.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC