[Bf-blender-cvs] [d1b9b838be8] master: BLI_kdtree: add 2D kdtree support

[Campbell Barton]

Commit: d1b9b838be8a09735f52637fecdd2a8200eb9862
Author: Campbell Barton
Date:   Wed Mar 20 00:57:52 2019 +1100
Branches: master
https://developer.blender.org/rBd1b9b838be8a09735f52637fecdd2a8200eb9862

BLI_kdtree: add 2D kdtree support

Some users of the 3D versions were storing 2D data in it.

Using a 3D tree for 2D data adds a spatially redundant branch
every 3rd level, as well as some extra memory use, best avoid this.

===================================================================

M	source/blender/blenlib/BLI_kdtree.h
M	source/blender/blenlib/CMakeLists.txt
A	source/blender/blenlib/intern/kdtree_2d.c

===================================================================

diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h
index af10a448423..18f3236a310 100644
--- a/source/blender/blenlib/BLI_kdtree.h
+++ b/source/blender/blenlib/BLI_kdtree.h
@@ -22,6 +22,17 @@
  * \brief A kd-tree for nearest neighbor search.
  */
 
+/* 2D version */
+#define KD_DIMS 2
+#define KDTREE_PREFIX_ID BLI_kdtree_2d
+#define KDTree KDTree_2d
+#define KDTreeNearest KDTreeNearest_2d
+#include "BLI_kdtree_impl.h"
+#undef KD_DIMS
+#undef KDTree
+#undef KDTreeNearest
+#undef KDTREE_PREFIX_ID
+
 /* 3D version */
 #define KD_DIMS 3
 #define KDTREE_PREFIX_ID BLI_kdtree_3d
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index d740fa03e70..fef24c059e7 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -75,6 +75,7 @@ set(SRC
 	intern/hash_mm2a.c
 	intern/hash_mm3.c
 	intern/jitter_2d.c
+	intern/kdtree_2d.c
 	intern/kdtree_3d.c
 	intern/kdtree_4d.c
 	intern/lasso_2d.c
diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/intern/kdtree_2d.c
similarity index 55%
copy from source/blender/blenlib/BLI_kdtree.h
copy to source/blender/blenlib/intern/kdtree_2d.c
index af10a448423..8ad55e2d964 100644
--- a/source/blender/blenlib/BLI_kdtree.h
+++ b/source/blender/blenlib/intern/kdtree_2d.c
@@ -14,34 +14,12 @@
  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  */
 
-#ifndef __BLI_KDTREE_H__
-#define __BLI_KDTREE_H__
-
 /** \file
  * \ingroup bli
- * \brief A kd-tree for nearest neighbor search.
  */
 
-/* 3D version */
-#define KD_DIMS 3
-#define KDTREE_PREFIX_ID BLI_kdtree_3d
-#define KDTree KDTree_3d
-#define KDTreeNearest KDTreeNearest_3d
-#include "BLI_kdtree_impl.h"
-#undef KD_DIMS
-#undef KDTree
-#undef KDTreeNearest
-#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__ */
+#define KD_DIMS 2
+#define KDTREE_PREFIX_ID BLI_kdtree_2d
+#define KDTree KDTree_2d
+#define KDTreeNearest KDTreeNearest_2d
+#  include "kdtree_impl.h"