6.1.2 Correctness.

Theorem 4  

SpiderWeb produces oriented manifolds (iso-surfaces) that satisfy the axioms.

Proof:

The proof of correctness for 3-d is quite simple and employs the same symmetries used to prove theorem 1 (see figures 29 through 32 ). Showing that the surface produced is a manifold involves demonstrating two properties (well known from elementary topology): firstly that each triangle edge is shared by exactly 2 triangles, and secondly that the triangles shared by any triangle vertex locally form a triangulation of the circle.

For example, let e be the triangle edge connecting 2 hits in a face F of cube C. e is shared by the triangle between these two hits and an articulation point of cube C, and also by the triangle between these same hits and an articulation point of the cube C', sharing face F (see figure 30). Similarly, let e be an edge between AP and hit h on cube edge a. Then e is shared by the triangle consisting of AP and the adjacent pairs of hits h and g in cube face F, and by the triangle consisting of AP, and the adjacent hits h, and g', on the face F' that shares cube edge a with face F (see figure 29).

Demonstrating the second property for each articulation point, and for each hit point, uses the same symmetries. Observe that each hit h is shared among the 4 cubes that share the edge on which h occurs, and thus 4 cube faces. The hit point will be the endpoint of eight distinct triangle edges (see figure 31). Four of the triangles edges will be to articulation points of the 4 cubes, and the other 4 edges will connect h with the unique adjacent hit on each of the 4 faces it shares. One can enumerate these edges in a cyclical fashion. We can start with a triangle edge e emanating from h, and circulate about the h, enumerating the emanating edges (and triangles) until we return to the initial edge e.

We can do the same for AP, as each edge e goes to a face hit (see figure 32). Each such hit h has a unique adjacent hit g, with respect to a face F. Then g has a unique adjacent hit g', with respect to the shared face F'. We continue in this fashion until we return to the hit h.

Each manifold produced is oriented, with the orientation defined locally for each triangle by the High readings on the face edges containing its hit pair. Finally, observe that the surfaces produced within a given cube satisfy axiom 2 and the collection of surfaces globally satisfy axiom 3.

Now in 4 dimensions, using the same symmetries, one can show that each patch produced in a given 4-dimensional cube forms a closed 2 manifold homeomorphic to a sphere, and thus bounds a 3-dimensional region homeomorphic to the unit 3-dimensional disk. Since each 2-dimensional surface patch within a 3-dimensional cube C, is completely shared by the two 4-dimensional cubes that share C as part of their boundary, it is straightforward to see that these 3-dimensional volumes correspond to the patches of the correct 3-dimensional manifolds. Thus one can recover an iso-volume from the SpiderWeb surfaces, and show that each such manifold satisfies the axioms.

What may strike one is the power of the simple observation that no face can have an odd number of hits. It makes one wonder why such a simple and elegant algorithm wasn't noticed before. It is certainly easier to program and prove correct than numerous tiling-based iso-surface algorithms in the literature!

Note that the algorithm is highly parallelizable, as each cube can be processed independently. Adjacency of triangles within cubes is based on cube face adjacency, and adjacency of triangles between cubes is easily computed as they share a pair of hits on their common face. Thus surface tracking can be done easily. Therefore surfaces can be constructed in a manner that minimizes disk seek time for large datasets. This is quite important.

For a 4-dimensional example consider volume data sampled over time. We can regard time as a fourth spatial dimension. For a fixed value of time t and threshold $\tau$ one can grow the iso-surfaces at time t. Or one can grow the iso-volume swept as the $\tau$ valued iso-surface moves and changes through time by applying SpiderWeb in 4-D.