Commit: eb1cde5a81d6cedb6ce0bcd885b5798184034a02
Author: Campbell Barton
Date: Sun Jun 11 19:07:18 2017 +1000
Branches: master
https://developer.blender.org/rBeb1cde5a81d6cedb6ce0bcd885b5798184034a02
GTest: initial kdopbvh test
Currently only find-nearest, ray-casting needs to be added.
===================================================================
A tests/gtests/blenlib/BLI_kdopbvh_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/tests/gtests/blenlib/BLI_kdopbvh_test.cc
b/tests/gtests/blenlib/BLI_kdopbvh_test.cc
new file mode 100644
index 00000000000..e65f0fafa67
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_kdopbvh_test.cc
@@ -0,0 +1,91 @@
+/* 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"
+}
+
+/* -------------------------------------------------------------------- */
+/* 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(1, BLI_bvhtree_get_size(tree));
+
+ 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);
+ float (*points)[3] = (float (*)[3])MEM_mallocN(sizeof(float[3]) *
points_len, __func__);
+ 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_TRUE(j >= 0 && 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/CMakeLists.txt
b/tests/gtests/blenlib/CMakeLists.txt
index a190d9cd8c5..8b013e7a7a6 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -37,6 +37,7 @@ set(CMAKE_EXE_LINKER_FLAGS_DEBUG
"${CMAKE_EXE_LINKER_FLAGS_DEBUG} ${PLATFORM_LIN
BLENDER_TEST(BLI_array_store "bf_blenlib")
BLENDER_TEST(BLI_array_utils "bf_blenlib")
+BLENDER_TEST(BLI_kdopbvh "bf_blenlib;bf_intern_eigen")
BLENDER_TEST(BLI_stack "bf_blenlib")
BLENDER_TEST(BLI_math_color "bf_blenlib")
BLENDER_TEST(BLI_math_geom "bf_blenlib;bf_intern_eigen")
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
