HP Labs Technical Reports

On Generating Topologically Correct Isosurfaces from Uniform Samples

Natarajan, Balas K.

HPL-91-76

Keyword(s):

Abstract: A function f(x,y,z) of three variables may be visualized by examining its isosurfaces f(s,y,z) = t for various values of t. To display these isosurfaces on a graphics device it is desirable to approximate them with piecewise polygonal surfaces that are (1) geometrically good approximations, (1) topologically correct, and (3) consist of a small number of polygons. By topologically correct we mean that the connectivity of the constructed surface matches that of the true isosurface-any two points in the given sample are connected by a path that does not pierce the constructed surface, if and only if they are connected by a path that does not pierce the true isosurface. / We are interested in functions specified as the piecewise trilinear interpolant of a uniform mesh of sample points. For such functions: the "marching cubes" algorithm of Cline et al. (1988) constructs a piecewise polygonal approximation to the isosurface, satisfying conditions (1) and (3) above, but not condition (2), i.e., the topology of the constructed surface may be incorrect; the "dividing cubes" algorithm of Cline et al. (1988) constructs a piecewise polygonal approximation to the isosurface satisfying conditions (1) and (2) above, but not condition (3), i.e., the constructed surface may not consist of a small number of polygons; here, we present an efficient algorithm that constructs a piecewise polygonal approximation to the isosurface satisfying all three conditions, i.e., the constructed surface is geometrically a good approximation, topologically correct, and consists of a small number of polygons.

Back to Index