New spatial query to find elements intersecting a Ray

[kennyweiss]

A user has requested a new spatial query to find a set of candidate elements from a mesh whose BoundingBoxes intersect a given Ray.

Request Details

• The input is a mesh containing a custom type of high order elements.
• They do not require us to develop a representation for this element type.
• They are able to provide the bounding box of each element
• They are also able to compute the exact intersection of a ray with one of their elements
• They are looking for us to provide a simple API that allows them to
  • build a spatial index over a collection of element bounding boxes
  • pose a query to the index that finds the indices of the elements whose bounding boxes intersect a given ray.
• For the purposes of this query, we can assume that the entire mesh is resident on a single rank. I.e. we do not need to worry about MPI communications.

Available functionality

• The spin component provides several spatial indices that can be built over a collection of axis-aligned bounding boxes. E.g. BVH tree, ImplicitGrid, ...
• primal already has an algorithm to determine if a Ray intersects an axis-aligned BoundingBox https://github.com/LLNL/axom/blob/975fc516e6b4dfd4bb82f9c8495db90a7150f8fc/src/axom/primal/operators/intersect.hpp#L77-L88

Missing functionality

• We do not currently have the capability to traverse a spatial index to find the set of candidate elements that intersect a Ray. This will have to be implemented to satisfy this request.
• We will also need a simple API for them to construct and query the spatial index. This should be similar to our quest_inout and quest_signed_distance API

[gzagaris]

@kennyweiss, since we do not get have access to the "custom high order mesh", it would be cleaner if they just use our spatial acceleration data-structures to prune their search, which takes the supplied bounding boxes, which they will be computing.

As I mentioned earlier, I am planning to do this for the BVH, which is also needed for the probe package.

[kennyweiss]

Thanks @gzagaris -- that is exactly what I had in mind.
I think the BVH will be a great fit for their needs.

So, are you claiming this ticket?

[kennyweiss]

@rhornung67 -- the bulk of this issue was resolved in #177 (~March 2020).

Based on the comments there, we kept this issue open in case we needed a Fortran interface for the Ray-BBox intersection query. Since this hasn't been requested since then, I'm closing this issue. We can create a new issue if needed.