Blender V5.3
BLI_kdopbvh.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2006 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
25
26#include <algorithm>
27
28#include "MEM_guardedalloc.h"
29
30#include "BLI_alloca.hh"
31#include "BLI_heap_simple.hh"
32#include "BLI_kdopbvh.hh"
33#include "BLI_math_geom_c.hh"
35#include "BLI_stack_c.hh"
36#include "BLI_task_c.hh"
37#include "BLI_utildefines.hh"
38
39#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
40
41namespace blender {
42
43/* used for iterative_raycast */
44// #define USE_SKIP_LINKS
45
46/* Use to print balanced output. */
47// #define USE_PRINT_TREE
48
49/* Check tree is valid. */
50// #define USE_VERIFY_TREE
51
52#define MAX_TREETYPE 32
53
54#ifndef NDEBUG
55/* Setting zero so we can catch bugs in BLI_task/KDOPBVH. */
56# define KDOPBVH_THREAD_LEAF_THRESHOLD 0
57#else
58# define KDOPBVH_THREAD_LEAF_THRESHOLD 1024
59#endif
60
61/* -------------------------------------------------------------------- */
64
65using axis_t = uchar;
66
67struct BVHNode {
69 BVHNode *parent; /* some user defined traversed need that */
70#ifdef USE_SKIP_LINKS
71 BVHNode *skip[2];
72#endif
73 float *bv; /* Bounding volume of all nodes, max 13 axis */
74 int index; /* face, edge, vertex index */
75 char node_num; /* how many nodes are used, used for speedup */
76 char main_axis; /* Axis used to split this node */
77};
78
79/* keep under 26 bytes for speed purposes */
80struct BVHTree {
82 BVHNode *nodearray; /* Pre-allocate branch nodes. */
83 BVHNode **nodechild; /* Pre-allocate children for nodes. */
84 float *nodebv; /* Pre-allocate bounding-volumes for nodes. */
85 float epsilon; /* Epsilon is used for inflation of the K-DOP. */
86 int leaf_num; /* Leafs. */
88 int nodes_num_alloc; /* Allocated length of #nodes & #nodearray. */
89 axis_t start_axis, stop_axis; /* bvhtree_kdop_axes array indices according to axis */
90 axis_t axis; /* KDOP type (6 => OBB, 7 => AABB, ...) */
91 char tree_type; /* type of tree (4 => quad-tree). */
92};
93
94/* optimization, ensure we stay small */
95BLI_STATIC_ASSERT((sizeof(void *) == 8 && sizeof(BVHTree) <= 56) ||
96 (sizeof(void *) == 4 && sizeof(BVHTree) <= 36),
97 "over sized")
98
99/* avoid duplicating vars in BVHOverlapData_Thread */
100struct BVHOverlapData_Shared {
101 const BVHTree *tree1, *tree2;
102 axis_t start_axis, stop_axis;
103 bool use_self;
104
105 /* use for callbacks */
107 void *userdata;
108};
109
111 BVHOverlapData_Shared *shared;
112 BLI_Stack *overlap; /* store BVHTreeOverlap */
114 /* use for callbacks */
116};
117
119 const BVHTree *tree;
120 const float *co;
122 void *userdata;
123 float proj[13]; /* coordinates projection over axis */
125};
126
128 const BVHTree *tree;
129
131 void *userdata;
132
134
135#ifdef USE_KDOPBVH_WATERTIGHT
136 IsectRayPrecalc isect_precalc;
137#endif
138
139 /* initialized by bvhtree_ray_cast_data_precalc */
140 float ray_dot_axis[13];
141 float idot_axis[13];
142 int index[6];
143
145};
146
157
159 const BVHTree *tree;
160 float plane[4];
161 BLI_Stack *intersect; /* Store indexes. */
162};
163
165
173
174const float bvhtree_kdop_axes[13][3] = {
175 {1.0, 0, 0},
176 {0, 1.0, 0},
177 {0, 0, 1.0},
178 {1.0, 1.0, 1.0},
179 {1.0, -1.0, 1.0},
180 {1.0, 1.0, -1.0},
181 {1.0, -1.0, -1.0},
182 {1.0, 1.0, 0},
183 {1.0, 0, 1.0},
184 {0, 1.0, 1.0},
185 {1.0, -1.0, 0},
186 {1.0, 0, -1.0},
187 {0, 1.0, -1.0},
188};
189
190/* Used to correct the epsilon and thus match the overlap distance. */
191static const float bvhtree_kdop_axes_length[13] = {
192 1.0f,
193 1.0f,
194 1.0f,
195 1.7320508075688772f,
196 1.7320508075688772f,
197 1.7320508075688772f,
198 1.7320508075688772f,
199 1.4142135623730951f,
200 1.4142135623730951f,
201 1.4142135623730951f,
202 1.4142135623730951f,
203 1.4142135623730951f,
204 1.4142135623730951f,
205};
206
207/* -------------------------------------------------------------------- */
210
212{
213 return (a < b) ? a : b;
214}
215#if 0
216MINLINE axis_t max_axis(axis_t a, axis_t b)
217{
218 return (b < a) ? a : b;
219}
220#endif
221
228
229static void node_minmax_init(const BVHTree *tree, BVHNode *node)
230{
231 axis_t axis_iter;
232 float (*bv)[2] = reinterpret_cast<float (*)[2]>(node->bv);
233
234 for (axis_iter = tree->start_axis; axis_iter != tree->stop_axis; axis_iter++) {
235 bv[axis_iter][0] = FLT_MAX;
236 bv[axis_iter][1] = -FLT_MAX;
237 }
238}
239
241
242/* -------------------------------------------------------------------- */
245
249static void bvh_insertionsort(BVHNode **a, int lo, int hi, int axis)
250{
251 int i, j;
252 BVHNode *t;
253 for (i = lo; i < hi; i++) {
254 j = i;
255 t = a[i];
256 while ((j != lo) && (t->bv[axis] < (a[j - 1])->bv[axis])) {
257 a[j] = a[j - 1];
258 j--;
259 }
260 a[j] = t;
261 }
262}
263
264static int bvh_partition(BVHNode **a, int lo, int hi, const BVHNode *x, int axis)
265{
266 int i = lo, j = hi;
267 while (true) {
268 while (a[i]->bv[axis] < x->bv[axis]) {
269 i++;
270 }
271 j--;
272 while (x->bv[axis] < a[j]->bv[axis]) {
273 j--;
274 }
275 if (!(i < j)) {
276 return i;
277 }
278 SWAP(BVHNode *, a[i], a[j]);
279 i++;
280 }
281}
282
283/* returns Sortable */
284static BVHNode *bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis)
285{
286 if ((a[mid])->bv[axis] < (a[lo])->bv[axis]) {
287 if ((a[hi])->bv[axis] < (a[mid])->bv[axis]) {
288 return a[mid];
289 }
290 if ((a[hi])->bv[axis] < (a[lo])->bv[axis]) {
291 return a[hi];
292 }
293 return a[lo];
294 }
295
296 if ((a[hi])->bv[axis] < (a[mid])->bv[axis]) {
297 if ((a[hi])->bv[axis] < (a[lo])->bv[axis]) {
298 return a[lo];
299 }
300 return a[hi];
301 }
302 return a[mid];
303}
304
310static void partition_nth_element(BVHNode **a, int begin, int end, const int n, const int axis)
311{
312 while (end - begin > 3) {
313 const int cut = bvh_partition(
314 a, begin, end, bvh_medianof3(a, begin, (begin + end) / 2, end - 1, axis), axis);
315 if (cut <= n) {
316 begin = cut;
317 }
318 else {
319 end = cut;
320 }
321 }
322 bvh_insertionsort(a, begin, end, axis);
323}
324
325#ifdef USE_SKIP_LINKS
326static void build_skip_links(BVHTree *tree, BVHNode *node, BVHNode *left, BVHNode *right)
327{
328 int i;
329
330 node->skip[0] = left;
331 node->skip[1] = right;
332
333 for (i = 0; i < node->node_num; i++) {
334 if (i + 1 < node->node_num) {
335 build_skip_links(tree, node->children[i], left, node->children[i + 1]);
336 }
337 else {
338 build_skip_links(tree, node->children[i], left, right);
339 }
340
341 left = node->children[i];
342 }
343}
344#endif
345
346/*
347 * BVHTree bounding volumes functions
348 */
350 const BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving)
351{
352 float newminmax;
353 float *bv = node->bv;
354 int k;
355 axis_t axis_iter;
356
357 /* Don't initialize bounds for the moving case */
358 if (!moving) {
359 node_minmax_init(tree, node);
360 }
361
362 for (k = 0; k < numpoints; k++) {
363 /* for all Axes. */
364 for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
365 newminmax = dot_v3v3(&co[k * 3], bvhtree_kdop_axes[axis_iter]);
366 bv[2 * axis_iter] = std::min(newminmax, bv[2 * axis_iter]);
367 bv[(2 * axis_iter) + 1] = std::max(newminmax, bv[(2 * axis_iter) + 1]);
368 }
369 }
370}
371
375static void refit_kdop_hull(const BVHTree *tree, BVHNode *node, int start, int end)
376{
377 float newmin, newmax;
378 float *__restrict bv = node->bv;
379 int j;
380 axis_t axis_iter;
381
382 node_minmax_init(tree, node);
383
384 for (j = start; j < end; j++) {
385 const float *__restrict node_bv = tree->nodes[j]->bv;
386
387 /* for all Axes. */
388 for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
389 newmin = node_bv[(2 * axis_iter)];
390 bv[(2 * axis_iter)] = std::min(newmin, bv[(2 * axis_iter)]);
391
392 newmax = node_bv[(2 * axis_iter) + 1];
393 bv[(2 * axis_iter) + 1] = std::max(newmax, bv[(2 * axis_iter) + 1]);
394 }
395 }
396}
397
402static char get_largest_axis(const float *bv)
403{
404 float middle_point[3];
405
406 middle_point[0] = (bv[1]) - (bv[0]); /* x axis */
407 middle_point[1] = (bv[3]) - (bv[2]); /* y axis */
408 middle_point[2] = (bv[5]) - (bv[4]); /* z axis */
409 if (middle_point[0] > middle_point[1]) {
410 if (middle_point[0] > middle_point[2]) {
411 return 1; /* max x axis */
412 }
413 return 5; /* max z axis */
414 }
415 if (middle_point[1] > middle_point[2]) {
416 return 3; /* max y axis */
417 }
418 return 5; /* max z axis */
419}
420
425static void node_join(BVHTree *tree, BVHNode *node)
426{
427 int i;
428 axis_t axis_iter;
429
430 node_minmax_init(tree, node);
431
432 for (i = 0; i < tree->tree_type; i++) {
433 if (node->children[i]) {
434 for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
435 /* update minimum */
436 node->bv[(2 * axis_iter)] = std::min(node->children[i]->bv[(2 * axis_iter)],
437 node->bv[(2 * axis_iter)]);
438
439 /* update maximum */
440 node->bv[(2 * axis_iter) + 1] = std::max(node->children[i]->bv[(2 * axis_iter) + 1],
441 node->bv[(2 * axis_iter) + 1]);
442 }
443 }
444 else {
445 break;
446 }
447 }
448}
449
451
452#ifdef USE_PRINT_TREE
453
454/* -------------------------------------------------------------------- */
457
458static void bvhtree_print_tree(BVHTree *tree, BVHNode *node, int depth)
459{
460 int i;
461 axis_t axis_iter;
462
463 for (i = 0; i < depth; i++) {
464 printf(" ");
465 }
466 printf(" - %d (%ld): ", node->index, (long int)(node - tree->nodearray));
467 for (axis_iter = (axis_t)(2 * tree->start_axis); axis_iter < (axis_t)(2 * tree->stop_axis);
468 axis_iter++)
469 {
470 printf("%.3f ", node->bv[axis_iter]);
471 }
472 printf("\n");
473
474 for (i = 0; i < tree->tree_type; i++) {
475 if (node->children[i]) {
476 bvhtree_print_tree(tree, node->children[i], depth + 1);
477 }
478 }
479}
480
481static void bvhtree_info(BVHTree *tree)
482{
483 printf("BVHTree Info: tree_type = %d, axis = %d, epsilon = %f\n",
484 tree->tree_type,
485 tree->axis,
486 tree->epsilon);
487 printf("nodes = %d, branches = %d, leafs = %d\n",
488 tree->branch_num + tree->leaf_num,
489 tree->branch_num,
490 tree->leaf_num);
491 printf("Memory per node = %ubytes\n",
492 uint(sizeof(BVHNode) + sizeof(BVHNode *) * tree->tree_type + sizeof(float) * tree->axis));
493 const size_t nodebv_len = sizeof(float) * size_t(tree->axis) * size_t(tree->nodes_num_alloc);
494 const size_t nodes_len = sizeof(BVHNode *) * size_t(tree->nodes_num_alloc);
495 const size_t nodearray_len = sizeof(BVHNode) * size_t(tree->nodes_num_alloc);
496 const size_t nodechild_len = sizeof(BVHNode *) * size_t(tree->tree_type) *
497 size_t(tree->nodes_num_alloc);
498
499 printf("BV memory = %ubytes\n", uint(nodebv_len));
500
501 printf("Total memory = %ubytes\n",
502 uint(sizeof(BVHTree) + nodes_len + nodearray_len + nodechild_len + nodebv_len));
503
504 bvhtree_print_tree(tree, tree->nodes[tree->leaf_num], 0);
505}
506
508
509#endif /* USE_PRINT_TREE */
510
511#ifdef USE_VERIFY_TREE
512
513static void bvhtree_verify(BVHTree *tree)
514{
515 int i, j, check = 0;
516
517 /* check the pointer list */
518 for (i = 0; i < tree->leaf_num; i++) {
519 if (tree->nodes[i]->parent == nullptr) {
520 printf("Leaf has no parent: %d\n", i);
521 }
522 else {
523 for (j = 0; j < tree->tree_type; j++) {
524 if (tree->nodes[i]->parent->children[j] == tree->nodes[i]) {
525 check = 1;
526 }
527 }
528 if (!check) {
529 printf("Parent child relationship doesn't match: %d\n", i);
530 }
531 check = 0;
532 }
533 }
534
535 /* check the leaf list */
536 for (i = 0; i < tree->leaf_num; i++) {
537 if (tree->nodearray[i].parent == nullptr) {
538 printf("Leaf has no parent: %d\n", i);
539 }
540 else {
541 for (j = 0; j < tree->tree_type; j++) {
542 if (tree->nodearray[i].parent->children[j] == &tree->nodearray[i]) {
543 check = 1;
544 }
545 }
546 if (!check) {
547 printf("Parent child relationship doesn't match: %d\n", i);
548 }
549 check = 0;
550 }
551 }
552
553 printf("branches: %d, leafs: %d, total: %d\n",
554 tree->branch_num,
555 tree->leaf_num,
556 tree->branch_num + tree->leaf_num);
557}
558#endif /* USE_VERIFY_TREE */
559
560/* -------------------------------------------------------------------- */
563
564/* Helper data and structures to build a min-leaf generalized implicit tree
565 * This code can be easily reduced
566 * (basically this is only method to calculate pow(k, n) in O(1).. and stuff like that) */
579
581{
582 int depth = 0;
583 int remain;
584 int nnodes;
585
586 data->leafs_num = tree->leaf_num;
587 data->tree_type = tree->tree_type;
588
589 /* Calculate the smallest tree_type^n such that tree_type^n >= leafs_num */
590 for (data->leafs_per_child[0] = 1; data->leafs_per_child[0] < data->leafs_num;
591 data->leafs_per_child[0] *= data->tree_type)
592 {
593 /* pass */
594 }
595
596 data->branches_on_level[0] = 1;
597
598 for (depth = 1; (depth < 32) && data->leafs_per_child[depth - 1]; depth++) {
599 data->branches_on_level[depth] = data->branches_on_level[depth - 1] * data->tree_type;
600 data->leafs_per_child[depth] = data->leafs_per_child[depth - 1] / data->tree_type;
601 }
602
603 remain = data->leafs_num - data->leafs_per_child[1];
604 nnodes = (remain + data->tree_type - 2) / (data->tree_type - 1);
605 data->remain_leafs = remain + nnodes;
606}
607
611static int implicit_leafs_index(const BVHBuildHelper *data, const int depth, const int child_index)
612{
613 int min_leaf_index = child_index * data->leafs_per_child[depth - 1];
614 if (min_leaf_index <= data->remain_leafs) {
615 return min_leaf_index;
616 }
617 if (data->leafs_per_child[depth]) {
618 return data->leafs_num -
619 (data->branches_on_level[depth - 1] - child_index) * data->leafs_per_child[depth];
620 }
621 return data->remain_leafs;
622}
623
652
653/* This functions returns the number of branches needed to have the requested number of leafs. */
654static int implicit_needed_branches(int tree_type, int leafs)
655{
656 return max_ii(1, (leafs + tree_type - 3) / (tree_type - 1));
657}
658
671static void split_leafs(BVHNode **leafs_array,
672 const int nth[],
673 const int partitions,
674 const int split_axis)
675{
676 int i;
677 for (i = 0; i < partitions - 1; i++) {
678 if (nth[i] >= nth[partitions]) {
679 break;
680 }
681
682 partition_nth_element(leafs_array, nth[i], nth[partitions], nth[i + 1], split_axis);
683 }
684}
685
700
701static void non_recursive_bvh_div_nodes_task_cb(void *__restrict userdata,
702 const int j,
703 const TaskParallelTLS *__restrict /*tls*/)
704{
705 BVHDivNodesData *data = static_cast<BVHDivNodesData *>(userdata);
706
707 int k;
708 const int parent_level_index = j - data->i;
709 BVHNode *parent = &data->branches_array[j];
710 int nth_positions[MAX_TREETYPE + 1];
711 char split_axis;
712
713 int parent_leafs_begin = implicit_leafs_index(data->data, data->depth, parent_level_index);
714 int parent_leafs_end = implicit_leafs_index(data->data, data->depth, parent_level_index + 1);
715
716 /* This calculates the bounding box of this branch
717 * and chooses the largest axis as the axis to divide leafs */
718 refit_kdop_hull(data->tree, parent, parent_leafs_begin, parent_leafs_end);
719 split_axis = get_largest_axis(parent->bv);
720
721 /* Save split axis (this can be used on ray-tracing to speedup the query time) */
722 parent->main_axis = split_axis / 2;
723
724 /* Split the children along the split_axis, NOTE: its not needed to sort the whole leafs array
725 * Only to assure that the elements are partitioned on a way that each child takes the elements
726 * it would take in case the whole array was sorted.
727 * Split_leafs takes care of that "sort" problem. */
728 nth_positions[0] = parent_leafs_begin;
729 nth_positions[data->tree_type] = parent_leafs_end;
730 for (k = 1; k < data->tree_type; k++) {
731 const int child_index = j * data->tree_type + data->tree_offset + k;
732 /* child level index */
733 const int child_level_index = child_index - data->first_of_next_level;
734 nth_positions[k] = implicit_leafs_index(data->data, data->depth + 1, child_level_index);
735 }
736
737 split_leafs(data->leafs_array, nth_positions, data->tree_type, split_axis);
738
739 /* Setup `children` and `node_num` counters
740 * Not really needed but currently most of BVH code
741 * relies on having an explicit children structure */
742 for (k = 0; k < data->tree_type; k++) {
743 const int child_index = j * data->tree_type + data->tree_offset + k;
744 /* child level index */
745 const int child_level_index = child_index - data->first_of_next_level;
746
747 const int child_leafs_begin = implicit_leafs_index(
748 data->data, data->depth + 1, child_level_index);
749 const int child_leafs_end = implicit_leafs_index(
750 data->data, data->depth + 1, child_level_index + 1);
751
752 if (child_leafs_end - child_leafs_begin > 1) {
753 parent->children[k] = &data->branches_array[child_index];
754 parent->children[k]->parent = parent;
755 }
756 else if (child_leafs_end - child_leafs_begin == 1) {
757 parent->children[k] = data->leafs_array[child_leafs_begin];
758 parent->children[k]->parent = parent;
759 }
760 else {
761 break;
762 }
763 }
764 parent->node_num = char(k);
765}
766
785static void non_recursive_bvh_div_nodes(const BVHTree *tree,
786 BVHNode *branches_array,
787 BVHNode **leafs_array,
788 int leafs_num)
789{
790 int i;
791
792 const int tree_type = tree->tree_type;
793 /* this value is 0 (on binary trees) and negative on the others */
794 const int tree_offset = 2 - tree->tree_type;
795
796 const int branches_num = implicit_needed_branches(tree_type, leafs_num);
797
799 int depth;
800
801 {
802 /* set parent from root node to nullptr */
803 BVHNode *root = &branches_array[1];
804 root->parent = nullptr;
805
806 /* Most of bvhtree code relies on 1-leaf trees having at least one branch
807 * We handle that special case here */
808 if (leafs_num == 1) {
809 refit_kdop_hull(tree, root, 0, leafs_num);
810 root->main_axis = get_largest_axis(root->bv) / 2;
811 root->node_num = 1;
812 root->children[0] = leafs_array[0];
813 root->children[0]->parent = root;
814 return;
815 }
816 }
817
819
820 BVHDivNodesData cb_data{};
821 cb_data.tree = tree;
822 cb_data.branches_array = branches_array;
823 cb_data.leafs_array = leafs_array;
824 cb_data.tree_type = tree_type;
825 cb_data.tree_offset = tree_offset;
826 cb_data.data = &data;
827 cb_data.first_of_next_level = 0;
828 cb_data.depth = 0;
829 cb_data.i = 0;
830
831 /* Loop tree levels (log N) loops */
832 for (i = 1, depth = 1; i <= branches_num; i = i * tree_type + tree_offset, depth++) {
833 const int first_of_next_level = i * tree_type + tree_offset;
834 /* index of last branch on this level */
835 const int i_stop = min_ii(first_of_next_level, branches_num + 1);
836
837 /* Loop all branches on this level */
838 cb_data.first_of_next_level = first_of_next_level;
839 cb_data.i = i;
840 cb_data.depth = depth;
841
842 if (true) {
843 TaskParallelSettings settings;
845 settings.use_threading = (leafs_num > KDOPBVH_THREAD_LEAF_THRESHOLD);
846 BLI_task_parallel_range(i, i_stop, &cb_data, non_recursive_bvh_div_nodes_task_cb, &settings);
847 }
848 else {
849 /* Less hassle for debugging. */
850 TaskParallelTLS tls = {nullptr};
851 for (int i_task = i; i_task < i_stop; i_task++) {
852 non_recursive_bvh_div_nodes_task_cb(&cb_data, i_task, &tls);
853 }
854 }
855 }
856}
857
859
860/* -------------------------------------------------------------------- */
863
864BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
865{
866 BLI_assert(tree_type >= 2 && tree_type <= MAX_TREETYPE);
867
868 BVHTree *tree = MEM_new_zeroed<BVHTree>(__func__);
869
870 /* tree epsilon must be >= FLT_EPSILON
871 * so that tangent rays can still hit a bounding volume..
872 * this bug would show up when casting a ray aligned with a KDOP-axis
873 * and with an edge of 2 faces */
874 epsilon = max_ff(FLT_EPSILON, epsilon);
875
876 if (tree) {
877 tree->epsilon = epsilon;
878 tree->tree_type = tree_type;
879 tree->axis = axis;
880
881 if (axis == 26) {
882 tree->start_axis = 0;
883 tree->stop_axis = 13;
884 }
885 else if (axis == 18) {
886 tree->start_axis = 7;
887 tree->stop_axis = 13;
888 }
889 else if (axis == 14) {
890 tree->start_axis = 0;
891 tree->stop_axis = 7;
892 }
893 else if (axis == 8) { /* AABB */
894 tree->start_axis = 0;
895 tree->stop_axis = 4;
896 }
897 else if (axis == 6) { /* OBB */
898 tree->start_axis = 0;
899 tree->stop_axis = 3;
900 }
901 else {
902 /* should never happen! */
904
905 goto fail;
906 }
907
908 /* Allocate arrays */
909 tree->nodes_num_alloc = maxsize + implicit_needed_branches(tree_type, maxsize) + tree_type;
910 const int numnodes = tree->nodes_num_alloc;
911
912 tree->nodes = MEM_new_array_zeroed<BVHNode *>(size_t(numnodes), "BVHNodes");
913 tree->nodebv = MEM_new_array_zeroed<float>(axis * size_t(numnodes), "BVHNodeBV");
914 tree->nodechild = MEM_new_array_zeroed<BVHNode *>(tree_type * size_t(numnodes), "BVHNodeBV");
915 tree->nodearray = MEM_new_array_zeroed<BVHNode>(size_t(numnodes), "BVHNodeArray");
916
917 if ((!tree->nodes) || (!tree->nodebv) || (!tree->nodechild) || (!tree->nodearray)) [[unlikely]]
918 {
919 goto fail;
920 }
921
922 /* link the dynamic bv and child links */
923 for (int i = 0; i < numnodes; i++) {
924 tree->nodearray[i].bv = &tree->nodebv[i * axis];
925 tree->nodearray[i].children = &tree->nodechild[i * tree_type];
926 }
927 }
928 return tree;
929
930fail:
931 BLI_bvhtree_free(tree);
932 return nullptr;
933}
934
936{
937 if (tree) {
938 MEM_SAFE_DELETE(tree->nodes);
939 MEM_SAFE_DELETE(tree->nodearray);
940 MEM_SAFE_DELETE(tree->nodebv);
941 MEM_SAFE_DELETE(tree->nodechild);
942 MEM_delete(tree);
943 }
944}
945
947{
948 BVHNode **leafs_array = tree->nodes;
949
950 /* This function should only be called once
951 * (some big bug goes here if its being called more than once per tree) */
952 BLI_assert(tree->branch_num == 0);
953
954 /* Build the implicit tree */
956 tree, tree->nodearray + (tree->leaf_num - 1), leafs_array, tree->leaf_num);
957
958 /* current code expects the branches to be linked to the nodes array
959 * we perform that linkage here */
961 for (int i = 0; i < tree->branch_num; i++) {
962 tree->nodes[tree->leaf_num + i] = &tree->nodearray[tree->leaf_num + i];
963 }
964
965#ifdef USE_SKIP_LINKS
966 build_skip_links(tree, tree->nodes[tree->leaf_num], nullptr, nullptr);
967#endif
968
969#ifdef USE_VERIFY_TREE
970 bvhtree_verify(tree);
971#endif
972
973#ifdef USE_PRINT_TREE
974 bvhtree_info(tree);
975#endif
976}
977
978static void bvhtree_node_inflate(const BVHTree *tree, BVHNode *node, const float dist)
979{
980 axis_t axis_iter;
981 for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
982 float dist_corrected = dist * bvhtree_kdop_axes_length[axis_iter];
983 node->bv[(2 * axis_iter)] -= dist_corrected; /* minimum */
984 node->bv[(2 * axis_iter) + 1] += dist_corrected; /* maximum */
985 }
986}
987
988void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
989{
990 BVHNode *node = nullptr;
991
992 /* insert should only possible as long as tree->branch_num is 0 */
993 BLI_assert(tree->branch_num <= 0);
994 BLI_assert(tree->leaf_num < tree->nodes_num_alloc);
995
996 node = tree->nodes[tree->leaf_num] = &(tree->nodearray[tree->leaf_num]);
997 tree->leaf_num++;
998
999 create_kdop_hull(tree, node, co, numpoints, 0);
1000 node->index = index;
1001
1002 /* inflate the bv with some epsilon */
1003 bvhtree_node_inflate(tree, node, tree->epsilon);
1004}
1005
1007 BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
1008{
1009 BVHNode *node = nullptr;
1010
1011 /* check if index exists */
1012 if (index > tree->leaf_num) {
1013 return false;
1014 }
1015
1016 node = tree->nodearray + index;
1017
1018 create_kdop_hull(tree, node, co, numpoints, 0);
1019
1020 if (co_moving) {
1021 create_kdop_hull(tree, node, co_moving, numpoints, 1);
1022 }
1023
1024 /* inflate the bv with some epsilon */
1025 bvhtree_node_inflate(tree, node, tree->epsilon);
1026
1027 return true;
1028}
1029
1031{
1032 /* Update bottom=>top
1033 * TRICKY: the way we build the tree all the children have an index greater than the parent
1034 * This allows us todo a bottom up update by starting on the bigger numbered branch. */
1035
1036 BVHNode **root = tree->nodes + tree->leaf_num;
1037 BVHNode **index = tree->nodes + tree->leaf_num + tree->branch_num - 1;
1038
1039 for (; index >= root; index--) {
1040 node_join(tree, *index);
1041 }
1042}
1044{
1045 return tree->leaf_num;
1046}
1047
1049{
1050 return tree->tree_type;
1051}
1052
1054{
1055 return tree->epsilon;
1056}
1057
1058void BLI_bvhtree_get_bounding_box(const BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
1059{
1060 const BVHNode *root = tree->nodes[tree->leaf_num];
1061 if (root != nullptr) {
1062 const float bb_min[3] = {root->bv[0], root->bv[2], root->bv[4]};
1063 const float bb_max[3] = {root->bv[1], root->bv[3], root->bv[5]};
1064 copy_v3_v3(r_bb_min, bb_min);
1065 copy_v3_v3(r_bb_max, bb_max);
1066 }
1067 else {
1068 BLI_assert(false);
1069 zero_v3(r_bb_min);
1070 zero_v3(r_bb_max);
1071 }
1072}
1073
1075
1076/* -------------------------------------------------------------------- */
1079
1083static bool tree_overlap_test(const BVHNode *node1,
1084 const BVHNode *node2,
1085 axis_t start_axis,
1086 axis_t stop_axis)
1087{
1088 const float *bv1 = node1->bv + (start_axis << 1);
1089 const float *bv2 = node2->bv + (start_axis << 1);
1090 const float *bv1_end = node1->bv + (stop_axis << 1);
1091
1092 /* test all axis if min + max overlap */
1093 for (; bv1 != bv1_end; bv1 += 2, bv2 += 2) {
1094 if ((bv1[0] > bv2[1]) || (bv2[0] > bv1[1])) {
1095 return false;
1096 }
1097 }
1098
1099 return true;
1100}
1101
1103 const BVHNode *node1,
1104 const BVHNode *node2)
1105{
1106 const BVHOverlapData_Shared *data = data_thread->shared;
1107 int j;
1108
1109 if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) {
1110 /* check if node1 is a leaf */
1111 if (!node1->node_num) {
1112 /* check if node2 is a leaf */
1113 if (!node2->node_num) {
1114 BVHTreeOverlap *overlap;
1115
1116 if (node1 == node2) [[unlikely]] {
1117 return;
1118 }
1119
1120 /* both leafs, insert overlap! */
1121 overlap = static_cast<BVHTreeOverlap *>(BLI_stack_push_r(data_thread->overlap));
1122 overlap->indexA = node1->index;
1123 overlap->indexB = node2->index;
1124 }
1125 else {
1126 for (j = 0; j < data->tree2->tree_type; j++) {
1127 if (node2->children[j]) {
1128 tree_overlap_traverse(data_thread, node1, node2->children[j]);
1129 }
1130 }
1131 }
1132 }
1133 else {
1134 for (j = 0; j < data->tree1->tree_type; j++) {
1135 if (node1->children[j]) {
1136 tree_overlap_traverse(data_thread, node1->children[j], node2);
1137 }
1138 }
1139 }
1140 }
1141}
1142
1147 const BVHNode *node1,
1148 const BVHNode *node2)
1149{
1150 BVHOverlapData_Shared *data = data_thread->shared;
1151 int j;
1152
1153 if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) {
1154 /* check if node1 is a leaf */
1155 if (!node1->node_num) {
1156 /* check if node2 is a leaf */
1157 if (!node2->node_num) {
1158 BVHTreeOverlap *overlap;
1159
1160 if (node1 == node2) [[unlikely]] {
1161 return;
1162 }
1163
1164 /* only difference to tree_overlap_traverse! */
1165 if (data->callback(data->userdata, node1->index, node2->index, data_thread->thread)) {
1166 /* both leafs, insert overlap! */
1167 overlap = static_cast<BVHTreeOverlap *>(BLI_stack_push_r(data_thread->overlap));
1168 overlap->indexA = node1->index;
1169 overlap->indexB = node2->index;
1170 }
1171 }
1172 else {
1173 for (j = 0; j < data->tree2->tree_type; j++) {
1174 if (node2->children[j]) {
1175 tree_overlap_traverse_cb(data_thread, node1, node2->children[j]);
1176 }
1177 }
1178 }
1179 }
1180 else {
1181 for (j = 0; j < data->tree1->tree_type; j++) {
1182 if (node1->children[j]) {
1183 tree_overlap_traverse_cb(data_thread, node1->children[j], node2);
1184 }
1185 }
1186 }
1187 }
1188}
1189
1194 const BVHNode *node1,
1195 const BVHNode *node2)
1196{
1197 BVHOverlapData_Shared *data = data_thread->shared;
1198 int j;
1199
1200 if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) {
1201 /* check if node1 is a leaf */
1202 if (!node1->node_num) {
1203 /* check if node2 is a leaf */
1204 if (!node2->node_num) {
1205 BVHTreeOverlap *overlap;
1206
1207 if (node1 == node2) [[unlikely]] {
1208 return false;
1209 }
1210
1211 /* only difference to tree_overlap_traverse! */
1212 if (!data->callback ||
1213 data->callback(data->userdata, node1->index, node2->index, data_thread->thread))
1214 {
1215 /* both leafs, insert overlap! */
1216 if (data_thread->overlap) {
1217 overlap = static_cast<BVHTreeOverlap *>(BLI_stack_push_r(data_thread->overlap));
1218 overlap->indexA = node1->index;
1219 overlap->indexB = node2->index;
1220 }
1221 return (--data_thread->max_interactions) == 0;
1222 }
1223 }
1224 else {
1225 for (j = 0; j < node2->node_num; j++) {
1226 if (tree_overlap_traverse_num(data_thread, node1, node2->children[j])) {
1227 return true;
1228 }
1229 }
1230 }
1231 }
1232 else {
1233 const uint max_interactions = data_thread->max_interactions;
1234 for (j = 0; j < node1->node_num; j++) {
1235 if (tree_overlap_traverse_num(data_thread, node1->children[j], node2)) {
1236 data_thread->max_interactions = max_interactions;
1237 }
1238 }
1239 }
1240 }
1241 return false;
1242}
1243
1246 const BVHNode *node1,
1247 const BVHNode *node2)
1248{
1249 if (data->max_interactions) {
1250 tree_overlap_traverse_num(data, node1, node2);
1251 }
1252 else if (data->shared->callback) {
1253 tree_overlap_traverse_cb(data, node1, node2);
1254 }
1255 else {
1256 tree_overlap_traverse(data, node1, node2);
1257 }
1258}
1259
1262{
1263 for (int i = 0; i < node->node_num; i++) {
1264 /* Recursively compute self-overlap within each child. */
1265 tree_overlap_traverse_self_cb(data_thread, node->children[i]);
1266
1267 /* Compute overlap of pairs of children, testing each one only once (assume symmetry). */
1268 for (int j = i + 1; j < node->node_num; j++) {
1269 tree_overlap_traverse_cb(data_thread, node->children[i], node->children[j]);
1270 }
1271 }
1272}
1273
1276{
1277 for (int i = 0; i < node->node_num; i++) {
1278 /* Recursively compute self-overlap within each child. */
1279 tree_overlap_traverse_self(data_thread, node->children[i]);
1280
1281 /* Compute overlap of pairs of children, testing each one only once (assume symmetry). */
1282 for (int j = i + 1; j < node->node_num; j++) {
1283 tree_overlap_traverse(data_thread, node->children[i], node->children[j]);
1284 }
1285 }
1286}
1287
1290 const BVHNode *node)
1291{
1292 if (data_thread->shared->callback) {
1293 tree_overlap_traverse_self_cb(data_thread, node);
1294 }
1295 else {
1296 tree_overlap_traverse_self(data_thread, node);
1297 }
1298}
1299
1301{
1302 return std::min<int>(tree->tree_type, tree->nodes[tree->leaf_num]->node_num);
1303}
1304
1305static void bvhtree_overlap_task_cb(void *__restrict userdata,
1306 const int j,
1307 const TaskParallelTLS *__restrict /*tls*/)
1308{
1309 BVHOverlapData_Thread *data = &(static_cast<BVHOverlapData_Thread *>(userdata))[j];
1310 BVHOverlapData_Shared *data_shared = data->shared;
1311
1312 const BVHNode *root1 = data_shared->tree1->nodes[data_shared->tree1->leaf_num];
1313
1314 if (data_shared->use_self) {
1315 /* This code matches one outer loop iteration within traverse_self. */
1317
1318 for (int k = j + 1; k < root1->node_num; k++) {
1319 tree_overlap_invoke_traverse(data, root1->children[j], root1->children[k]);
1320 }
1321 }
1322 else {
1323 const BVHNode *root2 = data_shared->tree2->nodes[data_shared->tree2->leaf_num];
1324
1325 tree_overlap_invoke_traverse(data, root1->children[j], root2);
1326 }
1327}
1328
1330 const BVHTree *tree1,
1331 const BVHTree *tree2,
1332 uint *r_overlap_num,
1333 /* optional callback to test the overlap before adding (must be thread-safe!) */
1334 BVHTree_OverlapCallback callback,
1335 void *userdata,
1336 const uint max_interactions,
1337 const int flag)
1338{
1339 bool overlap_pairs = (flag & BVH_OVERLAP_RETURN_PAIRS) != 0;
1340 bool use_threading = (flag & BVH_OVERLAP_USE_THREADING) != 0 &&
1342 bool use_self = (flag & BVH_OVERLAP_SELF) != 0;
1343
1344 /* 'RETURN_PAIRS' was not implemented without 'max_interactions'. */
1345 BLI_assert(overlap_pairs || max_interactions);
1346 /* Self-overlap does not support max interactions (it's not symmetrical). */
1347 BLI_assert(!use_self || (tree1 == tree2 && !max_interactions));
1348
1349 const int root_node_len = BLI_bvhtree_overlap_thread_num(tree1);
1350 const int thread_num = use_threading ? root_node_len : 1;
1351 int j;
1352 size_t total = 0;
1353 BVHTreeOverlap *overlap = nullptr, *to = nullptr;
1354 BVHOverlapData_Shared data_shared;
1355 BVHOverlapData_Thread *data = BLI_array_alloca(data, size_t(thread_num));
1356 axis_t start_axis, stop_axis;
1357
1358 /* check for compatibility of both trees (can't compare 14-DOP with 18-DOP) */
1359 if ((tree1->axis != tree2->axis) && (tree1->axis == 14 || tree2->axis == 14) &&
1360 (tree1->axis == 18 || tree2->axis == 18)) [[unlikely]]
1361 {
1362 BLI_assert(0);
1363 return nullptr;
1364 }
1365
1366 if (use_self && tree1 != tree2) [[unlikely]] {
1367 use_self = false;
1368 }
1369
1370 const BVHNode *root1 = tree1->nodes[tree1->leaf_num];
1371 const BVHNode *root2 = tree2->nodes[tree2->leaf_num];
1372
1373 start_axis = min_axis(tree1->start_axis, tree2->start_axis);
1374 stop_axis = min_axis(tree1->stop_axis, tree2->stop_axis);
1375
1376 /* fast check root nodes for collision before doing big splitting + traversal */
1377 if (!tree_overlap_test(root1, root2, start_axis, stop_axis)) {
1378 return nullptr;
1379 }
1380
1381 data_shared.tree1 = tree1;
1382 data_shared.tree2 = tree2;
1383 data_shared.start_axis = start_axis;
1384 data_shared.stop_axis = stop_axis;
1385 data_shared.use_self = use_self;
1386
1387 /* can be nullptr */
1388 data_shared.callback = callback;
1389 data_shared.userdata = userdata;
1390
1391 for (j = 0; j < thread_num; j++) {
1392 /* init BVHOverlapData_Thread */
1393 data[j].shared = &data_shared;
1394 data[j].overlap = overlap_pairs ? BLI_stack_new(sizeof(BVHTreeOverlap), __func__) : nullptr;
1395 data[j].max_interactions = use_self ? 0 : max_interactions;
1396
1397 /* for callback */
1398 data[j].thread = j;
1399 }
1400
1401 if (use_threading) {
1402 TaskParallelSettings settings;
1404 settings.min_iter_per_thread = 1;
1405 BLI_task_parallel_range(0, root_node_len, data, bvhtree_overlap_task_cb, &settings);
1406 }
1407 else if (use_self) {
1409 }
1410 else {
1411 tree_overlap_invoke_traverse(data, root1, root2);
1412 }
1413
1414 if (overlap_pairs) {
1415 for (j = 0; j < thread_num; j++) {
1416 total += BLI_stack_count(data[j].overlap);
1417 }
1418
1419 to = overlap = MEM_new_array_uninitialized<BVHTreeOverlap>(total, "BVHTreeOverlap");
1420
1421 for (j = 0; j < thread_num; j++) {
1422 uint count = uint(BLI_stack_count(data[j].overlap));
1423 BLI_stack_pop_n(data[j].overlap, to, count);
1424 BLI_stack_free(data[j].overlap);
1425 to += count;
1426 }
1427 *r_overlap_num = uint(total);
1428 }
1429
1430 return overlap;
1431}
1432
1434 const BVHTree *tree1,
1435 const BVHTree *tree2,
1436 uint *r_overlap_num,
1437 /* optional callback to test the overlap before adding (must be thread-safe!) */
1438 BVHTree_OverlapCallback callback,
1439 void *userdata)
1440{
1441 return BLI_bvhtree_overlap_ex(tree1,
1442 tree2,
1443 r_overlap_num,
1444 callback,
1445 userdata,
1446 0,
1448}
1449
1451 const BVHTree *tree,
1452 uint *r_overlap_num,
1453 /* optional callback to test the overlap before adding (must be thread-safe!) */
1454 BVHTree_OverlapCallback callback,
1455 void *userdata)
1456{
1457 return BLI_bvhtree_overlap_ex(tree,
1458 tree,
1459 r_overlap_num,
1460 callback,
1461 userdata,
1462 0,
1465}
1466
1468
1469/* -------------------------------------------------------------------- */
1472
1473static bool tree_intersect_plane_test(const float *bv, const float plane[4])
1474{
1475 /* TODO(@germano): Support other KDOP geometries. */
1476 const float bb_min[3] = {bv[0], bv[2], bv[4]};
1477 const float bb_max[3] = {bv[1], bv[3], bv[5]};
1478 float bb_near[3], bb_far[3];
1479 aabb_get_near_far_from_plane(plane, bb_min, bb_max, bb_near, bb_far);
1480 if ((plane_point_side_v3(plane, bb_near) > 0.0f) != (plane_point_side_v3(plane, bb_far) > 0.0f))
1481 {
1482 return true;
1483 }
1484
1485 return false;
1486}
1487
1489 const BVHNode *node)
1490{
1491 if (tree_intersect_plane_test(node->bv, data->plane)) {
1492 /* check if node is a leaf */
1493 if (!node->node_num) {
1494 int *intersect = static_cast<int *>(BLI_stack_push_r(data->intersect));
1495 *intersect = node->index;
1496 }
1497 else {
1498 for (int j = 0; j < data->tree->tree_type; j++) {
1499 if (node->children[j]) {
1501 }
1502 }
1503 }
1504 }
1505}
1506
1507int *BLI_bvhtree_intersect_plane(const BVHTree *tree, float plane[4], uint *r_intersect_num)
1508{
1509 int *intersect = nullptr;
1510 size_t total = 0;
1511
1512 if (tree->leaf_num) {
1514 data.tree = tree;
1515 copy_v4_v4(data.plane, plane);
1516 data.intersect = BLI_stack_new(sizeof(int), __func__);
1517
1518 const BVHNode *root = tree->nodes[tree->leaf_num];
1520
1521 total = BLI_stack_count(data.intersect);
1522 if (total) {
1524 BLI_stack_pop_n(data.intersect, intersect, uint(total));
1525 }
1526 BLI_stack_free(data.intersect);
1527 }
1528 *r_intersect_num = uint(total);
1529 return intersect;
1530}
1531
1533
1534/* -------------------------------------------------------------------- */
1537
1538/* Determines the nearest point of the given node BV.
1539 * Returns the squared distance to that point. */
1540static float calc_nearest_point_squared(const float proj[3], BVHNode *node, float nearest[3])
1541{
1542 int i;
1543 const float *bv = node->bv;
1544
1545 /* nearest on AABB hull */
1546 for (i = 0; i != 3; i++, bv += 2) {
1547 float val = proj[i];
1548 val = std::max(bv[0], val);
1549 val = std::min(bv[1], val);
1550 nearest[i] = val;
1551 }
1552
1553 return len_squared_v3v3(proj, nearest);
1554}
1555
1556/* Depth first search method */
1558{
1559 if (node->node_num == 0) {
1560 if (data->callback) {
1561 data->callback(data->userdata, node->index, data->co, &data->nearest);
1562 }
1563 else {
1564 data->nearest.index = node->index;
1565 data->nearest.dist_sq = calc_nearest_point_squared(data->proj, node, data->nearest.co);
1566 }
1567 }
1568 else {
1569 /* Better heuristic to pick the closest node to dive on */
1570 int i;
1571 float nearest[3];
1572
1573 if (data->proj[node->main_axis] <= node->children[0]->bv[node->main_axis * 2 + 1]) {
1574
1575 for (i = 0; i != node->node_num; i++) {
1576 if (calc_nearest_point_squared(data->proj, node->children[i], nearest) >=
1577 data->nearest.dist_sq)
1578 {
1579 continue;
1580 }
1581 dfs_find_nearest_dfs(data, node->children[i]);
1582 }
1583 }
1584 else {
1585 for (i = node->node_num - 1; i >= 0; i--) {
1586 if (calc_nearest_point_squared(data->proj, node->children[i], nearest) >=
1587 data->nearest.dist_sq)
1588 {
1589 continue;
1590 }
1591 dfs_find_nearest_dfs(data, node->children[i]);
1592 }
1593 }
1594 }
1595}
1596
1598{
1599 float nearest[3], dist_sq;
1600 dist_sq = calc_nearest_point_squared(data->proj, node, nearest);
1601 if (dist_sq >= data->nearest.dist_sq) {
1602 return;
1603 }
1605}
1606
1607/* Priority queue method */
1609{
1610 if (node->node_num == 0) {
1611 if (data->callback) {
1612 data->callback(data->userdata, node->index, data->co, &data->nearest);
1613 }
1614 else {
1615 data->nearest.index = node->index;
1616 data->nearest.dist_sq = calc_nearest_point_squared(data->proj, node, data->nearest.co);
1617 }
1618 }
1619 else {
1620 float nearest[3];
1621
1622 for (int i = 0; i != node->node_num; i++) {
1623 float dist_sq = calc_nearest_point_squared(data->proj, node->children[i], nearest);
1624
1625 if (dist_sq < data->nearest.dist_sq) {
1626 BLI_heapsimple_insert(heap, dist_sq, node->children[i]);
1627 }
1628 }
1629 }
1630}
1631
1633{
1634 float nearest[3];
1635 float dist_sq = calc_nearest_point_squared(data->proj, root, nearest);
1636
1637 if (dist_sq < data->nearest.dist_sq) {
1639
1640 heap_find_nearest_inner(data, heap, root);
1641
1642 while (!BLI_heapsimple_is_empty(heap) &&
1643 BLI_heapsimple_top_value(heap) < data->nearest.dist_sq)
1644 {
1645 BVHNode *node = static_cast<BVHNode *>(BLI_heapsimple_pop_min(heap));
1647 }
1648
1649 BLI_heapsimple_free(heap, nullptr);
1650 }
1651}
1652
1654 const float co[3],
1655 BVHTreeNearest *nearest,
1657 void *userdata,
1658 int flag)
1659{
1660 axis_t axis_iter;
1661
1663 BVHNode *root = tree->nodes[tree->leaf_num];
1664
1665 /* init data to search */
1666 data.tree = tree;
1667 data.co = co;
1668
1669 data.callback = callback;
1670 data.userdata = userdata;
1671
1672 for (axis_iter = data.tree->start_axis; axis_iter != data.tree->stop_axis; axis_iter++) {
1673 data.proj[axis_iter] = dot_v3v3(data.co, bvhtree_kdop_axes[axis_iter]);
1674 }
1675
1676 if (nearest) {
1677 memcpy(&data.nearest, nearest, sizeof(*nearest));
1678 }
1679 else {
1680 data.nearest.index = -1;
1681 data.nearest.dist_sq = FLT_MAX;
1682 }
1683
1684 /* dfs search */
1685 if (root) {
1686 if (flag & BVH_NEAREST_OPTIMAL_ORDER) {
1688 }
1689 else {
1691 }
1692 }
1693
1694 /* copy back results */
1695 if (nearest) {
1696 memcpy(nearest, &data.nearest, sizeof(*nearest));
1697 }
1698
1699 return data.nearest.index;
1700}
1701
1703 const float co[3],
1704 BVHTreeNearest *nearest,
1706 void *userdata)
1707{
1708 return BLI_bvhtree_find_nearest_ex(tree, co, nearest, callback, userdata, 0);
1709}
1710
1712
1713/* -------------------------------------------------------------------- */
1716
1717static bool isect_aabb_v3(BVHNode *node, const float co[3])
1718{
1719 const BVHTreeAxisRange *bv = reinterpret_cast<const BVHTreeAxisRange *>(node->bv);
1720
1721 if (co[0] > bv[0].min && co[0] < bv[0].max && co[1] > bv[1].min && co[1] < bv[1].max &&
1722 co[2] > bv[2].min && co[2] < bv[2].max)
1723 {
1724 return true;
1725 }
1726
1727 return false;
1728}
1729
1731{
1732 if (node->node_num == 0) {
1733 if (isect_aabb_v3(node, data->co)) {
1734 if (data->callback) {
1735 const float dist_sq = data->nearest.dist_sq;
1736 data->callback(data->userdata, node->index, data->co, &data->nearest);
1737 return (data->nearest.dist_sq < dist_sq);
1738 }
1739 data->nearest.index = node->index;
1740 return true;
1741 }
1742 }
1743 else {
1744 /* Better heuristic to pick the closest node to dive on */
1745 int i;
1746
1747 if (data->proj[node->main_axis] <= node->children[0]->bv[node->main_axis * 2 + 1]) {
1748 for (i = 0; i != node->node_num; i++) {
1749 if (isect_aabb_v3(node->children[i], data->co)) {
1750 if (dfs_find_duplicate_fast_dfs(data, node->children[i])) {
1751 return true;
1752 }
1753 }
1754 }
1755 }
1756 else {
1757 for (i = node->node_num; i--;) {
1758 if (isect_aabb_v3(node->children[i], data->co)) {
1759 if (dfs_find_duplicate_fast_dfs(data, node->children[i])) {
1760 return true;
1761 }
1762 }
1763 }
1764 }
1765 }
1766 return false;
1767}
1768
1770 const float co[3],
1771 const float dist_sq,
1773 void *userdata)
1774{
1776 BVHNode *root = tree->nodes[tree->leaf_num];
1777
1778 /* init data to search */
1779 data.tree = tree;
1780 data.co = co;
1781
1782 data.callback = callback;
1783 data.userdata = userdata;
1784 data.nearest.index = -1;
1785 data.nearest.dist_sq = dist_sq;
1786
1787 /* dfs search */
1788 if (root) {
1790 }
1791
1792 return data.nearest.index;
1793}
1794
1796
1797/* -------------------------------------------------------------------- */
1803
1804/* Determines the distance that the ray must travel to hit the bounding volume of the given node */
1805static float ray_nearest_hit(const BVHRayCastData *data, const float bv[6])
1806{
1807 int i;
1808
1809 float low = 0, upper = data->hit.dist;
1810
1811 for (i = 0; i != 3; i++, bv += 2) {
1812 if (data->ray_dot_axis[i] == 0.0f) {
1813 /* axis aligned ray */
1814 if (data->ray.origin[i] < bv[0] - data->ray.radius ||
1815 data->ray.origin[i] > bv[1] + data->ray.radius)
1816 {
1817 return FLT_MAX;
1818 }
1819 }
1820 else {
1821 float ll = (bv[0] - data->ray.radius - data->ray.origin[i]) / data->ray_dot_axis[i];
1822 float lu = (bv[1] + data->ray.radius - data->ray.origin[i]) / data->ray_dot_axis[i];
1823
1824 if (data->ray_dot_axis[i] > 0.0f) {
1825 low = std::max(ll, low);
1826 upper = std::min(lu, upper);
1827 }
1828 else {
1829 low = std::max(lu, low);
1830 upper = std::min(ll, upper);
1831 }
1832
1833 if (low > upper) {
1834 return FLT_MAX;
1835 }
1836 }
1837 }
1838 return low;
1839}
1840
1849{
1850 const float *bv = node->bv;
1851
1852 float t1x = (bv[data->index[0]] - data->ray.origin[0]) * data->idot_axis[0];
1853 float t2x = (bv[data->index[1]] - data->ray.origin[0]) * data->idot_axis[0];
1854 float t1y = (bv[data->index[2]] - data->ray.origin[1]) * data->idot_axis[1];
1855 float t2y = (bv[data->index[3]] - data->ray.origin[1]) * data->idot_axis[1];
1856 float t1z = (bv[data->index[4]] - data->ray.origin[2]) * data->idot_axis[2];
1857 float t2z = (bv[data->index[5]] - data->ray.origin[2]) * data->idot_axis[2];
1858
1859 if ((t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) ||
1860 (t2x < 0.0f || t2y < 0.0f || t2z < 0.0f) ||
1861 (t1x > data->hit.dist || t1y > data->hit.dist || t1z > data->hit.dist))
1862 {
1863 return FLT_MAX;
1864 }
1865 return std::max({t1x, t1y, t1z});
1866}
1867
1869{
1870 int i;
1871
1872 /* ray-bv is really fast.. and simple tests revealed its worth to test it
1873 * before calling the ray-primitive functions */
1874 /* XXX: temporary solution for particles until fast_ray_nearest_hit supports ray.radius */
1875 float dist = (data->ray.radius == 0.0f) ? fast_ray_nearest_hit(data, node) :
1877 if (dist >= data->hit.dist) {
1878 return;
1879 }
1880
1881 if (node->node_num == 0) {
1882 if (data->callback) {
1883 data->callback(data->userdata, node->index, &data->ray, &data->hit);
1884 }
1885 else {
1886 data->hit.index = node->index;
1887 data->hit.dist = dist;
1888 madd_v3_v3v3fl(data->hit.co, data->ray.origin, data->ray.direction, dist);
1889 }
1890 }
1891 else {
1892 /* pick loop direction to dive into the tree (based on ray direction and split axis) */
1893 if (data->ray_dot_axis[node->main_axis] > 0.0f) {
1894 for (i = 0; i != node->node_num; i++) {
1895 dfs_raycast(data, node->children[i]);
1896 }
1897 }
1898 else {
1899 for (i = node->node_num - 1; i >= 0; i--) {
1900 dfs_raycast(data, node->children[i]);
1901 }
1902 }
1903 }
1904}
1905
1910{
1911 int i;
1912
1913 /* ray-bv is really fast.. and simple tests revealed its worth to test it
1914 * before calling the ray-primitive functions */
1915 /* XXX: temporary solution for particles until fast_ray_nearest_hit supports ray.radius */
1916 float dist = (data->ray.radius == 0.0f) ? fast_ray_nearest_hit(data, node) :
1918 if (dist >= data->hit.dist) {
1919 return;
1920 }
1921
1922 if (node->node_num == 0) {
1923 /* no need to check for 'data->callback' (using 'all' only makes sense with a callback). */
1924 dist = data->hit.dist;
1925 data->callback(data->userdata, node->index, &data->ray, &data->hit);
1926 data->hit.index = -1;
1927 data->hit.dist = dist;
1928 }
1929 else {
1930 /* pick loop direction to dive into the tree (based on ray direction and split axis) */
1931 if (data->ray_dot_axis[node->main_axis] > 0.0f) {
1932 for (i = 0; i != node->node_num; i++) {
1933 dfs_raycast_all(data, node->children[i]);
1934 }
1935 }
1936 else {
1937 for (i = node->node_num - 1; i >= 0; i--) {
1938 dfs_raycast_all(data, node->children[i]);
1939 }
1940 }
1941 }
1942}
1943
1945{
1946 int i;
1947
1948 for (i = 0; i < 3; i++) {
1949 data->ray_dot_axis[i] = dot_v3v3(data->ray.direction, bvhtree_kdop_axes[i]);
1950
1951 if (fabsf(data->ray_dot_axis[i]) < FLT_EPSILON) {
1952 data->ray_dot_axis[i] = 0.0f;
1953 /* Sign is not important in this case, `data->index` is adjusted anyway. */
1954 data->idot_axis[i] = FLT_MAX;
1955 }
1956 else {
1957 data->idot_axis[i] = 1.0f / data->ray_dot_axis[i];
1958 }
1959
1960 data->index[2 * i] = data->idot_axis[i] < 0.0f ? 1 : 0;
1961 data->index[2 * i + 1] = 1 - data->index[2 * i];
1962 data->index[2 * i] += 2 * i;
1963 data->index[2 * i + 1] += 2 * i;
1964 }
1965
1966#ifdef USE_KDOPBVH_WATERTIGHT
1967 if (flag & BVH_RAYCAST_WATERTIGHT) {
1968 isect_ray_tri_watertight_v3_precalc(&data->isect_precalc, data->ray.direction);
1969 data->ray.isect_precalc = &data->isect_precalc;
1970 }
1971 else {
1972 data->ray.isect_precalc = nullptr;
1973 }
1974#else
1975 UNUSED_VARS(flag);
1976#endif
1977}
1978
1980 const float co[3],
1981 const float dir[3],
1982 float radius,
1983 BVHTreeRayHit *hit,
1984 BVHTree_RayCastCallback callback,
1985 void *userdata,
1986 int flag)
1987{
1989 BVHNode *root = tree->nodes[tree->leaf_num];
1990
1991 BLI_ASSERT_UNIT_V3(dir);
1992
1993 data.tree = tree;
1994
1995 data.callback = callback;
1996 data.userdata = userdata;
1997
1998 copy_v3_v3(data.ray.origin, co);
1999 copy_v3_v3(data.ray.direction, dir);
2000 data.ray.radius = radius;
2001
2003
2004 if (hit) {
2005 memcpy(&data.hit, hit, sizeof(*hit));
2006 }
2007 else {
2008 data.hit.index = -1;
2009 data.hit.dist = BVH_RAYCAST_DIST_MAX;
2010 }
2011
2012 if (root) {
2013 dfs_raycast(&data, root);
2014 // iterative_raycast(&data, root);
2015 }
2016
2017 if (hit) {
2018 memcpy(hit, &data.hit, sizeof(*hit));
2019 }
2020
2021 return data.hit.index;
2022}
2023
2025 const float co[3],
2026 const float dir[3],
2027 float radius,
2028 BVHTreeRayHit *hit,
2029 BVHTree_RayCastCallback callback,
2030 void *userdata)
2031{
2033 tree, co, dir, radius, hit, callback, userdata, BVH_RAYCAST_DEFAULT);
2034}
2035
2036float BLI_bvhtree_bb_raycast(const float bv[6],
2037 const float light_start[3],
2038 const float light_end[3],
2039 float pos[3])
2040{
2042 float dist;
2043
2044 data.hit.dist = BVH_RAYCAST_DIST_MAX;
2045
2046 /* get light direction */
2047 sub_v3_v3v3(data.ray.direction, light_end, light_start);
2048
2049 data.ray.radius = 0.0;
2050
2051 copy_v3_v3(data.ray.origin, light_start);
2052
2053 normalize_v3(data.ray.direction);
2054 copy_v3_v3(data.ray_dot_axis, data.ray.direction);
2055
2056 dist = ray_nearest_hit(&data, bv);
2057
2058 madd_v3_v3v3fl(pos, light_start, data.ray.direction, dist);
2059
2060 return dist;
2061}
2062
2064 const float co[3],
2065 const float dir[3],
2066 float radius,
2067 float hit_dist,
2068 BVHTree_RayCastCallback callback,
2069 void *userdata,
2070 int flag)
2071{
2073 BVHNode *root = tree->nodes[tree->leaf_num];
2074
2075 BLI_ASSERT_UNIT_V3(dir);
2076 BLI_assert(callback != nullptr);
2077
2078 data.tree = tree;
2079
2080 data.callback = callback;
2081 data.userdata = userdata;
2082
2083 copy_v3_v3(data.ray.origin, co);
2084 copy_v3_v3(data.ray.direction, dir);
2085 data.ray.radius = radius;
2086
2088
2089 data.hit.index = -1;
2090 data.hit.dist = hit_dist;
2091
2092 if (root) {
2093 dfs_raycast_all(&data, root);
2094 }
2095}
2096
2098 const float co[3],
2099 const float dir[3],
2100 float radius,
2101 float hit_dist,
2102 BVHTree_RayCastCallback callback,
2103 void *userdata)
2104{
2106 tree, co, dir, radius, hit_dist, callback, userdata, BVH_RAYCAST_DEFAULT);
2107}
2108
2110
2111/* -------------------------------------------------------------------- */
2119
2122 const float *center;
2123 float radius_sq; /* squared radius */
2124
2125 int hits;
2126
2129};
2130
2132{
2133 if (node->node_num == 0) {
2134#if 0 /*UNUSED*/
2135 /* Calculate the node min-coords
2136 * (if the node was a point then this is the point coordinates) */
2137 float co[3];
2138 co[0] = node->bv[0];
2139 co[1] = node->bv[2];
2140 co[2] = node->bv[4];
2141#endif
2142 }
2143 else {
2144 int i;
2145 for (i = 0; i != node->node_num; i++) {
2146 float nearest[3];
2147 float dist_sq = calc_nearest_point_squared(data->center, node->children[i], nearest);
2148 if (dist_sq < data->radius_sq) {
2149 /* Its a leaf.. call the callback */
2150 if (node->children[i]->node_num == 0) {
2151 data->hits++;
2152 data->callback(data->userdata, node->children[i]->index, data->center, dist_sq);
2153 }
2154 else {
2155 dfs_range_query(data, node->children[i]);
2156 }
2157 }
2158 }
2159 }
2160}
2161
2163 const float co[3],
2164 float radius,
2165 BVHTree_RangeQuery callback,
2166 void *userdata)
2167{
2168 BVHNode *root = tree->nodes[tree->leaf_num];
2169
2171 data.tree = tree;
2172 data.center = co;
2173 data.radius_sq = radius * radius;
2174 data.hits = 0;
2175
2176 data.callback = callback;
2177 data.userdata = userdata;
2178
2179 if (root != nullptr) {
2180 float nearest[3];
2181 float dist_sq = calc_nearest_point_squared(data.center, root, nearest);
2182 if (dist_sq < data.radius_sq) {
2183 /* Its a leaf.. call the callback */
2184 if (root->node_num == 0) {
2185 data.hits++;
2186 data.callback(data.userdata, root->index, co, dist_sq);
2187 }
2188 else {
2189 dfs_range_query(&data, root);
2190 }
2191 }
2192 }
2193
2194 return data.hits;
2195}
2196
2198
2199/* -------------------------------------------------------------------- */
2202
2204 const BVHNode *node)
2205{
2206 if (node->node_num == 0) {
2207 if (data->callback) {
2208 data->callback(data->userdata, node->index, &data->precalc, nullptr, 0, &data->nearest);
2209 }
2210 else {
2211 data->nearest.index = node->index;
2212 data->nearest.dist_sq = dist_squared_to_projected_aabb(
2213 &data->precalc,
2214 float3{node->bv[0], node->bv[2], node->bv[4]},
2215 float3{node->bv[1], node->bv[3], node->bv[5]},
2216 data->closest_axis);
2217 }
2218 }
2219 else {
2220 /* First pick the closest node to recurse into */
2221 if (data->closest_axis[node->main_axis]) {
2222 for (int i = 0; i != node->node_num; i++) {
2223 const float *bv = node->children[i]->bv;
2224
2226 float3{bv[0], bv[2], bv[4]},
2227 float3{bv[1], bv[3], bv[5]},
2228 data->closest_axis) <= data->nearest.dist_sq)
2229 {
2231 }
2232 }
2233 }
2234 else {
2235 for (int i = node->node_num; i--;) {
2236 const float *bv = node->children[i]->bv;
2237
2239 float3{bv[0], bv[2], bv[4]},
2240 float3{bv[1], bv[3], bv[5]},
2241 data->closest_axis) <= data->nearest.dist_sq)
2242 {
2244 }
2245 }
2246 }
2247 }
2248}
2249
2251 BVHNearestProjectedData *__restrict data, const BVHNode *node)
2252{
2253 if (node->node_num == 0) {
2254 if (data->callback) {
2255 data->callback(data->userdata,
2256 node->index,
2257 &data->precalc,
2258 data->clip_plane,
2259 data->clip_plane_len,
2260 &data->nearest);
2261 }
2262 else {
2263 data->nearest.index = node->index;
2264 data->nearest.dist_sq = dist_squared_to_projected_aabb(
2265 &data->precalc,
2266 float3{node->bv[0], node->bv[2], node->bv[4]},
2267 float3{node->bv[1], node->bv[3], node->bv[5]},
2268 data->closest_axis);
2269 }
2270 }
2271 else {
2272 /* First pick the closest node to recurse into */
2273 if (data->closest_axis[node->main_axis]) {
2274 for (int i = 0; i != node->node_num; i++) {
2275 const float *bv = node->children[i]->bv;
2276 const float bb_min[3] = {bv[0], bv[2], bv[4]};
2277 const float bb_max[3] = {bv[1], bv[3], bv[5]};
2278
2279 int isect_type = isect_aabb_planes_v3(
2280 data->clip_plane, data->clip_plane_len, bb_min, bb_max);
2281
2282 if ((isect_type != ISECT_AABB_PLANE_BEHIND_ANY) &&
2283 dist_squared_to_projected_aabb(&data->precalc, bb_min, bb_max, data->closest_axis) <=
2284 data->nearest.dist_sq)
2285 {
2286 if (isect_type == ISECT_AABB_PLANE_CROSS_ANY) {
2288 }
2289 else {
2290 /* ISECT_AABB_PLANE_IN_FRONT_ALL */
2292 }
2293 }
2294 }
2295 }
2296 else {
2297 for (int i = node->node_num; i--;) {
2298 const float *bv = node->children[i]->bv;
2299 const float bb_min[3] = {bv[0], bv[2], bv[4]};
2300 const float bb_max[3] = {bv[1], bv[3], bv[5]};
2301
2302 int isect_type = isect_aabb_planes_v3(
2303 data->clip_plane, data->clip_plane_len, bb_min, bb_max);
2304
2305 if (isect_type != ISECT_AABB_PLANE_BEHIND_ANY &&
2306 dist_squared_to_projected_aabb(&data->precalc, bb_min, bb_max, data->closest_axis) <=
2307 data->nearest.dist_sq)
2308 {
2309 if (isect_type == ISECT_AABB_PLANE_CROSS_ANY) {
2311 }
2312 else {
2313 /* ISECT_AABB_PLANE_IN_FRONT_ALL */
2315 }
2316 }
2317 }
2318 }
2319 }
2320}
2321
2323 float projmat[4][4],
2324 float winsize[2],
2325 float mval[2],
2326 float (*clip_plane)[4],
2327 int clip_plane_len,
2328 BVHTreeNearest *nearest,
2330 void *userdata)
2331{
2332 const BVHNode *root = tree->nodes[tree->leaf_num];
2333 if (root != nullptr) {
2335 alloca(sizeof(*data) + (sizeof(*clip_plane) * size_t(max_ii(1, clip_plane_len)))));
2336
2337 dist_squared_to_projected_aabb_precalc(&data->precalc, projmat, winsize, mval);
2338
2339 data->callback = callback;
2340 data->userdata = userdata;
2341
2342#ifdef __GNUC__ /* Invalid `data->clip_plane` warning with GCC 14.2.1. */
2343# pragma GCC diagnostic push
2344# pragma GCC diagnostic ignored "-Warray-bounds"
2345#endif
2346 if (clip_plane) {
2347 data->clip_plane_len = clip_plane_len;
2348 for (int i = 0; i < clip_plane_len; i++) {
2349 copy_v4_v4(data->clip_plane[i], clip_plane[i]);
2350 }
2351 }
2352 else {
2353 data->clip_plane_len = 1;
2355 projmat, nullptr, nullptr, nullptr, nullptr, data->clip_plane[0], nullptr);
2356 }
2357#ifdef __GNUC__
2358# pragma GCC diagnostic pop
2359#endif
2360
2361 if (nearest) {
2362 memcpy(&data->nearest, nearest, sizeof(*nearest));
2363 }
2364 else {
2365 data->nearest.index = -1;
2366 data->nearest.dist_sq = FLT_MAX;
2367 }
2368 {
2369 const float bb_min[3] = {root->bv[0], root->bv[2], root->bv[4]};
2370 const float bb_max[3] = {root->bv[1], root->bv[3], root->bv[5]};
2371
2372 int isect_type = isect_aabb_planes_v3(
2373 data->clip_plane, data->clip_plane_len, bb_min, bb_max);
2374
2375 if (isect_type != 0 &&
2376 dist_squared_to_projected_aabb(&data->precalc, bb_min, bb_max, data->closest_axis) <=
2377 data->nearest.dist_sq)
2378 {
2379 if (isect_type == 1) {
2381 }
2382 else {
2384 }
2385 }
2386 }
2387
2388 if (nearest) {
2389 memcpy(nearest, &data->nearest, sizeof(*nearest));
2390 }
2391
2392 return data->nearest.index;
2393 }
2394 return -1;
2395}
2396
2398
2399} // namespace blender
#define BLI_array_alloca(arr, realsize)
Definition BLI_alloca.hh:18
A min-heap / priority queue ADT.
#define KDOPBVH_THREAD_LEAF_THRESHOLD
#define MAX_TREETYPE
#define BVH_RAYCAST_DIST_MAX
#define BVH_RAYCAST_DEFAULT
#define BLI_ASSERT_UNIT_V3(v)
#define ISECT_AABB_PLANE_CROSS_ANY
#define ISECT_AABB_PLANE_BEHIND_ANY
#define MINLINE
Read Blender memory allocation and freeing.
#define BLI_assert_unreachable()
#define UNUSED_VARS(...)
#define SWAP(type, a, b)
btScalar max
#define printf
bool intersect(IsectPyramid i_pyramid, Box box)
#define FLT_MAX
#define FLT_EPSILON
BMesh Iterators.
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void(*)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) BVHTree_RayCastCallback
BVHTreeOverlap * BLI_bvhtree_overlap_ex(const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, uint max_interactions, int flag)
static char get_largest_axis(const float *bv)
void BLI_bvhtree_get_bounding_box(const BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
static int implicit_needed_branches(int tree_type, int leafs)
const float bvhtree_kdop_axes[13][3]
BLI_STATIC_ASSERT(ARRAY_SIZE(data_mode_strings)==CTX_MODE_NUM+1, "Must have a string for each context mode") const char *CTX_data_mode_string(const bContext *C)
static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node)
@ BVH_NEAREST_OPTIMAL_ORDER
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
void(*)(void *userdata, int index, const float co[3], float dist_sq) BVHTree_RangeQuery
uchar axis_t
int * BLI_bvhtree_intersect_plane(const BVHTree *tree, float plane[4], uint *r_intersect_num)
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
static BVHNode * bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
int BLI_bvhtree_get_tree_type(const BVHTree *tree)
int BLI_bvhtree_find_nearest(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
HeapSimple * BLI_heapsimple_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:99
float BLI_bvhtree_get_epsilon(const BVHTree *tree)
int isect_aabb_planes_v3(const float(*planes)[4], int totplane, const float bbmin[3], const float bbmax[3])
void BLI_bvhtree_free(BVHTree *tree)
static void bvh_insertionsort(BVHNode **a, int lo, int hi, int axis)
void planes_from_projmat(const float mat[4][4], float left[4], float right[4], float bottom[4], float top[4], float near[4], float far[4])
int BLI_bvhtree_ray_cast_ex(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata, int flag)
void BLI_bvhtree_balance(BVHTree *tree)
static const float bvhtree_kdop_axes_length[13]
static void bvhtree_ray_cast_data_precalc(BVHRayCastData *data, int flag)
static void bvhtree_nearest_projected_dfs_recursive(BVHNearestProjectedData *__restrict data, const BVHNode *node)
static void split_leafs(BVHNode **leafs_array, const int nth[], const int partitions, const int split_axis)
MINLINE int max_ii(int a, int b)
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
static void dfs_range_query(RangeQueryData *data, BVHNode *node)
static bool isect_aabb_v3(BVHNode *node, const float co[3])
static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
int BLI_bvhtree_ray_cast(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
void * BLI_stack_push_r(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:106
bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
static void node_minmax_init(const BVHTree *tree, BVHNode *node)
void dist_squared_to_projected_aabb_precalc(struct DistProjectedAABBPrecalc *precalc, const float projmat[4][4], const float winsize[2], const float mval[2])
Definition math_geom.cc:832
static void bvhtree_intersect_plane_dfs_recursive(BVHIntersectPlaneData *__restrict data, const BVHNode *node)
static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
static void tree_overlap_traverse_self(BVHOverlapData_Thread *data_thread, const BVHNode *node)
static void bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(BVHNearestProjectedData *__restrict data, const BVHNode *node)
int BLI_bvhtree_find_nearest_ex(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
void BLI_bvhtree_update_tree(BVHTree *tree)
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
unsigned char uchar
Definition BKE_text.h:58
size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:231
static void heap_find_nearest_inner(BVHNearestData *data, HeapSimple *heap, BVHNode *node)
BMesh const char void * data
static int implicit_leafs_index(const BVHBuildHelper *data, const int depth, const int child_index)
static void build_implicit_tree_helper(const BVHTree *tree, BVHBuildHelper *data)
int BLI_bvhtree_range_query(const BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
int BLI_bvhtree_get_len(const BVHTree *tree)
MINLINE axis_t min_axis(axis_t a, axis_t b)
static int bvh_partition(BVHNode **a, int lo, int hi, const BVHNode *x, int axis)
static void dfs_raycast_all(BVHRayCastData *data, BVHNode *node)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
void aabb_get_near_far_from_plane(const float plane_no[3], const float bbmin[3], const float bbmax[3], float bb_near[3], float bb_afar[3])
Definition math_geom.cc:665
static void tree_overlap_traverse(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
MINLINE float plane_point_side_v3(const float plane[4], const float co[3])
void isect_ray_tri_watertight_v3_precalc(struct IsectRayPrecalc *isect_precalc, const float ray_direction[3])
float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
static void tree_overlap_invoke_traverse_self(BVHOverlapData_Thread *data_thread, const BVHNode *node)
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
BVHTreeOverlap * BLI_bvhtree_overlap_self(const BVHTree *tree, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node)
@ BVH_OVERLAP_USE_THREADING
@ BVH_OVERLAP_RETURN_PAIRS
@ BVH_OVERLAP_SELF
void BLI_bvhtree_ray_cast_all(const BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata)
static void partition_nth_element(BVHNode **a, int begin, int end, const int n, const int axis)
MINLINE void zero_v3(float r[3])
@ BVH_RAYCAST_WATERTIGHT
static void tree_overlap_traverse_cb(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
void BLI_bvhtree_ray_cast_all_ex(const BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata, int flag)
static void non_recursive_bvh_div_nodes(const BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int leafs_num)
int BLI_bvhtree_overlap_thread_num(const BVHTree *tree)
static bool tree_overlap_test(const BVHNode *node1, const BVHNode *node2, axis_t start_axis, axis_t stop_axis)
float BLI_heapsimple_top_value(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
MINLINE float normalize_v3(float n[3])
bool(*)(void *userdata, int index_a, int index_b, int thread) BVHTree_OverlapCallback
static void bvhtree_node_inflate(const BVHTree *tree, BVHNode *node, const float dist)
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
static void heap_find_nearest_begin(BVHNearestData *data, BVHNode *root)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
static void create_kdop_hull(const BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving)
static bool dfs_find_duplicate_fast_dfs(BVHNearestData *data, BVHNode *node)
static void bvhtree_overlap_task_cb(void *__restrict userdata, const int j, const TaskParallelTLS *__restrict)
static void non_recursive_bvh_div_nodes_task_cb(void *__restrict userdata, const int j, const TaskParallelTLS *__restrict)
iter begin(iter)
MINLINE float max_ff(float a, float b)
static void tree_overlap_invoke_traverse(BVHOverlapData_Thread *data, const BVHNode *node1, const BVHNode *node2)
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
static float ray_nearest_hit(const BVHRayCastData *data, const float bv[6])
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
static bool tree_intersect_plane_test(const float *bv, const float plane[4])
static float calc_nearest_point_squared(const float proj[3], BVHNode *node, float nearest[3])
MINLINE void copy_v4_v4(float r[4], const float a[4])
VecBase< float, 3 > float3
float dist_squared_to_projected_aabb(struct DistProjectedAABBPrecalc *data, const float bbmin[3], const float bbmax[3], bool r_axis_closest[3])
Definition math_geom.cc:884
static void refit_kdop_hull(const BVHTree *tree, BVHNode *node, int start, int end)
void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
Definition stack.cc:150
BLI_Stack * BLI_stack_new(size_t elem_size, const char *description) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:85
static void node_join(BVHTree *tree, BVHNode *node)
MINLINE int min_ii(int a, int b)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void(*)(void *userdata, int index, const DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest) BVHTree_NearestProjectedCallback
int BLI_bvhtree_find_nearest_first(const BVHTree *tree, const float co[3], float dist_sq, BVHTree_NearestPointCallback callback, void *userdata)
static bool tree_overlap_traverse_num(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
int BLI_bvhtree_find_nearest_projected(const BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], float(*clip_planes)[4], int clip_plane_len, BVHTreeNearest *nearest, BVHTree_NearestProjectedCallback callback, void *userdata)
static void tree_overlap_traverse_self_cb(BVHOverlapData_Thread *data_thread, const BVHNode *node)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void(*)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest) BVHTree_NearestPointCallback
#define fabsf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define min(a, b)
Definition sort.cc:38
const BVHBuildHelper * data
BVHTree_NearestPointCallback callback
DistProjectedAABBPrecalc precalc
BVHTree_NearestProjectedCallback callback
BVHNode ** children
BVHOverlapData_Shared * shared
BVHTree_RayCastCallback callback
BVHNode ** nodes
BVHNode * nodearray
BVHNode ** nodechild
BVHTree_RangeQuery callback