This brings us to the notion of cache-rings. For any given voxel,
*v*[*i*,*j*,*k*], in order to generate the portion of the surface that
intersects that cell, we only need the scalar field data at the corners of
the cell, and the shared-edge intersection information from the
previously visited voxels: *v*[*i*,*j*,*k*-1], *v*[*i*,*j*-1,*k*], *v*[*i*,*j*-1,*k*-1],
*v*[*i*-1, *j*, *k*], *v*[*i*- 1,*j*,*k*-1], and *v*[*i*-1, *j*-1,*k*]. These voxels
and edges are shown in Figure 1.

Figure 1:Previously visited, neighboring voxels. The thick, dark lines indicate edges shared with the current voxel,v[i,j,k]. The location of the noden[i,j,k] is indicated with a dark point. The lighter gray lines on the current voxel indicate edges which have not yet been encountered, and whose intersection nodes might, therefore, need to be computed. Thinner lines indicate all other voxel edges - none of these are of interest when extracting at the current voxel.

The edge information from each direction is stored in a data-structure
called a ``cache-ring.'' Each ring is implemented as a ring-buffer, and
stores edge intersection information for the neighboring cells of a
particular direction. We note that each ring has a maximum length
equal to the the number of cells traversed between that neighboring
voxel and the current voxel. For example, voxel *v*[*i*,*j*-1,*k*] is
(*nz*-1) voxels away from the current voxel *v*[*i*,*j*,*k*]; therefore, the
ring in the y-direction, the y-ring, needs to have a maximum of *nz*
entries (both sides of the current voxel need to be stored, which
increases the total by one entry). We traverse the data in normal
Marching Cubes fashion, and upon completing each voxel, we record the
current information into all of the rings and advance the pointers. A
graphical depiction of three of these rings is shown in Figure 2.

Figure 2:The X-, Y-, and Z-Rings and their contents during data traversal. The left side of each ring shows the currently active edges whose data is stored in the ring. As indicated by the axes, the cells are visited from left to right, from top to bottom, and from back to front. The right side of each diagram depicts the cache-ring storing the edge information, with arrows indicating the direction of traversal.

In practice, we actually utilize only a small portion of each ring at a time for storing precomputed indices - most of the voxels between the current voxel and the last voxel in the ring contain no intersection points, and are empty. Recognizing that ring data is always accessed deterministically (every entry which is stored is guaranteed to be accessed, and the accesses will occur in exactly the same order in which they are stored), we only need to store those edges which contain an intersection. With this revised implementation, we now store two indices into each ring - one for the voxel being examined and one for the neighbor information being stored (previously, these indices were identical, so a single value was sufficient). New data is always inserted at the last index, and the next intersection index is always read from the head.

Scientific Computing and Imaging