Blender  V3.3
Classes | Macros | Typedefs | Functions
kdtree_impl.h File Reference
#include "MEM_guardedalloc.h"
#include "BLI_kdtree_impl.h"
#include "BLI_math.h"
#include "BLI_strict_flags.h"
#include "BLI_utildefines.h"

Go to the source code of this file.

Classes

struct  KDTreeNode_head
 
struct  KDTreeNode
 
struct  KDTree
 
struct  DeDuplicateParams
 

Macros

#define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)   MACRO_ARG1##MACRO_ARG2
 
#define _CONCAT(MACRO_ARG1, MACRO_ARG2)   _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
 
#define BLI_kdtree_nd_(id)   _CONCAT(KDTREE_PREFIX_ID, _##id)
 
#define KD_STACK_INIT   100 /* initial size for array (on the stack) */
 
#define KD_NEAR_ALLOC_INC   100 /* alloc increment for collecting nearest */
 
#define KD_FOUND_ALLOC_INC   50 /* alloc increment for collecting nearest */
 
#define KD_NODE_UNSET   ((uint)-1)
 
#define KD_NODE_ROOT_IS_INIT   ((uint)-2)
 
#define NODE_TEST_NEAREST(node)
 

Typedefs

typedef struct KDTreeNode_head KDTreeNode_head
 
typedef struct KDTreeNode KDTreeNode
 

Functions

KDTree *BLI_kdtree_nd_() new (uint nodes_len_capacity)
 
void BLI_kdtree_nd_() free (KDTree *tree)
 
void BLI_kdtree_nd_() insert (KDTree *tree, int index, const float co[KD_DIMS])
 
static uint kdtree_balance (KDTreeNode *nodes, uint nodes_len, uint axis, const uint ofs)
 
void BLI_kdtree_nd_() balance (KDTree *tree)
 
static uintrealloc_nodes (uint *stack, uint *stack_len_capacity, const bool is_alloc)
 
int BLI_kdtree_nd_() find_nearest (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest *r_nearest)
 
int BLI_kdtree_nd_() find_nearest_cb (const KDTree *tree, const float co[KD_DIMS], int(*filter_cb)(void *user_data, int index, const float co[KD_DIMS], float dist_sq), void *user_data, KDTreeNearest *r_nearest)
 
static void nearest_ordered_insert (KDTreeNearest *nearest, uint *nearest_len, const uint nearest_len_capacity, const int index, const float dist, const float co[KD_DIMS])
 
int BLI_kdtree_nd_() find_nearest_n_with_len_squared_cb (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest r_nearest[], const uint nearest_len_capacity, float(*len_sq_fn)(const float co_search[KD_DIMS], const float co_test[KD_DIMS], const void *user_data), const void *user_data)
 
int BLI_kdtree_nd_() find_nearest_n (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest r_nearest[], uint nearest_len_capacity)
 
static int nearest_cmp_dist (const void *a, const void *b)
 
static void nearest_add_in_range (KDTreeNearest **r_nearest, uint nearest_index, uint *nearest_len_capacity, const int index, const float dist, const float co[KD_DIMS])
 
int BLI_kdtree_nd_() range_search_with_len_squared_cb (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest **r_nearest, const float range, float(*len_sq_fn)(const float co_search[KD_DIMS], const float co_test[KD_DIMS], const void *user_data), const void *user_data)
 
int BLI_kdtree_nd_() range_search (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest **r_nearest, float range)
 
void BLI_kdtree_nd_() range_search_cb (const KDTree *tree, const float co[KD_DIMS], float range, bool(*search_cb)(void *user_data, int index, const float co[KD_DIMS], float dist_sq), void *user_data)
 
static uintkdtree_order (const KDTree *tree)
 
Local Math API
static void copy_vn_vn (float v0[KD_DIMS], const float v1[KD_DIMS])
 
static float len_squared_vnvn (const float v0[KD_DIMS], const float v1[KD_DIMS])
 
static float len_squared_vnvn_cb (const float co_kdtree[KD_DIMS], const float co_search[KD_DIMS], const void *UNUSED(user_data))
 
BLI_kdtree_3d_calc_duplicates_fast
static void deduplicate_recursive (const struct DeDuplicateParams *p, uint i)
 
int BLI_kdtree_nd_() calc_duplicates_fast (const KDTree *tree, const float range, bool use_index_order, int *duplicates)
 
BLI_kdtree_3d_deduplicate
static int kdtree_cmp_bool (const bool a, const bool b)
 
static int kdtree_node_cmp_deduplicate (const void *n0_p, const void *n1_p)
 
int BLI_kdtree_nd_() deduplicate (KDTree *tree)
 

Macro Definition Documentation

◆ _CONCAT

#define _CONCAT (   MACRO_ARG1,
  MACRO_ARG2 
)    _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)

Definition at line 15 of file kdtree_impl.h.

◆ _CONCAT_AUX

#define _CONCAT_AUX (   MACRO_ARG1,
  MACRO_ARG2 
)    MACRO_ARG1##MACRO_ARG2

Definition at line 14 of file kdtree_impl.h.

◆ BLI_kdtree_nd_

#define BLI_kdtree_nd_ (   id)    _CONCAT(KDTREE_PREFIX_ID, _##id)

Definition at line 16 of file kdtree_impl.h.

◆ KD_FOUND_ALLOC_INC

#define KD_FOUND_ALLOC_INC   50 /* alloc increment for collecting nearest */

Definition at line 43 of file kdtree_impl.h.

◆ KD_NEAR_ALLOC_INC

#define KD_NEAR_ALLOC_INC   100 /* alloc increment for collecting nearest */

Definition at line 42 of file kdtree_impl.h.

◆ KD_NODE_ROOT_IS_INIT

#define KD_NODE_ROOT_IS_INIT   ((uint)-2)

When set we know all values are unbalanced, otherwise clear them when re-balancing: see T62210.

Definition at line 51 of file kdtree_impl.h.

◆ KD_NODE_UNSET

#define KD_NODE_UNSET   ((uint)-1)

Definition at line 45 of file kdtree_impl.h.

◆ KD_STACK_INIT

#define KD_STACK_INIT   100 /* initial size for array (on the stack) */

Definition at line 41 of file kdtree_impl.h.

◆ NODE_TEST_NEAREST

#define NODE_TEST_NEAREST (   node)
Value:
{ \
const float dist_sq = len_squared_vnvn((node)->co, co); \
if (dist_sq < min_dist) { \
const int result = filter_cb(user_data, (node)->index, (node)->co, dist_sq); \
if (result == 1) { \
min_dist = dist_sq; \
min_node = node; \
} \
else if (result == 0) { \
/* pass */ \
} \
else { \
BLI_assert(result == -1); \
goto finally; \
} \
} \
} \
((void)0)
OperationNode * node
void * user_data
SyclQueue void void size_t num_bytes void
static float len_squared_vnvn(const float v0[KD_DIMS], const float v1[KD_DIMS])
Definition: kdtree_impl.h:64

Typedef Documentation

◆ KDTreeNode

typedef struct KDTreeNode KDTreeNode

◆ KDTreeNode_head

Function Documentation

◆ balance()

void BLI_kdtree_nd_() balance ( KDTree tree)

Definition at line 190 of file kdtree_impl.h.

References KD_NODE_ROOT_IS_INIT, KD_NODE_UNSET, kdtree_balance(), and tree.

◆ calc_duplicates_fast()

int BLI_kdtree_nd_() calc_duplicates_fast ( const KDTree tree,
const float  range,
bool  use_index_order,
int *  duplicates 
)

Find duplicate points in range. Favors speed over quality since it doesn't find the best target vertex for merging. Nodes are looped over, duplicates are added when found. Nevertheless results are predictable.

Parameters
rangeCoordinates in this range are candidates to be merged.
use_index_orderLoop over the coordinates ordered by KDTreeNode.index At the expense of some performance, this ensures the layout of the tree doesn't influence the iteration order.
duplicatesAn array of int's the length of KDTree.nodes_len Values initialized to -1 are candidates to me merged. Setting the index to its own position in the array prevents it from being touched, although it can still be used as a target.
Returns
The number of merges found (includes any merges already in the duplicates array).
Note
Merging is always a single step (target indices won't be marked for merging).

Definition at line 873 of file kdtree_impl.h.

References copy_vn_vn(), deduplicate_recursive(), DeDuplicateParams::duplicates, ELEM, KDTreeNode::index, kdtree_order(), MEM_freeN, DeDuplicateParams::nodes, order, DeDuplicateParams::range, DeDuplicateParams::search, DeDuplicateParams::search_co, square_f(), and tree.

◆ copy_vn_vn()

static void copy_vn_vn ( float  v0[KD_DIMS],
const float  v1[KD_DIMS] 
)
static

◆ deduplicate()

int BLI_kdtree_nd_() deduplicate ( KDTree tree)

Remove exact duplicates (run before balancing).

Keep the first element added when duplicates are found.

Definition at line 967 of file kdtree_impl.h.

References KD_DIMS, kdtree_node_cmp_deduplicate(), and tree.

◆ deduplicate_recursive()

static void deduplicate_recursive ( const struct DeDuplicateParams p,
uint  i 
)
static

◆ find_nearest()

int BLI_kdtree_nd_() find_nearest ( const KDTree tree,
const float  co[KD_DIMS],
KDTreeNearest r_nearest 
)

◆ find_nearest_cb()

int BLI_kdtree_nd_() find_nearest_cb ( const KDTree tree,
const float  co[KD_DIMS],
int(*)(void *user_data, int index, const float co[KD_DIMS], float dist_sq)  filter_cb,
void user_data,
KDTreeNearest r_nearest 
)

A version of #BLI_kdtree_3d_find_nearest which runs a callback to filter out values.

Parameters
filter_cbFilter find results, Return codes: (1: accept, 0: skip, -1: immediate exit).

Definition at line 328 of file kdtree_impl.h.

References ARRAY_SIZE, BLI_assert, KDTreeNearest::co, KDTreeNode::co, copy_vn_vn(), KDTreeNearest::dist, KDTreeNearest::index, KDTreeNode::index, KD_DIMS, KD_NODE_UNSET, KD_STACK_INIT, MEM_freeN, node, NODE_TEST_NEAREST, NULL, realloc_nodes(), sqrtf, tree, and UNLIKELY.

◆ find_nearest_n()

int BLI_kdtree_nd_() find_nearest_n ( const KDTree tree,
const float  co[KD_DIMS],
KDTreeNearest  r_nearest[],
uint  nearest_len_capacity 
)

Definition at line 580 of file kdtree_impl.h.

References BLI_kdtree_nd_, find_nearest_n_with_len_squared_cb(), NULL, and tree.

◆ find_nearest_n_with_len_squared_cb()

int BLI_kdtree_nd_() find_nearest_n_with_len_squared_cb ( const KDTree tree,
const float  co[KD_DIMS],
KDTreeNearest  r_nearest[],
const uint  nearest_len_capacity,
float(*)(const float co_search[KD_DIMS], const float co_test[KD_DIMS], const void *user_data len_sq_fn,
const void user_data 
)

Find nearest_len_capacity nearest returns number of points found, with results in nearest.

Parameters
r_nearestAn array of nearest, sized at least nearest_len_capacity.

Definition at line 466 of file kdtree_impl.h.

References ARRAY_SIZE, BLI_assert, KDTreeNode::co, KDTreeNode::d, KDTreeNearest::dist, KDTreeNode::index, KD_DIMS, KD_NODE_UNSET, KD_STACK_INIT, KDTreeNode::left, len_squared_vnvn_cb(), MEM_freeN, nearest_ordered_insert(), node, NULL, realloc_nodes(), KDTreeNode::right, sqrtf, tree, UNLIKELY, and user_data.

Referenced by find_nearest_n().

◆ free()

void BLI_kdtree_nd_() free ( KDTree tree)

Definition at line 102 of file kdtree_impl.h.

References MEM_freeN, and tree.

Referenced by blender::ResourceScope::add(), add_orco_mesh(), iTaSC::Cache::addCacheItem(), iTaSC::Armature::addConstraint(), aligned_free(), libmv::aligned_free(), arg_handle_addons_set(), Freestyle::BezierII(), BKE_blender_atexit(), BKE_blender_atexit_unregister(), BKE_gpencil_stroke_editcurve_generate(), BKE_rigidbody_free_world(), BLI_dynstr_clear(), BLI_exists(), BLI_freelist(), BLI_getenv(), BLI_rng_shuffle_array(), BLI_system_backtrace(), btFreeDefault(), button_matches_search_filter(), callback_main_atexit(), ccl_try_align(), iTaSC::CacheChannel::clear(), iTaSC::Cache::clearCacheFrom(), create_orco_mesh(), createGPUShader(), curve_draw_exec(), CustomData_external_write(), GuardedAllocator< T >::deallocate(), blender::RawAllocator::deallocate(), MemoryAllocator< N >::destroy(), display_destroy(), ED_gpencil_trace_bitmap_free(), ED_gpencil_trace_bitmap_new(), ED_region_draw_cb_remove_by_type(), event_to_buf(), Freestyle::FitCurveWrapper::FitCubic(), free_tree(), FreeReverseLookup(), GenerateSharedVerticesIndexList(), GenerateTSpaces(), genTangSpace(), get_orco_coords(), GHOST_SystemX11::getClipboard(), GHOST_SystemX11::getClipboard_xcout(), GHOST_DropTargetX11::getGhostData(), GHOST_DropTargetX11::GHOST_HandleClientMessage(), GHOST_SystemCocoa::GHOST_SystemCocoa(), GHOST_WindowWin32::GHOST_WindowWin32(), GHOST_WindowX11::GHOST_WindowX11(), gim_free(), GIZMO_GT_snap_3d(), Freestyle::gts_vertex_principal_directions(), GHOST_SystemCocoa::handleDraggingEvent(), icon_decode(), icon_merge(), icon_merge_context_free(), icondir_to_png(), IFileStream::IFileStream(), IMB_freeImBuf(), imb_save_dds(), imb_savetiff(), imb_savewebp(), InitTriInfo(), insert_key_menu_invoke(), MEM_guarded_printmemlist_stats(), MEM_lockfree_freeN(), memfd_create_sealed(), blender::ed::space_node::node_space_subtype_item_extend(), object_remove_parent_deform_modifiers(), ocean_bake_exec(), OFileStream::OFileStream(), osx_user_locale(), processEvent(), GHOST_SystemX11::putClipboard(), GHOST_SystemWayland::putClipboard(), pyrna_enum_as_string(), pyrna_prop_to_enum_bitfield(), RB_shape_delete(), DirectDrawSurface::readData(), rect_bevel_smooth(), recursive_operation(), rem_memblock(), RNA_enum_is_equal(), RNA_property_as_string(), RNA_property_enum_bitflag_identifiers(), RNA_property_enum_identifier(), RNA_property_enum_item_from_value(), RNA_property_enum_items_gettexted_all(), RNA_property_enum_name(), RNA_property_enum_step(), RNA_property_enum_value(), GHOST_WindowWin32::setTitle(), GHOST_SystemWin32::showMessageBox(), GHOST_SystemX11::showMessageBox(), SKY_arhosekskymodelstate_free(), space_type_set_or_cycle_exec(), split(), thumb_data_vertical_flip(), u_free_getenv(), ui_but_event_property_operator_string(), ui_def_but_rna(), ui_def_but_rna__menu(), ui_icon_view_menu_cb(), ui_item_enum_expand_exec(), ui_item_rna_size(), ui_menu_enumpropname(), uiItemEnumO_string(), uiItemEnumR_string_prop(), uiItemsEnumR(), uiItemsFullEnumO(), util_aligned_free(), where_am_i(), wm_clipboard_text_get_ex(), WM_jobs_customdata_set(), WM_paint_cursor_remove_by_type(), write_png(), wWinMain(), iTaSC::CacheEntry::~CacheEntry(), GHOST_ContextWGL::~GHOST_ContextWGL(), GHOST_EventDragnDrop::~GHOST_EventDragnDrop(), GHOST_EventString::~GHOST_EventString(), and iTaSC::Armature::JointConstraint_struct::~JointConstraint_struct().

◆ insert()

void BLI_kdtree_nd_() insert ( KDTree tree,
int  index,
const float  co[KD_DIMS] 
)

Construction: first insert points, then call balance. Normal is optional.

Definition at line 113 of file kdtree_impl.h.

References BLI_assert, copy_vn_vn(), KD_NODE_UNSET, node, and tree.

◆ kdtree_balance()

static uint kdtree_balance ( KDTreeNode nodes,
uint  nodes_len,
uint  axis,
const uint  ofs 
)
static

Definition at line 134 of file kdtree_impl.h.

References KDTreeNode::co, KD_DIMS, KD_NODE_UNSET, left, node, right, and SWAP.

Referenced by balance().

◆ kdtree_cmp_bool()

static int kdtree_cmp_bool ( const bool  a,
const bool  b 
)
static

Definition at line 930 of file kdtree_impl.h.

References Freestyle::a, and usdtokens::b().

Referenced by kdtree_node_cmp_deduplicate().

◆ kdtree_node_cmp_deduplicate()

static int kdtree_node_cmp_deduplicate ( const void n0_p,
const void n1_p 
)
static

Definition at line 938 of file kdtree_impl.h.

References KDTreeNode::co, KDTreeNode::d, KD_DIMS, and kdtree_cmp_bool().

Referenced by deduplicate().

◆ kdtree_order()

static uint* kdtree_order ( const KDTree tree)
static

Use when we want to loop over nodes ordered by index. Requires indices to be aligned with nodes.

Definition at line 799 of file kdtree_impl.h.

References KDTreeNode::index, MEM_mallocN, order, and tree.

Referenced by calc_duplicates_fast().

◆ len_squared_vnvn()

static float len_squared_vnvn ( const float  v0[KD_DIMS],
const float  v1[KD_DIMS] 
)
static

Definition at line 64 of file kdtree_impl.h.

References KD_DIMS, square_f(), and v1.

Referenced by deduplicate_recursive(), find_nearest(), len_squared_vnvn_cb(), and range_search_cb().

◆ len_squared_vnvn_cb()

static float len_squared_vnvn_cb ( const float  co_kdtree[KD_DIMS],
const float  co_search[KD_DIMS],
const void UNUSEDuser_data 
)
static

◆ nearest_add_in_range()

static void nearest_add_in_range ( KDTreeNearest **  r_nearest,
uint  nearest_index,
uint nearest_len_capacity,
const int  index,
const float  dist,
const float  co[KD_DIMS] 
)
static

◆ nearest_cmp_dist()

static int nearest_cmp_dist ( const void a,
const void b 
)
static

Definition at line 589 of file kdtree_impl.h.

References Freestyle::a, usdtokens::b(), and KDTreeNearest::dist.

Referenced by range_search_with_len_squared_cb().

◆ nearest_ordered_insert()

static void nearest_ordered_insert ( KDTreeNearest nearest,
uint nearest_len,
const uint  nearest_len_capacity,
const int  index,
const float  dist,
const float  co[KD_DIMS] 
)
static

◆ new()

KDTree* BLI_kdtree_nd_() new ( uint  nodes_len_capacity)

Creates or free a kdtree

Definition at line 85 of file kdtree_impl.h.

References KD_NODE_ROOT_IS_INIT, MEM_mallocN, and tree.

Referenced by blender::gpu::GLShader::finalize(), and pygpu_interface_info__tp_new().

◆ range_search()

int BLI_kdtree_nd_() range_search ( const KDTree tree,
const float  co[KD_DIMS],
KDTreeNearest **  r_nearest,
float  range 
)

Definition at line 712 of file kdtree_impl.h.

References BLI_kdtree_nd_, NULL, range_search_with_len_squared_cb(), and tree.

◆ range_search_cb()

void BLI_kdtree_nd_() range_search_cb ( const KDTree tree,
const float  co[KD_DIMS],
float  range,
bool(*)(void *user_data, int index, const float co[KD_DIMS], float dist_sq)  search_cb,
void user_data 
)

A version of #BLI_kdtree_3d_range_search which runs a callback instead of allocating an array.

Parameters
search_cbCalled for every node found in range, false return value performs an early exit.
Note
the order of calls isn't sorted based on distance.

Definition at line 729 of file kdtree_impl.h.

References ARRAY_SIZE, BLI_assert, KD_DIMS, KD_NODE_UNSET, KD_STACK_INIT, len_squared_vnvn(), MEM_freeN, node, realloc_nodes(), tree, UNLIKELY, and user_data.

◆ range_search_with_len_squared_cb()

int BLI_kdtree_nd_() range_search_with_len_squared_cb ( const KDTree tree,
const float  co[KD_DIMS],
KDTreeNearest **  r_nearest,
const float  range,
float(*)(const float co_search[KD_DIMS], const float co_test[KD_DIMS], const void *user_data len_sq_fn,
const void user_data 
)

Range search returns number of points nearest_len, with results in nearest

Parameters
r_nearestAllocated array of nearest nearest_len (caller is responsible for freeing).

Definition at line 630 of file kdtree_impl.h.

References ARRAY_SIZE, BLI_assert, KD_DIMS, KD_NODE_UNSET, KD_STACK_INIT, len_squared_vnvn_cb(), MEM_freeN, nearest_add_in_range(), nearest_cmp_dist(), node, NULL, realloc_nodes(), tree, UNLIKELY, and user_data.

Referenced by range_search().

◆ realloc_nodes()

static uint* realloc_nodes ( uint stack,
uint stack_len_capacity,
const bool  is_alloc 
)
static