2.1 Properties of admissable interpolating functions

We now give the properties of admissable interpolants. We restrict the class of interpolants to those whose contours behave in a manner consistent with standard isosurface extraction methods. Since these methods usually interpolate contours without extending the interpolating function f to the entire space, this is reasonable.

Definition 5   A function f is admissable if it interpolates and satisfies the following 2 properties for each not in the range of :

1

We assume that (for n dimensional data) is a finite collection of disjoint, compact, and oriented n-1-manifolds, embedded in , which divides into disjoint connected components, each of which contains either a single nonempty connected component of Highs ( ) or a single nonempty connected component of Lows ( $\bf {X}_{\delta}^{< \tau}$).

2

Let C be a d dimensional cell, $d \leq n$. We assume that $B (\bf {X}_{f}^{\geq \tau}) \cap C$ is a finite set of d-1 dimensional components (called surface patches), each of which is bicontinuously mappable to the d-1 dimensional unit disk (ball), and that this intersection divides C into disjoint simply connected components, each of which contains precisely the vertices from a single nonempty, connected component (with respect to C) of High vertices, or precisely the vertices from a single nonempty connected component of Lows (with respect to C).

Property 1 merely expresses the goal of isosurface construction from a global perspective, and property 2 expresses the type of local nondegeneracy assumed by isosurface construction algorithms. For example, an appropriately corrected marching cubes [11] will produce surface patches satisfying property 2. Note that while a tetrahedral cell will contain a single surface patch [12], a cubic cell in 3 dimensions (in unusual cases) may contain up to 4 distinct surface patches. This will occur when there exists a threshold such that all faces in the cell are 4-hit faces, and the threshold is above the disambiguation value for all the faces. The 4 High vertices of the cube will all be contained in separate regions.

We now show that these properties are sufficient to uniquely define the topology of the contours for irregularly gridded data, and only the disambiguation values of f are needed to uniquely specify the topology of regularly gridded data. More precisely,

Theorem 1   If f and f' are admissable and additionally, for regularly gridded data, f and f' have the same disambiguation values then the boundary manifolds (contours) of and $B (\bf {X}_{f'}^{\geq \tau})$ are homeomorphic.

We prove this theorem by a series of lemmas. Here is an outine of the proof. We first observe that no cell face can have an odd number of hits. The dual of data reading connectivity is hit connectivity. We identify a hit by the cell edge on which it occurs. Hits are adjacent if they are connected by a curve segment (of a contour) in a cell face. Property 2 insures that the pair of hits on a cell face with 2 hits are adjacent, and that the hits on a 4-hit face will be divided into 2 adjacent pairs (see figure 1). Both f and f' will have the same hit sets (as cell edges) and the connectivity of these hit sets will be the same. One can show by induction on the dimension d that each surface patch of corresponds to a connected set of hits in a d dimensional cell and use this fact to show that the hits in each manifold M of form a single connected set H. Let M' be the manifold of containing H. We form a graph from the surface patches of a manifold where the nodes of the graph are the patches, and the edges connect intersecting patches. Since intersecting patches must share a common hit, one can show that the graphs G and G', formed from M and M' respectively, are isomorphic. Since the patches intersect by sharing lower dimensional patches, it follows from property 2 that we can iteratively construct a continuous bijection from M to M'.

Lemma 1  

Let e be a cell edge. Then e has a single intersection point (termed a hit) with if and only if the incident endpoints are High and Low, respectively.

Proof:

This follows immediately from property 2.

Q.E.D.

Lemma 2  

Each 2 dimensional hypercube face (square) F has 0, 2 or 4 hit points. Each 2 dimensional simplex face (triangle) has 0 or 2 hits.

Proof:

This follows from a simple parity argument; or by examining the 4 possible arrangements of Highs and Lows on the 4 vertices of a cube face: 1, 2 or 3 edge adjacent Highs give 2 hits, and a pair of diagonally opposite Highs give 4 hits (see figure 1).

Q.E.D.

Definition 6  

Two hits are adjacent in face F if they are connected by a curve segment of $B (\bf {X}_{f}^{\geq \tau}) \cap F$. Connectivity of sets of hits is defined by the transitive closure of adjacency. Connected components are defined accordingly.

Lemma 3  

Each hit point h of face F is connected by a curve segment of to a unique (adjacent) hit point h' in F.

Proof:

This result follows from the previous lemma, the disambiguation rule, and property 2 (see figure 1).

Q.E.D.

Definition 7  

We can identify a hit (uniquely) by the cell edge on which it occurs. Below when we wish to refer to the actual hit point (and not merely the edge) we will indicate this fact.

Lemma 4   and have the same hit sets (as edge sets). Moreover they have the same hit connectivity.

Proof:

Changing the interpolation function does not change whether a vertex is High or Low. For regularly gridded data f and f' are assumed to share the same disambiguation values, and thus hit connectivity is the same for both.

Q.E.D.

Definition 8  

Two surface patches are adjacent if they intersect.

Lemma 5   Two d-1 dimensional surface patches of M, $\sigma \in C$ and $\sigma' \in C'$, are adjacent if and only if their intersection is a set of d-2 dimensional surface patches of M in the d-1 dimensional boundary cell shared by C and C'. Further, if $\sigma$ and $\sigma'$ are adjacent then they share at least one hit point in each component of their intersection.

Proof: The fact that they must intersect in some lower dimensional patch follows from the fact that the d-1 dimensional boundary cell is completely shared by C and C' and property 2. The fact that they share a hit point in each component of their intersection is due to the fact that their intersection must occur on at least one cell edge, and thus they share this hit.

Q.E.D.

Lemma 6   Each connected component of hits of cell C is a member of a unique surface patch $\sigma \in B (\bf {X}_{f}^{\geq \tau}) \cap C$, and conversely the hits contained in each surface patch form a unique connected component of hits of C.

Proof: By the definitions of hit point adjacency and connectivity, each pair of hits in a connected component of hits within C is connected by a path within , and by path connectivity of surface patches, this path must be part of the same patch. Thus the connected set of hits all lie in a single patch of C.

For the other direction, we must show that the hit points of form a connected set within C. The proof is by induction on the dimension d. The result is clearly true for d=1 and d=2. For the inductive hypothesis, we assume that for all $j \leq d-1$, the hits of each patch of a j dimensional cell C is a connected set, within C. For the inductive step let be a patch of a d dimensional cell C. Let h and h' be any two hit points of . Since is homeomophic to the unit ball, its boundary, $\beta$, is also connected, and is contained in the d-1 dimensional boundary cells of C. Then there is a path $\pi \in \beta$ from h₁ to h₂, such that this path $\pi$ passes through a sequence, $\sigma_1 , \ldots , \sigma_m$, of adjacent d-2 dimensional patches in the d-1 dimensional boundary cells of C. For each $1 \leq i < m$, let h_i be any hit point in $\sigma_i$ and let h_i+1 be any hit point in $\sigma_{i+1}$. We claim h_i and h_i+1 are part of the same component of hits of C. Since and are adjacent, then, by lemma 5 and the induction hypothesis, they share at least one hit point in common. Also, by the induction hypothesis, the hits of and are each connected sets of hits, within their respective boundary cells, and thus the union of the hits of and , must be part of the same connected set of hits in C. Thus h_i and h_i+1 are part of the same component of hits in C. Since $h \in \sigma_1$ and $h' \in \sigma_m$, this gives the result.

Q.E.D.

Lemma 7   Each connected component of hits is contained in a unique component manifold M (contour) of , and conversely the hits contained in each such manifold M form a unique connected component of hits.

Proof: A connected component of hits is contained in a single manifold M by the definition of hit adjacency and the connectivity of M. This manifold is unique, since by property 1 the manifolds are pairwise disjoint.

For the other direction suppose that M contains two hits h₁ and h₂. There is clearly a path in M from h₁ to h₂. This path passes through some sequence of patches of M, , of cells $C_1, \ldots , C_m$, where $h_1 \in \sigma_1$ and $h_2 \in \sigma_m$. For each , contains a unique connected component of hits within C_i, by lemma 6. For each such i, and intersect in in a shared boundary cell C'_i of C_i and C_i+1, from lemma 5. Also from lemma 5, we know that and share at least one hit point in C'_i. It follows that hit points of and are part of the same connected component of hits. Thus h₁ and h₂ are part of the same connected component of hits.

Q.E.D.

From lemma 7 we immediately get:

Lemma 8   and consist of the same number of components.

Let H be a connected component of hits (as edges). Let M be the component of containing H and let M' be the component of containing H.

Lemma 9   Let M consist of patches $\Sigma = \sigma_1 , \ldots , \sigma_k$. Then there exists a one-to-one mapping $\iota$ of $\Sigma$ onto the patches of M' so that for all $1 \leq i < j \leq k$, is adjacent to $\sigma_j$ if and only if $\iota ( \sigma_i )$ is adjacent to $\iota ( \sigma_j )$. In addition, their respective intersections have the same number of components.

Proof: The mapping associates two patches if they share the same hit set (as edges). This mapping is one to one and onto by lemma 6.

If is adjacent to , then from the above lemmas, they share at least one hit in common (on edge e), for each component of their intersection. Then and also share a hit on edge e and are thus also adjacent. It is easy to see that the converse holds.

Q.E.D.

In other words if we represent the patches and their adjacencies by graphs in the natural way, then the graphs representing M and M' are isomorphic.

Using the above facts we can prove:

Lemma 10  

M and M' are homeomorphic.

Proof:

We can construct a global homeomorphism from M to M' piecewise via their patches. From property 2, both patches and are bicontinuously mappable to the unit disk. From lemma 9 we know that is adjacent to if and only if is adjacent to , and from lemma 5 and from property 2 we know that the intersections of the corresponding pairs of adjacent patches are also bicontinuously mappable. We can thus bicontinuously map to in a manner that extends to a bicontinuous mapping of to , for each such adjacent patch. Thus we can define the homeomorphism iteratively on each in a manner that produces a global homeomorphism from M to M', giving the result.

Q.E.D.

Theorem 1 now follows immediately from lemmas 7 and 10.