title: What's the algorithm for 2:1 balancing a linear octree?
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>