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