## Friday, 30 October 2015

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

## Monday, 26 October 2015

### Common bit prefix length for two integers

Here's a neat trick I discovered a couple of months back: given two signed or unsigned integers of the same bit width, you can calculate the length of their common prefix very efficiently:


int common_prefix_length(int a, int b)
{
return __builtin_clz(a ^ b);
}


What's this doing? Let's break it down:

a ^ b is the bitwise-xor of a and b. The boolean xor operation is true when one of it's inputs is true and the other is false; or false if both have the same value. Another way to put this is that xor returns true when its inputs are different and false if they're the same. The bitwise-xor operation then, returns a value which has zeros for every bit that is the same in both a and b; and ones for every bit that's different.

__builtin_clz is a GCC intrisinc function which counts the number of leading zero bits of its argument. It compiles down to a single machine code instruction on hardware that supports it (which includes every Intel chip made in this decade). The Visual C++ equivalent is the _BitScanReverse intrinsic, which has a slightly more complicated API; implementing the above with it is left as an exercise for the reader. :-)

Passing the result of a ^ b to __builtin_clz means we're counting the leading zero bits in a number where a zero bit indicates that the corresponding bits in a and b had the same value; which is exactly how we get the length of the common prefix.

You can get the common suffix in the same way. The only difference is that you use the __builtin_ctz intrinsic (Visual C++: _BitScanForward) instead, to count the trailing zero bits:


int common_suffix_length(int a, int b)
{
return __builtin_ctz(a ^ b);
}


Neat huh?