The Spatial Index

The geometry of a node in an orthtree may be described by its level and the N index coordinates of its lower corner. There are various ways of storing this information. One can use an integer to store the level and N integers to store the index coordinates. Alternatively one can pack this information into integer or bit array. For the packed case, one can store each index coordinate in contiguous bits, or one can interleave the bits. Typically, the method of storage directly translates into an ordering of the nodes. If one packs the information into a single integer type, then one uses the standard less than comparison on integers to order the nodes.

There is a standard spatial indexing scheme called the quadcode which stores the level and coordinates in a single integer type. The index coordinates are interleaved and packed into the most significant bits. The level is stored in the less significant bits. This translates into an ordering of the nodes that has some handy properties. Most importantly, there is a spatial coherence to a block of nodes accessed in order. This is useful both from an algorithmic perspective (some searching operations are easier) and for performance (fewer cache misses). In addition, this ordering can be used for partitioning the nodes across processors.

Z-ordering.

While the quadcode is handy for ordering the nodes, a non-interleaved representation is more useful for manipulating the spatial index. When determining the parent, children, or neighbors of a node, one needs to manipulate the index coordinates and level. With the quadcode, one extracts the coordinates and level, manipulates then, and then packs them back into the quadcode. Because the bits are interleaved, this unpacking and packing is fairly expensive. (The computational complexity of both packing and unpacking is linear in the depth of the tree.) If one uses a separated or non-interleaved representation for the spatial index, then manipulations can be done in constant time.

For our implementation, we store the interleaved quadcode in a single integer type and also separately store the index coordinates and level. We use the quadcode for ordering the nodes and use the separate index coordinates and level for spatial index arithmetic. This makes the algorithms easier to implement and more efficient, but roughly doubles the storage requirements for the spatial index. If one is storing a significant amount of data in each node (a small grid, or a spectral element), then this extra storage requirement for the spatial indices will be neglible.