contents up previous next
Up: Methods
Previous: Methods
Next: Cache-Ring Data Structure

Predictable Data Traversal

As we march through the data and generate these triangles, we recognize that every interior edge intersection (i.e. any edge that is not on a bounding face of the volume) is shared by exactly four voxels. If an edge is intersected by a triangle in one voxel, it will necessarily be intersected at exactly the same point by triangles in the other three voxels as well (because Marching Cube surfaces are manifold and piecewise continuous). Without loss of generality, let us assume that we are traversing our data in x-major order ( i.e. the data is stored as consecutive slices of x, with z-coordinates changing fastest). If we are currently examining voxel v[i,j,k], and we find an intersection point along its (+x,+y) edge, then we know that when we reach voxel v[i,j+1,k] we are guaranteed to find a triangle with this same intersection. Similarly, this intersection point will be repeatedly found in voxel v[i+1,j,k] and voxel v[i+1,j+1,k]. Since we can predict exactly when we will be arriving at voxel v[i+1,j,k], we should be able to ``prefetch'' all of the precomputed edge intersections so we can reuse their values ``on the fly.'' If the size of our volume is (nx * ny * nz) nodes, then we have ((nx-1) * (ny-1) * (nz-1)) voxels. It follows that we will arrive at voxel v[i,j+1,k] exactly (nz-1) iterations later; at voxel v[i+1,j,k], ((nz-1)*(ny-1)) iterations later; and at voxel v[i+1,j+1,k], ((nz-1)*ny) iterations later.


contents up previous next
Up: Methods
Previous: Methods
Next: Cache-Ring Data Structure

Scientific Computing and Imaging
Wed Apr 23 17:39:06 MDT 1997