26template<
typename ValueT>
struct Node {
51template<
typename Filter>
58template<
typename Query,
typename ValueT>
59concept QueryType =
requires(Query &query,
const ValueT distance_sq,
const int index) {
63 } -> std::convertible_to<bool>;
66 query.add_point(distance_sq,
index)
67 } -> std::convertible_to<bool>;
70 query.max_distance_sq()
71 } -> std::convertible_to<ValueT>;
120 const T *points_ =
nullptr;
125 const int *tree_indices_ =
nullptr;
128 Node *root_ =
nullptr;
135 void *owned_buffer_ =
nullptr;
143 static LinearAllocator<> &make_allocator(
int points_num,
int leaf_size,
void *&r_owned);
218 template<
typename Filter>
222 requires
kdtree::FilterFn<Filter>;
232 template<typename Fn>
251 template<typename Query>
272 template<typename Query>
273 bool search_node(Query &query,
287 ValueT distance_sq_ = std::numeric_limits<ValueT>::max();
319 ValueT distance_sq_ = std::numeric_limits<ValueT>::max();
337 if (filter_(
index)) {
369 const int capacity = int(nearest_.size());
371 for (i = count_; i > 0; i--) {
372 if (nearest_[i - 1].distance_sq <= distance_sq) {
376 nearest_[i] = nearest_[i - 1];
380 nearest_[i] = {
index, distance_sq};
390 if (count_ <
int(nearest_.size())) {
391 return std::numeric_limits<ValueT>::max();
393 return nearest_[count_ - 1].distance_sq;
420 fn_(
index, distance_sq);
432template<
typename Query,
typename ValueT>
433inline bool keep_distance(
const ValueT distance_sq,
const ValueT max_distance_sq)
435 if constexpr (Query::inclusive) {
436 return distance_sq <= max_distance_sq;
439 return distance_sq < max_distance_sq;
467 typename T::base_type range,
472 typename T::base_type range,
485 const typename T::base_type range,
521 if (query.
index() != -1 && r_distance_sq) {
524 return query.
index();
528template<
typename Filter>
538 std::forward<Filter>(
filter));
540 if (query.
index() != -1 && r_distance_sq) {
543 return query.
index();
554 return query.
count();
578 return a.distance_sq < b.distance_sq || (a.distance_sq == b.distance_sq && a.index < b.index);
580 return int(r_nearest.
size());
591 return query.count();
595template<
typename Query>
605 if (
position[dim] < bounds_.min[dim]) {
608 else if (
position[dim] > bounds_.max[dim]) {
611 distance_sq += offsets[dim];
613 this->search_node(query,
position, root_, distance_sq, offsets);
617template<
typename Query>
618bool KDTreeNew<T>::search_node(Query &query,
625 if (
node->children ==
nullptr) {
626 const int *indices = tree_indices_;
628 for (
int i =
node->leaf.start; i < node->leaf.end; i++) {
629 const int index = indices[i];
632 if (!query.add_point(point_distance_sq,
index)) {
643 const Node *low_child = &
node->children[0];
644 const Node *high_child = &
node->children[1];
648 const int dim =
node->dim;
656 const Node *far_child;
658 if ((to_low + to_high) < 0) {
659 if (!this->search_node(query,
position, low_child, distance_sq, offsets)) {
662 far_child = high_child;
666 if (!this->search_node(query,
position, high_child, distance_sq, offsets)) {
669 far_child = low_child;
675 const value_type far_distance_sq = distance_sq + far_offset - previous;
679 offsets[dim] = far_offset;
680 const bool keep_searching = this->search_node(
681 query,
position, far_child, far_distance_sq, offsets);
682 offsets[dim] = previous;
683 return keep_searching;
constexpr IndexRange()=default
KDTreeNew(Span< T > points, const IndexMask &mask, LinearAllocator<> &allocator, int leaf_size=LEAF_SIZE_DEFAULT)
int find_in_radius(const float3 &position, const value_type radius, Vector< Nearest > &r_nearest) const
void foreach_in_radius(const float3 &position, const value_type radius, Fn &&fn) const
int find_nearest(const T &position, value_type *r_distance_sq=nullptr) const
KDTreeNew(Span< T > points, LinearAllocator<> &allocator, int leaf_size=LEAF_SIZE_DEFAULT)
KDTreeNew(Span< T > points, Span< int > indices, int leaf_size=LEAF_SIZE_DEFAULT)
int count_in_radius(const float3 &position, const value_type radius) const
KDTreeNew(Span< T > points, Span< int > indices, LinearAllocator<> &allocator, int leaf_size=LEAF_SIZE_DEFAULT)
Span< int > tree_indices() const
int find_nearest_filtered(const T &position, Filter &&filter, value_type *r_distance_sq=nullptr) const
KDTreeNew(Span< T > points, const IndexMask &mask, int leaf_size=LEAF_SIZE_DEFAULT)
static constexpr int LEAF_SIZE_DEFAULT
const float3 * points() const
int find_nearest_n(const float3 &position, MutableSpan< Nearest > r_nearest) const
typename T::base_type value_type
static constexpr int dimensions
void search(Query &query, const float3 &position) const
KDTreeNew(Span< T > points, int leaf_size=LEAF_SIZE_DEFAULT)
constexpr bool is_empty() const
void append(const T &value)
NonCopyable(const NonCopyable &other)=delete
NonMovable(NonMovable &&other)=delete
static constexpr bool inclusive
FilteredNearestQuery(Filter filter)
ValueT distance_sq() const
ValueT max_distance_sq() const
bool add_point(const ValueT distance_sq, const int index)
NearestNQuery(MutableSpan< NearestT > nearest)
ValueT max_distance_sq() const
static constexpr bool inclusive
bool add_point(const ValueT distance_sq, const int index)
bool add_point(const ValueT distance_sq, const int index)
ValueT distance_sq() const
static constexpr bool inclusive
ValueT max_distance_sq() const
bool add_point(const ValueT distance_sq, const int index)
ValueT max_distance_sq() const
static constexpr bool inclusive
RadiusQuery(const ValueT radius_sq, Fn fn)
int calc_duplicates(const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
bool keep_distance(const ValueT distance_sq, const ValueT max_distance_sq)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
struct blender::kdtree::Node::@136202335367076324045241233256012145133315376374::@052000000061374247324310024311347011327123106314 leaf
struct blender::kdtree::Node::@136202335367076324045241233256012145133315376374::@006376166267370336061007055145172370271056263274 split