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 anArborX::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).
BVHis a shorter name for this class.-
using memory_space = MemorySpace¶
-
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.
MemorySpacemust be accessible fromExecutionSpace(i.e.,Kokkos::SpaceAccessibility<ExecutionSpace, MemorySpace>::accessiblemust betrue).A specialization of
AccessTraitsmust matchValuesas the template argument.The return type of
AccessTraits::get()must decay toValue.IndexableGettermust provide anoperator()taking in a type that decays toValueand 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 bool empty() const noexcept¶
- Returns:
trueif the tree has no leaves,falseotherwise.
-
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
callbackon each of them.The second overload stores them in
{values, offsets}.The third overload invokes
callbackon 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,
valuesholds them grouped by predicate andoffsetsholds the position invalueswhere the entries of each predicate start, i.e., the results ofpredicates(i)arevalues(j)foroffsets(i) <= j < offsets(i+1). Following the usual convention,offsets(n) == values.size(), wherenis the number of predicates andvalues.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
valuesof the first entry of each predicate.
The requirements and costs below apply to all the overloads of
query().MemorySpacemust be accessible fromExecutionSpace.A specialization of
AccessTraitsmust matchPredicatesas the template argument. The member typeAccessTraits<Predicates>::memory_spacemust be accessible fromExecutionSpace, and the return type ofAccessTraits::get()must decay to a valid ArborX predicate, such as one generated byintersects()ornearest().Callbackmust be a valid ArborX callback.ValuesandOffsetsmust be (managed) Kokkos views accessible fromExecutionSpace.
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). UseBoundingVolumeHierarchywhen 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;
}