Commit: 0719d5fa0c8244feb70efa330b10f103a6da2f3c
Author: Campbell Barton
Date: Mon Mar 18 11:22:48 2019 +1100
Branches: master
https://developer.blender.org/rB0719d5fa0c8244feb70efa330b10f103a6da2f3c
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.
===================================================================
M source/blender/blenlib/BLI_kdtree.h
A source/blender/blenlib/BLI_kdtree_impl.h
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/kdtree_3d.c
A source/blender/blenlib/intern/kdtree_4d.c
R083 source/blender/blenlib/intern/BLI_kdtree.c
source/blender/blenlib/intern/kdtree_impl.h
===================================================================
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__ */
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_
diff --git a/source/blender/blenlib/CMakeLists.txt
b/source/blender/blenlib/CMakeLists.txt
index f1aac6cd5b2..d740fa03e70 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -45,7 +45,6 @@ set(SRC
intern/BLI_heap.c
intern/BLI_heap_simple.c
intern/BLI_kdopbvh.c
- intern/BLI_kdtree.c
intern/BLI_linklist.c
intern/BLI_linklist_lockfree.c
intern/BLI_memarena.c
@@ -76,8 +75,9 @@ set(SRC
intern/hash_mm2a.c
intern/hash_mm3.c
intern/jitter_2d.c
+ intern/kdtree_3d.c
+ intern/kdtree_4d.c
intern/lasso_2d.c
- intern/list_sort_impl.h
intern/listbase.c
intern/math_base.c
intern/math_base_inline.c
@@ -124,6 +124,10 @@ set(SRC
intern/winstuff.c
intern/winstuff_dir.c
+ # Header as source (included in C files above).
+ intern/kdtree_impl.h
+ intern/list_sort_impl.h
+
BLI_alloca.h
BLI_args.h
BLI_array.h
@@ -167,6 +171,7 @@ set(SRC
BLI_jitter_2d.h
BLI_kdopbvh.h
BLI_kdtree.h
+ BLI_kdtree_impl.h
BLI_lasso_2d.h
BLI_link_utils.h
BLI_linklist.h
diff --git a/source/blender/blenlib/intern/kdtree_3d.c
b/source/blender/blenlib/intern/kdtree_3d.c
new file mode 100644
index 00000000000..1da93772aa9
--- /dev/null
+++ b/source/blender/blenlib/intern/kdtree_3d.c
@@ -0,0 +1,25 @@
+/*
+ * 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
+ */
+
+#define KD_DIMS 3
+#define KDTREE_PREFIX_ID BLI_kdtree
+# include "kdtree_impl.h"
+#undef DIMS
+#undef KDTREE_PREFIX_ID
diff --git a/source/blender/blenlib/intern/kdtree_4d.c
b/source/blender/blenlib/intern/kdtree_4d.c
new file mode 100644
index 00000000000..cdddf5e3168
--- /dev/null
+++ b/source/blender/blenlib/intern/kdtree_4d.c
@@ -0,0 +1,25 @@
+/*
+ * 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
+ */
+
+#define KD_DIMS 4
+#define KDTREE_PREFIX_ID BLI_kdtree_4d
+#define KDTree KDTree_4d
+#define KDTreeNearest KDTreeNearest_4d
+#include "kdtree_impl.h"
diff --git a/source/blender/blenlib/intern/BLI_kdtree.c
b/source/blender/blenlib/intern/kdtree_impl.h
similarity index 83%
rename from source/blender/blenlib/intern/BLI_kdtree.c
rename to source/blender/blenlib/intern/kdtree_impl.h
i
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
Bf-blender-cvs@blender.org
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
