#include "MEM_guardedalloc.h"
#include "BLI_array.hh"
#include "BLI_kdtree_impl.h"
#include "BLI_math_base.h"
#include "BLI_utildefines.h"
#include "BLI_vector.hh"
#include <algorithm>
#include <cstring>
#include "BLI_strict_flags.h"

Classes
struct	KDTreeNode_head
struct	KDTreeNode
struct	KDTree
struct	DeDuplicateParams

Macros
#define	_BLI_KDTREE_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
#define	_BLI_KDTREE_CONCAT(MACRO_ARG1, MACRO_ARG2)
#define	BLI_kdtree_nd_(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)

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 uint *	realloc_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 blender::Vector< int >	kdtree_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 *)
BLI_kdtree_3d_calc_duplicates_fast
static void	deduplicate_recursive (const DeDuplicateParams *p, uint i)
int BLI_kdtree_nd_	calc_duplicates_fast (const KDTree tree, const float range, const bool use_index_order, int duplicates)
BLI_kdtree_3d_calc_duplicates_cb
int BLI_kdtree_nd_	calc_duplicates_cb (const KDTree tree, const float range, int duplicates, const bool has_self_index, int(duplicates_cb)(void user_data, const int cluster, int cluster_num), void user_data)
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

◆ _BLI_KDTREE_CONCAT

#define _BLI_KDTREE_CONCAT	(		MACRO_ARG1,
			MACRO_ARG2 )

Value:

_BLI_KDTREE_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)

_BLI_KDTREE_CONCAT_AUX

#define _BLI_KDTREE_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)

Definition kdtree_impl.h:22

Definition at line 23 of file kdtree_impl.h.

◆ _BLI_KDTREE_CONCAT_AUX

#define _BLI_KDTREE_CONCAT_AUX	(		MACRO_ARG1,
			MACRO_ARG2 )

Value:

MACRO_ARG1##MACRO_ARG2

Definition at line 22 of file kdtree_impl.h.

◆ BLI_kdtree_nd_

#define BLI_kdtree_nd_ ( id )

Value:

_BLI_KDTREE_CONCAT(KDTREE_PREFIX_ID, _##id)

KDTREE_PREFIX_ID

#define KDTREE_PREFIX_ID

Definition BLI_kdtree.h:14

_BLI_KDTREE_CONCAT

#define _BLI_KDTREE_CONCAT(MACRO_ARG1, MACRO_ARG2)

Definition kdtree_impl.h:23

Definition at line 24 of file kdtree_impl.h.

Referenced by calc_duplicates_cb(), find_nearest_n(), and range_search().

◆ KD_FOUND_ALLOC_INC

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

Definition at line 56 of file kdtree_impl.h.

Referenced by nearest_add_in_range().

◆ KD_NEAR_ALLOC_INC

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

Definition at line 55 of file kdtree_impl.h.

Referenced by realloc_nodes().

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

Definition at line 64 of file kdtree_impl.h.

Referenced by balance(), and new().

◆ KD_NODE_UNSET

#define KD_NODE_UNSET ((uint) - 1)

Definition at line 58 of file kdtree_impl.h.

Referenced by balance(), calc_duplicates_cb(), deduplicate_recursive(), find_nearest(), find_nearest_cb(), find_nearest_n_with_len_squared_cb(), insert(), kdtree_balance(), range_search_cb(), and range_search_with_len_squared_cb().

◆ KD_STACK_INIT

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

Definition at line 54 of file kdtree_impl.h.

Referenced by find_nearest(), find_nearest_cb(), find_nearest_n_with_len_squared_cb(), range_search_cb(), and range_search_with_len_squared_cb().

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

Referenced by find_nearest_cb().

Function Documentation

◆ balance()

void BLI_kdtree_nd_ balance ( KDTree * tree )

Definition at line 205 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_cb()

int BLI_kdtree_nd_ calc_duplicates_cb	(	const KDTree *	tree,
		const float	range,
		int *	duplicates,
		bool	has_self_index,
		int(*	deduplicate_cb )(void user_data, const int cluster, int cluster_num),
		void *	user_data )

De-duplicate utility where the callback can evaluate duplicates and select the target which other indices are merged into.

Parameters

tree	A tree, all indices must be unique.
has_self_index	When true, account for indices in the duplicates array that reference themselves, prioritizing them as targets before de-duplicating the remainder with each other.
deduplicate_cb	A function which receives duplicate indices, it must choose the "target" index to keep which is returned. The return value is an index in the cluster array (a value from 0..cluster_num). The last item in cluster is the index from which the search began.

Note: ~1.1x-1.5x slower than calc_duplicates_fast depending on the distribution of points.; The duplicate search is performed in an order defined by the tree-nodes index, the index of the input (first to last) for predictability.

Definition at line 898 of file kdtree_impl.h.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_assert, BLI_kdtree_nd_, calc_duplicates_cb(), blender::Vector< T, InlineBufferCapacity, Allocator >::clear(), blender::Vector< T, InlineBufferCapacity, Allocator >::data(), i, blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), KD_NODE_UNSET, KDTree, range_search_cb_cpp(), blender::Vector< T, InlineBufferCapacity, Allocator >::size(), tree, and UNLIKELY.

Referenced by calc_duplicates_cb(), and calc_duplicates_cb_cpp().

◆ calc_duplicates_fast()

int BLI_kdtree_nd_ calc_duplicates_fast	(	const KDTree *	tree,
		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 839 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().

◆ copy_vn_vn()

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

static

Definition at line 70 of file kdtree_impl.h.

References KD_DIMS.

Referenced by calc_duplicates_fast(), find_nearest(), find_nearest_cb(), insert(), nearest_add_in_range(), and nearest_ordered_insert().

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

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

Referenced by deduplicate().

◆ deduplicate_recursive()

void deduplicate_recursive	(	const DeDuplicateParams *	p,
		uint	i )

static

Definition at line 810 of file kdtree_impl.h.

References KDTreeNode::co, KDTreeNode::d, deduplicate_recursive(), DeDuplicateParams::duplicates, DeDuplicateParams::duplicates_found, i, KDTreeNode::index, KD_NODE_UNSET, KDTreeNode, KDTreeNode::left, len_squared_vnvn(), DeDuplicateParams::nodes, DeDuplicateParams::range, DeDuplicateParams::range_sq, KDTreeNode::right, DeDuplicateParams::search, and DeDuplicateParams::search_co.

Referenced by calc_duplicates_fast(), and deduplicate_recursive().

◆ find_nearest()

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

Find nearest returns index, and -1 if no node is found.

Definition at line 237 of file kdtree_impl.h.

References BLI_assert, KDTreeNode::co, copy_vn_vn(), KDTreeNode::d, find_nearest(), KDTreeNode::index, KD_DIMS, KD_NODE_UNSET, KD_STACK_INIT, KDTree, KDTreeNearest, KDTreeNode, KDTreeNode::left, len_squared_vnvn(), MEM_freeN(), realloc_nodes(), KDTreeNode::right, sqrtf, tree, and UNLIKELY.

◆ 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(), 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_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 579 of file kdtree_impl.h.

References BLI_kdtree_nd_, find_nearest_n(), find_nearest_n_with_len_squared_cb(), KD_DIMS, KDTree, KDTreeNearest, 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(*	len_sq_fn )(const float co_search[KD_DIMS], const float co_test[KD_DIMS], const void *user_data),
		const void *	user_data )

Definition at line 465 of file kdtree_impl.h.

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

◆ free()

void BLI_kdtree_nd_ free ( KDTree * tree )

Definition at line 116 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(), GHOST_SystemCocoa::handleDraggingEvent(), GHOST_SystemWayland::hasClipboardImage(), GHOST_SystemWin32::hasClipboardImage(), IFileStream::IFileStream(), imb_free_dds_buffer(), 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(), uiLayout::op_enum(), blender::ed::greasepencil::polyline_detect_corners(), blender::ed::greasepencil::polyline_fit_curve(), processEvent(), uiLayout::prop_enum(), uiLayout::props_enum(), 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(), 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] )

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

Definition at line 127 of file kdtree_impl.h.

References BLI_assert, KDTreeNode::co, copy_vn_vn(), KDTreeNode::d, KDTreeNode::index, insert(), KD_DIMS, KD_NODE_UNSET, KDTree, KDTreeNode, KDTreeNode::left, KDTreeNode::right, and tree.

◆ kdtree_balance()

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

static

Definition at line 149 of file kdtree_impl.h.

References KDTreeNode::co, KDTreeNode::d, i, KD_DIMS, KD_NODE_UNSET, kdtree_balance(), KDTreeNode, KDTreeNode_head, KDTreeNode::left, left, KDTreeNode::right, and SWAP.

Referenced by balance(), and kdtree_balance().

◆ kdtree_cmp_bool()

int kdtree_cmp_bool	(	const bool	a,
		const bool	b )

static

Definition at line 1004 of file kdtree_impl.h.

References b.

Referenced by kdtree_node_cmp_deduplicate().

◆ kdtree_node_cmp_deduplicate()

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

static

Definition at line 1012 of file kdtree_impl.h.

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

Referenced by deduplicate().

◆ kdtree_order()

blender::Vector< int > 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 783 of file kdtree_impl.h.

References i, KDTreeNode::index, KDTree, KDTreeNode, and tree.

Referenced by calc_duplicates_fast().

◆ len_squared_vnvn()

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

static

Definition at line 77 of file kdtree_impl.h.

References KD_DIMS, and square_f().

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

◆ len_squared_vnvn_cb()

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

static

Definition at line 86 of file kdtree_impl.h.

References KD_DIMS, and len_squared_vnvn().

Referenced by find_nearest_n_with_len_squared_cb(), and range_search_with_len_squared_cb().

◆ nearest_add_in_range()

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

Definition at line 601 of file kdtree_impl.h.

References KDTreeNearest::co, copy_vn_vn(), KDTreeNearest::dist, KDTreeNearest::index, KD_DIMS, KD_FOUND_ALLOC_INC, KDTreeNearest, KDTreeNode, MEM_reallocN_id, sqrtf, and UNLIKELY.

Referenced by range_search_with_len_squared_cb().

◆ nearest_cmp_dist()

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

static

Definition at line 588 of file kdtree_impl.h.

References b, KDTreeNearest::dist, and KDTreeNearest.

Referenced by range_search_with_len_squared_cb().

◆ nearest_ordered_insert()

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

Definition at line 440 of file kdtree_impl.h.

References copy_vn_vn(), KDTreeNearest::dist, i, KDTreeNearest::index, KD_DIMS, and KDTreeNearest.

Referenced by find_nearest_n_with_len_squared_cb().

◆ new()

KDTree *BLI_kdtree_nd_ new ( uint nodes_len_capacity )

Creates or free a kdtree

Definition at line 98 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_WindowWayland::GHOST_WindowWayland(), blender::gpu::GLShader::post_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 704 of file kdtree_impl.h.

References BLI_kdtree_nd_, KD_DIMS, KDTree, KDTreeNearest, range_search(), 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(*	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 713 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_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(*	len_sq_fn )(const float co_search[KD_DIMS], const float co_test[KD_DIMS], const void *user_data),
		const void *	user_data )

Definition at line 622 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, KDTreeNearest, KDTreeNode, KDTreeNode::left, len_squared_vnvn_cb(), MEM_freeN(), nearest_add_in_range(), nearest_cmp_dist(), range_search_with_len_squared_cb(), realloc_nodes(), KDTreeNode::right, tree, and UNLIKELY.

◆ realloc_nodes()

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

static

Definition at line 221 of file kdtree_impl.h.

References KD_NEAR_ALLOC_INC, MEM_freeN(), and MEM_malloc_arrayN().

Referenced by find_nearest(), find_nearest_cb(), find_nearest_n_with_len_squared_cb(), range_search_cb(), and range_search_with_len_squared_cb().

Classes

Macros

Functions

Macro Definition Documentation

◆ _BLI_KDTREE_CONCAT

◆ _BLI_KDTREE_CONCAT_AUX

◆ BLI_kdtree_nd_

◆ KD_FOUND_ALLOC_INC

◆ KD_NEAR_ALLOC_INC

◆ KD_NODE_ROOT_IS_INIT

◆ KD_NODE_UNSET

◆ KD_STACK_INIT

◆ NODE_TEST_NEAREST

Function Documentation

◆ balance()

◆ calc_duplicates_cb()

◆ calc_duplicates_fast()

◆ copy_vn_vn()

◆ deduplicate()

◆ deduplicate_recursive()

◆ find_nearest()

◆ find_nearest_cb()

◆ find_nearest_n()

◆ find_nearest_n_with_len_squared_cb()

◆ free()

◆ insert()

◆ kdtree_balance()

◆ kdtree_cmp_bool()

◆ kdtree_node_cmp_deduplicate()

◆ kdtree_order()

◆ len_squared_vnvn()

◆ len_squared_vnvn_cb()

◆ nearest_add_in_range()

◆ nearest_cmp_dist()

◆ nearest_ordered_insert()

◆ new()

◆ range_search()

◆ range_search_cb()

◆ range_search_with_len_squared_cb()

◆ realloc_nodes()