Octree node identifiers

Let's say we have an octree and we want to come up with a unique integer that can identify any node in the tree - including interior nodes, not just leaf nodes. Let's also say that the octree has a maximum depth no greater than 9 levels, i.e. the level containing the leaf nodes divides space into 512 parts along each axis.

The encoding

The morton encoding of a node's i,j,k coordinates within the tree lets us identify a node uniquely if we already know it's depth. Without knowing the depth, there's no way to differentiate between cells at different depths in the tree. For example, the node at depth 1 with coords 0,0,0 has exactly the same morton encoding as the node at depth 2 with coords 0,0,0.

We can fix this by appending the depth of the node to the morton encoding. If we have an octree of depth 9 then we need up to 27 bits for the morton encoding and 4 bits for the depth, which still fits nicely into a 32-bit integer. We'll shift the morton code up so that it starts at the topmost bit and set any unused trailing bits to zero. We'll put the depth in the bottom 4 bits. That leaves at least one bit free between the two parts - bit 4 - which we'll always set to zero (this will be useful later). The structure of the key will look like this:

bit	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
	morton index																											0	depth

For a node at depth 7, for example, it would look like this:

bit	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
	morton index																					0	0	0	0	0	0	0	7

Why do it this way? Well, in addition to identifying each node uniquely, this representation has a few other nice properties:

1. Sorting nodes by this number puts them in the order they would be visited by a pre-order traversal of the octree.
2. You can calculate the identifier of a parent node from a child using simple bitwise operations.
3. If you have two nodes at the same depth in the tree, you can calculate their lowest common ancestor using simple bitwise operations too.

Implementing it

Here's an example implementation of the scheme above:

struct NodeKey {
  uint32_t key;

  // Depth of this node.
  uint32_t depth() const
  {
    return key & 0xF;
  }

  // Morton index for this node.
  uint32_t index() const
  {
    return key >> (31 - depth() * 3);
  }

  // Calculate the NodeKey for the parent of this node.
  NodeKey parent() const
  {
    return ancestor_at_depth(depth() - 1);
  }

  // Calculate the NodeKey for the nth ancestor.
  // n = 0 means self, n = 1 means parent, n = 2 means grandparent, ...
  NodeKey ancestor_n(uint32_t n) const
  {
    return ancestor_at_depth(depth() - n);
  }
  
  // Calculate the NodeKey for the ancestor of this node at depth d in
  // the octree.
  NodeKey ancestor_at_depth(uint32_t d) const
  {
    assert(d <= depth());
    uint32_t mask = 0xFFFFFFFF << (31 - d * 3));
    return { (key & mask) | d };
  }
};

// Find the deepest node that is a common ancestor of both input nodes.
NodeKey common_ancestor(const NodeKey a, const NodeKey b)
{
  uint32_t bits = min(a.depth(), b.depth()) * 3;
  uint32_t marker = 0x80000000 >> bits;
  uint32_t depth = __builtin_clz((a.key ^ b.key) | marker) / 3;
  return a.ancestor_at_depth(depth);
}

The line in common ancestor which calculates the depth of the common ancestor uses a slight variation on the technique from my previous post.

Variations

If you want a post-order traversal instead, just set the trailing bits to 1 rather than 0.

You can turn this into a breadth-first traversal by swapping the positions of the depth and the morton index: use the top 4 bits for the depth and the bottom 27 bits for the morton index. In this case the morton index should have leading bits set to zero instead of the trailing bits (i.e. the index should be aligned to the right of the available bits, intead of the left).

Another way to represent a breadth-first traversal is to put the morton index in the bottom-most bits and have a sentinel bit which is always set to 1 to indicate where the morton index ends. Every bit above the sentinel must be set to zero for this to work. This allows you to represent an additional octree and makes it even simpler to calculate the parent identifier (it's just child >> 3), but calculating the depth of the node involves counting the leading zeros and dividing by 3.

Limitations

Assuming a 32-bit identifier, the maximum octree depth it can represent is 9 levels. Depending on your application this may or may not be sufficient. The scheme generalises easily to a 64 bit identifier which can store up to 19 levels, but at the cost of doubling storage requirements and there are still some important platforms (e.g. many GPUs) which don't provide support for 64 bit integers.