Blender V5.3
BLI_kdtree_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include <algorithm>
6#include <string>
7
8#include "testing/testing.h"
9
10#include "BLI_array.hh"
11#include "BLI_array_utils.hh"
12#include "BLI_index_mask.hh"
13#include "BLI_kdtree_new.hh"
14#include "BLI_math_vector.hh"
15#include "BLI_rand.hh"
16#include "BLI_task_c.hh"
17#include "BLI_threads.hh"
18#include "BLI_vector.hh"
19
20namespace blender::tests {
21
23
24static Array<float3> random_points(const int points_num, const int seed = 0)
25{
27 Array<float3> positions(points_num);
28 for (const int i : positions.index_range()) {
29 positions[i] = float3(random.get_float(), random.get_float(), random.get_float());
30 }
31 return positions;
32}
33
36 const Span<int> indices,
37 const float3 &position)
38{
40 for (const int i : indices) {
41 result.append({i, math::distance_squared(positions[i], position)});
42 }
43 std::ranges::sort(result, [](const Nearest &a, const Nearest &b) {
44 return a.distance_sq < b.distance_sq || (a.distance_sq == b.distance_sq && a.index < b.index);
45 });
46 return result;
47}
48
50static Array<float3> grid_points(const int side)
51{
52 Array<float3> positions(side * side * side);
53 int i = 0;
54 for (const int x : IndexRange(side)) {
55 for (const int y : IndexRange(side)) {
56 for (const int z : IndexRange(side)) {
57 positions[i++] = float3(float(x), float(y), float(z));
58 }
59 }
60 }
61 return positions;
62}
63
64static Vector<int> all_indices(const int points_num)
65{
66 Vector<int> indices(points_num);
68 return indices;
69}
70
71TEST(kdtree, Empty)
72{
73 const Array<float3> positions(0);
74 const KDTreeNew<float3> tree(positions);
75 EXPECT_TRUE(tree.is_empty());
76 EXPECT_EQ(tree.size(), 0);
77 EXPECT_EQ(tree.find_nearest(float3(0.0f)), -1);
78 EXPECT_EQ(tree.count_in_radius(float3(0.0f), 100.0f), 0);
79
80 Array<Nearest> nearest(4);
81 EXPECT_EQ(tree.find_nearest_n(float3(0.0f), nearest), 0);
82
83 Vector<Nearest> in_radius;
84 EXPECT_EQ(tree.find_in_radius(float3(0.0f), 100.0f, in_radius), 0);
85}
86
87TEST(kdtree, SinglePoint)
88{
89 const Array<float3> positions = {float3(1.0f, 2.0f, 3.0f)};
90 const KDTreeNew<float3> tree(positions);
91 EXPECT_EQ(tree.size(), 1);
92
93 float distance_sq = -1.0f;
94 EXPECT_EQ(tree.find_nearest(float3(1.0f, 2.0f, 4.0f), &distance_sq), 0);
95 EXPECT_FLOAT_EQ(distance_sq, 1.0f);
96
97 /* The only point is filtered out. */
98 EXPECT_EQ(tree.find_nearest_filtered(float3(0.0f), [](const int /*index*/) { return false; }),
99 -1);
100}
101
102TEST(kdtree, FindNearest)
103{
104 const Array<float3> positions = random_points(1000);
105 const KDTreeNew<float3> tree(positions);
106 EXPECT_EQ(tree.size(), 1000);
107
108 const Vector<int> indices = all_indices(positions.size());
109 const Array<float3> queries = random_points(50, 1);
110 for (const float3 &query : queries) {
111 const Vector<Nearest> expected = brute_force_sorted(positions, indices, query);
112 float distance_sq = -1.0f;
113 const int index = tree.find_nearest(query, &distance_sq);
114 EXPECT_EQ(index, expected.first().index);
115 EXPECT_FLOAT_EQ(distance_sq, expected.first().distance_sq);
116 }
117}
118
119TEST(kdtree, FindNearestFiltered)
120{
121 const Array<float3> positions = random_points(500);
122 const KDTreeNew<float3> tree(positions);
123 const Vector<int> indices = all_indices(positions.size());
124
125 /* Skipping the search point itself is the common use of the filter. */
126 for (const int i : positions.index_range()) {
127 const Vector<Nearest> expected = brute_force_sorted(positions, indices, positions[i]);
128 ASSERT_EQ(expected.first().index, i);
129 const int index = tree.find_nearest_filtered(positions[i],
130 [&](const int other) { return other != i; });
131 EXPECT_EQ(index, expected[1].index);
132 }
133
134 /* Only even indices are accepted. */
135 const int index = tree.find_nearest_filtered(positions[3],
136 [](const int other) { return other % 2 == 0; });
137 ASSERT_GE(index, 0);
138 EXPECT_EQ(index % 2, 0);
139 const Vector<Nearest> expected = brute_force_sorted(positions, indices, positions[3]);
140 for (const Nearest &nearest : expected) {
141 if (nearest.index % 2 == 0) {
142 EXPECT_EQ(nearest.index, index);
143 break;
144 }
145 }
146}
147
148TEST(kdtree, FindNearestN)
149{
150 const Array<float3> positions = random_points(400);
151 const KDTreeNew<float3> tree(positions);
152 const Vector<int> indices = all_indices(positions.size());
153 const Array<float3> queries = random_points(20, 2);
154
155 for (const float3 &query : queries) {
156 const Vector<Nearest> expected = brute_force_sorted(positions, indices, query);
157 Array<Nearest> nearest(7);
158 const int found = tree.find_nearest_n(query, nearest);
159 ASSERT_EQ(found, 7);
160 for (const int i : IndexRange(found)) {
161 EXPECT_EQ(nearest[i].index, expected[i].index);
162 EXPECT_FLOAT_EQ(nearest[i].distance_sq, expected[i].distance_sq);
163 if (i > 0) {
164 EXPECT_LE(nearest[i - 1].distance_sq, nearest[i].distance_sq);
165 }
166 }
167 }
168}
169
170TEST(kdtree, FindNearestNMoreThanSize)
171{
172 const Array<float3> positions = random_points(5);
173 const KDTreeNew<float3> tree(positions);
174 Array<Nearest> nearest(10);
175 EXPECT_EQ(tree.find_nearest_n(float3(0.5f), nearest), 5);
176}
177
178TEST(kdtree, Radius)
179{
180 const Array<float3> positions = random_points(600);
181 const KDTreeNew<float3> tree(positions);
182 const Vector<int> indices = all_indices(positions.size());
183 const Array<float3> queries = random_points(20, 3);
184
185 for (const float3 &query : queries) {
186 for (const float radius : {0.05f, 0.2f, 2.0f}) {
187 Vector<Nearest> expected;
188 for (const Nearest &nearest : brute_force_sorted(positions, indices, query)) {
189 if (nearest.distance_sq <= radius * radius) {
190 expected.append(nearest);
191 }
192 }
193
194 Vector<Nearest> found;
195 EXPECT_EQ(tree.find_in_radius(query, radius, found), expected.size());
196 for (const int i : expected.index_range()) {
197 EXPECT_EQ(found[i].index, expected[i].index);
198 EXPECT_FLOAT_EQ(found[i].distance_sq, expected[i].distance_sq);
199 }
200
201 EXPECT_EQ(tree.count_in_radius(query, radius), expected.size());
202
203 Vector<int> visited;
204 tree.foreach_in_radius(query, radius, [&](const int index, const float distance_sq) {
205 EXPECT_FLOAT_EQ(distance_sq, math::distance_squared(positions[index], query));
206 visited.append(index);
207 });
208 std::ranges::sort(visited);
209 ASSERT_EQ(visited.size(), expected.size());
210 Vector<int> expected_indices;
211 for (const Nearest &nearest : expected) {
212 expected_indices.append(nearest.index);
213 }
214 std::ranges::sort(expected_indices);
215 EXPECT_EQ(visited, expected_indices);
216 }
217 }
218}
219
220TEST(kdtree, RadiusIsInclusive)
221{
222 /* A point exactly the radius away is inside it, matching #blender::kdtree_range_search_cb. */
223 const Array<float3> positions = grid_points(3);
224 const KDTreeNew<float3> tree(positions);
225 const float3 center(1.0f, 1.0f, 1.0f);
226
227 /* Only the point on the center itself. */
228 EXPECT_EQ(tree.count_in_radius(center, 0.0f), 1);
229 /* The center and the six points one unit away along an axis. */
230 EXPECT_EQ(tree.count_in_radius(center, 1.0f), 7);
231 /* Every point, the furthest being a corner a bit over 1.7 away. */
232 EXPECT_EQ(tree.count_in_radius(center, 2.0f), 27);
233 /* A radius just short of one leaves everything but the center out. */
234 EXPECT_EQ(tree.count_in_radius(center, std::nextafter(1.0f, 0.0f)), 1);
235
236 Vector<Nearest> found;
237 EXPECT_EQ(tree.find_in_radius(center, 1.0f, found), 7);
238 for (const Nearest &nearest : found.as_span().drop_front(1)) {
239 EXPECT_FLOAT_EQ(nearest.distance_sq, 1.0f);
240 }
241}
242
243TEST(kdtree, FindNearestWithEqualDistances)
244{
245 /* Points equally far away never displace the one already found, however the search is pruned. */
246 const Array<float3> positions = grid_points(3);
247 const KDTreeNew<float3> tree(positions);
248
249 float distance_sq;
250 const int nearest = tree.find_nearest(float3(1.5f, 1.0f, 1.0f), &distance_sq);
251 EXPECT_FLOAT_EQ(distance_sq, 0.25f);
252 /* Two points are exactly as close, so it must be one of them. */
253 EXPECT_TRUE(nearest == 4 || nearest == 13) << "found point " << nearest;
254
255 Array<Nearest> nearest_n(2);
256 EXPECT_EQ(tree.find_nearest_n(float3(1.5f, 1.0f, 1.0f), nearest_n), 2);
257 EXPECT_FLOAT_EQ(nearest_n[0].distance_sq, 0.25f);
258 EXPECT_FLOAT_EQ(nearest_n[1].distance_sq, 0.25f);
259 EXPECT_NE(nearest_n[0].index, nearest_n[1].index);
260}
261
262TEST(kdtree, MaskedBuild)
263{
264 const Array<float3> positions = random_points(300);
265 IndexMaskMemory memory;
267 positions.index_range(), memory, [](const int64_t i) { return i % 3 == 0; });
268 const KDTreeNew<float3> tree(positions, mask);
269 EXPECT_EQ(tree.size(), mask.size());
270
271 const Vector<int> indices = mask.to_indices<int>();
272 const Array<float3> queries = random_points(20, 4);
273 for (const float3 &query : queries) {
274 const Vector<Nearest> expected = brute_force_sorted(positions, indices, query);
275
276 /* Results are indices into the original array, not positions in the mask. */
277 float distance_sq = -1.0f;
278 const int index = tree.find_nearest(query, &distance_sq);
279 EXPECT_EQ(index, expected.first().index);
280 EXPECT_EQ(index % 3, 0);
281 EXPECT_FLOAT_EQ(distance_sq, expected.first().distance_sq);
282
283 Array<Nearest> nearest(4);
284 ASSERT_EQ(tree.find_nearest_n(query, nearest), 4);
285 for (const int i : IndexRange(4)) {
286 EXPECT_EQ(nearest[i].index, expected[i].index);
287 }
288
289 Vector<Nearest> found;
290 tree.find_in_radius(query, 0.3f, found);
291 for (const Nearest &nearest : found) {
292 EXPECT_EQ(nearest.index % 3, 0);
293 EXPECT_LE(nearest.distance_sq, 0.3f * 0.3f);
294 }
295 }
296
297 const int filtered = tree.find_nearest_filtered(positions[0],
298 [](const int index) { return index != 0; });
299 EXPECT_NE(filtered, 0);
300 EXPECT_EQ(filtered % 3, 0);
301}
302
303TEST(kdtree, MaskedBuildFullRange)
304{
305 const Array<float3> positions = random_points(100);
306 const KDTreeNew<float3> tree(positions, IndexMask(positions.index_range()));
307 EXPECT_EQ(tree.size(), 100);
308 EXPECT_EQ(tree.find_nearest(positions[42]), 42);
309}
310
311TEST(kdtree, EmptyMask)
312{
313 const Array<float3> positions = random_points(100);
314 const KDTreeNew<float3> tree(positions, IndexMask(0));
315 EXPECT_TRUE(tree.is_empty());
316 EXPECT_EQ(tree.find_nearest(positions[0]), -1);
317}
318
319TEST(kdtree, DuplicatePoints)
320{
321 /* Many points at the same position is a common degenerate case. */
322 Array<float3> positions(100);
323 for (const int i : positions.index_range()) {
324 positions[i] = i < 60 ? float3(1.0f, 1.0f, 1.0f) : float3(float(i), 0.0f, 0.0f);
325 }
326 const KDTreeNew<float3> tree(positions);
327
328 EXPECT_LT(tree.find_nearest(float3(1.0f, 1.0f, 1.0f)), 60);
329 EXPECT_EQ(tree.count_in_radius(float3(1.0f, 1.0f, 1.0f), 0.001f), 60);
330
331 Array<Nearest> nearest(70);
332 EXPECT_EQ(tree.find_nearest_n(float3(1.0f, 1.0f, 1.0f), nearest), 70);
333 for (const int i : IndexRange(60)) {
334 EXPECT_LT(nearest[i].index, 60);
335 EXPECT_FLOAT_EQ(nearest[i].distance_sq, 0.0f);
336 }
337
338 Vector<Nearest> found;
339 EXPECT_EQ(tree.find_in_radius(float3(1.0f, 1.0f, 1.0f), 0.5f, found), 60);
340 /* Equal distances are broken by index, so the order is deterministic. */
341 for (const int i : IndexRange(60)) {
342 EXPECT_EQ(found[i].index, i);
343 }
344}
345
354static void check_duplicates(const Span<float3> positions,
355 const Span<int> indices,
356 const float range,
357 const Span<int> duplicates,
358 const int found,
359 const bool pairwise = true)
360{
361 const float range_sq = range * range;
362
363 int merged_num = 0;
364 for (const int i : indices) {
365 const int target = duplicates[i];
366 if (target == -1 || target == i) {
367 continue;
368 }
369 merged_num++;
370 /* A point is only ever merged into a point it is actually within the range of. */
371 EXPECT_LE(math::distance_squared(positions[i], positions[target]), range_sq)
372 << "point " << i << " merged into " << target << " beyond the range";
373 /* Merging is a single step, so what a point merged into is never merged itself. */
374 EXPECT_EQ(duplicates[target], target) << "point " << i << " merged into a merged point";
375 }
376 EXPECT_EQ(found, merged_num);
377
378 if (!pairwise) {
379 return;
380 }
381 /* Two points within the range of each other can never both be left out of a cluster: whichever
382 * of them the tree visits first claims the other. */
383 for (const int i : indices) {
384 if (duplicates[i] != -1) {
385 continue;
386 }
387 for (const int j : indices) {
388 if (j == i || duplicates[j] != -1) {
389 continue;
390 }
391 EXPECT_GT(math::distance_squared(positions[i], positions[j]), range_sq)
392 << "points " << i << " and " << j << " are in range but neither was merged";
393 }
394 }
395}
396
397TEST(kdtree, CalcDuplicates)
398{
399 for (const int points_num : {10, 100, 2000}) {
400 const Array<float3> positions = random_points(points_num, 5);
401 const Vector<int> indices = all_indices(points_num);
402 /* From "no point is close enough" to "everything is one cluster". */
403 for (const float range : {0.001f, 0.02f, 0.05f, 0.2f, 5.0f}) {
404 const KDTreeNew<float3> tree(positions);
405 Array<int> duplicates(points_num, -1);
406 const int found = kdtree::calc_duplicates(tree, range, duplicates);
407 SCOPED_TRACE(std::to_string(points_num) + " points, range " + std::to_string(range));
408 check_duplicates(positions, indices, range, duplicates, found);
409 }
410 }
411}
412
413TEST(kdtree, CalcDuplicatesWithDuplicatePoints)
414{
415 /* Exactly equal coordinates are the case this is used for in the first place. Ten groups of
416 * twenty points, each group a unit apart, so the clusters are the same whatever the order. */
417 Array<float3> positions(200);
418 for (const int i : positions.index_range()) {
419 positions[i] = float3(float(i % 10), 0.0f, 0.0f);
420 }
421 const Vector<int> indices = all_indices(positions.size());
422
423 const KDTreeNew<float3> tree(positions);
424 Array<int> duplicates(positions.size(), -1);
425 const int found = kdtree::calc_duplicates(tree, 0.1f, duplicates);
426 check_duplicates(positions, indices, 0.1f, duplicates, found);
427
428 /* Every point ends up in the cluster of the points that share its coordinates, and each of the
429 * ten clusters has exactly one target that the other nineteen merged into. */
430 int targets_num = 0;
431 for (const int i : positions.index_range()) {
432 ASSERT_NE(duplicates[i], -1) << "point " << i << " was left out of a cluster";
433 EXPECT_EQ(duplicates[i] % 10, i % 10);
434 targets_num += duplicates[i] == i;
435 }
436 EXPECT_EQ(targets_num, 10);
437 EXPECT_EQ(found, 190);
438}
439
440TEST(kdtree, CalcDuplicatesExactRange)
441{
442 /* The range is inclusive, so points exactly that far apart are merged. A zero range still
443 * merges the points that share a position exactly. */
444 Array<float3> positions(60);
445 for (const int i : positions.index_range()) {
446 positions[i] = float3(float(i % 3), 0.0f, 0.0f);
447 }
448 const Vector<int> indices = all_indices(positions.size());
449 const KDTreeNew<float3> tree(positions);
450
451 Array<int> duplicates(positions.size(), -1);
452 EXPECT_EQ(kdtree::calc_duplicates(tree, 0.0f, duplicates), 57);
453 check_duplicates(positions, indices, 0.0f, duplicates, 57);
454
455 /* At exactly the spacing of the groups, the first point claims the first two of them, and the
456 * first point of the third group claims what is left. */
457 duplicates.fill(-1);
458 EXPECT_EQ(kdtree::calc_duplicates(tree, 1.0f, duplicates), 58);
459 check_duplicates(positions, indices, 1.0f, duplicates, 58);
460 EXPECT_EQ(duplicates[0], 0);
461 EXPECT_EQ(duplicates[1], 0);
462 EXPECT_EQ(duplicates[2], 2);
463}
464
465TEST(kdtree, CalcDuplicatesMasked)
466{
467 const Array<float3> positions = random_points(500, 6);
468 IndexMaskMemory memory;
470 positions.index_range(), memory, [](const int64_t i) { return i % 4 != 0; });
471 const Vector<int> indices = mask.to_indices<int>();
472
473 const KDTreeNew<float3> tree(positions, mask);
474 Array<int> duplicates(positions.size(), -1);
475 const int found = kdtree::calc_duplicates(tree, 0.1f, duplicates);
476 check_duplicates(positions, indices, 0.1f, duplicates, found);
477
478 /* Points outside the mask are never touched. */
479 for (const int i : positions.index_range()) {
480 if (i % 4 == 0) {
481 EXPECT_EQ(duplicates[i], -1);
482 }
483 }
484
485 /* Building from an index array must give the same tree as building from the mask, and so the
486 * same clusters down to which point of each is the target. */
487 const KDTreeNew<float3> tree_from_indices(positions, indices.as_span());
488 Array<int> from_indices(positions.size(), -1);
489 const int found_from_indices = kdtree::calc_duplicates(tree_from_indices, 0.1f, from_indices);
490 EXPECT_EQ(Span<int>(from_indices), Span<int>(duplicates));
491 EXPECT_EQ(found_from_indices, found);
492}
493
494TEST(kdtree, CalcDuplicatesPresetTargets)
495{
496 const Array<float3> positions = random_points(300, 7);
497 const Vector<int> indices = all_indices(positions.size());
498
499 /* Points preset to their own index are kept out of any cluster but can still be targets. */
500 Array<int> duplicates(positions.size(), -1);
501 for (const int i : IndexRange(0, 20)) {
502 duplicates[i] = i;
503 }
504 const KDTreeNew<float3> tree(positions);
505 const int found = kdtree::calc_duplicates(tree, 0.15f, duplicates);
506
507 for (const int i : IndexRange(0, 20)) {
508 EXPECT_EQ(duplicates[i], i) << "preset point " << i << " was merged into another point";
509 }
510 check_duplicates(positions, indices, 0.15f, duplicates, found);
511}
512
518TEST(kdtree, CalcDuplicatesIndexOrder)
519{
520 const Array<float3> positions = random_points(2000, 10);
521 const Vector<int> indices = all_indices(positions.size());
522
523 for (const float range : {0.02f, 0.05f, 0.2f}) {
524 SCOPED_TRACE("range " + std::to_string(range));
525 const KDTreeNew<float3> tree(positions);
526 Array<int> duplicates(positions.size(), -1);
527 const int found = kdtree::calc_duplicates(tree, range, indices.as_span(), duplicates);
528 check_duplicates(positions, indices, range, duplicates, found);
529
530 /* Every cluster is targeted at its lowest index: a point with a lower index would have been
531 * visited first and claimed the target rather than the other way around. */
532 for (const int i : positions.index_range()) {
533 if (duplicates[i] != -1) {
534 EXPECT_GE(i, duplicates[i]) << "point " << i << " merged into a higher index";
535 }
536 }
537
538 /* The mask overload visits the same points in the same order. */
539 IndexMaskMemory memory;
540 const IndexMask mask = IndexMask::from_indices<int>(indices, memory);
541 Array<int> from_mask(positions.size(), -1);
542 const int found_from_mask = kdtree::calc_duplicates(tree, range, mask, from_mask);
543 EXPECT_EQ(Span<int>(from_mask), Span<int>(duplicates));
544 EXPECT_EQ(found_from_mask, found);
545
546 /* Nothing of the tree reaches the result, so a tree with a different leaf size, which stores
547 * the points in a different order, gives exactly the same clusters. */
548 const KDTreeNew<float3> other_tree(positions, 4);
549 Array<int> other(positions.size(), -1);
550 const int other_found = kdtree::calc_duplicates(other_tree, range, indices.as_span(), other);
551 EXPECT_EQ(Span<int>(other), Span<int>(duplicates));
552 EXPECT_EQ(other_found, found);
553 }
554}
555
557TEST(kdtree, CalcDuplicatesIndexOrderMasked)
558{
559 const Array<float3> positions = random_points(500, 11);
560 IndexMaskMemory memory;
562 positions.index_range(), memory, [](const int64_t i) { return i % 4 != 0; });
563 const Vector<int> indices = mask.to_indices<int>();
564
565 const KDTreeNew<float3> tree(positions, mask);
566 Array<int> duplicates(positions.size(), -1);
567 const int found = kdtree::calc_duplicates(tree, 0.1f, mask, duplicates);
568 check_duplicates(positions, indices, 0.1f, duplicates, found);
569
570 for (const int i : indices) {
571 if (duplicates[i] != -1) {
572 EXPECT_GE(i, duplicates[i]) << "point " << i << " merged into a higher index";
573 }
574 }
575
576 /* Points outside the mask are never touched. */
577 for (const int i : positions.index_range()) {
578 if (i % 4 == 0) {
579 EXPECT_EQ(duplicates[i], -1);
580 }
581 }
582
583 /* The span overload visits the same points in the same order. */
584 Array<int> from_indices(positions.size(), -1);
585 const int found_from_indices = kdtree::calc_duplicates(
586 tree, 0.1f, indices.as_span(), from_indices);
587 EXPECT_EQ(Span<int>(from_indices), Span<int>(duplicates));
588 EXPECT_EQ(found_from_indices, found);
589}
590
599TEST(kdtree, ThreadedBuild)
600{
601 /* Larger than the point count threading threshold. */
602 const Array<float3> positions = random_points(50000, 8);
603 const KDTreeNew<float3> tree(positions);
604 EXPECT_EQ(tree.size(), 50000);
605
606 const Array<float3> queries = random_points(50, 9);
607 for (const float3 &query : queries) {
608 int expected_index = -1;
609 float expected_distance_sq = FLT_MAX;
610 for (const int i : positions.index_range()) {
611 const float distance_sq = math::distance_squared(positions[i], query);
612 if (distance_sq < expected_distance_sq) {
613 expected_distance_sq = distance_sq;
614 expected_index = i;
615 }
616 }
617
618 float distance_sq = -1.0f;
619 EXPECT_EQ(tree.find_nearest(query, &distance_sq), expected_index);
620 EXPECT_FLOAT_EQ(distance_sq, expected_distance_sq);
621 }
622
623 Array<int> duplicates(positions.size(), -1);
624 const int found = kdtree::calc_duplicates(tree, 0.02f, duplicates);
625 EXPECT_GT(found, 0);
626 check_duplicates(positions, all_indices(positions.size()), 0.02f, duplicates, found, false);
627
628 /* However many threads the build is given, including none, the tree and so the clusters have to
629 * come out the same. */
630 for (const int threads_num : {1, 2, 3, 8}) {
633 Array<int> other(positions.size(), -1);
634 int other_found = 0;
635 {
636 const KDTreeNew<float3> other_tree(positions);
637 other_found = kdtree::calc_duplicates(other_tree, 0.02f, other);
638 }
641
642 EXPECT_EQ(Span<int>(other), Span<int>(duplicates)) << threads_num << " threads";
643 EXPECT_EQ(other_found, found) << threads_num << " threads";
644 }
645}
646
647TEST(kdtree, Float2)
648{
649 const Array<float2> positions = {
650 float2(0.0f, 0.0f), float2(1.0f, 0.0f), float2(0.0f, 5.0f), float2(4.0f, 4.0f)};
651 const KDTreeNew<float2> tree(positions);
652 EXPECT_EQ(tree.find_nearest(float2(0.9f, 0.1f)), 1);
653 EXPECT_EQ(tree.count_in_radius(float2(0.0f, 0.0f), 1.5f), 2);
654}
655
656} // namespace blender::tests
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
int64_t size() const
Definition BLI_array.hh:267
IndexRange index_range() const
Definition BLI_array.hh:371
void fill(const T &value) const
Definition BLI_array.hh:283
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
constexpr IndexRange()=default
int find_in_radius(const T &position, const value_type radius, Vector< Nearest > &r_nearest) const
void foreach_in_radius(const T &position, const value_type radius, Fn &&fn) const
int find_nearest(const T &position, value_type *r_distance_sq=nullptr) const
int count_in_radius(const T &position, const value_type radius) const
int find_nearest_filtered(const T &position, Filter &&filter, value_type *r_distance_sq=nullptr) const
int find_nearest_n(const T &position, MutableSpan< Nearest > r_nearest) const
int64_t size() const
void append(const T &value)
IndexRange index_range() const
MutableSpan< T > as_mutable_span()
Span< T > as_span() const
const T & first() const
#define FLT_MAX
#define position
#define EXPECT_GT(result, expect)
#define EXPECT_LT(result, expect)
#define EXPECT_GE(result, expect)
#define EXPECT_NE(result, expect)
#define EXPECT_TRUE(result)
#define EXPECT_LE(result, expect)
void fill_index_range(MutableSpan< T > span, const T start=0)
int calc_duplicates(const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
Definition kdtree.cc:867
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
static Array< float3 > grid_points(const int side)
static Array< float3 > random_points(const int points_num, const int seed=0)
static void check_duplicates(const Span< float3 > positions, const Span< int > indices, const float range, const Span< int > duplicates, const int found, const bool pairwise=true)
KDTreeNew< float3 >::Nearest Nearest
TEST(any_virtual, DefaultConstructor)
static Vector< int > all_indices(const int points_num)
static Vector< Nearest > brute_force_sorted(const Span< float3 > positions, const Span< int > indices, const float3 &position)
__int64 int64_t
Definition BKE_text.h:90
void BLI_system_num_threads_override_set(int num)
Definition threads.cc:294
void BLI_task_scheduler_exit()
VecBase< float, 2 > float2
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
void BLI_task_scheduler_init(bool use_flush_denormals_to_zero=true)
VecBase< float, 3 > float3