For comparison, we also implemented an edge-hashing extraction/construction method that builds the same connected surfaces as out cache-ring method. Here again we exploit the predictability of edge accesses, recognizing that an interior node will be accessed by exactly four voxels. After a node has been accessed four times, we delete it from the hash table, thus saving time (less likely to have collisions during future lookups) and memory (only the active node indices are stored).
Every edge spans two voxels. For the purpose of defining a unique, consistent hash-key for each edge, we use the ``smaller'' node as the root of our index. (By ``smaller'' we mean the node to the left, below, or behind the other node - see Figure 1 for reference.) The i, j, and k indices of this node are concatenated to form the high-order bits of the key. These are followed by two bits to encode direction information (right, up, or forward), and two final bits to encode how many times the node has been referenced. If we have a data set containing less than 228 (134 million) voxels, then this hash-key can be constructed as a 32-bit integer. Alternatively, for larger data sets, we can hash long integer keys.
The multiprocessor implementation of the edge-hashing method utilized the same synchronization mechanisms as the cache-ring version. The only difference is that a separate hash table is created for the boundary voxels. This global object is analogous to the shared boundary cache-ring discussed above.