6 files changed, 136 insertions, 13 deletions
diff --git a/tests/gtests/blenlib/BLI_kdopbvh_test.cc b/tests/gtests/blenlib/BLI_kdopbvh_test.cc
new file mode 100644
index 00000000000..74db7cf20a0
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_kdopbvh_test.cc
@@ -0,0 +1,97 @@
+/* Apache License, Version 2.0 */
+
+#include "testing/testing.h"
+
+/* TODO: ray intersection, overlap ... etc.*/
+
+extern "C" {
+#include "BLI_compiler_attrs.h"
+#include "BLI_kdopbvh.h"
+#include "BLI_rand.h"
+#include "BLI_math_vector.h"
+#include "MEM_guardedalloc.h"
+}
+
+#include "stubs/bf_intern_eigen_stubs.h"
+
+/* -------------------------------------------------------------------- */
+/* Helper Functions */
+
+static void rng_v3_round(
+        float *coords, int coords_len,
+        struct RNG *rng, int round, float scale)
+{
+	for (int i = 0; i < coords_len; i++) {
+		float f = BLI_rng_get_float(rng) * 2.0f - 1.0f;
+		coords[i] = ((float)((int)(f * round)) / (float)round) * scale;
+	}
+}
+
+/* -------------------------------------------------------------------- */
+/* Tests */
+
+TEST(kdopbvh, Empty)
+{
+	BVHTree *tree = BLI_bvhtree_new(0, 0.0, 8, 8);
+	BLI_bvhtree_balance(tree);
+	EXPECT_EQ(0, BLI_bvhtree_get_size(tree));
+	BLI_bvhtree_free(tree);
+}
+
+TEST(kdopbvh, Single)
+{
+	BVHTree *tree = BLI_bvhtree_new(1, 0.0, 8, 8);
+	{
+		float co[3] = {0};
+		BLI_bvhtree_insert(tree, 0, co, 1);
+	}
+
+	EXPECT_EQ(BLI_bvhtree_get_size(tree), 1);
+
+	BLI_bvhtree_balance(tree);
+	BLI_bvhtree_free(tree);
+}
+
+/**
+ * Note that a small epsilon is added to the BVH nodes bounds, even if we pass in zero.
+ * Use rounding to ensure very close nodes don't cause the wrong node to be found as nearest.
+ */
+static void find_nearest_points_test(int points_len, float scale, int round, int random_seed)
+{
+	struct RNG *rng = BLI_rng_new(random_seed);
+	BVHTree *tree = BLI_bvhtree_new(points_len, 0.0, 8, 8);
+
+	void *mem = MEM_mallocN(sizeof(float[3]) * points_len, __func__);
+	float (*points)[3] = (float (*)[3])mem;
+
+	for (int i = 0; i < points_len; i++) {
+		rng_v3_round(points[i], 3, rng, round, scale);
+		BLI_bvhtree_insert(tree, i, points[i], 1);
+	}
+	BLI_bvhtree_balance(tree);
+	/* first find each point */
+	for (int i = 0; i < points_len; i++) {
+		const int j = BLI_bvhtree_find_nearest(tree, points[i], NULL, NULL, NULL);
+		if (j != i) {
+#if 0
+			const float dist = len_v3v3(points[i], points[j]);
+			if (dist > (1.0f / (float)round)) {
+				printf("%.15f (%d %d)\n", dist, i, j);
+				print_v3_id(points[i]);
+				print_v3_id(points[j]);
+				fflush(stdout);
+			}
+#endif
+			EXPECT_GE(j, 0);
+			EXPECT_LT(j, points_len);
+			EXPECT_EQ_ARRAY(points[i], points[j], 3);
+		}
+	}
+	BLI_bvhtree_free(tree);
+	BLI_rng_free(rng);
+	MEM_freeN(points);
+}
+
+TEST(kdopbvh, FindNearest_1)		{ find_nearest_points_test(1, 1.0, 1000, 1234); }
+TEST(kdopbvh, FindNearest_2)		{ find_nearest_points_test(2, 1.0, 1000, 123); }
+TEST(kdopbvh, FindNearest_500)		{ find_nearest_points_test(500, 1.0, 1000, 12); }
diff --git a/tests/gtests/blenlib/BLI_math_geom_test.cc b/tests/gtests/blenlib/BLI_math_geom_test.cc
index cd15a4eb8ff..92e2532392e 100644
--- a/tests/gtests/blenlib/BLI_math_geom_test.cc
+++ b/tests/gtests/blenlib/BLI_math_geom_test.cc
@@ -4,6 +4,8 @@
 
 #include "BLI_math.h"
 
+#include "stubs/bf_intern_eigen_stubs.h"
+
 TEST(math_geom, DistToLine2DSimple)
 {
 	float p[2] = {5.0f, 1.0f},
diff --git a/tests/gtests/blenlib/BLI_path_util_test.cc b/tests/gtests/blenlib/BLI_path_util_test.cc
index ef469da50b2..41fad661ea9 100644
--- a/tests/gtests/blenlib/BLI_path_util_test.cc
+++ b/tests/gtests/blenlib/BLI_path_util_test.cc
@@ -41,7 +41,7 @@ const char *GHOST_getSystemDir(int version, const char *versionstr)
 
 struct ImBuf;
 void IMB_freeImBuf(struct ImBuf *ibuf) {}
-struct ImBuf *IMB_dupImBuf(struct ImBuf *ibuf) {return NULL;}
+struct ImBuf *IMB_dupImBuf(const ImBuf *ibuf) {return NULL;}
 
 #ifdef __linux__
 char *zLhm65070058860608_br_find_exe(const char *default_exe)
diff --git a/tests/gtests/blenlib/BLI_polyfill2d_test.cc b/tests/gtests/blenlib/BLI_polyfill2d_test.cc
index 5d112751fa0..eefcdd6e85e 100644
--- a/tests/gtests/blenlib/BLI_polyfill2d_test.cc
+++ b/tests/gtests/blenlib/BLI_polyfill2d_test.cc
@@ -27,6 +27,8 @@ extern "C" {
 #endif
 }
 
+#include "stubs/bf_intern_eigen_stubs.h"
+
 static void polyfill_to_obj(
         const char *id,
         const float poly[][2], const unsigned int poly_tot,
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index a190d9cd8c5..ffdb8d08d31 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -34,23 +34,27 @@ include_directories(${INC})
 set(CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} ${PLATFORM_LINKFLAGS}")
 set(CMAKE_EXE_LINKER_FLAGS_DEBUG "${CMAKE_EXE_LINKER_FLAGS_DEBUG} ${PLATFORM_LINKFLAGS_DEBUG}")
 
+if(WIN32)
+	set(BLI_path_util_extra_libs "bf_blenlib;bf_intern_utfconv;extern_wcwidth;${ZLIB_LIBRARIES}")
+else()
+	set(BLI_path_util_extra_libs "bf_blenlib;extern_wcwidth;${ZLIB_LIBRARIES}")
+endif()
 
 BLENDER_TEST(BLI_array_store "bf_blenlib")
 BLENDER_TEST(BLI_array_utils "bf_blenlib")
-BLENDER_TEST(BLI_stack "bf_blenlib")
-BLENDER_TEST(BLI_math_color "bf_blenlib")
-BLENDER_TEST(BLI_math_geom "bf_blenlib;bf_intern_eigen")
+BLENDER_TEST(BLI_ghash "bf_blenlib")
+BLENDER_TEST(BLI_hash_mm2a "bf_blenlib")
+BLENDER_TEST(BLI_kdopbvh "bf_blenlib")
+BLENDER_TEST(BLI_listbase "bf_blenlib")
 BLENDER_TEST(BLI_math_base "bf_blenlib")
+BLENDER_TEST(BLI_math_color "bf_blenlib")
+BLENDER_TEST(BLI_math_geom "bf_blenlib")
+BLENDER_TEST(BLI_path_util "${BLI_path_util_extra_libs}")
+BLENDER_TEST(BLI_polyfill2d "bf_blenlib")
+BLENDER_TEST(BLI_stack "bf_blenlib")
 BLENDER_TEST(BLI_string "bf_blenlib")
 BLENDER_TEST(BLI_string_utf8 "bf_blenlib")
-if(WIN32)
-	BLENDER_TEST(BLI_path_util "bf_blenlib;bf_intern_utfconv;extern_wcwidth;${ZLIB_LIBRARIES}")
-else()
-	BLENDER_TEST(BLI_path_util "bf_blenlib;extern_wcwidth;${ZLIB_LIBRARIES}")
-endif()
-BLENDER_TEST(BLI_polyfill2d "bf_blenlib;bf_intern_eigen")
-BLENDER_TEST(BLI_listbase "bf_blenlib")
-BLENDER_TEST(BLI_hash_mm2a "bf_blenlib")
-BLENDER_TEST(BLI_ghash "bf_blenlib")
 
 BLENDER_TEST_PERFORMANCE(BLI_ghash_performance "bf_blenlib")
+
+unset(BLI_path_util_extra_libs)
diff --git a/tests/gtests/blenlib/stubs/bf_intern_eigen_stubs.h b/tests/gtests/blenlib/stubs/bf_intern_eigen_stubs.h
new file mode 100644
index 00000000000..dad77a257d5
--- /dev/null
+++ b/tests/gtests/blenlib/stubs/bf_intern_eigen_stubs.h
@@ -0,0 +1,18 @@
+/* Apache License, Version 2.0 */
+
+extern "C" {
+
+bool EIG_self_adjoint_eigen_solve(const int size, const float *matrix, float *r_eigen_values, float *r_eigen_vectors)
+{
+	BLI_assert(0);
+	UNUSED_VARS(size, matrix, r_eigen_values, r_eigen_vectors);
+	return false;
+}
+
+void EIG_svd_square_matrix(const int size, const float *matrix, float *r_U, float *r_S, float *r_V)
+{
+	BLI_assert(0);
+	UNUSED_VARS(size, matrix, r_U, r_S, r_V);
+}
+
+}