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.

Scientific Computing and Imaging