BVHTree

The BVHTree implements a bounding volume hierarchy tree. This data structure recursively subdivides a rectilinear region of interest into a “tree” of subregions, stopping when a subregion contains less than some number of objects or when the tree reaches a specified height. Similar to UniformGrid, subregions are also called bins.

The BVHTree is well-suited for particle-mesh or ray-mesh intersection tests. It is also well-suited to data sets where the contents are unevenly distributed, since the bins are subdivided based on their contents. The figure below shows several 2D triangles and their bounding box, which serves as the root bin in the tree.

The BVHTree::build() method recurses into each bin, creating up to two child bins depending on how many objects are located there and how they are distributed.

Unlike the UniformGrid, BVHTree bins can overlap.

The following code example shows how a BVHTree can be used to accelerate a point-mesh intersection algorithm. First, we insert all triangles into the index and call BVHTree::build().

#include "axom/spin/BVHTree.hpp"
// the BVHTree is in 2D, storing an index to 2D triangles
using BVHTree2DType = axom::spin::BVHTree<int, in2D>;
// supporting classes
using BoundingBox2DType = axom::primal::BoundingBox<double, in2D>;
using Point2DType = axom::primal::Point<double, in2D>;
using Triangle2DType = axom::primal::Triangle<double, in2D>;

BoundingBox2DType findBbox(Triangle2DType& tri);

BVHTree2DType* buildBVHTree(std::vector<Triangle2DType>& tris)
{
  // Initialize BVHTree with the triangles
  const int MaxBinFill = 1;
  const int MaxLevels = 4;
  int tricount = static_cast<int>(tris.size());
  BVHTree2DType* tree = new BVHTree2DType(tricount, MaxLevels);

  for(int i = 0; i < tricount; ++i)
  {
    tree->insert(findBbox(tris[i]), i);
  }

  // Build bounding volume hierarchy
  tree->build(MaxBinFill);

  return tree;
}

After the structure is built, make a list of triangles that are candidate neighbors to the query point. Call BVHTree::find() to get the list of bins that the query point intersects. The key idea of find() is that testing for probe intersection with a bin (bounding box) is cheap. If a bin intersection test fails (misses), the contents of the bin are cheaply pruned out of the search. If the probe does intersect a bin, the next level of bins is tested for probe intersection. Without the acceleration data structure, each probe point must be tested against each triangle.

void findCandidateBVHTreeBins(BVHTree2DType* tree,
                              Point2DType ppoint,
                              std::vector<int>& candidates)
{
  // Which triangles does the probe point intersect?
  // Get the candidate bins
  std::vector<int> bins;
  tree->find(ppoint, bins);
  size_t nbins = bins.size();

  // for each candidate bin,
  for(size_t curb = 0; curb < nbins; ++curb)
  {
    // get its size and object array
    int bcount = tree->getBucketNumObjects(bins[curb]);
    const int* ary = tree->getBucketObjectArray(bins[curb]);

    // For each object in the current bin,
    for(int j = 0; j < bcount; ++j)
    {
      // find the tree's internal object ID
      int treeObjID = ary[j];
      // and use it to retrieve the triangle's ID.
      int triID = tree->getObjectData(treeObjID);

      // Then store the ID in the candidates list.
      candidates.push_back(triID);
    }
  }

  // Sort the candidate triangles, and throw out duplicates.
  // This is not strictly necessary but saves some calls to checkInTriangle().
  std::sort(candidates.begin(), candidates.end());
  std::vector<int>::iterator jend =
    std::unique(candidates.begin(), candidates.end());
  candidates.erase(jend, candidates.end());
}

Finally, test the point against all candidate neighbor triangles.

void findIntersectionsWithCandidates(std::vector<Triangle2DType>& tris,
                                     std::vector<int>& candidates,
                                     Point2DType ppoint,
                                     std::vector<int>& intersections)
{
  // Test if ppoint lands in any of its neighbor triangles.
  int csize = static_cast<int>(candidates.size());
  for(int i = 0; i < csize; ++i)
  {
    Triangle2DType& t = tris[candidates[i]];
    if(t.checkInTriangle(ppoint))
    {
      intersections.push_back(candidates[i]);
    }
  }
}