Blender V5.3
blender::kdtree Namespace Reference

Classes

struct  Node
class  NearestQuery
class  FilteredNearestQuery
class  NearestNQuery
class  RadiusQuery

Concepts

concept  FilterFn
concept  QueryType

Functions

template<typename Query, typename ValueT>
bool keep_distance (const ValueT distance_sq, const ValueT max_distance_sq)
template<typename T>
int calc_duplicates (const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
template<typename T>
int calc_duplicates (const KDTreeNew< T > &tree, typename T::base_type range, const IndexMask &visit_order, MutableSpan< int > duplicates)
template<typename T>
int calc_duplicates (const KDTreeNew< T > &tree, const typename T::base_type range, const MutableSpan< int > duplicates)
template<typename T, typename ForeachFn>
static int calc_duplicates_impl (const KDTreeNew< T > &tree, const typename T::base_type range, const MutableSpan< int > duplicates, const ForeachFn foreach_index)
template int calc_duplicates (const KDTreeNew< float2 > &, float, Span< int >, MutableSpan< int >)
template int calc_duplicates (const KDTreeNew< float3 > &, float, Span< int >, MutableSpan< int >)
template int calc_duplicates (const KDTreeNew< float2 > &, float, const IndexMask &, MutableSpan< int >)
template int calc_duplicates (const KDTreeNew< float3 > &, float, const IndexMask &, MutableSpan< int >)

Function Documentation

◆ calc_duplicates() [1/7]

template int blender::kdtree::calc_duplicates ( const KDTreeNew< float2 > & ,
float ,
const IndexMask & ,
MutableSpan< int >  )

References calc_duplicates().

◆ calc_duplicates() [2/7]

template int blender::kdtree::calc_duplicates ( const KDTreeNew< float2 > & ,
float ,
Span< int > ,
MutableSpan< int >  )

References calc_duplicates().

◆ calc_duplicates() [3/7]

template int blender::kdtree::calc_duplicates ( const KDTreeNew< float3 > & ,
float ,
const IndexMask & ,
MutableSpan< int >  )

References calc_duplicates().

◆ calc_duplicates() [4/7]

template int blender::kdtree::calc_duplicates ( const KDTreeNew< float3 > & ,
float ,
Span< int > ,
MutableSpan< int >  )

References calc_duplicates().

◆ calc_duplicates() [5/7]

template<typename T>
int blender::kdtree::calc_duplicates ( const KDTreeNew< T > & tree,
const typename T::base_type range,
const MutableSpan< int > duplicates )
inline

calc_duplicates visiting the points in the order the tree stores them, measured to be roughly 1.1x to 1.8x faster than providing a separate visit order as the point count increases to ~ 1 million, though that depends on the spatial contiguity of the original point order. The downside is that this ties the result to the internal layout, so it is only meant for callers that don't care which point of a cluster the others merge into. See #KDTreeNew::indices.

Definition at line 484 of file BLI_kdtree_new.hh.

References calc_duplicates(), and blender::KDTreeNew< T >::tree_indices().

◆ calc_duplicates() [6/7]

template<typename T>
int blender::kdtree::calc_duplicates ( const KDTreeNew< T > & tree,
typename T::base_type range,
const IndexMask & visit_order,
MutableSpan< int > duplicates )

◆ calc_duplicates() [7/7]

template<typename T>
int blender::kdtree::calc_duplicates ( const KDTreeNew< T > & tree,
typename T::base_type range,
Span< int > visit_order,
MutableSpan< int > duplicates )

Group points that are within range of each other, favoring speed over quality: each point is merged into the first point that claims it rather than into its closest neighbor. Points are visited in visit_order, which must contain every point in the tree.

Which point of a cluster the others merge into follows from that order alone, since a point claims every unclaimed point in range of it whatever order the search finds them in. Visiting them in a fixed order, their index order for example, therefore keeps the result from depending on the tree's layout and so on where the points are.

Parameters
duplicatesIndexed by point index, so it must be large enough for the largest index in the tree. Points with a value of -1 are candidates to be merged into another point. Presetting a point to its own index keeps it from being merged into anything, though it can still become the target other points merge into. When the function returns, a merged point holds the index of the point it was merged into, and a point that others were merged into holds its own index. Points that are neither are left at -1.
Returns
The number of points that were merged into another point.
Note
Merging is a single step: a point is never merged into a point that is itself merged into a third point.

Definition at line 867 of file kdtree.cc.

References blender::BLI_assert(), calc_duplicates(), calc_duplicates_impl(), blender::KDTreeNew< T >::size(), and blender::Span< T >::size().

Referenced by calc_duplicates(), calc_duplicates(), calc_duplicates(), calc_duplicates(), calc_duplicates(), calc_duplicates(), calc_duplicates(), blender::nodes::node_geo_cluster_by_distance_cc::ClusterByDistanceFieldInput::get_varray_for_context(), blender::geometry::mesh_merge_by_distance_all(), blender::geometry::point_merge_by_distance(), blender::TEST(), blender::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().

◆ calc_duplicates_impl()

template<typename T, typename ForeachFn>
int blender::kdtree::calc_duplicates_impl ( const KDTreeNew< T > & tree,
const typename T::base_type range,
const MutableSpan< int > duplicates,
const ForeachFn foreach_index )
static

◆ keep_distance()

template<typename Query, typename ValueT>
bool blender::kdtree::keep_distance ( const ValueT distance_sq,
const ValueT max_distance_sq )
inline

Whether a distance is close enough for Query to still be interested in it.

Definition at line 433 of file BLI_kdtree_new.hh.

References keep_distance().

Referenced by keep_distance().