What's the algorithm for 2:1 balancing a linear octree?

Question

I have a top-down procedure that builds a linear octree (e.g. with leaves arranged in an array and sorted by Morton encoding) from an high-level description of 3D objects. The problem is that, for my intended application, the resulting octree must be 2:1 balanced, i.e. there must not be any pair of adjacent blocks where one is more than double the size of the other.

The only thing I could find is the article "Bottom Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel" (you find it from multiple sources but the copyright is not clear, not sure what's the policy for linking things like that on this site), which explains an algorithm to do that. The problem is that the presented algorithm works in a parallel message-passing architecture, and it's overkill for my application. The other problem is that the (bottom-up) construction and balancing algorithms seem tied together, and I don't know at a glance how to only balance it after having constructed the tree with my own method.

So what is a (hopefully simple and) efficient method for 2:1 balancing a linear octree? A parallel algorithm would also be great, but with a shared memory model, not a message passing one like the linked algorithm.

Answer 1

The simplest sequential algorithm probably is to keep a queue containing unprocessed octree nodes and process each one in turn by ensuring that its three level - 1 non-sibling neighbors exist. The additional nodes created during processing go in the queue.

-----------------
| | | | |       |
---------       |
| | | | |       |
---------       |
| | |d| |       |
--b------       |
| | |a|e|       |
-----------------
|       |       |
|       |       |
|       |       |
|   c   |       |
|       |       |
|       |       |
|       |       |
-----------------

Here a's two (quadtree) level - 1 non-sibling neighbors are b and an as yet nonexistent child of c. Nodes d and e are the (same-level) sibling neighbors.

The complex part of this algorithm is determining how to find these neighbors. This can be accomplished by computing the coordinates of the node and its non-sibling neighbors, Morton encoding them, and then looking for the most-significant set bit in the XOR of the encoding for the node and each of its neighbors in turn. The index of this bit over three plus one is the number of parent links that need to be traversed.

For example, let's use yxyxyx as the Morton interleaving for the quadtree diagram. Node a is the square from (2,4) to (3,5) and has Morton coordinates 100100. Node b is the square from (0,4) to (2,6) and has Morton coordinates 100000. Node c is the square from (0,0) to (4,4) and has Morton coordinates 000000. Node d is the square from (2,5) to (3,6) and has Morton coordinates 100110. Node e is the square from (3,4) to (4,5) and has Morton coordinates 100101.

To find a's neighbors, we encode (2+1, 4) and (2-1, 4) and (2, 4+1) and (2, 4-1). Let's do (2, 4-1) = (2,3). The Morton encoding of (2,3) is 001110. Compared with a's Morton encoding,

    001110
    100100
XOR ------
    101010
    \/\/\/

Since the third-least significant group of two bits is nonzero, we ascend to the leaf level minus three (i.e., three parent links from a) and then descend twice (three minus one times) according to the Morton code. When we encounter nonexistent children, as with the second descending step, we make them as needed and add them to the queue.

Parallel version

Since I have avoided some complicating optimizations in the sequential algorithm, it is robust to changes in the processing order and even to parallelism, so long as there are no races in splitting octree nodes. For shared-memory parallelism, given a compare-and-swap primitive, it's easy enough to make constructing a child lock-free (allocate a node and then CAS the appropriate child pointer from null; if the CAS fails, then just read the winning child). Given that CAS is available, an efficient shared collection for the queue shouldn't be too hard (it doesn't have to be FIFO). I have no idea what kind of speedup parallelism would give here.