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

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

Classes
struct	KDTreeNearest

Macros
#define	_BLI_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1##MACRO_ARG2

#define	_BLI_CONCAT(MACRO_ARG1, MACRO_ARG2) _BLI_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)

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

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

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 ) _BLI_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)

Definition at line 14 of file BLI_kdtree_impl.h.

◆ _BLI_CONCAT_AUX

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

Definition at line 13 of file BLI_kdtree_impl.h.

◆ BLI_kdtree_nd_

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

Definition at line 15 of file BLI_kdtree_impl.h.

Typedef Documentation

◆ KDTree

typedef struct KDTree KDTree

Definition at line 22 of file BLI_kdtree_impl.h.

◆ KDTreeNearest

typedef struct KDTreeNearest KDTreeNearest

Function Documentation

◆ balance()

void BLI_kdtree_nd_ balance ( KDTree * tree )

Definition at line 198 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

range	Coordinates in this range are candidates to be merged.
use_index_order	Loop 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.
duplicates	An 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 883 of file kdtree_impl.h.

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

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

References KD_DIMS, kdtree_node_cmp_deduplicate(), and tree.

◆ find_nearest()

void BLI_kdtree_nd_ 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(*	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_cb Filter find results, Return codes: (1: accept, 0: skip, -1: immediate exit).

Definition at line 336 of file kdtree_impl.h.

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

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

◆ 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.

◆ free()

void BLI_kdtree_nd_ free ( KDTree * tree )

Definition at line 109 of file kdtree_impl.h.

References 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_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(), blender::gpu::MTLUniformBuf::clear_to_zero(), iTaSC::Cache::clearCacheFrom(), createGPUShader(), curve_draw_exec(), blender::ed::curves::curves_draw_exec(), CustomData_external_write(), data_device_handle_drop(), blender::RawAllocator::deallocate(), GuardedAllocator< T >::deallocate(), MemoryAllocator< N >::destroy(), device_oneapi_capabilities(), ED_region_draw_cb_remove_by_type(), event_to_buf(), Freestyle::FitCurveWrapper::FitCubic(), blender::bke::pbvh::free_tree(), GPUDevice::generic_alloc(), blender::ed::geometry::geometry_attribute_add_invoke(), blender::gpu::MTLContext::get_null_buffer(), GHOST_SystemX11::getClipboard(), GHOST_SystemX11::getClipboard_xcout(), GHOST_SystemWayland::getClipboardImage(), 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(), 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(), 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(), osx_user_locale(), 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(), 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(), strbuf_free(), 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] )

Referenced by AUD_addSet(), BVHObjectBinning::BVHObjectBinning(), nanovdb::CachedReadAccessor< BuildT >::getValueAndCache(), nanovdb::CachedReadAccessor< BuildT >::getValueAndCache(), hull_angle_insert_ordered(), MOD_solidify_nonmanifold_modifyMesh(), blender::ed::space_node::node_link_insert_offset_ntree(), and blender::geometry::subdivide_bezier_segment().

◆ new()

KDTree *BLI_kdtree_nd_ new ( uint nodes_len_capacity )

Parameters

nodes_len_capacity The maximum length this KD-tree may hold.

Creates or free a kdtree

Definition at line 91 of file kdtree_impl.h.

References KD_NODE_ROOT_IS_INIT, MEM_mallocN, and tree.

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

◆ 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_cb Called 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 737 of file kdtree_impl.h.

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

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

Variable Documentation

◆ ATTR_WARN_UNUSED_RESULT

int BLI_kdtree_nd_ int BLI_kdtree_nd_ ATTR_WARN_UNUSED_RESULT

Definition at line 50 of file BLI_kdtree_impl.h.

Classes

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ _BLI_CONCAT

◆ _BLI_CONCAT_AUX

◆ BLI_kdtree_nd_

Typedef Documentation

◆ KDTree

◆ KDTreeNearest

Function Documentation

◆ balance()

◆ calc_duplicates_fast()

◆ deduplicate()

◆ find_nearest()

◆ find_nearest_cb()

◆ find_nearest_n()

◆ find_nearest_n_with_len_squared_cb()

◆ free()

◆ insert()

◆ new()

◆ range_search()

◆ range_search_cb()

◆ range_search_with_len_squared_cb()

Variable Documentation

◆ ATTR_WARN_UNUSED_RESULT