1. Introduction

Many applications produce data in the form of a scalar function defined at discrete points in space (called volume data). Examples include X-ray crystallography, CT, MRI, and data from continuous field simulations such as computational fluid dynamics. The data is visualized using either volume rendering ([8],[9],[10]) or isosurface extraction (See [11],[12], [13],[14],[15]). In volume rendering the data is regarded as consisting of semi-transparent material and volume primitives are directly projected onto the screen using ray casting. In isosurface based methods the data is segmented by thresholding, that is, identifying objects defined by the sets of points in space where a suitable interpolating function f for the data is greater than equal to a real value $\tau$, called the isovalue or threshold. The topological boundary of these objects will generally correspond to the level sets of f, that is, the points p where $f(p) = \tau$. The data is either regularly gridded, that is, represents a function $\delta$ defined at points of $\bf {Z}^n$ on the vertices of a hypercubic decomposition of space, or it is irregularly gridded and is typically defined on the vertices of a simplicial decomposition of $\bf {R}^n$. The simplices or (hyper)cubes are called cells. The isosurface extraction problem is to construct the level set of f, called the isosurface, for specific isovalue . Individual connected components of this set are typically called the contours, even when they are higher dimensional surfaces.

Many researchers have developed methods of organizing the data so that the ``active cells'', those cells that a given contour intersects, can be quickly accessed from disk for out-of-core rendering. The three main methods include geometric organization [16], [17], [18], value based organization [19], [20], [21], [22], [23], and recently the topology based organization using augmented contour trees [4], [5], [6]. The I/O optimal interval trees of [23] seem to produce the least disk I/O and seek time, and input the minimal number of blocks in active cell acquisition. Our organization is topology based.

Topological organization of the data uses Morse Theory. Morse theory studies the changes in the topology of the level sets of a Morse function f as the parameter is decreased. These changes occur at the values of critical points of f, where the derivative vanishes. A Morse function has the property that the critical points are isolated and the Hessian is nonsingular at each of these points. Typically the data readings () are perturbed to insure that no two values are identical, and a simple (e.g. linear) interpolant f is selected, to insure that f is Morse. The contour tree tracks the topological changes of individual contours as the parameter is varied. The augmented contour trees of [5] are used to produce a seed cell set and active cells for a given contour are acquired by local propogation from the seed cells.

We define a simplified variant of the contour tree (the differences are discussed in section 4.2), and use it to segment the data into topological zones and topological zone components. The algorithm to compute the topological zone segmentation is simpler and more space efficient than [4] and [6], works for both cubic and simplicial data cells, and doesn't assume a specific interpolant, but rather produces the same segmentation for any interpolant satisfying two simple properties. The properties are selected so that interpolants satisfying them are consistent with the typical isosurface (contour) extraction methods referenced above. Moreover, we show that we can extend the results to data where the values are not unique. We feel that this is important because sampled density data from a physical phenomenon may in fact contain regions of constant density. We give a combinatorial characterization of the topology changing criticalities in this case and state a related open problem.

In section 5 we show how to actually compute the data cells that intersect a topological zone component. In section 6 we give a very simple algorithm that computes contours in all dimensions. In section 7 we discuss the applications of our technique, including I/O optimal extraction of the active cells of a contour and topologically correct volume data simplification.