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.

1 files changed, 17 insertions, 52 deletions

diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h
index fd404fa5aab..eb0421eaec1 100644
--- a/source/blender/blenlib/BLI_kdtree.h
+++ b/source/blender/blenlib/BLI_kdtree.h
@@ -22,57 +22,22 @@
  * \brief A kd-tree for nearest neighbor search.
  */
 
-#include "BLI_compiler_attrs.h"
-
-struct KDTree;
-typedef struct KDTree KDTree;
-
-typedef struct KDTreeNearest {
-	int index;
-	float dist;
-	float co[3];
-} KDTreeNearest;
-
-KDTree *BLI_kdtree_new(unsigned int maxsize);
-void BLI_kdtree_free(KDTree *tree);
-void BLI_kdtree_balance(KDTree *tree) ATTR_NONNULL(1);
-
-void BLI_kdtree_insert(
-        KDTree *tree, int index,
-        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;
+/* 3D version */
+#define KD_DIMS 3
+#define KDTREE_PREFIX_ID BLI_kdtree
+#include "BLI_kdtree_impl.h"
+#undef KD_DIMS
+#undef KDTREE_PREFIX_ID
+
+/* 4D version */
+#define KD_DIMS 4
+#define KDTREE_PREFIX_ID BLI_kdtree_4d
+#define KDTree KDTree_4d
+#define KDTreeNearest KDTreeNearest_4d
+#include "BLI_kdtree_impl.h"
+#undef KD_DIMS
+#undef KDTree
+#undef KDTreeNearest
+#undef KDTREE_PREFIX_ID
 
 #endif  /* __BLI_KDTREE_H__ */