The original SpiderWeb algorithm [13] constructs isosurfaces in regularly gridded 3-D data (that satisfy admissability) by constructing the surface patches in the cells as follows:
For each connected set of hits within a given 3 dimensional cube, we interpolate an interior articulation point AP (center of mass of all the hits in the set) and for each pair of adjacent hits in the set, we form a triangle consisting of AP and the two adjacent face hits. We repeat this action for all cubes with hits.
The proof of correctness for 3-d is quite simple and follows the proof of theorem 1 (see figure 4). To show that each surface produced is a manifold involves demonstrating the followong two properties:
The first property follows for edges from AP to a hit from the fact that each hit has a unique adjacent hit in each of the 2 faces that it occurs. Further, by using this fact and starting from a given hit, one can show that the triangle edges that connect each pair of adjacent hits in connected set of hits in a cube will form a circuit (a non intersecting closed curve) on the boundary of the cube, establishing property 2 for each AP.
The triangle edge connecting adjacent hits in a face is also shared by exactly two triangles, because it is shared by a triangle to an AP of the adjoining cube. The second property is also easy to establish for any hit, as each hit will be incident on exactly 8 triangle edges (and triangles): one triangle edge for each (unique) adjacent hit in each of the 4 cube faces that share the cube edge on which it occurs, and one edge to an AP of each of the 4 cubes that share this edge. Figure 4 C illustrates the edges from a hit to adjacent hits and articulation points, by an overhead view.
The triangle mesh can be oriented in a consistent manner by choosing the direction of the Low cube vertex at each hit point. Also property 2 of admissabilty has been esatblished by the proof that the triangles incident on an AP form a triangulation of the circle.
We can easily extend SpiderWeb to any dimension n to construct the surface patches in each n-cell. For a given n dimensional cell C, recursively construct the n-2-simplices in the n-1 dimensional boundary cells of C. Now for each connected sets of hits in C, select an AP for the set. Each n-1-simplex consists of the AP and the vertices of an n-2-simplex that contains adjacent face hits from the set (each simplex will contain a pair of adjacent hits). It will be shown in a forthcoming paper that this produces manifolds satisfying the admissability properties. In fact the proof of theorem 1, and this entire work, was motivated by the analysis of SpiderWeb and the simple perspective that it provides.
Let us just give the idea for 4 dimensions. Take a surface patch in one 3 dimensional boundary cube, , of the 4-cube C (there are 8 such boundary cubes). It intersects patches in the neighboring boundary cubes of C along triangle edges in faces of , and each face of is shared by two boundary cubes of C. A little thought reveals that this patch is part of a surface that closes in C, and this surface is topologically equivalent to a sphere. The AP of C for this hit set will be an interior point of this sphere and the tetrahedra formed by the AP and each triangle on the sphere will form our 3 dimensional surface patch (it will be equivalent to a ball). Now each such 3-D patch will intersect a patch in a neighboring hypercube C', by completely sharing a 2-D patch in a 3-D boundary cube of C. This is because C and C' will completely share . Thus the entire complex for any contour will form a 3-D manifold. We can view any 2-D slice of this complex by fixing a coordinate.
In general, the output produced by SpiderWeb for n dimensional data will be the list of the n-1-simplices in each contour.