Graphics Reference
In-Depth Information
been enhanced to contain its own locational code. The locational codes for both the
parent node and all children nodes can be computed from the stored locational code.
As such, the octree nodes no longer need explicit pointers to the children, thereby
becoming smaller.
// Octree node data structure (hashed)
struct Node {
Point center;
// Center point of octree node (not strictly needed)
int key;
// The location (Morton) code for this node
int8 hasChildK;
// Bitmask indicating which eight children exist (optional)
Object *pObjList;
// Linked list of objects contained at this node
};
The size of a node can be explicitly stored or it can be derived from the “depth”of
the locational code. In the latter case, a sentinel bit is required in the locational code
to be able to distinguish between, say, 011 and 000000011, turning these into 1011
and 1000000011, respectively. The code for this follows.
int NodeDepth(unsigned int key)
{
// Keep shifting off three bits at a time, increasing depth counter
for(intd=0;key; d++) {
// If only sentinel bit remains, exit with node depth
if (key == 1) return d;
key >>= 3;
}
assert(0);
// Bad key
}
To be able to access the octree nodes quickly given just a locational code, the
nodes are stored in a hash table using the node's locational code as the hash key. This
hashed storage representation provides
O
(1) access to any node, whereas locating an
arbitrary node in a pointer-based tree takes
O
(log
n
) operations.
To avoid a failed hash table lookup, the node is often enhanced (as previously) with
a bitmask indicating which of the eight children exist. The following code for visiting
all existing nodes in a linear octree illustrates both how child nodes are computed
and how the bitmask is used.
void VisitLinearOctree(Node *pTree)
{
// For all eight possible children
