SpatialOctree

Axom provides an implementation of the octree spatial index. The SpatialOctree recursively divides a bounding box into a hierarchy of non-intersecting bounding boxes. Each level of subdivision divides the bounding box of interest along each of its dimensions, so 2D SpatialOctree objects contain four child bounding boxes at each level, while 3D objects contain eight children at each level.

The Octree class hierarchy is useful for building custom spatial acceleration data structures, such as quest::InOutOctree.

The figure below shows the construction of several levels of a 2D octree.

In contrast to a BVHTree, which computes a bounding box at each step, the octree structure begins with a user-specified bounding box.

The octree divides all dimensions in half at each step.

Similar to the BVHTree, the Octree divides a bounding box only if an object intersects that bounding box. In contrast to the BVHTree, the bounding box bins are non-intersecting, and division does not depend on the data in the bounding box. An \(N\)-dimensional octree divides into \(2^N\) bounding boxes at each step.

The following code example shows use of the SpatialOctree. Include headers and define types:

#include "axom/spin/SpatialOctree.hpp"

using LeafNodeType = axom::spin::BlockData;

using OctreeType = axom::spin::SpatialOctree<in3D, LeafNodeType>;
using OctBlockIndex = OctreeType::BlockIndex;
using OctSpacePt = OctreeType::SpacePt;
using OctBBox = OctreeType::GeometricBoundingBox;

Then, instantiate the SpatialOctree and locate or refine blocks that contain query points.

  OctBBox bb(OctSpacePt(10), OctSpacePt(20));

  // Generate a point within the bounding box
  double alpha = 2. / 3.;
  OctSpacePt queryPt = OctSpacePt::lerp(bb.getMin(), bb.getMax(), alpha);

  // Instantiate the Octree
  OctreeType octree(bb);

  // Find the block containing the query point
  OctBlockIndex leafBlock = octree.findLeafBlock(queryPt);
  // and the bounding box of the block.
  OctBBox leafBB = octree.blockBoundingBox(leafBlock);

  for(int i = 0; i < octree.maxInternalLevel(); ++i)
  {
    // SpatialOctree allows a code to refine (subdivide) a block
    octree.refineLeaf(leafBlock);
    // and locate the (new) child block containing the query point.
    leafBlock = octree.findLeafBlock(queryPt);
  }

Unlike the BVHTree class, the SpatialOctree is intended as a building block for further specialization. Please see the quest::InOutOctree as an example of this.

Some ancillary classes used in the implementation of SpatialOctree include BlockData, which ties data to a block; Brood, used to construct and organize sibling blocks; OctreeBase, implementing non-geometric operations such as refinement and identification of parent or child nodes; and SparseOctreeLevel and DenseOctreeLevel, which hold the blocks at any one level of the SpatialOctree. Of these, library users will probably be most interested in providing a custom implementation of BlockData to hold algorithm data associated with a box within an octree. See the quest::InOutOctree class for an example of this.