Blender V5.3
BLI_kdtree.hh File Reference

A KD-tree for nearest neighbor search. More...

#include "MEM_guardedalloc.h"
#include "BLI_array.hh"
#include "BLI_kdtree_types.hh"
#include "BLI_math_base_c.hh"
#include "BLI_math_vector.hh"
#include "BLI_stack.hh"
#include "BLI_vector.hh"
#include "PRF_profile.hh"
#include <algorithm>

Go to the source code of this file.

Classes

struct  blender::detail::DeDuplicateParams< CoordT >

Namespaces

namespace  blender
 BMesh Iterators.
namespace  blender::detail

Functions

template<typename CoordT>
KDTreeCoordTraits< CoordT >::ValueType blender::detail::axis_get (const CoordT &co, uint axis)
template<typename CoordT>
KDTreeCoordTraits< CoordT >::ValueType blender::detail::distance_squared (const CoordT &a, const CoordT &b)
template<>
float blender::detail::distance_squared< float > (const float &a, const float &b)
template<typename CoordT>
KDTree< CoordT > * blender::kdtree_new (uint nodes_len_capacity)
template<typename CoordT>
void blender::kdtree_free (KDTree< CoordT > *tree)
template<typename CoordT>
void blender::kdtree_insert (KDTree< CoordT > *tree, int index, const CoordT &co)
template<typename CoordT>
static uint blender::detail::kdtree_balance (KDTreeNode< CoordT > *nodes, uint nodes_len, uint axis, const uint ofs)
template<typename CoordT>
void blender::kdtree_balance (KDTree< CoordT > *tree)
template<typename CoordT, typename Filter>
int blender::kdtree_find_nearest_cb (const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest, Filter &&filter_cb)
template<typename CoordT>
int blender::kdtree_find_nearest (const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest)
template<typename CoordT>
static void blender::detail::nearest_ordered_insert (KDTreeNearest< CoordT > *nearest, uint *nearest_len, const uint nearest_len_capacity, const int index, const typename KDTree< CoordT >::ValueType dist, const CoordT &co)
template<typename CoordT, typename Func>
int blender::kdtree_find_nearest_n_with_len_squared_cb (const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > r_nearest[], const uint nearest_len_capacity, Func &&len_sq_fn)
template<typename CoordT>
int blender::kdtree_find_nearest_n (const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > r_nearest[], uint nearest_len_capacity)
template<typename CoordT>
static int blender::detail::nearest_cmp_dist (const void *a, const void *b)
template<typename CoordT>
static void blender::detail::nearest_add_in_range (KDTreeNearest< CoordT > **r_nearest, uint nearest_index, uint *nearest_len_capacity, const int index, const typename KDTree< CoordT >::ValueType dist, const CoordT &co)
template<typename CoordT, typename Func>
int blender::kdtree_range_search_with_len_squared_cb (const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > **r_nearest, const typename KDTree< CoordT >::ValueType range, Func &&len_sq_fn)
template<typename CoordT>
int blender::kdtree_range_search (const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > **r_nearest, typename KDTree< CoordT >::ValueType range)
template<typename CoordT, typename Fn>
void blender::kdtree_range_search_cb (const KDTree< CoordT > *tree, const CoordT &co, typename KDTree< CoordT >::ValueType range, Fn &&search_cb)
template<typename CoordT>
static Vector< int > blender::detail::kdtree_order (const KDTree< CoordT > *tree)
template<typename CoordT>
int blender::kdtree_calc_duplicates_fast (const KDTree< CoordT > *tree, const typename KDTree< CoordT >::ValueType range, const bool use_index_order, int *duplicates)
kdtree_calc_duplicates_fast
template<typename CoordT>
static void blender::detail::deduplicate_recursive (const DeDuplicateParams< CoordT > *p, uint i)
kdtree_calc_duplicates_cb
template<typename CoordT, typename Func>
int blender::kdtree_calc_duplicates_cb (const KDTree< CoordT > *tree, const typename KDTree< CoordT >::ValueType range, int *duplicates, const bool has_self_index, Func &&duplicates_cb)

Variables

constexpr int blender::detail::kd_stack_init = 100
constexpr int blender::detail::kd_near_alloc_inc = 100
constexpr int blender::detail::kd_found_alloc_inc = 50
constexpr uint blender::detail::kd_node_unset = (uint(-1))
constexpr uint blender::detail::kd_node_root_is_init = (uint(-2))

Detailed Description

A KD-tree for nearest neighbor search.

Definition in file BLI_kdtree.hh.