Blender
V3.3
|
A KD-tree for nearest neighbor search. More...
Go to the source code of this file.
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 |
Variables | |
void BLI_kdtree_nd_() int BLI_kdtree_nd_() int BLI_kdtree_nd_() int BLI_kdtree_nd_() | ATTR_WARN_UNUSED_RESULT |
A KD-tree for nearest neighbor search.
Definition in file BLI_kdtree_impl.h.
#define _BLI_CONCAT | ( | MACRO_ARG1, | |
MACRO_ARG2 | |||
) | _BLI_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) |
Definition at line 12 of file BLI_kdtree_impl.h.
#define _BLI_CONCAT_AUX | ( | MACRO_ARG1, | |
MACRO_ARG2 | |||
) | MACRO_ARG1##MACRO_ARG2 |
Definition at line 11 of file BLI_kdtree_impl.h.
#define BLI_kdtree_nd_ | ( | id | ) | _BLI_CONCAT(KDTREE_PREFIX_ID, _##id) |
Definition at line 13 of file BLI_kdtree_impl.h.
Definition at line 1 of file BLI_kdtree_impl.h.
typedef struct KDTreeNearest KDTreeNearest |
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.
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.
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. |
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.
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.
void BLI_kdtree_nd_() 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(*)(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.
filter_cb | Filter 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.
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 | ||
) |
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(*)(const float co_search[KD_DIMS], const float co_test[KD_DIMS], const void *user_data) | len_sq_fn, | ||
const void * | user_data | ||
) |
Versions of find/range search that take a squared distance callback to support bias.
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().
void BLI_kdtree_nd_() insert | ( | KDTree * | tree, |
int | index, | ||
const float | co[KD_DIMS] | ||
) |
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().
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 | ||
) |
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.
search_cb | Called for every node found in range, false return value performs an early exit. |
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.
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(*)(const float co_search[KD_DIMS], const float co_test[KD_DIMS], const void *user_data) | len_sq_fn, | ||
const void * | user_data | ||
) |
int BLI_kdtree_nd_() int BLI_kdtree_nd_() ATTR_WARN_UNUSED_RESULT |
Definition at line 45 of file BLI_kdtree_impl.h.