Blender V5.3
BLI_kdtree_performance_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 <array>
7#include <cinttypes>
8#include <cmath>
9#include <ctime>
10
11#include "testing/testing.h"
12
13#include "BLI_array.hh"
14#include "BLI_function_ref.hh"
15#include "BLI_index_mask.hh"
16#include "BLI_kdtree.hh"
17#include "BLI_kdtree_new.hh"
19#include "BLI_rand.hh"
20#include "BLI_task_c.hh"
21#include "BLI_threads.hh"
22#include "BLI_time.hh"
23
24namespace blender {
25
26static const std::array<int64_t, 4> POINT_COUNTS = {1000, 10000, 100000, 1000000};
27
32static const std::array<int64_t, 5> TINY_POINT_COUNTS = {4, 16, 64, 256, 1024};
33
35static constexpr int64_t QUERY_COUNT = 100000;
36
38static constexpr int NEAREST_N = 8;
39
45static constexpr double NEIGHBORS_IN_RANGE = 8.0;
46
47static float radius_for_neighbor_count(const int64_t points_num)
48{
49 /* Volume of the sphere containing #NEIGHBORS_IN_RANGE points in the unit cube. */
50 return float(std::cbrt(NEIGHBORS_IN_RANGE * 3.0 / (4.0 * M_PI * double(points_num))));
51}
52
53/* -------------------------------------------------------------------- */
58
61{
63 Array<float3> positions(points_num);
64 for (const int64_t i : positions.index_range()) {
65 positions[i] = float3(random.get_float(), random.get_float(), random.get_float());
66 }
67 return positions;
68}
69
76{
78 Array<float3> positions(points_num);
79 /* Round up, so the grid is always large enough to contain every point. */
80 const int64_t side = std::max<int64_t>(std::ceil(std::cbrt(double(points_num))), 1);
81 const float step = 1.0f / float(side);
82 for (const int64_t i : positions.index_range()) {
83 const int64_t x = i % side;
84 const int64_t y = (i / side) % side;
85 const int64_t z = i / (side * side);
86 const float3 corner = float3(float(x), float(y), float(z)) * step;
87 const float3 jitter = float3(random.get_float(), random.get_float(), random.get_float()) *
88 step;
89 positions[i] = corner + jitter;
90 }
91 return positions;
92}
93
101{
102 constexpr int hotspots_num = 16;
104 Array<float3> hotspots(hotspots_num);
105 for (const int i : hotspots.index_range()) {
106 hotspots[i] = float3(random.get_float(), random.get_float(), random.get_float());
107 }
108
109 Array<float3> positions(points_num);
110 for (const int64_t i : positions.index_range()) {
111 if (i % 2 == 0) {
112 positions[i] = hotspots[random.get_int32(hotspots_num)];
113 }
114 else {
115 positions[i] = float3(random.get_float(), random.get_float(), random.get_float());
116 }
117 }
118 return positions;
119}
120
122
127
128static const Distribution DISTRIBUTIONS[] = {
129 {"random", make_random_points},
130 {"contiguous", make_contiguous_points},
131 {"duplicates", make_duplicate_points},
132};
133
135
136/* -------------------------------------------------------------------- */
139
141enum class Impl {
144};
145
146static const std::array<Impl, 2> IMPLEMENTATIONS = {Impl::BLI, Impl::New};
147
148static const char *impl_name(const Impl impl)
149{
150 return impl == Impl::BLI ? "BLI_kdtree" : "New";
151}
152
159{
160 const int64_t queries_num = std::min<int64_t>(QUERY_COUNT, positions.size());
161 const int64_t stride = positions.size() / queries_num;
163 Array<float3> queries(queries_num);
164 for (const int64_t i : queries.index_range()) {
165 const float3 offset = float3(random.get_float(), random.get_float(), random.get_float());
166 queries[i] = positions[i * stride] + (offset - 0.5f) * 0.01f;
167 }
168 return queries;
169}
170
172{
173 KDTree<float3> *tree = kdtree_new<float3>(positions.size());
174 for (const int64_t i : positions.index_range()) {
175 kdtree_insert(tree, int(i), positions[i]);
176 }
177 kdtree_balance(tree);
178 return tree;
179}
180
185static double run_iterations(const int64_t points_num, const FunctionRef<void()> function)
186{
187 const int iterations = int(std::clamp<int64_t>(2000000 / points_num, 3, 1000));
188 double min_time = 1e30;
189 for (int repetition = 0; repetition < iterations; repetition++) {
190 const double time_before = BLI_time_now_seconds();
191 function();
192 const double time_after = BLI_time_now_seconds();
193 min_time = std::min(min_time, time_after - time_before);
194 }
195 return min_time;
196}
197
205static double run_batched(const int64_t points_num, const FunctionRef<void()> function)
206{
207 const int64_t batch_size = std::max<int64_t>(20000 / points_num, 1);
208 double min_time = 1e30;
209 for (int repetition = 0; repetition < 20; repetition++) {
210 const double time_before = BLI_time_now_seconds();
211 for ([[maybe_unused]] const int64_t i : IndexRange(batch_size)) {
212 function();
213 }
214 const double time_after = BLI_time_now_seconds();
215 min_time = std::min(min_time, (time_after - time_before) / double(batch_size));
216 }
217 return min_time;
218}
219
227static double run_queries(const Span<float3> queries,
228 const FunctionRef<void(const float3 &query)> query_fn)
229{
230 /* Small enough that the slowest queries don't overshoot the budget by much, large enough that
231 * the timer isn't a significant cost. */
232 constexpr int64_t batch_size = 256;
233 constexpr double time_budget = 0.25;
234 constexpr int64_t min_queries = 2000;
235
236 double total_time = 0.0;
237 int64_t queries_num = 0;
238 while (total_time < time_budget || queries_num < min_queries) {
239 const int64_t start = queries_num % queries.size();
240 const int64_t size = std::min(batch_size, queries.size() - start);
241 const double time_before = BLI_time_now_seconds();
242 for (const float3 &query : queries.slice(start, size)) {
243 query_fn(query);
244 }
245 total_time += BLI_time_now_seconds() - time_before;
246 queries_num += size;
247 }
248 return total_time / double(queries_num);
249}
250
251static void print_time(const double seconds)
252{
253 if (seconds < 0.000001) {
254 printf(" %8.1f ns |", seconds * 1000000000.0);
255 }
256 else if (seconds < 0.001) {
257 printf(" %8.2f µs |", seconds * 1000000.0);
258 }
259 else {
260 printf(" %8.2f ms |", seconds * 1000.0);
261 }
262}
263
264static void print_table_header(const char *title,
265 const char *value_description,
266 const Span<int64_t> point_counts)
267{
268 printf("\n#### %s\n\n(%s)\n\n| distribution | implementation |", title, value_description);
269 for (const int64_t points_num : point_counts) {
270 printf(" %" PRId64 " points |", points_num);
271 }
272 printf("\n|---:|---:|");
273 for ([[maybe_unused]] const int64_t points_num : point_counts) {
274 printf("---:|");
275 }
276 printf("\n");
277}
278
284using RunCellFn = FunctionRef<double(Impl impl, const Span<float3> positions, int64_t points_num)>;
285
286static void run_table(const char *title,
287 const char *value_description,
288 const RunCellFn run_cell,
289 const Span<int64_t> point_counts = POINT_COUNTS,
290 const Span<Impl> implementations = IMPLEMENTATIONS)
291{
292 /* Without this the scheduler reports a single thread, which makes #threading::max_threads_task
293 * do nothing, so the tree's own limit on how many threads it builds with has no effect. */
295
296 print_table_header(title, value_description, point_counts);
297 for (const Distribution &distribution : DISTRIBUTIONS) {
298 for (const Impl impl : implementations) {
299 printf("| %s | %s |", distribution.name, impl_name(impl));
300 for (const int64_t points_num : point_counts) {
301 const Array<float3> positions = distribution.make_points(points_num);
302 print_time(run_cell(impl, positions, points_num));
303 fflush(stdout);
304 }
305 printf("\n");
306 }
307 }
308}
309
311
312/* -------------------------------------------------------------------- */
315
316TEST(kdtree_performance, Build)
317{
318 run_table("Building the tree",
319 "`kdtree_insert` and `kdtree_balance` vs. the `KDTreeNew` constructor",
320 [](const Impl impl, const Span<float3> positions, const int64_t points_num) {
321 if (impl == Impl::BLI) {
322 return run_iterations(points_num, [&]() {
323 KDTree<float3> *tree = build_bli_tree(positions);
324 kdtree_free(tree);
325 });
326 }
327 return run_iterations(points_num, [&]() { KDTreeNew<float3> tree(positions); });
328 });
329}
330
331TEST(kdtree_performance, FindNearest)
332{
333 run_table("Find the nearest point",
334 "time per query",
335 [](const Impl impl, const Span<float3> positions, const int64_t /*points_num*/) {
336 const Array<float3> queries = make_query_points(positions);
337 int64_t index_sum = 0;
338 double time;
339 if (impl == Impl::BLI) {
340 KDTree<float3> *tree = build_bli_tree(positions);
341 time = run_queries(queries, [&](const float3 &query) {
342 KDTreeNearest<float3> nearest;
343 index_sum += kdtree_find_nearest(tree, query, &nearest);
344 });
345 kdtree_free(tree);
346 }
347 else {
348 const KDTreeNew<float3> tree(positions);
349 time = run_queries(
350 queries, [&](const float3 &query) { index_sum += tree.find_nearest(query); });
351 }
352 EXPECT_GT(index_sum, 0);
353 return time;
354 });
355}
356
357TEST(kdtree_performance, FindNearestSkipSelf)
358{
359 run_table("Find the nearest point, skipping the search point itself",
360 "time per query, this is what the Index of Nearest node does",
361 [](const Impl impl, const Span<float3> positions, const int64_t /*points_num*/) {
362 /* Search from the points themselves, since that's the only case where skipping
363 * the search point matters. */
364 const Span<float3> queries = positions.take_front(
365 std::min<int64_t>(QUERY_COUNT, positions.size()));
366 int64_t index_sum = 0;
367 double time;
368 /* The queries are the points themselves, so the index to skip is the position of
369 * the query in the array. Counting the calls instead would go wrong as soon as
370 * #run_queries wraps around, and then the search would accept the point it is
371 * searching from and return immediately. */
372 const auto query_index = [&](const float3 &query) {
373 return int(&query - queries.data());
374 };
375 if (impl == Impl::BLI) {
376 KDTree<float3> *tree = build_bli_tree(positions);
377 time = run_queries(queries, [&](const float3 &query) {
378 const int i = query_index(query);
380 tree,
381 query,
382 nullptr,
383 [i](const int other, const float3 & /*co*/, const float /*dist_sq*/) {
384 return other == i ? 0 : 1;
385 });
386 });
387 kdtree_free(tree);
388 }
389 else {
390 const KDTreeNew<float3> tree(positions);
391 time = run_queries(queries, [&](const float3 &query) {
392 const int i = query_index(query);
393 index_sum += tree.find_nearest_filtered(
394 query, [i](const int other) { return other != i; });
395 });
396 }
397 EXPECT_GT(index_sum, 0);
398 return time;
399 });
400}
401
402TEST(kdtree_performance, FindNearestN)
403{
404 run_table("Find the 8 nearest points",
405 "time per query",
406 [](const Impl impl, const Span<float3> positions, const int64_t /*points_num*/) {
407 const Array<float3> queries = make_query_points(positions);
408 int64_t found_sum = 0;
409 double time;
410 if (impl == Impl::BLI) {
411 KDTree<float3> *tree = build_bli_tree(positions);
413 time = run_queries(queries, [&](const float3 &query) {
414 found_sum += kdtree_find_nearest_n(tree, query, nearest.data(), NEAREST_N);
415 });
416 kdtree_free(tree);
417 }
418 else {
419 const KDTreeNew<float3> tree(positions);
421 time = run_queries(queries, [&](const float3 &query) {
422 found_sum += tree.find_nearest_n(query, nearest);
423 });
424 }
425 EXPECT_GT(found_sum, 0);
426 return time;
427 });
428}
429
430TEST(kdtree_performance, RangeSearch)
431{
432 run_table("Visit every point in a radius",
433 "time per query, radius scaled for ~8 points in range",
434 [](const Impl impl, const Span<float3> positions, const int64_t points_num) {
435 const Array<float3> queries = make_query_points(positions);
436 const float radius = radius_for_neighbor_count(points_num);
437 int64_t found_sum = 0;
438 double time;
439 if (impl == Impl::BLI) {
440 KDTree<float3> *tree = build_bli_tree(positions);
441 time = run_queries(queries, [&](const float3 &query) {
443 tree,
444 query,
445 radius,
446 [&](const int /*index*/, const float3 & /*co*/, const float /*dist_sq*/) {
447 found_sum++;
448 return true;
449 });
450 });
451 kdtree_free(tree);
452 }
453 else {
454 const KDTreeNew<float3> tree(positions);
455 time = run_queries(queries, [&](const float3 &query) {
457 query, radius, [&](const int /*index*/, const float /*distance_sq*/) {
458 found_sum++;
459 });
460 });
461 }
462 EXPECT_GT(found_sum, 0);
463 return time;
464 });
465}
466
467TEST(kdtree_performance, CalcDuplicates)
468{
469 run_table("Merging points by distance",
470 "time for the whole tree, radius scaled for ~8 points in range, this is what the "
471 "Cluster by Distance node does",
472 [](const Impl impl, const Span<float3> positions, const int64_t points_num) {
473 const float radius = radius_for_neighbor_count(points_num);
474 Array<int> duplicates(points_num);
475 if (impl == Impl::BLI) {
476 KDTree<float3> *tree = build_bli_tree(positions);
477 const double time = run_iterations(points_num, [&]() {
478 duplicates.as_mutable_span().fill(-1);
479 kdtree_calc_duplicates_fast(tree, radius, true, duplicates.data());
480 });
481 kdtree_free(tree);
482 return time;
483 }
484 const KDTreeNew<float3> tree(positions);
485 const IndexMask visit_order(points_num);
486 return run_iterations(points_num, [&]() {
487 duplicates.as_mutable_span().fill(-1);
488 kdtree::calc_duplicates(tree, radius, visit_order, duplicates);
489 });
490 });
491}
492
494
495/* -------------------------------------------------------------------- */
498
499TEST(kdtree_performance, ThreadedBuild)
500{
501 static const int thread_counts[] = {1, 2, 4, 8, 16, 32};
502 static const int64_t point_counts[] = {1000, 10000, 100000, 1000000};
503
504 printf(
505 "\n#### Threaded build\n\n(`KDTreeNew` build time by thread count, random. The\n"
506 "tree limits its own thread count by size as well, so the larger counts give the same\n"
507 "time once that limit is the lower of the two.)\n\n");
508 printf("| points |");
509 for (const int threads_num : thread_counts) {
510 printf(" %d threads |", threads_num);
511 }
512 printf(" speedup |\n|---:|");
513 for ([[maybe_unused]] const int threads_num : thread_counts) {
514 printf("---:|");
515 }
516 printf("---:|\n");
517
518 Vector<double> cpu_times;
519 for (const int64_t points_num : point_counts) {
520 const Array<float3> positions = make_random_points(points_num);
521 printf("| %" PRId64 " |", points_num);
522 double single_thread_time = 0.0;
523 double best_time = 1e30;
524 for (const int threads_num : thread_counts) {
527
528 /* Processor time as well as elapsed time, to show how much of the machine the build
529 * occupies. Threads spent here are not available for other work. */
530 const std::clock_t cpu_before = std::clock();
531 const double time = run_iterations(points_num, [&]() { KDTreeNew<float3> tree(positions); });
532 const std::clock_t cpu_after = std::clock();
533 cpu_times.append(double(cpu_after - cpu_before) / double(CLOCKS_PER_SEC));
534
535 if (threads_num == 1) {
536 single_thread_time = time;
537 }
538 best_time = std::min(best_time, time);
539 print_time(time);
540 fflush(stdout);
541
543 }
544 printf(" %.1fx |\n", single_thread_time / best_time);
545 }
546
547 printf("\n(processor time of the same builds, relative to the single threaded build)\n\n");
548 printf("| points |");
549 for (const int threads_num : thread_counts) {
550 printf(" %d threads |", threads_num);
551 }
552 printf("\n|---:|");
553 for ([[maybe_unused]] const int threads_num : thread_counts) {
554 printf("---:|");
555 }
556 printf("\n");
557 int64_t cpu_time_i = 0;
558 for (const int64_t points_num : point_counts) {
559 printf("| %" PRId64 " |", points_num);
560 const double base = cpu_times[cpu_time_i];
561 for ([[maybe_unused]] const int threads_num : thread_counts) {
562 printf(" %.1fx |", cpu_times[cpu_time_i++] / base);
563 }
564 printf("\n");
565 }
566
569}
570
572
573/* -------------------------------------------------------------------- */
580
581TEST(kdtree_performance, TinyTreesBuild)
582{
583 run_table(
584 "Building a tiny tree",
585 "time to build and free one tree",
586 [](const Impl impl, const Span<float3> positions, const int64_t points_num) {
587 int64_t sum = 0;
588 double time;
589 if (impl == Impl::BLI) {
590 time = run_batched(points_num, [&]() {
591 KDTree<float3> *tree = build_bli_tree(positions);
592 sum += tree->nodes_len;
593 kdtree_free(tree);
594 });
595 }
596 else {
598 time = run_batched(points_num, [&]() {
599 LinearAllocator<> memory;
600 memory.provide_buffer(buffer);
601 const KDTreeNew<float3> tree(positions, memory);
602 sum += tree.size();
603 });
604 }
605 EXPECT_GT(sum, 0);
606 return time;
607 },
609}
610
611TEST(kdtree_performance, TinyTreesFindNearestOther)
612{
613 run_table(
614 "Building a tiny tree and finding the nearest other point for every point",
615 "time for the whole group, this is what the Index of Nearest node does per group",
616 [](const Impl impl, const Span<float3> positions, const int64_t points_num) {
617 int64_t sum = 0;
618 double time;
619 if (impl == Impl::BLI) {
620 time = run_batched(points_num, [&]() {
621 KDTree<float3> *tree = build_bli_tree(positions);
622 for (const int64_t i : IndexRange(points_num)) {
624 tree,
625 positions[i],
626 nullptr,
627 [i](const int other, const float3 & /*co*/, const float /*dist_sq*/) {
628 return other == int(i) ? 0 : 1;
629 });
630 }
631 kdtree_free(tree);
632 });
633 }
634 else {
636 time = run_batched(points_num, [&]() {
637 LinearAllocator<> memory;
638 memory.provide_buffer(buffer);
639 const KDTreeNew<float3> tree(positions, memory);
640 for (const int64_t i : IndexRange(points_num)) {
641 sum += tree.find_nearest_filtered(positions[i],
642 [i](const int other) { return other != int(i); });
643 }
644 });
645 }
646 EXPECT_GT(sum, 0);
647 return time;
648 },
650}
651
652TEST(kdtree_performance, TinyTreesCalcDuplicates)
653{
654 run_table(
655 "Building a tiny tree and merging its points by distance",
656 "time for the whole group, this is what the Cluster by Distance node does per group",
657 [](const Impl impl, const Span<float3> positions, const int64_t points_num) {
658 const float radius = radius_for_neighbor_count(points_num);
659 Array<int> duplicates(points_num);
660 if (impl == Impl::BLI) {
661 return run_batched(points_num, [&]() {
662 KDTree<float3> *tree = build_bli_tree(positions);
663 duplicates.as_mutable_span().fill(-1);
664 kdtree_calc_duplicates_fast(tree, radius, true, duplicates.data());
665 kdtree_free(tree);
666 });
667 }
669 const IndexMask visit_order(points_num);
670 return run_batched(points_num, [&]() {
671 LinearAllocator<> memory;
672 memory.provide_buffer(buffer);
673 const KDTreeNew<float3> tree(positions, memory);
674 duplicates.as_mutable_span().fill(-1);
675 kdtree::calc_duplicates(tree, radius, visit_order, duplicates);
676 });
677 },
679}
680
682
683/* -------------------------------------------------------------------- */
686
687TEST(kdtree_performance, KDTreeNewLeafSize)
688{
689 BLI_task_scheduler_init(); /* Without this, the build's own thread limit has no effect. */
690
691 static const int leaf_sizes[] = {4, 8, 10, 16, 32, 64, 128};
692 static const int64_t point_counts[] = {10000, 1000000};
693
694 for (const int64_t points_num : point_counts) {
695 printf("\n#### KDTreeNew leaf size\n\n(%" PRId64 " points)\n\n", points_num);
696 printf("| distribution | leaf size | build | find nearest | 8 nearest | radius |\n");
697 printf("|---:|---:|---:|---:|---:|---:|\n");
698
699 const float radius = radius_for_neighbor_count(points_num);
700 for (const Distribution &distribution : DISTRIBUTIONS) {
701 const Array<float3> positions = distribution.make_points(points_num);
702 const Array<float3> queries = make_query_points(positions);
703 for (const int leaf_size : leaf_sizes) {
704 printf("| %s | %d |", distribution.name, leaf_size);
706 run_iterations(points_num, [&]() { KDTreeNew<float3> tree(positions, leaf_size); }));
707
708 const KDTreeNew<float3> tree(positions, leaf_size);
709 int64_t sum = 0;
711 run_queries(queries, [&](const float3 &query) { sum += tree.find_nearest(query); }));
712
715 queries, [&](const float3 &query) { sum += tree.find_nearest_n(query, nearest); }));
716
717 print_time(run_queries(queries, [&](const float3 &query) {
718 tree.foreach_in_radius(
719 query, radius, [&](const int /*index*/, const float /*distance_sq*/) { sum++; });
720 }));
721 EXPECT_GT(sum, 0);
722 printf("\n");
723 fflush(stdout);
724 }
725 }
726 }
727}
728
730
731} // namespace blender
A KD-tree for nearest neighbor search.
#define M_PI
Platform independent time functions.
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
const T * data() const
Definition BLI_array.hh:323
IndexRange index_range() const
Definition BLI_array.hh:371
constexpr IndexRange()=default
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 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
void provide_buffer(void *buffer, const int64_t size)
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr Span take_front(int64_t n) const
Definition BLI_span.hh:197
void append(const T &value)
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
#define EXPECT_GT(result, expect)
#define PRId64
Definition inttypes.h:78
int calc_duplicates(const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
Definition kdtree.cc:867
BMesh Iterators.
static constexpr int64_t QUERY_COUNT
void kdtree_balance(KDTree< CoordT > *tree)
__int64 int64_t
Definition BKE_text.h:90
static Array< float3 > make_random_points(const int64_t points_num)
static double run_queries(const Span< float3 > queries, const FunctionRef< void(const float3 &query)> query_fn)
static Array< float3 > make_duplicate_points(const int64_t points_num)
static double run_batched(const int64_t points_num, const FunctionRef< void()> function)
int kdtree_find_nearest_cb(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest, Filter &&filter_cb)
void kdtree_range_search_cb(const KDTree< CoordT > *tree, const CoordT &co, typename KDTree< CoordT >::ValueType range, Fn &&search_cb)
void BLI_system_num_threads_override_set(int num)
Definition threads.cc:294
void BLI_task_scheduler_exit()
static const std::array< int64_t, 5 > TINY_POINT_COUNTS
static double run_iterations(const int64_t indices_num, const FunctionRef< void()> function)
Array< float3 >(*)(int64_t) MakePointsFn
static constexpr double NEIGHBORS_IN_RANGE
TEST(array_store, Nop)
static const Distribution DISTRIBUTIONS[]
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
Definition BLI_kdtree.hh:65
FunctionRef< double(Impl impl, const Span< float3 > positions, int64_t points_num)> RunCellFn
static void run_table(const char *title, const char *value_description, const RunCellFn run_cell, const Span< int64_t > point_counts=POINT_COUNTS, const Span< Impl > implementations=IMPLEMENTATIONS)
int kdtree_find_nearest_n(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > r_nearest[], uint nearest_len_capacity)
static const char * impl_name(const Impl impl)
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
Definition BLI_kdtree.hh:96
static const std::array< int64_t, 4 > POINT_COUNTS
int kdtree_find_nearest(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest)
static void print_time(const double seconds)
void kdtree_free(KDTree< CoordT > *tree)
Definition BLI_kdtree.hh:84
static constexpr int NEAREST_N
static Array< float3 > make_contiguous_points(const int64_t points_num)
static KDTree< float3 > * build_bli_tree(const Span< float3 > positions)
int kdtree_calc_duplicates_fast(const KDTree< CoordT > *tree, const typename KDTree< CoordT >::ValueType range, const bool use_index_order, int *duplicates)
static Array< float3 > make_query_points(const Span< float3 > positions)
double BLI_time_now_seconds()
Definition time.cc:30
void BLI_task_scheduler_init(bool use_flush_denormals_to_zero=true)
static void print_table_header(const char *title)
static float radius_for_neighbor_count(const int64_t points_num)
VecBase< float, 3 > float3
static const std::array< Impl, 2 > IMPLEMENTATIONS
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float