Blender  V3.3
BLI_kdopbvh_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 
5 /* TODO: ray intersection, overlap ... etc. */
6 
7 #include "MEM_guardedalloc.h"
8 
9 #include "BLI_compiler_attrs.h"
10 #include "BLI_kdopbvh.h"
11 #include "BLI_math_vector.h"
12 #include "BLI_rand.h"
13 
14 /* -------------------------------------------------------------------- */
15 /* Helper Functions */
16 
17 static void rng_v3_round(float *coords, int coords_len, struct RNG *rng, int round, float scale)
18 {
19  for (int i = 0; i < coords_len; i++) {
20  float f = BLI_rng_get_float(rng) * 2.0f - 1.0f;
21  coords[i] = ((float)((int)(f * round)) / (float)round) * scale;
22  }
23 }
24 
25 /* -------------------------------------------------------------------- */
26 /* Tests */
27 
28 TEST(kdopbvh, Empty)
29 {
30  BVHTree *tree = BLI_bvhtree_new(0, 0.0, 8, 8);
34 }
35 
36 TEST(kdopbvh, Single)
37 {
38  BVHTree *tree = BLI_bvhtree_new(1, 0.0, 8, 8);
39  {
40  float co[3] = {0};
41  BLI_bvhtree_insert(tree, 0, co, 1);
42  }
43 
45 
48 }
49 
50 static void optimal_check_callback(void *userdata,
51  int index,
52  const float co[3],
53  BVHTreeNearest *nearest)
54 {
55  float(*points)[3] = (float(*)[3])userdata;
56 
57  /* BVH_NEAREST_OPTIMAL_ORDER should hit the right node on the first try */
58  EXPECT_EQ(nearest->index, -1);
59  EXPECT_EQ_ARRAY(co, points[index], 3);
60 
61  nearest->index = index;
62  nearest->dist_sq = len_squared_v3v3(co, points[index]);
63 }
64 
70  int points_len, float scale, int round, int random_seed, bool optimal = false)
71 {
72  struct RNG *rng = BLI_rng_new(random_seed);
73  BVHTree *tree = BLI_bvhtree_new(points_len, 0.0, 8, 8);
74 
75  void *mem = MEM_mallocN(sizeof(float[3]) * points_len, __func__);
76  float(*points)[3] = (float(*)[3])mem;
77 
78  for (int i = 0; i < points_len; i++) {
79  rng_v3_round(points[i], 3, rng, round, scale);
80  BLI_bvhtree_insert(tree, i, points[i], 1);
81  }
83 
84  /* first find each point */
86  int flags = optimal ? BVH_NEAREST_OPTIMAL_ORDER : 0;
87 
88  for (int i = 0; i < points_len; i++) {
89  const int j = BLI_bvhtree_find_nearest_ex(tree, points[i], nullptr, callback, points, flags);
90  if (j != i) {
91 #if 0
92  const float dist = len_v3v3(points[i], points[j]);
93  if (dist > (1.0f / (float)round)) {
94  printf("%.15f (%d %d)\n", dist, i, j);
95  print_v3_id(points[i]);
96  print_v3_id(points[j]);
97  fflush(stdout);
98  }
99 #endif
100  EXPECT_GE(j, 0);
101  EXPECT_LT(j, points_len);
102  EXPECT_EQ_ARRAY(points[i], points[j], 3);
103  }
104  }
106  BLI_rng_free(rng);
107  MEM_freeN(points);
108 }
109 
110 TEST(kdopbvh, FindNearest_1)
111 {
112  find_nearest_points_test(1, 1.0, 1000, 1234);
113 }
114 TEST(kdopbvh, FindNearest_2)
115 {
116  find_nearest_points_test(2, 1.0, 1000, 123);
117 }
118 TEST(kdopbvh, FindNearest_500)
119 {
120  find_nearest_points_test(500, 1.0, 1000, 12);
121 }
122 
123 TEST(kdopbvh, OptimalFindNearest_1)
124 {
125  find_nearest_points_test(1, 1.0, 1000, 1234, true);
126 }
127 TEST(kdopbvh, OptimalFindNearest_2)
128 {
129  find_nearest_points_test(2, 1.0, 1000, 123, true);
130 }
131 TEST(kdopbvh, OptimalFindNearest_500)
132 {
133  find_nearest_points_test(500, 1.0, 1000, 12, true);
134 }
typedef float(TangentPoint)[2]
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
int BLI_bvhtree_find_nearest_ex(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
Definition: BLI_kdopbvh.c:1567
void BLI_bvhtree_balance(BVHTree *tree)
Definition: BLI_kdopbvh.c:937
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
Definition: BLI_kdopbvh.c:854
void BLI_bvhtree_free(BVHTree *tree)
Definition: BLI_kdopbvh.c:926
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
Definition: BLI_kdopbvh.c:979
@ BVH_NEAREST_OPTIMAL_ORDER
Definition: BLI_kdopbvh.h:82
int BLI_bvhtree_get_len(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1034
void(* BVHTree_NearestPointCallback)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition: BLI_kdopbvh.h:94
static void optimal_check_callback(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
TEST(kdopbvh, Empty)
static void rng_v3_round(float *coords, int coords_len, struct RNG *rng, int round, float scale)
static void find_nearest_points_test(int points_len, float scale, int round, int random_seed, bool optimal=false)
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
#define print_v3_id(v)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
Random number functions.
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition: rand.cc:58
struct RNG * BLI_rng_new(unsigned int seed)
Definition: rand.cc:39
float BLI_rng_get_float(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: rand.cc:93
Read Guarded memory(de)allocation.
DEGForeachIDComponentCallback callback
void * tree
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
Definition: rand.cc:33
blender::RandomNumberGenerator rng
Definition: rand.cc:34