Blender V4.5
Classes | Macros | Typedefs | Functions | Variables
BLI_kdtree_impl.h File Reference
Blender » BlenLib

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

#include "BLI_compiler_attrs.h"
#include "BLI_sys_types.h"

Go to the source code of this file.

Classes

struct  KDTreeNearest

Macros

#define _BLI_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
#define _BLI_CONCAT(MACRO_ARG1, MACRO_ARG2)
#define BLI_kdtree_nd_(id)
#define KD_DIMS   0

Typedefs

typedef struct KDTree KDTree
typedef struct KDTreeNearest KDTreeNearest

Functions

KDTree *BLI_kdtree_nd_ new (unsigned int nodes_len_capacity)
void BLI_kdtree_nd_ free (KDTree *tree)
void BLI_kdtree_nd_ balance (KDTree *tree) ATTR_NONNULL(1)
void BLI_kdtree_nd_ insert (KDTree *tree, int index, const float co[KD_DIMS]) ATTR_NONNULL(1
void BLI_kdtree_nd_ int BLI_kdtree_nd_ find_nearest (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest *r_nearest) ATTR_NONNULL(1
void BLI_kdtree_nd_ int BLI_kdtree_nd_ int BLI_kdtree_nd_ find_nearest_n (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest *r_nearest, uint nearest_len_capacity) ATTR_NONNULL(1
void BLI_kdtree_nd_ int BLI_kdtree_nd_ int BLI_kdtree_nd_ int BLI_kdtree_nd_ range_search (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest **r_nearest, float range) ATTR_NONNULL(1
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)
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)
int BLI_kdtree_nd_ calc_duplicates_fast (const KDTree *tree, float range, bool use_index_order, int *duplicates)
int BLI_kdtree_nd_ deduplicate (KDTree *tree)
int BLI_kdtree_nd_ find_nearest_n_with_len_squared_cb (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest *r_nearest, 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) ATTR_NONNULL(1
int BLI_kdtree_nd_ int BLI_kdtree_nd_ range_search_with_len_squared_cb (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest **r_nearest, 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) ATTR_NONNULL(1
template<typename Fn>
void BLI_kdtree_nd_ range_search_cb_cpp (const KDTree *tree, const float co[KD_DIMS], float distance, const Fn &fn)
template<typename Fn>
int BLI_kdtree_nd_ find_nearest_cb_cpp (const KDTree *tree, const float co[KD_DIMS], KDTreeNearest *r_nearest, Fn &&fn)

Variables

void BLI_kdtree_nd_ int BLI_kdtree_nd_ int BLI_kdtree_nd_ int BLI_kdtree_nd_ ATTR_WARN_UNUSED_RESULT

Detailed Description

A KD-tree for nearest neighbor search.

Definition in file BLI_kdtree_impl.h.

Macro Definition Documentation

◆ _BLI_CONCAT

#define _BLI_CONCAT ( MACRO_ARG1,
MACRO_ARG2 )
Value:
_BLI_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
_BLI_CONCAT_AUX
#define _BLI_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
Definition BLI_kdtree_impl.h:13

Definition at line 14 of file BLI_kdtree_impl.h.

◆ _BLI_CONCAT_AUX

#define _BLI_CONCAT_AUX ( MACRO_ARG1,
MACRO_ARG2 )
Value:
MACRO_ARG1##MACRO_ARG2

Definition at line 13 of file BLI_kdtree_impl.h.

◆ BLI_kdtree_nd_

#define BLI_kdtree_nd_ ( id)
Value:
_BLI_CONCAT(KDTREE_PREFIX_ID, _##id)
KDTREE_PREFIX_ID
#define KDTREE_PREFIX_ID
Definition BLI_kdtree.h:14
_BLI_CONCAT
#define _BLI_CONCAT(MACRO_ARG1, MACRO_ARG2)
Definition BLI_kdtree_impl.h:14

Definition at line 15 of file BLI_kdtree_impl.h.

Referenced by find_nearest_cb_cpp(), and range_search_cb_cpp().

◆ KD_DIMS

#define KD_DIMS   0

Definition at line 19 of file BLI_kdtree_impl.h.

Typedef Documentation

◆ KDTree

typedef struct KDTree KDTree

Definition at line 23 of file BLI_kdtree_impl.h.

◆ KDTreeNearest

typedef struct KDTreeNearest KDTreeNearest

Function Documentation

◆ balance()

void BLI_kdtree_nd_ balance ( KDTree * tree)

Definition at line 204 of file kdtree_impl.h.

References balance(), i, KD_NODE_ROOT_IS_INIT, KD_NODE_UNSET, KDTree, kdtree_balance(), and tree.

Referenced by balance(), and blender::gpu::shader::Preprocessor::get_content_between_balanced_pair().

◆ 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 882 of file kdtree_impl.h.

References calc_duplicates_fast(), copy_vn_vn(), deduplicate_recursive(), DeDuplicateParams::duplicates, DeDuplicateParams::duplicates_found, ELEM, i, KDTreeNode::index, KDTree, kdtree_order(), DeDuplicateParams::nodes, DeDuplicateParams::range, DeDuplicateParams::range_sq, DeDuplicateParams::search, DeDuplicateParams::search_co, square_f(), and tree.

Referenced by calc_duplicates_fast().

◆ 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 978 of file kdtree_impl.h.

References deduplicate(), i, KD_DIMS, KDTree, kdtree_node_cmp_deduplicate(), and tree.

Referenced by deduplicate().

◆ find_nearest()

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

References find_nearest(), KD_DIMS, KDTree, KDTreeNearest, and tree.

Referenced by find_nearest(), and find_nearest().

◆ find_nearest_cb()

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 )

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 342 of file kdtree_impl.h.

References ARRAY_SIZE, BLI_assert, KDTreeNearest::co, KDTreeNode::co, copy_vn_vn(), KDTreeNode::d, KDTreeNearest::dist, find_nearest_cb(), FLT_MAX, KDTreeNearest::index, KDTreeNode::index, KD_DIMS, KD_NODE_UNSET, KD_STACK_INIT, KDTree, KDTreeNearest, KDTreeNode, KDTreeNode::left, MEM_freeN(), NODE_TEST_NEAREST, realloc_nodes(), KDTreeNode::right, sqrtf, tree, and UNLIKELY.

Referenced by find_nearest_cb(), and find_nearest_cb_cpp().

◆ find_nearest_cb_cpp()

template<typename Fn>
int BLI_kdtree_nd_ find_nearest_cb_cpp ( const KDTree * tree,
const float co[KD_DIMS],
KDTreeNearest * r_nearest,
Fn && fn )
inline

Definition at line 111 of file BLI_kdtree_impl.h.

References BLI_kdtree_nd_, find_nearest_cb(), find_nearest_cb_cpp(), KD_DIMS, KDTree, KDTreeNearest, and tree.

Referenced by find_nearest_cb_cpp().

◆ find_nearest_n()

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

References find_nearest_n(), KD_DIMS, KDTree, KDTreeNearest, and tree.

Referenced by find_nearest_n(), and find_nearest_n().

◆ 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,
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 )

Versions of find/range search that take a squared distance callback to support bias.

References find_nearest_n_with_len_squared_cb(), KD_DIMS, KDTree, KDTreeNearest, and tree.

Referenced by find_nearest_n(), find_nearest_n_with_len_squared_cb(), and find_nearest_n_with_len_squared_cb().

◆ free()

void BLI_kdtree_nd_ free ( KDTree * tree)

Definition at line 115 of file kdtree_impl.h.

References free(), KDTree, MEM_freeN(), and tree.

Referenced by blender::ResourceScope::add(), 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_rigidbody_free_world(), BLI_dynstr_clear(), BLI_exists(), BLI_freelist(), BLI_getenv(), BLI_rng_shuffle_array(), BLI_system_backtrace_with_os_info(), BLI_windows_exception_show_dialog(), btFreeDefault(), button_matches_search_filter(), callback_main_atexit(), ccl_try_align(), iTaSC::CacheChannel::clear(), blender::gpu::MTLUniformBuf::clear_to_zero(), iTaSC::Cache::clearCacheFrom(), curve_draw_exec(), blender::ed::curves::curves_draw_exec(), CustomData_external_write(), data_device_handle_drop(), blender::RawAllocator::deallocate(), GuardedAllocator< U >::deallocate(), MemoryAllocator< N >::destroy(), device_oneapi_capabilities(), ED_region_draw_cb_remove_by_type(), event_to_buf(), Freestyle::FitCurveWrapper::FitCubic(), free(), blender::bke::pbvh::free_tree(), GPUDevice::generic_alloc(), blender::ed::geometry::geometry_attribute_add_invoke(), GPUDevice::get_device_memory_info(), blender::gpu::MTLContext::get_null_buffer(), GHOST_SystemX11::getClipboard(), GHOST_SystemX11::getClipboard_xcout(), GHOST_SystemWayland::getClipboardImage(), getClipboardImageFilepath(), GHOST_DropTargetX11::getGhostData(), GHOST_DropTargetX11::GHOST_HandleClientMessage(), GHOST_URL_decode_alloc(), GHOST_WindowWin32::GHOST_WindowWin32(), GHOST_WindowX11::GHOST_WindowX11(), gim_free(), GIZMO_GT_snap_3d(), Freestyle::gts_vertex_principal_directions(), gwl_simple_buffer_free_data(), gwl_simple_buffer_set_from_string(), gwl_window_cursor_custom_free(), GHOST_SystemCocoa::handleDraggingEvent(), GHOST_SystemWayland::hasClipboardImage(), GHOST_SystemWin32::hasClipboardImage(), IFileStream::IFileStream(), imb_free_dds_buffer(), imb_savewebp(), insert_key_menu_invoke(), MEM_guarded_printmemlist_stats(), MEM_lockfree_freeN(), memfd_create_sealed(), menu_item_enum_opname_menu_active(), GPUDevice::move_textures_to_host(), blender::ed::space_node::node_space_subtype_item_extend(), blender::ed::object::object_remove_parent_deform_modifiers(), blender::ed::object::ocean_bake_exec(), OFileStream::OFileStream(), blender::ed::greasepencil::polyline_detect_corners(), blender::ed::greasepencil::polyline_fit_curve(), processEvent(), GHOST_SystemX11::putClipboard(), pyrna_enum_as_string(), pyrna_prop_to_enum_bitfield(), RB_shape_delete(), read_file_as_buffer(), rect_bevel_smooth(), recursive_operation_impl(), rem_memblock(), blender::ResourceScope::ResourceScope(), 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(), rna_PropertyGroup_register(), GHOST_WindowWin32::setTitle(), GHOST_SystemWin32::showMessageBox(), GHOST_SystemX11::showMessageBox(), SKY_arhosekskymodelstate_free(), space_type_set_or_cycle_exec(), split(), strbuf_free(), TEST(), thumb_data_vertical_flip(), u_free_getenv(), UI_block_set_active_operator(), 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_image_get(), wm_clipboard_text_get_ex(), WM_jobs_customdata_set(), WM_paint_cursor_remove_by_type(), blender::io::grease_pencil::PDFExporter::write_to_file(), blender::io::grease_pencil::SVGExporter::write_to_file(), 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] )

References insert(), KD_DIMS, KDTree, and tree.

Referenced by blender::gpu::GPUSource::add_function(), AUD_addSet(), BVHObjectBinning::BVHObjectBinning(), blender::Vector< SubdivCCGCoord, 256 >::extend(), nanovdb::CachedReadAccessor< BuildT >::getValueAndCache(), nanovdb::CachedReadAccessor< BuildT >::getValueAndCache(), hull_angle_insert_ordered(), blender::Vector< SubdivCCGCoord, 256 >::insert(), blender::Vector< SubdivCCGCoord, 256 >::insert(), blender::Vector< SubdivCCGCoord, 256 >::insert(), blender::Vector< SubdivCCGCoord, 256 >::insert(), insert(), insert(), MOD_solidify_nonmanifold_modifyMesh(), blender::ed::space_node::node_link_insert_offset_ntree(), blender::Vector< SubdivCCGCoord, 256 >::prepend(), blender::Vector< SubdivCCGCoord, 256 >::prepend(), blender::Vector< SubdivCCGCoord, 256 >::prepend(), blender::Vector< SubdivCCGCoord, 256 >::prepend(), and blender::geometry::subdivide_bezier_segment().

◆ new()

KDTree *BLI_kdtree_nd_ new ( uint nodes_len_capacity)
Parameters
nodes_len_capacityThe maximum length this KD-tree may hold.

Creates or free a kdtree

Definition at line 97 of file kdtree_impl.h.

References KD_NODE_ROOT_IS_INIT, KDTree, MEM_callocN(), MEM_malloc_arrayN(), and tree.

Referenced by blender::gpu::MSLGeneratorInterface::bake_shader_interface(), GHOST_SystemWayland::GHOST_SystemWayland(), GHOST_Window::GHOST_Window(), GHOST_WindowWayland::GHOST_WindowWayland(), blender::gpu::GLShader::post_finalize(), and pygpu_interface_info__tp_new().

◆ range_search()

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

References KD_DIMS, KDTree, KDTreeNearest, range_search(), and tree.

Referenced by range_search(), and range_search().

◆ range_search_cb()

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 )

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 738 of file kdtree_impl.h.

References ARRAY_SIZE, BLI_assert, KDTreeNode::co, KDTreeNode::d, KDTreeNode::index, KD_DIMS, KD_NODE_UNSET, KD_STACK_INIT, KDTree, KDTreeNode, KDTreeNode::left, len_squared_vnvn(), MEM_freeN(), range_search_cb(), realloc_nodes(), KDTreeNode::right, tree, and UNLIKELY.

Referenced by range_search_cb(), and range_search_cb_cpp().

◆ range_search_cb_cpp()

template<typename Fn>
void BLI_kdtree_nd_ range_search_cb_cpp ( const KDTree * tree,
const float co[KD_DIMS],
float distance,
const Fn & fn )
inline

Definition at line 94 of file BLI_kdtree_impl.h.

References BLI_kdtree_nd_, distance(), KD_DIMS, KDTree, range_search_cb(), range_search_cb_cpp(), and tree.

Referenced by range_search_cb_cpp().

◆ range_search_with_len_squared_cb()

int BLI_kdtree_nd_ int BLI_kdtree_nd_ range_search_with_len_squared_cb ( const KDTree * tree,
const float co[KD_DIMS],
KDTreeNearest ** r_nearest,
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 )

References ATTR_WARN_UNUSED_RESULT, KD_DIMS, KDTree, KDTreeNearest, range_search_with_len_squared_cb(), and tree.

Referenced by range_search(), range_search_with_len_squared_cb(), and range_search_with_len_squared_cb().

Variable Documentation

◆ ATTR_WARN_UNUSED_RESULT

int BLI_kdtree_nd_ int BLI_kdtree_nd_ ATTR_WARN_UNUSED_RESULT

Definition at line 51 of file BLI_kdtree_impl.h.

Generated on for Blender by  doxygen 1.16.1