1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
/* SPDX-License-Identifier: Apache-2.0 */
#include "testing/testing.h"
/* TODO: ray intersection, overlap ... etc. */
#include "MEM_guardedalloc.h"
#include "BLI_compiler_attrs.h"
#include "BLI_kdopbvh.h"
#include "BLI_math_vector.h"
#include "BLI_rand.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_len(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_len(tree), 1);
BLI_bvhtree_balance(tree);
BLI_bvhtree_free(tree);
}
static void optimal_check_callback(void *userdata,
int index,
const float co[3],
BVHTreeNearest *nearest)
{
float(*points)[3] = (float(*)[3])userdata;
/* BVH_NEAREST_OPTIMAL_ORDER should hit the right node on the first try */
EXPECT_EQ(nearest->index, -1);
EXPECT_EQ_ARRAY(co, points[index], 3);
nearest->index = index;
nearest->dist_sq = len_squared_v3v3(co, points[index]);
}
/**
* 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, bool optimal = false)
{
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 */
BVHTree_NearestPointCallback callback = optimal ? optimal_check_callback : nullptr;
int flags = optimal ? BVH_NEAREST_OPTIMAL_ORDER : 0;
for (int i = 0; i < points_len; i++) {
const int j = BLI_bvhtree_find_nearest_ex(tree, points[i], nullptr, callback, points, flags);
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);
}
TEST(kdopbvh, OptimalFindNearest_1)
{
find_nearest_points_test(1, 1.0, 1000, 1234, true);
}
TEST(kdopbvh, OptimalFindNearest_2)
{
find_nearest_points_test(2, 1.0, 1000, 123, true);
}
TEST(kdopbvh, OptimalFindNearest_500)
{
find_nearest_points_test(500, 1.0, 1000, 12, true);
}
|
