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

Visiting callback

(Predicate, Value)

query(space, predicates, callback)

Output callback

(Predicate, Value, OutputFunctor)

query(space, predicates, callback, values, offsets)

In both forms,

  • Predicate is the type of the predicates returned by AccessTraits<Predicates>::get() after decay (e.g., what intersects() or nearest() returns).

  • Value is the Value template argument of the spatial index.

  • The call operator is invoked through a const reference, so it must be const.

  • 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

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 out the same number of times for the same (predicate, value) pair in every invocation, and

  • not 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.

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 (or void or ArborX::CallbackTreeTraversalControl for a visiting callback with a spatial predicate).

  • With NVCC, __host__ __device__ extended lambdas cannot be generic lambdas: a KOKKOS_LAMBDA cannot have auto parameters 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;
}

See also