How to implement a nearest neighbor search with cutoff distance?

[overfelt]

I am using ArborX for a distance-to-surface calculation with cutoff. The basic algorithm is:

1. Box every facet of the curved surface.
2. For every point in the volume, use ArborX to find the nearest N surface boxes. (N small, less than 10)
3. Determine the actual shortest distance from the volume point to nearest N surface facets.
4. If the distance from (3) is larger than the cutoff, set the distance to some special value, e.g. numeric_limits<>::max()

I would like to optimize this by pushing the cutoff distance into the nearest neighbor search but I'm not sure of the mix of Predicate and Callback for an optimal algorithm. Optimal given that (1) For points in the volume that are close to the surface, there are a great many facets within the cutoff distance of the point, hence the nearest neighbor search. (2) When distributed over a large number of MPI ranks, there will be many ranks with all nodes beyond the cutoff distance from the surface, hence no need for a nearest neighbor search.

Suggestions as to which examples/tests to copy and modify would be helpful. Or maybe this is trivial and I just don't see it.
Thanks,
@overfelt

[dalg24]

You could do something like

struct Callback {
  template <class Predicate, class OutputFunctor>
  KOKKOS_FUNCTION void operator()(Predicate predicate, int primitive_index,
                                  OutputFunctor const &out) const
  {
    // compute distance and attach other quantities of interest
    auto const distance_and_other_qoi = compute_actual_distance_to_facet(predicate, primitive_index);
    // insert in the result "vector" (you may want to do conditional insertion
    // if you don't care about the value when distance exceeds the cutoff)
    out(distance_and_other_qoi);  
  }
};


using Value = /* whatever "distance_and_other_qoi" is above */
Kokkos::View<Value*> values("values", 0);
Kokkos::View<int*> offsets("offsets", 0);
bvh.query(execution_space, predicates, callback, values, offsets);

[aprokop]

The way the problem is formulated seems to be a workaround for the current ArborX limitation of not providing exact distance. I think the problem may be reformulated as finding the closest distance from a point to surface facets, and set it to some number if it's over a threshold.

In general, I think using either the original approach, or the approach suggested by @dalg24 may still lead to erroneous results, as there is no guarantee that the nearest N boxes will contain the nearest surface facet.

I think this is another candidate to using the #675. There is also an additional limitation of the nearest callback in the distributed setting, though.