BVH

The BVH class implements a bounding volume hierarchy. This data structure recursively subdivides a rectilinear region of interest into a “tree” of subregions.

BVH 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 following code example shows how a BVH can be used to accelerate a point-mesh intersection algorithm. First, we generate bounding boxes for all triangles in the mesh, and call BVH::initialize() with the bounding boxes.

#include "axom/spin/BVH.hpp"
// the BVH is in 2D, storing an index to 2D triangles
using BVH2DType = axom::spin::BVH<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);

BVH2DType* buildBVHTree(std::vector<Triangle2DType>& tris)
{
  // Create a BVH
  BVH2DType* tree = new BVH2DType;

  std::vector<BoundingBox2DType> bboxes(tris.size());

  // Get bounding boxes of each element
  for(size_t i = 0; i < tris.size(); ++i)
  {
    bboxes[i] = findBbox(tris[i]);
  }

  // Build bounding volume hierarchy from bounding boxes
  tree->initialize(bboxes.data(), bboxes.size());

  return tree;
}

After the structure is built, we can use the BVH to generate a list of element IDs that are candidate neighbors to the query points. Call BVH::findPoints() to get the list of element IDs that the query point intersects. The key idea of findPoints() is that testing for probe intersection with a child node (bounding box) is cheap. If a node intersection test fails (misses), the child node, and all of its corresponding elements, can be skipped during the BVH traversal. If the probe does intersect a child node, the node’s children are also tested for probe intersection. Without the acceleration data structure, each probe point must be tested against each triangle.

void findCandidateBVHTreeBins(BVH2DType* tree,
                              Point2DType ppoint,
                              std::vector<int>& candidates)
{
  axom::IndexType offsets;
  axom::IndexType counts;
  axom::IndexType* candidatesPtr;
  // Get the candidates for a given probe point:
  // BVH::findPoints takes an array of points, and allocates and fills an array
  // for all the candidate intersections with the points in a packed manner.
  tree->findPoints(&offsets, &counts, candidatesPtr, 1, &ppoint);

  // Since we are only querying one point, offsets == 0 and
  // len(candidatesPtr) == counts
  candidates = std::vector<int>(candidatesPtr, candidatesPtr + counts);

  // Deallocate candidates array
  axom::deallocate(candidatesPtr);
}

Note that the returned packed candidate intersection array (candidatesPtr above) needs to be deallocated by the caller.

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]);
    }
  }
}

Device Traversal API

The BVH class contains a getTraverser() method, which returns an object that can be used to traverse a BVH with user-defined actions.

The returned traverser type has one function, traverse_tree(), which takes the following arguments:

• const PointType& p: the query point to traverse the BVH with
• LeafAction&& lf: a function or lambda which is executed on each leaf node of the BVH that is reached during traversal. It should take in two arguments, the index of the leaf node in the BVH, and a pointer to an array mapping leaf node indices to the original index of elements.
• Predicate&& predicate: a function which determines whether to traverse down to a given internal node. It should take in two arguments: the query point, and the tentative node’s bounding box.

This object may be used within a CUDA kernel, so long as the execution space parameter of BVH is set correctly.

This method can be used to avoid the extra memory allocation needed for holding an array of candidate intersections. For example, if we only wish to count the number of intersections for a given query point, our leaf action could get the underlying mesh element based on the element index, check whether the query point intersects it and then increment a per-point counter.

This method also allows uses of the BVH beyond intersection testing. quest::SignedDistance uses the BVH traversal object to search for the closest surface elements to a query point. The leaf action that is used checks each candidate leaf against a current-minimum candidate; if closer, the current-minimum candidate is set to the new surface element. The predicate used for traversal also utilizes the current-minimum candidate data to avoid traversing internal nodes that are farther than the current minimum squared distance.