BoundingVolumeHierarchy

Defined in header <ArborX_LinearBVH.hpp>

Note

For ArborX 1.x, see ArborX::BoundingVolumeHierarchy (v1).

template<typename MemorySpace, typename Value, typename IndexableGetter = Experimental::DefaultIndexableGetter, typename BoundingVolume = Box<DIM, Coordinate>>
class BoundingVolumeHierarchy

A tree data structure that can be used to accelerate the search for geometrical objects in space.

Template Parameters:
  • MemorySpace – A valid Kokkos memory space, in which the tree resides.

  • Value – The type of the objects stored in the tree.

  • IndexableGetter – A function object extracting an indexable geometry from a Value, see IndexableGetter. The default, Experimental::DefaultIndexableGetter, uses the value itself as the indexable, or the geometry it wraps if the value is an ArborX::PairValueIndex.

  • BoundingVolume – The bounding volume used for the internal nodes. By default, an ArborX::Box with the dimension and the coordinate type of the indexables.

The template arguments may be deduced from the arguments of the constructor (see the example below). BVH is a shorter name for this class.

using memory_space = MemorySpace
using value_type = Value
using size_type = MemorySpace::size_type
using bounding_volume_type = BoundingVolume
BoundingVolumeHierarchy() = default

Construct an empty tree.

template<typename ExecutionSpace, typename Values, typename SpaceFillingCurve = Experimental::Morton64>
BoundingVolumeHierarchy(ExecutionSpace const &space, Values const &values, IndexableGetter const &indexable_getter = IndexableGetter())

Construct a tree from a given data source.

Parameters:
  • space – The execution space in which to build the tree.

  • values – The values to store in the tree.

  • indexable_getter – A function object to transform a value into an indexable.

The following requirements must be satisfied.

  • MemorySpace must be accessible from ExecutionSpace (i.e., Kokkos::SpaceAccessibility<ExecutionSpace, MemorySpace>::accessible must be true).

  • A specialization of AccessTraits must match Values as the template argument.

  • The return type of AccessTraits::get() must decay to Value.

  • IndexableGetter must provide an operator() taking in a type that decays to Value and returning an indexable (geometric object).

The complexity is O(N log N), where N is the number of values passed to the constructor (AccessTraits<Values>::size(values)). Memory allocation with Kokkos may throw.

KOKKOS_FUNCTION size_type size() const noexcept
Returns:

The number of leaves in the tree.

KOKKOS_FUNCTION bool empty() const noexcept
Returns:

true if the tree has no leaves, false otherwise.

KOKKOS_FUNCTION bounding_volume_type bounds() const noexcept
Returns:

A bounding volume containing all leaves stored in the tree, or an invalid bounding volume if the tree is empty.

template<typename ExecutionSpace, typename Predicates, typename Callback>
void query(ExecutionSpace const &space, Predicates const &predicates, Callback const &callback) const
template<typename ExecutionSpace, typename Predicates, typename Values, typename Offsets>
void query(ExecutionSpace const &space, Predicates const &predicates, Values &values, Offsets &offsets) const
template<typename ExecutionSpace, typename Predicates, typename Callback, typename Values, typename Offsets>
void query(ExecutionSpace const &space, Predicates const &predicates, Callback const &callback, Values &values, Offsets &offsets) const

Find the values that satisfy the predicates.

  • The first overload invokes callback on each of them.

  • The second overload stores them in {values, offsets}.

  • The third overload invokes callback on each of them and stores what the callback outputs in {values, offsets}. The callback is an output callback, see Callbacks for how results are stored and for the number of times it may be invoked.

For spatial predicates, the call finds all the values whose indexable meets the predicate. Conceptually, it is equivalent to

for (auto predicate : predicates)
  for (auto value : values)
    if (predicate(indexable_getter(value)))
      callback(predicate, value);

For nearest predicates, the call finds the specified number of the values whose indexables are the nearest to the predicate geometry. Conceptually, it is equivalent to

for (auto predicate : predicates)
  for (auto value : k_nearest_values_of_predicate)
    callback(predicate, value);

When results are stored, values holds them grouped by predicate and offsets holds the position in values where the entries of each predicate start, i.e., the results of predicates(i) are values(j) for offsets(i) <= j < offsets(i+1). Following the usual convention, offsets(n) == values.size(), where n is the number of predicates and values.size() is the total number of results. The views are resized as needed.

Parameters:
  • space – The execution space in which to run the query.

  • predicates – The predicates to check against the values.

  • callback – A function object invoked when a value satisfies a predicate.

  • values – The values that satisfy the predicates or, if a callback is passed, the entries it outputs.

  • offsets – The position in values of the first entry of each predicate.

The requirements and costs below apply to all the overloads of query().

  • MemorySpace must be accessible from ExecutionSpace.

  • A specialization of AccessTraits must match Predicates as the template argument. The member type AccessTraits<Predicates>::memory_space must be accessible from ExecutionSpace, and the return type of AccessTraits::get() must decay to a valid ArborX predicate, such as one generated by intersects() or nearest().

  • Callback must be a valid ArborX callback.

  • Values and Offsets must be (managed) Kokkos views accessible from ExecutionSpace.

The complexity is O(M log N), where M is the number of predicates (AccessTraits<Predicates>::size(predicates)) and N is the number of values stored in the tree (size()). Memory allocation with Kokkos may throw.

template<typename MemorySpace, typename Value, typename IndexableGetter = Experimental::DefaultIndexableGetter, typename BoundingVolume = Box<DIM, Coordinate>>
using BVH = BoundingVolumeHierarchy<MemorySpace, Value, IndexableGetter, BoundingVolume>

A convenience alias for BoundingVolumeHierarchy, for brevity. The two names are interchangeable, except that the template arguments cannot be deduced through the alias with compilers that do not support class template argument deduction for alias templates (a C++20 feature, which older compilers lack). Use BoundingVolumeHierarchy when relying on deduction.

Deduction guides

The MemorySpace and Value template arguments are deduced from the Values passed to the constructor through AccessTraits: MemorySpace is AccessTraits<Values>::memory_space and Value is the type returned by AccessTraits::get(), without cv-qualifiers and reference.

template<typename Values>
using access_traits_value_t = std::remove_cvref_t<decltype(AccessTraits<Values>::get(std::declval<Values const&>(), 0))>

Exposition only: the type of the values provided by AccessTraits<Values>.

template<typename ExecutionSpace, typename Values>
BoundingVolumeHierarchy(ExecutionSpace, Values) -> BoundingVolumeHierarchy<typename AccessTraits<Values>::memory_space, access_traits_value_t<Values>>
template<typename ExecutionSpace, typename Values, typename IndexableGetter>
BoundingVolumeHierarchy(ExecutionSpace, Values, IndexableGetter) -> BoundingVolumeHierarchy<typename AccessTraits<Values>::memory_space, access_traits_value_t<Values>, IndexableGetter>

The first guide uses the default IndexableGetter.

Example

The example below builds a tree over four boxes and searches for the ones that intersect three points.

#include <ArborX.hpp>

#include <Kokkos_Core.hpp>

#include <iostream>

int main(int argc, char *argv[])
{
  Kokkos::ScopeGuard guard(argc, argv);

  using ExecutionSpace = Kokkos::DefaultExecutionSpace;
  using MemorySpace = ExecutionSpace::memory_space;

  using Box = ArborX::Box<2>;
  using Point = ArborX::Point<2>;

  Kokkos::View<Box *, MemorySpace> boxes("Example::boxes", 4);
  auto boxes_host = Kokkos::create_mirror_view(boxes);
  boxes_host[0] = {{0, 0}, {1, 1}};
  boxes_host[1] = {{1, 0}, {2, 1}};
  boxes_host[2] = {{0, 1}, {1, 2}};
  boxes_host[3] = {{1, 1}, {2, 2}};
  Kokkos::deep_copy(boxes, boxes_host);

  // -----------
  // |    | 1  |
  // |    |  0 |
  // |----2----|
  // |    |    |
  // |    |    |
  // -----------
  Kokkos::View<decltype(ArborX::intersects(Point{})) *, MemorySpace> queries(
      "Example::queries", 3);
  auto queries_host = Kokkos::create_mirror_view(queries);
  queries_host[0] = ArborX::intersects(Point{1.8, 1.5});
  queries_host[1] = ArborX::intersects(Point{1.3, 1.7});
  queries_host[2] = ArborX::intersects(Point{1, 1});
  Kokkos::deep_copy(queries, queries_host);

  ExecutionSpace space;

  ArborX::BoundingVolumeHierarchy const tree(
      space, ArborX::Experimental::attach_indices(boxes));

  // The query will resize values and offsets accordingly
  Kokkos::View<typename decltype(tree)::value_type *, MemorySpace> values(
      "Example::values", 0);
  Kokkos::View<int *, MemorySpace> offsets("Example::offsets", 0);
  tree.query(space, queries, values, offsets);

  auto offsets_host =
      Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace{}, offsets);
  auto values_host =
      Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace{}, values);

  // Expected output:
  //   offsets: 0 1 2 6
  //   indices: 3 3 0 2 1 3
  // The order of the last 4 indices may vary.
  std::cout << "offsets: ";
  std::copy(offsets_host.data(), offsets_host.data() + offsets.size(),
            std::ostream_iterator<int>(std::cout, " "));
  std::cout << "\nindices:";
  std::transform(values_host.data(), values_host.data() + values.size(),
                 std::ostream_iterator<int>(std::cout, " "),
                 [](auto value) { return value.index; });

  return 0;
}

See also