|
Blender V5.3
|
#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 () | |
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:
Definition at line 89 of file BLI_kdtree_new.hh.
| using blender::KDTreeNew< T >::value_type = typename T::base_type |
Definition at line 91 of file BLI_kdtree_new.hh.
|
explicit |
Build a tree containing every point in points.
Definition at line 789 of file kdtree.cc.
References points(), and blender::Span< T >::size().
| 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.
Definition at line 800 of file kdtree.cc.
References blender::Span< T >::index_range(), and points().
| 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.
Definition at line 813 of file kdtree.cc.
References points(), and blender::Span< T >::size().
| 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.
Definition at line 758 of file kdtree.cc.
References points(), and blender::Span< T >::size().
| 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().
| 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().
| blender::KDTreeNew< T >::~KDTreeNew | ( | ) |
Definition at line 747 of file kdtree.cc.
References blender::MEM_delete_void().
| 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().
| 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.
| r_nearest | Cleared, then filled with the results in order of increasing distance. Passing in the same vector for many searches avoids reallocating it every time. |
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().
| int blender::KDTreeNew< T >::find_nearest | ( | const T & | position, |
| value_type * | r_distance_sq = nullptr ) const |
Find the point closest to position.
Definition at line 514 of file BLI_kdtree_new.hh.
References blender::kdtree::NearestQuery< ValueT >::distance_sq(), blender::kdtree::NearestQuery< ValueT >::index(), is_empty(), position, search(), and T.
Referenced by blender::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), and blender::tests::TEST().
| 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.
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().
| 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.
| r_nearest | Filled with at most r_nearest.size() results. |
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().
| 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().
| bool blender::KDTreeNew< T >::is_empty | ( | ) | const |
Definition at line 498 of file BLI_kdtree_new.hh.
Referenced by count_in_radius(), find_nearest(), find_nearest_filtered(), find_nearest_n(), foreach_in_radius(), search(), blender::tests::TEST(), and blender::tests::TEST().
| 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().
| 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().
| int blender::KDTreeNew< T >::size | ( | ) | const |
The number of points, which may be less than the size of points for a masked tree.
Definition at line 493 of file BLI_kdtree_new.hh.
Referenced by blender::kdtree::calc_duplicates(), blender::kdtree::calc_duplicates(), blender::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), and blender::tests::TEST().
| 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.
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().
|
staticconstexpr |
Definition at line 92 of file BLI_kdtree_new.hh.
Referenced by search().
|
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.