Blender V5.3
kdtree.cc File Reference
#include <algorithm>
#include <bit>
#include <cmath>
#include <numeric>
#include <optional>
#include "BLI_array.hh"
#include "BLI_bounds.hh"
#include "BLI_enumerable_thread_specific.hh"
#include "BLI_index_mask.hh"
#include "BLI_kdtree_new.hh"
#include "BLI_linear_allocator.hh"
#include "BLI_math_vector.hh"
#include "BLI_task.hh"
#include "BLI_threads.hh"

Go to the source code of this file.

Classes

class  blender::TreeBuilder< T >

Namespaces

namespace  blender
 BMesh Iterators.
namespace  blender::kdtree

Functions

template<typename T, typename ForeachFn>
static int blender::kdtree::calc_duplicates_impl (const KDTreeNew< T > &tree, const typename T::base_type range, const MutableSpan< int > duplicates, const ForeachFn foreach_index)
template<typename T>
int blender::kdtree::calc_duplicates (const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
template<typename T>
int blender::kdtree::calc_duplicates (const KDTreeNew< T > &tree, typename T::base_type range, const IndexMask &visit_order, MutableSpan< int > duplicates)
template int blender::kdtree::calc_duplicates (const KDTreeNew< float2 > &, float, Span< int >, MutableSpan< int >)
template int blender::kdtree::calc_duplicates (const KDTreeNew< float3 > &, float, Span< int >, MutableSpan< int >)
template int blender::kdtree::calc_duplicates (const KDTreeNew< float2 > &, float, const IndexMask &, MutableSpan< int >)
template int blender::kdtree::calc_duplicates (const KDTreeNew< float3 > &, float, const IndexMask &, MutableSpan< int >)

Build Tuning

static constexpr int blender::PARALLEL_BUILD_THRESHOLD = 10000
static constexpr int blender::PARALLEL_BUILD_THRESHOLD_THREADS = 4
static constexpr int blender::PARALLEL_SUBTREE_GRAIN = 4096
static constexpr int blender::NODE_BLOCK_SIZE = 8192
static constexpr int blender::NODE_MAX_BLOCKS = 64
static constexpr int blender::NODE_BLOCK_FRACTION = 8
static constexpr int blender::PARTITION_BLOCK_SIZE = 128
static int blender::parallel_build_threads (const int64_t points_num)

Detailed Description

A KD-tree for nearest neighbor search, which started from the nanoflann library and has since been rewritten around Blender's own containers, threading and math. The node layout and the way a search walks it are still recognizably nanoflann's, which is where the copyright above comes from.

Definition in file kdtree.cc.