2. Preliminaries

Definition 1  

We will assume our volume data set is given by a real-valued function defined on a discrete set of points in V in . Regularly gridded data is given by a function defined on , where we form unit hypercubes in the natural way, and irregularly gridded data is given on the vertices of a simplicial decomposition of and we assume that this information is represented on external storage. We term both the hypercubes and simplices cells. We shall assume, for simplicity, that is non-negative and that $\delta > 0$ on a finite subset of points. If does not take the same value on any two points, we say that it satisfies data uniqueness.

We will later consider the case where identically valued, spatially proximate data readings imply isovolumes (level sets with dimension n for n dimensional volume data). We are also primarily concerned with the objects bounded by the contours, and thus we give different formulation of the isosurface extraction problem.

Definition 2   We will say that a continuous real-valued function f interpolates if the domain of f is , f is non-zero on a closed and bounded subset of , and for all $p \in V$, $f(p) = \delta (p)$. We denote by $\bf {X}_{f}^{\geq \tau}$, the set of $p \in \bf {R}^n$ such that $f(p) \geq \tau$, for f that interpolates . The topologically connected components of this set are called objects. Similarly, $\bf {X}_{\delta}^{\geq \tau}$ denotes the set such that $\delta (p) \geq \tau$. We call these points High and points p in V for which $\delta < \tau$ are called Low. Clearly, if f interpolates then $\bf {X}_{\delta}^{\geq \tau} \subseteq \bf {X}_{f}^{\geq \tau}$.

Definition 3   The isosurface extraction problem is to compute the components (contours) of $B (\bf {X}_{f}^{\geq \tau})$ for specific real number , where B(X) denotes the topological boundary of the set X.

Typical isosurface extraction methods construct with the simplest topology consistent with the data. These methods interpolate a single contour intersection point (called a hit) with a cell edge iff the two edge endpoint values are High and Low, respectively, and for simplicially organized data the objects will contain connected sets of of Highs, where adjacency between High vertices (resp. Lows) is defined by cell edge adjacency, and paths are defined accordingly. However, regularly gridded data contains well known ambiguities [24], and so edge adjacency is insufficient. The ambiguity occurs when for a range of thresholds a cube face F contains diagonally opposite Highs and diagonally opposite Lows. We call F a 4-hit face since there is a hit on each edge (see figure 1).

Definition 4   The disambiguation value c with respect to a function f is the maximum threshold for which the diagonally opposite Highs in F are locally connected through the interior a cell sharing this face. Note that once they are path connected they will be path connected for all thresholds less than c. We associate a disambiguation point with F, having the value c (though it may actually be in the cube interior) and extend to this point. For $\tau > c$ we create a pseudo-edge from the diagonal connecting the two Lows, else we connect the two Highs by their diagonal. We extend the definitions of adjacency and connectivity of Highs and Lows to include the pseudo-edges.