The article Advanced Octrees 2: node representations states:
The AABB (axis-aligned bounding box) of the node can be stored explicitly as before, or it can be computed from the node’s tree depth stored implicitly inside the locational code. To derive the tree depth at a node from its locational code a flag bit is required to indicate the end of the locational code. Without such a flag it wouldn’t be possible to distinguish e.g. between 001 and 000 001. By using a 1 bit to mark the end of the sequence 1 001 can be easily distinguished from 1 000 001. Using such a flag is equivalent to setting the locational code of the Octree root to 1.
The book Real-Time Collision Detection, Volume 1 by Christer Ericson states:
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, say, 011 and 000000011, turning these into 1011 and 1000000011, respectively.
Both offer the following algorithm for computing the depth of a node:
int node_depth(unsigned int key) {
for (int d = 0; key; ++d) {
if (key == 1) { return d; }
key >>=3;
}
assert(false);
}
How and why does this work?
The location code is a 32 bit word. That is, ... 011
and ... 000 011
might be equal, depending on what the remaining bits of the first location code are. using a sentinel, one has ... xx1 011
and ... xx1 000 011
and now they are different location codes.
What I don't understand is how can I get the depth of the nodes from the location codes and how does the sentinel help me with that.
Going back to the example above, ... xx1 011
and ... xx1 000 011
, these words could be ... 000 001 011
and ... 000 001 000 011
, respectively. Both cases have the sentinel bit, but since 001
(and any other xx1
combination) is a valid triple, all triples are valid, and there is no way for me to tell what the depth of the nodes is.
The only solution I've found is to store the depth of the node next to the location code, but that article and the book seem to indicate that the depth can be derived from the location code somehow.