Callbacks¶
A callback is a user-provided function object that a spatial index query()
invokes, from the device, every time a value stored in the index satisfies a
predicate.
It lets you process results on the fly instead of (or in addition to) storing
them, for example to apply a filter, to compute a reduction without
materializing the results, or to transform the stored values.
ArborX does not provide a type for callbacks. Any copyable function object (including a lambda) with a matching call operator is a valid callback. This page documents the requirements on such an object.
Note
For ArborX 1.x, callbacks received the index of the primitive as an int
instead of the stored value. See the migration guide.
Callback forms¶
There are two forms, selected by the query() overload the callback is
passed to.
Form |
Call operator |
Used by |
|---|---|---|
|
|
|
|
|
In both forms,
Predicateis the type of the predicates returned byAccessTraits<Predicates>::get()after decay (e.g., whatintersects()ornearest()returns).Valueis theValuetemplate argument of the spatial index.The call operator is invoked through a
constreference, so it must beconst.The call operator is invoked from the device, so it must be marked with
KOKKOS_FUNCTION.
Note
For an index built with ArborX::Experimental::attach_indices(), the
stored value is an ArborX::PairValueIndex: the geometry is available as
value.value and its position in the input as value.index.
The examples below use it.
Visiting callback¶
KOKKOS_FUNCTION void operator()(Predicate const &predicate, Value const &value) const;
KOKKOS_FUNCTION ArborX::CallbackTreeTraversalControl
operator()(Predicate const &predicate, Value const &value) const;
Invoked once per (predicate, value) pair that satisfies the predicate (for
nearest predicates, once per each of the k nearest values).
Nothing is stored by query(): the callback is the only consumer of the
results.
The return type must be
void, orCallbackTreeTraversalControl(spatial predicates only), to hint that the search for the current predicate may stop early. See Early exit.
The return type of a callback used with a nearest predicate must be void.
Output callback¶
template <typename OutputFunctor>
KOKKOS_FUNCTION void operator()(Predicate const &predicate, Value const &value,
OutputFunctor const &out) const;
Invoked for every (predicate, value) pair that satisfies the predicate.
Results are stored by calling out(x), where x is convertible to the
value type of the values view passed to query().
The callback decides what is stored: out may be called any number of times,
including zero (to discard the result) or more than once (to emit several
entries per result).
The stored entries are grouped by predicate, and offsets records where the
entries of each predicate start, as for the {values, offsets} overload
without a callback.
Warning
The callback may be invoked more than once for the same (predicate, value) pair.
Because the size of the output is not known beforehand, query() may
traverse the index twice: a first pass that only counts how many times
out is called for each predicate, and a second pass that invokes the
callback again to write the entries at the right location.
For spatial predicates, this is the default.
The second pass is skipped only if a buffer size was provided through
ArborX::Experimental::TraversalPolicy and was large enough to hold all
the entries.
For nearest predicates, query() preallocates room for k entries per
predicate and needs a second pass only if the callback calls out more
times than that.
The callback must therefore
call
outthe same number of times for the same (predicate, value) pair in every invocation, andnot rely on side effects (counters, printing, etc.) happening exactly once per result.
The number of calls and their order across threads are otherwise unspecified. The entries of a given predicate may be stored in any order.
OutputFunctor is an unspecified type, so the call operator must be a
template (or a generic lambda) on that argument.
The return type must be void.
The overload of query() without a callback behaves as if it were passed the
callback
struct DefaultCallback
{
template <typename Predicate, typename Value, typename OutputFunctor>
KOKKOS_FUNCTION void operator()(Predicate const &, Value const &value,
OutputFunctor const &out) const
{
out(value);
}
};
Early exit¶
-
enum class CallbackTreeTraversalControl¶
Returned by a visiting callback for a spatial predicate to control the traversal of the index.
-
enumerator normal_continuation¶
Continue the search for the current predicate. This is the behavior of a callback that returns
void.
-
enumerator early_exit¶
Hint that the search for the current predicate may stop. The search for other predicates is not affected.
-
enumerator normal_continuation¶
Early exit is useful when only some of the results are needed, for example to find any (rather than all) value intersecting a region.
Warning
early_exit is a hint, not a guarantee.
The callback may still be invoked for the same predicate after it has
returned early_exit, possibly with other values and possibly
concurrently from several threads.
Whether the hint is honored depends on the spatial index.
ArborX::BoundingVolumeHierarchy currently stops the traversal of a
predicate as soon as its callback returns early_exit.
ArborX::BruteForce ignores it, as checking it would require
synchronization between the threads working on the same predicate.
A callback must therefore be correct if it keeps being invoked, and must not assume that it sees a single value per predicate.
Compile-time checks¶
query() diagnoses an invalid callback with a static_assert:
Callback 'operator()' does not have the correct signature: the callback cannot be invoked with the arguments of the corresponding form above.Callback 'operator()' return type must be void(orvoid or ArborX::CallbackTreeTraversalControlfor a visiting callback with a spatial predicate).With NVCC,
__host__ __device__ extended lambdas cannot be generic lambdas: aKOKKOS_LAMBDAcannot haveautoparameters when compiling with CUDA. Use a function object with a templated call operator instead.
Examples¶
Store the index of every value found (output callback):
struct StoreIndex
{
template <typename Predicate, typename Value, typename OutputFunctor>
KOKKOS_FUNCTION void operator()(Predicate const &, Value const &value,
OutputFunctor const &out) const
{
out(value.index);
}
};
Kokkos::View<int*, MemorySpace> values("Example::values", 0);
Kokkos::View<int*, MemorySpace> offsets("Example::offsets", 0);
bvh.query(space, predicates, StoreIndex{}, values, offsets);
Keep only the values on one side of a plane (output callback with a filter):
struct KeepPositiveX
{
template <typename Predicate, typename OutputFunctor>
KOKKOS_FUNCTION void
operator()(Predicate const &,
ArborX::PairValueIndex<ArborX::Point<3>, int> const &value,
OutputFunctor const &out) const
{
if (value.value[0] > 0)
out(value.index);
}
};
Count the results of a spatial query without storing them (visiting callback):
Kokkos::View<int, ExecutionSpace, Kokkos::MemoryTraits<Kokkos::Atomic>>
counter("Example::counter");
bvh.query(
space, predicates,
KOKKOS_LAMBDA(auto /*predicate*/, auto /*value*/) { ++counter(); });
Record one value found for each predicate (early exit):
struct FindAny
{
// initialized to std::numeric_limits<int>::max()
Kokkos::View<int*, MemorySpace> found;
template <typename Predicate, typename Value>
KOKKOS_FUNCTION auto operator()(Predicate const &predicate,
Value const &value) const
{
// the predicates were generated with ArborX::attach(predicate, i)
int const i = ArborX::getData(predicate);
Kokkos::atomic_min(&found(i), value.index);
return ArborX::CallbackTreeTraversalControl::early_exit;
}
};
Each predicate carries its own position i (see ArborX::attach()) so that
it writes to its own entry of found.
The update is atomic because the callback may be invoked concurrently for the
same predicate and may be invoked again after returning early_exit.
Which of the values intersecting the predicate ends up in found(i) is
unspecified.
A complete program is available in examples/callback/example_callback.cpp:
#include <ArborX.hpp>
#include <Kokkos_Core.hpp>
#include <iostream>
#include <random>
#include <vector>
using ExecutionSpace = Kokkos::DefaultExecutionSpace;
using MemorySpace = ExecutionSpace::memory_space;
struct FirstOctant
{};
struct NearestToOrigin
{
int k;
};
template <>
struct ArborX::AccessTraits<FirstOctant>
{
static KOKKOS_FUNCTION std::size_t size(FirstOctant) { return 1; }
static KOKKOS_FUNCTION auto get(FirstOctant, std::size_t)
{
return ArborX::intersects(ArborX::Box<3>{{0.f, 0.f, 0.f}, {1.f, 1.f, 1.f}});
}
using memory_space = MemorySpace;
};
template <>
struct ArborX::AccessTraits<NearestToOrigin>
{
static KOKKOS_FUNCTION std::size_t size(NearestToOrigin) { return 1; }
static KOKKOS_FUNCTION auto get(NearestToOrigin d, std::size_t)
{
return ArborX::nearest(ArborX::Point{0.f, 0.f, 0.f}, d.k);
}
using memory_space = MemorySpace;
};
struct PrintfCallback
{
template <typename Predicate, typename Value, typename OutputFunctor>
KOKKOS_FUNCTION void operator()(Predicate, Value const &value,
OutputFunctor const &out) const
{
auto const index = value.index;
Kokkos::printf("Found %d from functor\n", index);
out(index);
}
};
int main(int argc, char *argv[])
{
Kokkos::ScopeGuard guard(argc, argv);
using Point = ArborX::Point<3>;
int const n = 100;
std::vector<Point> points;
// Fill vector with random points in [-1, 1]^3
std::uniform_real_distribution<float> dis{-1., 1.};
std::default_random_engine gen;
auto rd = [&]() { return dis(gen); };
std::generate_n(std::back_inserter(points), n, [&]() {
return Point{rd(), rd(), rd()};
});
ArborX::BoundingVolumeHierarchy bvh{
ExecutionSpace{},
ArborX::Experimental::attach_indices(Kokkos::create_mirror_view_and_copy(
MemorySpace{},
Kokkos::View<Point *, Kokkos::HostSpace, Kokkos::MemoryUnmanaged>(
points.data(), points.size())))};
{
Kokkos::View<int *, MemorySpace> values("Example::values", 0);
Kokkos::View<int *, MemorySpace> offsets("Example::offsets", 0);
ArborX::query(bvh, ExecutionSpace{}, FirstOctant{}, PrintfCallback{},
values, offsets);
#ifndef __NVCC__
ArborX::query(
bvh, ExecutionSpace{}, FirstOctant{},
KOKKOS_LAMBDA(auto /*predicate*/, auto value, auto /*output_functor*/) {
Kokkos::printf("Found %d from generic lambda\n", value.index);
},
values, offsets);
#endif
}
{
int const k = 10;
Kokkos::View<int *, MemorySpace> values("Example::values", 0);
Kokkos::View<int *, MemorySpace> offsets("Example::offsets", 0);
ArborX::query(bvh, ExecutionSpace{}, NearestToOrigin{k}, PrintfCallback{},
values, offsets);
#ifndef __NVCC__
ArborX::query(
bvh, ExecutionSpace{}, NearestToOrigin{k},
KOKKOS_LAMBDA(auto /*predicate*/, auto value, auto /*output_functor*/) {
Kokkos::printf("Found %d from generic lambda\n", value.index);
},
values, offsets);
#endif
}
{
// EXPERIMENTAL
Kokkos::View<int, ExecutionSpace, Kokkos::MemoryTraits<Kokkos::Atomic>> c(
"counter");
#ifndef __NVCC__
bvh.query(
ExecutionSpace{}, FirstOctant{},
KOKKOS_LAMBDA(auto /*predicate*/, auto value) {
Kokkos::printf("%d %d %d\n", ++c(), -1, value.index);
});
#endif
}
return 0;
}