Changeset View
Changeset View
Standalone View
Standalone View
source/blender/blenlib/BLI_kdtree.h
| Show All 16 Lines | |||||
| #ifndef __BLI_KDTREE_H__ | #ifndef __BLI_KDTREE_H__ | ||||
| #define __BLI_KDTREE_H__ | #define __BLI_KDTREE_H__ | ||||
| /** \file | /** \file | ||||
| * \ingroup bli | * \ingroup bli | ||||
| * \brief A kd-tree for nearest neighbor search. | * \brief A kd-tree for nearest neighbor search. | ||||
| */ | */ | ||||
| #include "BLI_compiler_attrs.h" | /* 3D version */ | ||||
| #define KD_DIMS 3 | |||||
| struct KDTree; | #define KDTREE_PREFIX_ID BLI_kdtree | ||||
| typedef struct KDTree KDTree; | #include "BLI_kdtree_impl.h" | ||||
| #undef KD_DIMS | |||||
| typedef struct KDTreeNearest { | #undef KDTREE_PREFIX_ID | ||||
| int index; | |||||
| float dist; | /* 4D version */ | ||||
| float co[3]; | #define KD_DIMS 4 | ||||
| } KDTreeNearest; | #define KDTREE_PREFIX_ID BLI_kdtree_4d | ||||
| #define KDTree KDTree_4d | |||||
| KDTree *BLI_kdtree_new(unsigned int maxsize); | #define KDTreeNearest KDTreeNearest_4d | ||||
| void BLI_kdtree_free(KDTree *tree); | #include "BLI_kdtree_impl.h" | ||||
| void BLI_kdtree_balance(KDTree *tree) ATTR_NONNULL(1); | #undef KD_DIMS | ||||
| #undef KDTree | |||||
| void BLI_kdtree_insert( | #undef KDTreeNearest | ||||
| KDTree *tree, int index, | #undef KDTREE_PREFIX_ID | ||||
| const float co[3]) ATTR_NONNULL(1, 3); | |||||
| int BLI_kdtree_find_nearest( | |||||
| const KDTree *tree, const float co[3], | |||||
| KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2); | |||||
| #define BLI_kdtree_find_nearest_n(tree, co, r_nearest, nearest_len_capacity) \ | |||||
| BLI_kdtree_find_nearest_n_with_len_squared_cb(tree, co, r_nearest, nearest_len_capacity, NULL, NULL) | |||||
| #define BLI_kdtree_range_search(tree, co, r_nearest, range) \ | |||||
| BLI_kdtree_range_search_with_len_squared_cb(tree, co, r_nearest, range, NULL, NULL) | |||||
| int BLI_kdtree_find_nearest_cb( | |||||
| const KDTree *tree, const float co[3], | |||||
| int (*filter_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data, | |||||
| KDTreeNearest *r_nearest); | |||||
| void BLI_kdtree_range_search_cb( | |||||
| const KDTree *tree, const float co[3], float range, | |||||
| bool (*search_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data); | |||||
| int BLI_kdtree_calc_duplicates_fast( | |||||
| const KDTree *tree, const float range, bool use_index_order, | |||||
| int *doubles); | |||||
| /* Versions of find/range search that take a squared distance callback to support bias. */ | |||||
| int BLI_kdtree_find_nearest_n_with_len_squared_cb( | |||||
| const KDTree *tree, const float co[3], | |||||
| KDTreeNearest *r_nearest, | |||||
| const uint nearest_len_capacity, | |||||
| float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), | |||||
| const void *user_data) ATTR_NONNULL(1, 2, 3); | |||||
| int BLI_kdtree_range_search_with_len_squared_cb( | |||||
| const KDTree *tree, const float co[3], | |||||
| KDTreeNearest **r_nearest, | |||||
| const float range, | |||||
| float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), | |||||
| const void *user_data) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT; | |||||
| #endif /* __BLI_KDTREE_H__ */ | #endif /* __BLI_KDTREE_H__ */ | ||||