Interpolation and parallel adjustment of center-sampled trees with new balancing constraints
We present a novel tree balancing constraint that is slightly stronger than the well-known 2-to-1 balancing constraint used in octree data structures (Tu and Ohallaron, Balanced refinement of massive linear octrees. Tech. Rep. CMU-CS-04-129. Carnegie Mellon School of Computer Science, Pennsylvania, 2004). The new balancing produces a limited number of local cell connectivity types (stencils): 5 for a quadtree and 21 for an octree. Using this constraint, we interpolate the data sampled at cell centers using weights pre-computed by interpolation or by generating interpolation codes for each stencil. In addition, we develop a parallel tree adjustment algorithm, and show that the imposed balancing constraint is satisfied even when the tree is adjusted in parallel. We also show that the adjustment has high parallelization performance. We finally apply the new balancing scheme to level set image segmentation and smoke simulation problems.
interpolation parallelization octree quadtree segmentation smoke simulation balanced tree