diff options
author | Campbell Barton <ideasman42@gmail.com> | 2019-03-18 03:22:48 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2019-03-19 16:30:45 +0300 |
commit | 0719d5fa0c8244feb70efa330b10f103a6da2f3c (patch) | |
tree | 60eda71273eeeaacbaadf61fa68f95b876032f87 /source/blender/blenlib/BLI_kdtree_impl.h | |
parent | e72dc667c4d3ef0b4a4c306dd6b12cae9d37287b (diff) |
BLI_kdtree: refactor to support different numbers of dimensions
This moves logic into kdtree_impl.h which is included in a source
file that defines the number of dimensions - so we can easily support
different numbers of dimensions as needed
(currently 3D and 4D are supported).
Macro use isn't so nice but avoids a lot of duplicate code.
Diffstat (limited to 'source/blender/blenlib/BLI_kdtree_impl.h')
-rw-r--r-- | source/blender/blenlib/BLI_kdtree_impl.h | 86 |
1 files changed, 86 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_kdtree_impl.h b/source/blender/blenlib/BLI_kdtree_impl.h new file mode 100644 index 00000000000..08b66c16d3e --- /dev/null +++ b/source/blender/blenlib/BLI_kdtree_impl.h @@ -0,0 +1,86 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/** \file + * \ingroup bli + * \brief A kd-tree for nearest neighbor search. + */ + +#include "BLI_compiler_attrs.h" + +#define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1 ## MACRO_ARG2 +#define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) +#define BLI_kdtree_nd_(id) _CONCAT(KDTREE_PREFIX_ID, _##id) + +struct KDTree; +typedef struct KDTree KDTree; + +typedef struct KDTreeNearest { + int index; + float dist; + float co[KD_DIMS]; +} KDTreeNearest; + +KDTree *BLI_kdtree_nd_(new)(unsigned int maxsize); +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, 3); +int BLI_kdtree_nd_(find_nearest)( + const KDTree *tree, const float co[KD_DIMS], + KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2); + +int BLI_kdtree_nd_(find_nearest_n)( + const KDTree *tree, const float co[KD_DIMS], + KDTreeNearest *r_nearest, + const uint nearest_len_capacity) ATTR_NONNULL(1, 2, 3); + +int BLI_kdtree_nd_(range_search)( + const KDTree *tree, const float co[KD_DIMS], + KDTreeNearest **r_nearest, + const float range) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT; + +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, 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_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) ATTR_NONNULL(1, 2, 3); +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) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT; + +#undef _CONCAT_AUX +#undef _CONCAT +#undef BLI_kdtree_nd_ |