## 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:

- Sorting nodes by this number puts them in the order they would be visited by a pre-order traversal of the octree.
- You can calculate the identifier of a parent node from a child using simple bitwise operations.
- 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.
## No comments:

## Post a Comment