How can I calculate an octree node's depth from its location code?

Question

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.

Answer 1

It might be helpful to think of the key variable as a stack that you're trying to count the depth of. Every iteration, you add 1 to the depth, return if the stack is empty, then pop 3 bits off the stack.

The sentinel bit just marks where the stack ends.

An example (imagine lots more zeros to the left):

... 001 000 010 111 # pop 111
... 000 001 001 010 # pop 010
... 000 000 001 001 # pop 001
... 000 000 000 001 # done (because the stack == 1)

Since the key == 1 check is only true when the bits are exactly 000 000 … 001, it doesn't matter that a 001 was also encountered in the middle of the sequence.

It doesn't actually matter what value the sentinel bit is, as long as it's not 000. You could have a "sentinel seven" by putting 111 at that point and checking for key == 7 instead.

So why not a 000 "sentinel zero"? Because if the location code starts with a bunch of zeros, you wouldn't be able to distinguish the "bottom of the stack" from the zeros that the bit shift keeps introducing:

... 000 000 001 010 # pop 010
... 000 000 000 001 # pop 001
... 000 000 000 000 # pop 000
... 000 000 000 000 # pop 000
... 000 000 000 000 # pop 000
... 000 000 000 000 # pop 000
... 000 000 000 000 # pop 000
... 000 000 000 000 # When do we stop?

Answer 2

Given the locational code c of a node, its depth in the Octree can be computed as log2(c)/3