Blender V5.3
blender::KDTreeNew< T > Class Template Reference

#include <BLI_kdtree_new.hh>

Inherits blender::blender::NonMovable, and blender::blender::NonCopyable.

Classes

struct  Nearest

Public Types

using value_type = typename T::base_type

Public Member Functions

int size () const
bool is_empty () const
const T * points () const
Span< int > tree_indices () const
int find_nearest (const T &position, value_type *r_distance_sq=nullptr) const
template<typename Filter>
requires kdtree::FilterFn<Filter>
int find_nearest_filtered (const T &position, Filter &&filter, value_type *r_distance_sq=nullptr) const
int find_nearest_n (const T &position, MutableSpan< Nearest > r_nearest) const
template<typename Fn>
void foreach_in_radius (const T &position, const value_type radius, Fn &&fn) const
int find_in_radius (const T &position, const value_type radius, Vector< Nearest > &r_nearest) const
int count_in_radius (const T &position, const value_type radius) const
template<typename Query>
requires kdtree::QueryType<Query, value_type>
void search (Query &query, const T &position) const

Static Public Attributes

static constexpr int dimensions = T::type_length
static constexpr int LEAF_SIZE_DEFAULT = 32

#KDTreeNew

 KDTreeNew (Span< T > points, int leaf_size=LEAF_SIZE_DEFAULT)
 KDTreeNew (Span< T > points, const IndexMask &mask, int leaf_size=LEAF_SIZE_DEFAULT)
 KDTreeNew (Span< T > points, Span< int > indices, int leaf_size=LEAF_SIZE_DEFAULT)
 KDTreeNew (Span< T > points, LinearAllocator<> &allocator, int leaf_size=LEAF_SIZE_DEFAULT)
 KDTreeNew (Span< T > points, const IndexMask &mask, LinearAllocator<> &allocator, int leaf_size=LEAF_SIZE_DEFAULT)
 KDTreeNew (Span< T > points, Span< int > indices, LinearAllocator<> &allocator, int leaf_size=LEAF_SIZE_DEFAULT)
 ~KDTreeNew ()

Detailed Description

template<typename T>
class blender::KDTreeNew< T >

A KD-tree for nearest neighbor search. References a subset of values in a Span. Results are indices into that span, so data attached to the points can be referenced sparsely with this level of indirection.

Differences from blender::KDTree in BLI_kdtree.hh:

  • The tree references the caller's coordinate array instead of storing a copy of it. The array must stay alive and unchanged for as long as the tree is used.
  • Points are added when the tree is built, there is no separate insert and balance step.
  • Distances are squared, since that's what the searches compute anyway.
  • Results don't include coordinates which are instead found in points with the returned index.
  • Performance and memory usage are much better.

Definition at line 89 of file BLI_kdtree_new.hh.

Member Typedef Documentation

◆ value_type

template<typename T>
using blender::KDTreeNew< T >::value_type = typename T::base_type

Definition at line 91 of file BLI_kdtree_new.hh.

Constructor & Destructor Documentation

◆ KDTreeNew() [1/6]

template<typename T>
blender::KDTreeNew< T >::KDTreeNew ( Span< T > points,
int leaf_size = LEAF_SIZE_DEFAULT )
explicit

Build a tree containing every point in points.

Note
points must outlive the tree.

Definition at line 789 of file kdtree.cc.

References points(), and blender::Span< T >::size().

◆ KDTreeNew() [2/6]

template<typename T>
blender::KDTreeNew< T >::KDTreeNew ( Span< T > points,
const IndexMask & mask,
int leaf_size = LEAF_SIZE_DEFAULT )

Build a tree containing the points selected by mask. Results are still indices into points rather than positions in the mask.

Note
points must outlive the tree, mask does not have to.

Definition at line 800 of file kdtree.cc.

References blender::Span< T >::index_range(), and points().

◆ KDTreeNew() [3/6]

template<typename T>
blender::KDTreeNew< T >::KDTreeNew ( Span< T > points,
Span< int > indices,
int leaf_size = LEAF_SIZE_DEFAULT )

Build a tree containing the points at indices. Results are indices into points, not positions in indices.

Note
points must outlive the tree, indices does not have to.

Definition at line 813 of file kdtree.cc.

References points(), and blender::Span< T >::size().

◆ KDTreeNew() [4/6]

template<typename T>
blender::KDTreeNew< T >::KDTreeNew ( Span< T > points,
LinearAllocator<> & allocator,
int leaf_size = LEAF_SIZE_DEFAULT )

The same constructors reusing an existing LinearAllocator rather. This can be used to avoid heap allocations when building a tree for a small number of points.

Note
allocator must outlive the tree.

Definition at line 758 of file kdtree.cc.

References points(), and blender::Span< T >::size().

◆ KDTreeNew() [5/6]

template<typename T>
blender::KDTreeNew< T >::KDTreeNew ( Span< T > points,
const IndexMask & mask,
LinearAllocator<> & allocator,
int leaf_size = LEAF_SIZE_DEFAULT )

Definition at line 764 of file kdtree.cc.

References blender::Span< T >::index_range(), and points().

◆ KDTreeNew() [6/6]

template<typename T>
blender::KDTreeNew< T >::KDTreeNew ( Span< T > points,
Span< int > indices,
LinearAllocator<> & allocator,
int leaf_size = LEAF_SIZE_DEFAULT )

Definition at line 781 of file kdtree.cc.

References points(), and blender::Span< T >::size().

◆ ~KDTreeNew()

template<typename T>
blender::KDTreeNew< T >::~KDTreeNew ( )

Definition at line 747 of file kdtree.cc.

References blender::MEM_delete_void().

Member Function Documentation

◆ count_in_radius()

template<typename T>
int blender::KDTreeNew< T >::count_in_radius ( const T & position,
const value_type radius ) const

The number of points within radius of position.

Definition at line 584 of file BLI_kdtree_new.hh.

References is_empty(), position, search(), and T.

Referenced by blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), and blender::tests::TEST().

◆ find_in_radius()

template<typename T>
int blender::KDTreeNew< T >::find_in_radius ( const T & position,
const value_type radius,
Vector< Nearest > & r_nearest ) const

Find every point within radius of position.

Parameters
r_nearestCleared, then filled with the results in order of increasing distance. Passing in the same vector for many searches avoids reallocating it every time.
Returns
The number of results.

Definition at line 569 of file BLI_kdtree_new.hh.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), b, blender::Vector< T, InlineBufferCapacity, Allocator >::begin(), blender::Vector< T, InlineBufferCapacity, Allocator >::clear(), blender::Vector< T, InlineBufferCapacity, Allocator >::end(), foreach_in_radius(), position, blender::Vector< T, InlineBufferCapacity, Allocator >::size(), and T.

Referenced by blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), and blender::tests::TEST().

◆ find_nearest()

◆ find_nearest_filtered()

template<typename T>
requires kdtree::FilterFn<Filter>
template<typename Filter>
requires kdtree::FilterFn<Filter>
int blender::KDTreeNew< T >::find_nearest_filtered ( const T & position,
Filter && filter,
value_type * r_distance_sq = nullptr ) const

Find the point closest to position for which filter returns true. Useful to skip the search position itself when finding the neighbors of points that are in the tree.

Note
filter is called for candidate points in an unspecified order.
Returns
The index of the closest accepted point, or -1 if there is none.

Definition at line 529 of file BLI_kdtree_new.hh.

References blender::kdtree::FilteredNearestQuery< ValueT, Filter >::distance_sq(), blender::kdtree::FilteredNearestQuery< ValueT, Filter >::index(), is_empty(), position, search(), and T.

Referenced by blender::nodes::node_geo_index_of_nearest_cc::find_nearest_non_self(), blender::TEST(), blender::TEST(), blender::tests::TEST(), blender::tests::TEST(), and blender::tests::TEST().

◆ find_nearest_n()

template<typename T>
int blender::KDTreeNew< T >::find_nearest_n ( const T & position,
MutableSpan< Nearest > r_nearest ) const

Find the closest points to position, in order of increasing distance.

Parameters
r_nearestFilled with at most r_nearest.size() results.
Returns
The number of results written, which is smaller when the tree has fewer points.

Definition at line 547 of file BLI_kdtree_new.hh.

References blender::kdtree::NearestNQuery< NearestT, ValueT >::count(), is_empty(), blender::MutableSpan< T >::is_empty(), position, search(), and T.

Referenced by blender::geometry::find_curve_neighbors(), blender::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), and blender::tests::TEST().

◆ foreach_in_radius()

template<typename T>
template<typename Fn>
void blender::KDTreeNew< T >::foreach_in_radius ( const T & position,
const value_type radius,
Fn && fn ) const

Call fn for every point within radius of position, in an unspecified order.

Definition at line 559 of file BLI_kdtree_new.hh.

References is_empty(), position, search(), and T.

Referenced by blender::kdtree::calc_duplicates_impl(), find_in_radius(), blender::TEST(), blender::tests::TEST(), and blender::nodes::node_geo_distribute_points_on_faces_cc::update_elimination_mask_for_close_points().

◆ is_empty()

◆ points()

template<typename T>
const T * blender::KDTreeNew< T >::points ( ) const

The coordinates the tree was built from, which every index it returns refers to. Only the start of the array is known, since the tree may cover a subset of it.

Definition at line 503 of file BLI_kdtree_new.hh.

References T.

Referenced by blender::kdtree::calc_duplicates_impl(), KDTreeNew(), KDTreeNew(), KDTreeNew(), KDTreeNew(), KDTreeNew(), and KDTreeNew().

◆ search()

template<typename T>
requires kdtree::QueryType<Query, value_type>
template<typename Query>
requires kdtree::QueryType<Query, value_type>
void blender::KDTreeNew< T >::search ( Query & query,
const T & position ) const

Visit the points that could be closer to position than the query has accepted so far, reporting each of them to it. The query decides what to keep and how far the search still has to look. See #NearestResult and the others beside it.

Definition at line 596 of file BLI_kdtree_new.hh.

References blender::BLI_assert(), dimensions, blender::IndexRange::IndexRange(), is_empty(), position, blender::math::square(), and T.

Referenced by count_in_radius(), find_nearest(), find_nearest_filtered(), find_nearest_n(), and foreach_in_radius().

◆ size()

template<typename T>
int blender::KDTreeNew< T >::size ( ) const

◆ tree_indices()

template<typename T>
Span< int > blender::KDTreeNew< T >::tree_indices ( ) const

The indices of the points in the tree, in the order it stores them. Points close together in space are closer in this order, which can utilized for more optimal cache usage.

Note
The order is deterministic, but it follows from the coordinates and from how the tree is built. It changes when unrelated points move and when the build is tuned, so results that have to stay the same as geometry is edited or animated should not depend on it.

Definition at line 508 of file BLI_kdtree_new.hh.

Referenced by blender::kdtree::calc_duplicates(), and blender::nodes::node_geo_index_of_nearest_cc::IndexOfNearestFieldInput::get_varray_for_context().

Member Data Documentation

◆ dimensions

template<typename T>
int blender::KDTreeNew< T >::dimensions = T::type_length
staticconstexpr

Definition at line 92 of file BLI_kdtree_new.hh.

Referenced by search().

◆ LEAF_SIZE_DEFAULT

template<typename T>
int blender::KDTreeNew< T >::LEAF_SIZE_DEFAULT = 32
staticconstexpr

Indices in a leaf node are searched linearly. Larger values build faster and use less memory whereas smaller values make queries visit fewer points.

32 was measured to be the best tradeoff between build time and memory usage for float3 point clouds, building 1.3-2x faster than a leaf size of 10 and halving the memory the nodes use (6.5 MB vs. 12.6 MB for a million points). See BLI_kdtree_performance_test.

Definition at line 110 of file BLI_kdtree_new.hh.


The documentation for this class was generated from the following files: