Blender  V3.3
BLI_kdopbvh.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2006 NaN Holding BV. All rights reserved. */
3 
25 #include "MEM_guardedalloc.h"
26 
27 #include "BLI_alloca.h"
28 #include "BLI_heap_simple.h"
29 #include "BLI_kdopbvh.h"
30 #include "BLI_math.h"
31 #include "BLI_stack.h"
32 #include "BLI_task.h"
33 #include "BLI_utildefines.h"
34 
35 #include "BLI_strict_flags.h"
36 
37 /* used for iterative_raycast */
38 // #define USE_SKIP_LINKS
39 
40 /* Use to print balanced output. */
41 // #define USE_PRINT_TREE
42 
43 /* Check tree is valid. */
44 // #define USE_VERIFY_TREE
45 
46 #define MAX_TREETYPE 32
47 
48 /* Setting zero so we can catch bugs in BLI_task/KDOPBVH.
49  * TODO(sergey): Deduplicate the limits with PBVH from BKE.
50  */
51 #ifdef DEBUG
52 # define KDOPBVH_THREAD_LEAF_THRESHOLD 0
53 #else
54 # define KDOPBVH_THREAD_LEAF_THRESHOLD 1024
55 #endif
56 
57 /* -------------------------------------------------------------------- */
61 typedef unsigned char axis_t;
62 
63 typedef struct BVHNode {
64  struct BVHNode **children;
65  struct BVHNode *parent; /* some user defined traversed need that */
66 #ifdef USE_SKIP_LINKS
67  struct BVHNode *skip[2];
68 #endif
69  float *bv; /* Bounding volume of all nodes, max 13 axis */
70  int index; /* face, edge, vertex index */
71  char node_num; /* how many nodes are used, used for speedup */
72  char main_axis; /* Axis used to split this node */
74 
75 /* keep under 26 bytes for speed purposes */
76 struct BVHTree {
78  BVHNode *nodearray; /* pre-alloc branch nodes */
79  BVHNode **nodechild; /* pre-alloc children for nodes */
80  float *nodebv; /* pre-alloc bounding-volumes for nodes */
81  float epsilon; /* Epsilon is used for inflation of the K-DOP. */
82  int leaf_num; /* leafs */
84  axis_t start_axis, stop_axis; /* bvhtree_kdop_axes array indices according to axis */
85  axis_t axis; /* KDOP type (6 => OBB, 7 => AABB, ...) */
86  char tree_type; /* type of tree (4 => quad-tree). */
87 };
88 
89 /* optimization, ensure we stay small */
90 BLI_STATIC_ASSERT((sizeof(void *) == 8 && sizeof(BVHTree) <= 48) ||
91  (sizeof(void *) == 4 && sizeof(BVHTree) <= 32),
92  "over sized")
93 
94 /* avoid duplicating vars in BVHOverlapData_Thread */
95 typedef struct BVHOverlapData_Shared {
96  const BVHTree *tree1, *tree2;
97  axis_t start_axis, stop_axis;
98 
99  /* use for callbacks */
101  void *userdata;
103 
104 typedef struct BVHOverlapData_Thread {
106  struct BLI_Stack *overlap; /* store BVHTreeOverlap */
108  /* use for callbacks */
109  int thread;
111 
112 typedef struct BVHNearestData {
113  const BVHTree *tree;
114  const float *co;
116  void *userdata;
117  float proj[13]; /* coordinates projection over axis */
119 
121 
122 typedef struct BVHRayCastData {
123  const BVHTree *tree;
124 
126  void *userdata;
127 
129 
130 #ifdef USE_KDOPBVH_WATERTIGHT
131  struct IsectRayPrecalc isect_precalc;
132 #endif
133 
134  /* initialized by bvhtree_ray_cast_data_precalc */
135  float ray_dot_axis[13];
136  float idot_axis[13];
137  int index[6];
138 
141 
142 typedef struct BVHNearestProjectedData {
143  const BVHTree *tree;
145  bool closest_axis[3];
146  float clip_plane[6][4];
149  void *userdata;
151 
153 
154 typedef struct BVHIntersectPlaneData {
155  const BVHTree *tree;
156  float plane[4];
157  struct BLI_Stack *intersect; /* Store indexes. */
159 
170 const float bvhtree_kdop_axes[13][3] = {
171  {1.0, 0, 0},
172  {0, 1.0, 0},
173  {0, 0, 1.0},
174  {1.0, 1.0, 1.0},
175  {1.0, -1.0, 1.0},
176  {1.0, 1.0, -1.0},
177  {1.0, -1.0, -1.0},
178  {1.0, 1.0, 0},
179  {1.0, 0, 1.0},
180  {0, 1.0, 1.0},
181  {1.0, -1.0, 0},
182  {1.0, 0, -1.0},
183  {0, 1.0, -1.0},
184 };
185 
186 /* Used to correct the epsilon and thus match the overlap distance. */
187 static const float bvhtree_kdop_axes_length[13] = {
188  1.0f,
189  1.0f,
190  1.0f,
191  1.7320508075688772f,
192  1.7320508075688772f,
193  1.7320508075688772f,
194  1.7320508075688772f,
195  1.4142135623730951f,
196  1.4142135623730951f,
197  1.4142135623730951f,
198  1.4142135623730951f,
199  1.4142135623730951f,
200  1.4142135623730951f,
201 };
202 
203 /* -------------------------------------------------------------------- */
208 {
209  return (a < b) ? a : b;
210 }
211 #if 0
212 MINLINE axis_t max_axis(axis_t a, axis_t b)
213 {
214  return (b < a) ? a : b;
215 }
216 #endif
217 
225 static void node_minmax_init(const BVHTree *tree, BVHNode *node)
226 {
227  axis_t axis_iter;
228  float(*bv)[2] = (float(*)[2])node->bv;
229 
230  for (axis_iter = tree->start_axis; axis_iter != tree->stop_axis; axis_iter++) {
231  bv[axis_iter][0] = FLT_MAX;
232  bv[axis_iter][1] = -FLT_MAX;
233  }
234 }
235 
238 /* -------------------------------------------------------------------- */
245 static void bvh_insertionsort(BVHNode **a, int lo, int hi, int axis)
246 {
247  int i, j;
248  BVHNode *t;
249  for (i = lo; i < hi; i++) {
250  j = i;
251  t = a[i];
252  while ((j != lo) && (t->bv[axis] < (a[j - 1])->bv[axis])) {
253  a[j] = a[j - 1];
254  j--;
255  }
256  a[j] = t;
257  }
258 }
259 
260 static int bvh_partition(BVHNode **a, int lo, int hi, BVHNode *x, int axis)
261 {
262  int i = lo, j = hi;
263  while (1) {
264  while (a[i]->bv[axis] < x->bv[axis]) {
265  i++;
266  }
267  j--;
268  while (x->bv[axis] < a[j]->bv[axis]) {
269  j--;
270  }
271  if (!(i < j)) {
272  return i;
273  }
274  SWAP(BVHNode *, a[i], a[j]);
275  i++;
276  }
277 }
278 
279 /* returns Sortable */
280 static BVHNode *bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis)
281 {
282  if ((a[mid])->bv[axis] < (a[lo])->bv[axis]) {
283  if ((a[hi])->bv[axis] < (a[mid])->bv[axis]) {
284  return a[mid];
285  }
286  if ((a[hi])->bv[axis] < (a[lo])->bv[axis]) {
287  return a[hi];
288  }
289  return a[lo];
290  }
291 
292  if ((a[hi])->bv[axis] < (a[mid])->bv[axis]) {
293  if ((a[hi])->bv[axis] < (a[lo])->bv[axis]) {
294  return a[lo];
295  }
296  return a[hi];
297  }
298  return a[mid];
299 }
300 
305 static void partition_nth_element(BVHNode **a, int begin, int end, const int n, const int axis)
306 {
307  while (end - begin > 3) {
308  const int cut = bvh_partition(
309  a, begin, end, bvh_medianof3(a, begin, (begin + end) / 2, end - 1, axis), axis);
310  if (cut <= n) {
311  begin = cut;
312  }
313  else {
314  end = cut;
315  }
316  }
317  bvh_insertionsort(a, begin, end, axis);
318 }
319 
320 #ifdef USE_SKIP_LINKS
321 static void build_skip_links(BVHTree *tree, BVHNode *node, BVHNode *left, BVHNode *right)
322 {
323  int i;
324 
325  node->skip[0] = left;
326  node->skip[1] = right;
327 
328  for (i = 0; i < node->node_num; i++) {
329  if (i + 1 < node->node_num) {
330  build_skip_links(tree, node->children[i], left, node->children[i + 1]);
331  }
332  else {
333  build_skip_links(tree, node->children[i], left, right);
334  }
335 
336  left = node->children[i];
337  }
338 }
339 #endif
340 
341 /*
342  * BVHTree bounding volumes functions
343  */
344 static void create_kdop_hull(
345  const BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving)
346 {
347  float newminmax;
348  float *bv = node->bv;
349  int k;
350  axis_t axis_iter;
351 
352  /* Don't initialize bounds for the moving case */
353  if (!moving) {
355  }
356 
357  for (k = 0; k < numpoints; k++) {
358  /* for all Axes. */
359  for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
360  newminmax = dot_v3v3(&co[k * 3], bvhtree_kdop_axes[axis_iter]);
361  if (newminmax < bv[2 * axis_iter]) {
362  bv[2 * axis_iter] = newminmax;
363  }
364  if (newminmax > bv[(2 * axis_iter) + 1]) {
365  bv[(2 * axis_iter) + 1] = newminmax;
366  }
367  }
368  }
369 }
370 
374 static void refit_kdop_hull(const BVHTree *tree, BVHNode *node, int start, int end)
375 {
376  float newmin, newmax;
377  float *__restrict bv = node->bv;
378  int j;
379  axis_t axis_iter;
380 
382 
383  for (j = start; j < end; j++) {
384  float *__restrict node_bv = tree->nodes[j]->bv;
385 
386  /* for all Axes. */
387  for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
388  newmin = node_bv[(2 * axis_iter)];
389  if ((newmin < bv[(2 * axis_iter)])) {
390  bv[(2 * axis_iter)] = newmin;
391  }
392 
393  newmax = node_bv[(2 * axis_iter) + 1];
394  if ((newmax > bv[(2 * axis_iter) + 1])) {
395  bv[(2 * axis_iter) + 1] = newmax;
396  }
397  }
398  }
399 }
400 
404 static char get_largest_axis(const float *bv)
405 {
406  float middle_point[3];
407 
408  middle_point[0] = (bv[1]) - (bv[0]); /* x axis */
409  middle_point[1] = (bv[3]) - (bv[2]); /* y axis */
410  middle_point[2] = (bv[5]) - (bv[4]); /* z axis */
411  if (middle_point[0] > middle_point[1]) {
412  if (middle_point[0] > middle_point[2]) {
413  return 1; /* max x axis */
414  }
415  return 5; /* max z axis */
416  }
417  if (middle_point[1] > middle_point[2]) {
418  return 3; /* max y axis */
419  }
420  return 5; /* max z axis */
421 }
422 
427 {
428  int i;
429  axis_t axis_iter;
430 
432 
433  for (i = 0; i < tree->tree_type; i++) {
434  if (node->children[i]) {
435  for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
436  /* update minimum */
437  if (node->children[i]->bv[(2 * axis_iter)] < node->bv[(2 * axis_iter)]) {
438  node->bv[(2 * axis_iter)] = node->children[i]->bv[(2 * axis_iter)];
439  }
440 
441  /* update maximum */
442  if (node->children[i]->bv[(2 * axis_iter) + 1] > node->bv[(2 * axis_iter) + 1]) {
443  node->bv[(2 * axis_iter) + 1] = node->children[i]->bv[(2 * axis_iter) + 1];
444  }
445  }
446  }
447  else {
448  break;
449  }
450  }
451 }
452 
453 #ifdef USE_PRINT_TREE
454 
459 static void bvhtree_print_tree(BVHTree *tree, BVHNode *node, int depth)
460 {
461  int i;
462  axis_t axis_iter;
463 
464  for (i = 0; i < depth; i++) {
465  printf(" ");
466  }
467  printf(" - %d (%ld): ", node->index, (long int)(node - tree->nodearray));
468  for (axis_iter = (axis_t)(2 * tree->start_axis); axis_iter < (axis_t)(2 * tree->stop_axis);
469  axis_iter++) {
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 
481 static 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(
492  "Memory per node = %ubytes\n",
493  (uint)(sizeof(BVHNode) + sizeof(BVHNode *) * tree->tree_type + sizeof(float) * tree->axis));
494  printf("BV memory = %ubytes\n", (uint)MEM_allocN_len(tree->nodebv));
495 
496  printf("Total memory = %ubytes\n",
497  (uint)(sizeof(BVHTree) + MEM_allocN_len(tree->nodes) + MEM_allocN_len(tree->nodearray) +
498  MEM_allocN_len(tree->nodechild) + MEM_allocN_len(tree->nodebv)));
499 
500  bvhtree_print_tree(tree, tree->nodes[tree->leaf_num], 0);
501 }
502 #endif /* USE_PRINT_TREE */
503 
504 #ifdef USE_VERIFY_TREE
505 
506 static void bvhtree_verify(BVHTree *tree)
507 {
508  int i, j, check = 0;
509 
510  /* check the pointer list */
511  for (i = 0; i < tree->leaf_num; i++) {
512  if (tree->nodes[i]->parent == NULL) {
513  printf("Leaf has no parent: %d\n", i);
514  }
515  else {
516  for (j = 0; j < tree->tree_type; j++) {
517  if (tree->nodes[i]->parent->children[j] == tree->nodes[i]) {
518  check = 1;
519  }
520  }
521  if (!check) {
522  printf("Parent child relationship doesn't match: %d\n", i);
523  }
524  check = 0;
525  }
526  }
527 
528  /* check the leaf list */
529  for (i = 0; i < tree->leaf_num; i++) {
530  if (tree->nodearray[i].parent == NULL) {
531  printf("Leaf has no parent: %d\n", i);
532  }
533  else {
534  for (j = 0; j < tree->tree_type; j++) {
535  if (tree->nodearray[i].parent->children[j] == &tree->nodearray[i]) {
536  check = 1;
537  }
538  }
539  if (!check) {
540  printf("Parent child relationship doesn't match: %d\n", i);
541  }
542  check = 0;
543  }
544  }
545 
546  printf("branches: %d, leafs: %d, total: %d\n",
547  tree->branch_num,
548  tree->leaf_num,
549  tree->branch_num + tree->leaf_num);
550 }
551 #endif /* USE_VERIFY_TREE */
552 
553 /* Helper data and structures to build a min-leaf generalized implicit tree
554  * This code can be easily reduced
555  * (basically this is only method to calculate pow(k, n) in O(1).. and stuff like that) */
556 typedef struct BVHBuildHelper {
559 
564 
567 
569 
571 {
572  int depth = 0;
573  int remain;
574  int nnodes;
575 
576  data->leafs_num = tree->leaf_num;
577  data->tree_type = tree->tree_type;
578 
579  /* Calculate the smallest tree_type^n such that tree_type^n >= leafs_num */
580  for (data->leafs_per_child[0] = 1; data->leafs_per_child[0] < data->leafs_num;
581  data->leafs_per_child[0] *= data->tree_type) {
582  /* pass */
583  }
584 
585  data->branches_on_level[0] = 1;
586 
587  for (depth = 1; (depth < 32) && data->leafs_per_child[depth - 1]; depth++) {
588  data->branches_on_level[depth] = data->branches_on_level[depth - 1] * data->tree_type;
589  data->leafs_per_child[depth] = data->leafs_per_child[depth - 1] / data->tree_type;
590  }
591 
592  remain = data->leafs_num - data->leafs_per_child[1];
593  nnodes = (remain + data->tree_type - 2) / (data->tree_type - 1);
594  data->remain_leafs = remain + nnodes;
595 }
596 
600 static int implicit_leafs_index(const BVHBuildHelper *data, const int depth, const int child_index)
601 {
602  int min_leaf_index = child_index * data->leafs_per_child[depth - 1];
603  if (min_leaf_index <= data->remain_leafs) {
604  return min_leaf_index;
605  }
606  if (data->leafs_per_child[depth]) {
607  return data->leafs_num -
608  (data->branches_on_level[depth - 1] - child_index) * data->leafs_per_child[depth];
609  }
610  return data->remain_leafs;
611 }
612 
642 /* This functions returns the number of branches needed to have the requested number of leafs. */
643 static int implicit_needed_branches(int tree_type, int leafs)
644 {
645  return max_ii(1, (leafs + tree_type - 3) / (tree_type - 1));
646 }
647 
660 static void split_leafs(BVHNode **leafs_array,
661  const int nth[],
662  const int partitions,
663  const int split_axis)
664 {
665  int i;
666  for (i = 0; i < partitions - 1; i++) {
667  if (nth[i] >= nth[partitions]) {
668  break;
669  }
670 
671  partition_nth_element(leafs_array, nth[i], nth[partitions], nth[i + 1], split_axis);
672  }
673 }
674 
675 typedef struct BVHDivNodesData {
676  const BVHTree *tree;
679 
682 
684 
685  int depth;
686  int i;
689 
690 static void non_recursive_bvh_div_nodes_task_cb(void *__restrict userdata,
691  const int j,
692  const TaskParallelTLS *__restrict UNUSED(tls))
693 {
694  BVHDivNodesData *data = userdata;
695 
696  int k;
697  const int parent_level_index = j - data->i;
698  BVHNode *parent = &data->branches_array[j];
699  int nth_positions[MAX_TREETYPE + 1];
700  char split_axis;
701 
702  int parent_leafs_begin = implicit_leafs_index(data->data, data->depth, parent_level_index);
703  int parent_leafs_end = implicit_leafs_index(data->data, data->depth, parent_level_index + 1);
704 
705  /* This calculates the bounding box of this branch
706  * and chooses the largest axis as the axis to divide leafs */
707  refit_kdop_hull(data->tree, parent, parent_leafs_begin, parent_leafs_end);
708  split_axis = get_largest_axis(parent->bv);
709 
710  /* Save split axis (this can be used on ray-tracing to speedup the query time) */
711  parent->main_axis = split_axis / 2;
712 
713  /* Split the children along the split_axis, NOTE: its not needed to sort the whole leafs array
714  * Only to assure that the elements are partitioned on a way that each child takes the elements
715  * it would take in case the whole array was sorted.
716  * Split_leafs takes care of that "sort" problem. */
717  nth_positions[0] = parent_leafs_begin;
718  nth_positions[data->tree_type] = parent_leafs_end;
719  for (k = 1; k < data->tree_type; k++) {
720  const int child_index = j * data->tree_type + data->tree_offset + k;
721  /* child level index */
722  const int child_level_index = child_index - data->first_of_next_level;
723  nth_positions[k] = implicit_leafs_index(data->data, data->depth + 1, child_level_index);
724  }
725 
726  split_leafs(data->leafs_array, nth_positions, data->tree_type, split_axis);
727 
728  /* Setup `children` and `node_num` counters
729  * Not really needed but currently most of BVH code
730  * relies on having an explicit children structure */
731  for (k = 0; k < data->tree_type; k++) {
732  const int child_index = j * data->tree_type + data->tree_offset + k;
733  /* child level index */
734  const int child_level_index = child_index - data->first_of_next_level;
735 
736  const int child_leafs_begin = implicit_leafs_index(
737  data->data, data->depth + 1, child_level_index);
738  const int child_leafs_end = implicit_leafs_index(
739  data->data, data->depth + 1, child_level_index + 1);
740 
741  if (child_leafs_end - child_leafs_begin > 1) {
742  parent->children[k] = &data->branches_array[child_index];
743  parent->children[k]->parent = parent;
744  }
745  else if (child_leafs_end - child_leafs_begin == 1) {
746  parent->children[k] = data->leafs_array[child_leafs_begin];
747  parent->children[k]->parent = parent;
748  }
749  else {
750  break;
751  }
752  }
753  parent->node_num = (char)k;
754 }
755 
775  BVHNode *branches_array,
776  BVHNode **leafs_array,
777  int leafs_num)
778 {
779  int i;
780 
781  const int tree_type = tree->tree_type;
782  /* this value is 0 (on binary trees) and negative on the others */
783  const int tree_offset = 2 - tree->tree_type;
784 
785  const int branches_num = implicit_needed_branches(tree_type, leafs_num);
786 
788  int depth;
789 
790  {
791  /* set parent from root node to NULL */
792  BVHNode *root = &branches_array[1];
793  root->parent = NULL;
794 
795  /* Most of bvhtree code relies on 1-leaf trees having at least one branch
796  * We handle that special case here */
797  if (leafs_num == 1) {
798  refit_kdop_hull(tree, root, 0, leafs_num);
799  root->main_axis = get_largest_axis(root->bv) / 2;
800  root->node_num = 1;
801  root->children[0] = leafs_array[0];
802  root->children[0]->parent = root;
803  return;
804  }
805  }
806 
808 
809  BVHDivNodesData cb_data = {
810  .tree = tree,
811  .branches_array = branches_array,
812  .leafs_array = leafs_array,
813  .tree_type = tree_type,
814  .tree_offset = tree_offset,
815  .data = &data,
816  .first_of_next_level = 0,
817  .depth = 0,
818  .i = 0,
819  };
820 
821  /* Loop tree levels (log N) loops */
822  for (i = 1, depth = 1; i <= branches_num; i = i * tree_type + tree_offset, depth++) {
823  const int first_of_next_level = i * tree_type + tree_offset;
824  /* index of last branch on this level */
825  const int i_stop = min_ii(first_of_next_level, branches_num + 1);
826 
827  /* Loop all branches on this level */
828  cb_data.first_of_next_level = first_of_next_level;
829  cb_data.i = i;
830  cb_data.depth = depth;
831 
832  if (true) {
833  TaskParallelSettings settings;
835  settings.use_threading = (leafs_num > KDOPBVH_THREAD_LEAF_THRESHOLD);
836  BLI_task_parallel_range(i, i_stop, &cb_data, non_recursive_bvh_div_nodes_task_cb, &settings);
837  }
838  else {
839  /* Less hassle for debugging. */
840  TaskParallelTLS tls = {0};
841  for (int i_task = i; i_task < i_stop; i_task++) {
842  non_recursive_bvh_div_nodes_task_cb(&cb_data, i_task, &tls);
843  }
844  }
845  }
846 }
847 
850 /* -------------------------------------------------------------------- */
854 BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
855 {
856  BVHTree *tree;
857  int numnodes, i;
858 
859  BLI_assert(tree_type >= 2 && tree_type <= MAX_TREETYPE);
860 
861  tree = MEM_callocN(sizeof(BVHTree), "BVHTree");
862 
863  /* tree epsilon must be >= FLT_EPSILON
864  * so that tangent rays can still hit a bounding volume..
865  * this bug would show up when casting a ray aligned with a KDOP-axis
866  * and with an edge of 2 faces */
867  epsilon = max_ff(FLT_EPSILON, epsilon);
868 
869  if (tree) {
870  tree->epsilon = epsilon;
871  tree->tree_type = tree_type;
872  tree->axis = axis;
873 
874  if (axis == 26) {
875  tree->start_axis = 0;
876  tree->stop_axis = 13;
877  }
878  else if (axis == 18) {
879  tree->start_axis = 7;
880  tree->stop_axis = 13;
881  }
882  else if (axis == 14) {
883  tree->start_axis = 0;
884  tree->stop_axis = 7;
885  }
886  else if (axis == 8) { /* AABB */
887  tree->start_axis = 0;
888  tree->stop_axis = 4;
889  }
890  else if (axis == 6) { /* OBB */
891  tree->start_axis = 0;
892  tree->stop_axis = 3;
893  }
894  else {
895  /* should never happen! */
897 
898  goto fail;
899  }
900 
901  /* Allocate arrays */
902  numnodes = maxsize + implicit_needed_branches(tree_type, maxsize) + tree_type;
903 
904  tree->nodes = MEM_callocN(sizeof(BVHNode *) * (size_t)numnodes, "BVHNodes");
905  tree->nodebv = MEM_callocN(sizeof(float) * (size_t)(axis * numnodes), "BVHNodeBV");
906  tree->nodechild = MEM_callocN(sizeof(BVHNode *) * (size_t)(tree_type * numnodes), "BVHNodeBV");
907  tree->nodearray = MEM_callocN(sizeof(BVHNode) * (size_t)numnodes, "BVHNodeArray");
908 
909  if (UNLIKELY((!tree->nodes) || (!tree->nodebv) || (!tree->nodechild) || (!tree->nodearray))) {
910  goto fail;
911  }
912 
913  /* link the dynamic bv and child links */
914  for (i = 0; i < numnodes; i++) {
915  tree->nodearray[i].bv = &tree->nodebv[i * axis];
916  tree->nodearray[i].children = &tree->nodechild[i * tree_type];
917  }
918  }
919  return tree;
920 
921 fail:
923  return NULL;
924 }
925 
927 {
928  if (tree) {
929  MEM_SAFE_FREE(tree->nodes);
930  MEM_SAFE_FREE(tree->nodearray);
931  MEM_SAFE_FREE(tree->nodebv);
932  MEM_SAFE_FREE(tree->nodechild);
933  MEM_freeN(tree);
934  }
935 }
936 
938 {
939  BVHNode **leafs_array = tree->nodes;
940 
941  /* This function should only be called once
942  * (some big bug goes here if its being called more than once per tree) */
943  BLI_assert(tree->branch_num == 0);
944 
945  /* Build the implicit tree */
947  tree, tree->nodearray + (tree->leaf_num - 1), leafs_array, tree->leaf_num);
948 
949  /* current code expects the branches to be linked to the nodes array
950  * we perform that linkage here */
951  tree->branch_num = implicit_needed_branches(tree->tree_type, tree->leaf_num);
952  for (int i = 0; i < tree->branch_num; i++) {
953  tree->nodes[tree->leaf_num + i] = &tree->nodearray[tree->leaf_num + i];
954  }
955 
956 #ifdef USE_SKIP_LINKS
957  build_skip_links(tree, tree->nodes[tree->leaf_num], NULL, NULL);
958 #endif
959 
960 #ifdef USE_VERIFY_TREE
961  bvhtree_verify(tree);
962 #endif
963 
964 #ifdef USE_PRINT_TREE
965  bvhtree_info(tree);
966 #endif
967 }
968 
969 static void bvhtree_node_inflate(const BVHTree *tree, BVHNode *node, const float dist)
970 {
971  axis_t axis_iter;
972  for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
973  float dist_corrected = dist * bvhtree_kdop_axes_length[axis_iter];
974  node->bv[(2 * axis_iter)] -= dist_corrected; /* minimum */
975  node->bv[(2 * axis_iter) + 1] += dist_corrected; /* maximum */
976  }
977 }
978 
979 void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
980 {
981  BVHNode *node = NULL;
982 
983  /* insert should only possible as long as tree->branch_num is 0 */
984  BLI_assert(tree->branch_num <= 0);
985  BLI_assert((size_t)tree->leaf_num < MEM_allocN_len(tree->nodes) / sizeof(*(tree->nodes)));
986 
987  node = tree->nodes[tree->leaf_num] = &(tree->nodearray[tree->leaf_num]);
988  tree->leaf_num++;
989 
990  create_kdop_hull(tree, node, co, numpoints, 0);
991  node->index = index;
992 
993  /* inflate the bv with some epsilon */
994  bvhtree_node_inflate(tree, node, tree->epsilon);
995 }
996 
998  BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
999 {
1000  BVHNode *node = NULL;
1001 
1002  /* check if index exists */
1003  if (index > tree->leaf_num) {
1004  return false;
1005  }
1006 
1007  node = tree->nodearray + index;
1008 
1009  create_kdop_hull(tree, node, co, numpoints, 0);
1010 
1011  if (co_moving) {
1012  create_kdop_hull(tree, node, co_moving, numpoints, 1);
1013  }
1014 
1015  /* inflate the bv with some epsilon */
1016  bvhtree_node_inflate(tree, node, tree->epsilon);
1017 
1018  return true;
1019 }
1020 
1022 {
1023  /* Update bottom=>top
1024  * TRICKY: the way we build the tree all the children have an index greater than the parent
1025  * This allows us todo a bottom up update by starting on the bigger numbered branch. */
1026 
1027  BVHNode **root = tree->nodes + tree->leaf_num;
1028  BVHNode **index = tree->nodes + tree->leaf_num + tree->branch_num - 1;
1029 
1030  for (; index >= root; index--) {
1031  node_join(tree, *index);
1032  }
1033 }
1035 {
1036  return tree->leaf_num;
1037 }
1038 
1040 {
1041  return tree->tree_type;
1042 }
1043 
1045 {
1046  return tree->epsilon;
1047 }
1048 
1049 void BLI_bvhtree_get_bounding_box(BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
1050 {
1051  BVHNode *root = tree->nodes[tree->leaf_num];
1052  if (root != NULL) {
1053  const float bb_min[3] = {root->bv[0], root->bv[2], root->bv[4]};
1054  const float bb_max[3] = {root->bv[1], root->bv[3], root->bv[5]};
1055  copy_v3_v3(r_bb_min, bb_min);
1056  copy_v3_v3(r_bb_max, bb_max);
1057  }
1058  else {
1059  BLI_assert(false);
1060  zero_v3(r_bb_min);
1061  zero_v3(r_bb_max);
1062  }
1063 }
1064 
1067 /* -------------------------------------------------------------------- */
1074 static bool tree_overlap_test(const BVHNode *node1,
1075  const BVHNode *node2,
1076  axis_t start_axis,
1077  axis_t stop_axis)
1078 {
1079  const float *bv1 = node1->bv + (start_axis << 1);
1080  const float *bv2 = node2->bv + (start_axis << 1);
1081  const float *bv1_end = node1->bv + (stop_axis << 1);
1082 
1083  /* test all axis if min + max overlap */
1084  for (; bv1 != bv1_end; bv1 += 2, bv2 += 2) {
1085  if ((bv1[0] > bv2[1]) || (bv2[0] > bv1[1])) {
1086  return 0;
1087  }
1088  }
1089 
1090  return 1;
1091 }
1092 
1094  const BVHNode *node1,
1095  const BVHNode *node2)
1096 {
1097  BVHOverlapData_Shared *data = data_thread->shared;
1098  int j;
1099 
1100  if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) {
1101  /* check if node1 is a leaf */
1102  if (!node1->node_num) {
1103  /* check if node2 is a leaf */
1104  if (!node2->node_num) {
1105  BVHTreeOverlap *overlap;
1106 
1107  if (UNLIKELY(node1 == node2)) {
1108  return;
1109  }
1110 
1111  /* both leafs, insert overlap! */
1112  overlap = BLI_stack_push_r(data_thread->overlap);
1113  overlap->indexA = node1->index;
1114  overlap->indexB = node2->index;
1115  }
1116  else {
1117  for (j = 0; j < data->tree2->tree_type; j++) {
1118  if (node2->children[j]) {
1119  tree_overlap_traverse(data_thread, node1, node2->children[j]);
1120  }
1121  }
1122  }
1123  }
1124  else {
1125  for (j = 0; j < data->tree1->tree_type; j++) {
1126  if (node1->children[j]) {
1127  tree_overlap_traverse(data_thread, node1->children[j], node2);
1128  }
1129  }
1130  }
1131  }
1132 }
1133 
1138  const BVHNode *node1,
1139  const BVHNode *node2)
1140 {
1141  BVHOverlapData_Shared *data = data_thread->shared;
1142  int j;
1143 
1144  if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) {
1145  /* check if node1 is a leaf */
1146  if (!node1->node_num) {
1147  /* check if node2 is a leaf */
1148  if (!node2->node_num) {
1149  BVHTreeOverlap *overlap;
1150 
1151  if (UNLIKELY(node1 == node2)) {
1152  return;
1153  }
1154 
1155  /* only difference to tree_overlap_traverse! */
1156  if (data->callback(data->userdata, node1->index, node2->index, data_thread->thread)) {
1157  /* both leafs, insert overlap! */
1158  overlap = BLI_stack_push_r(data_thread->overlap);
1159  overlap->indexA = node1->index;
1160  overlap->indexB = node2->index;
1161  }
1162  }
1163  else {
1164  for (j = 0; j < data->tree2->tree_type; j++) {
1165  if (node2->children[j]) {
1166  tree_overlap_traverse_cb(data_thread, node1, node2->children[j]);
1167  }
1168  }
1169  }
1170  }
1171  else {
1172  for (j = 0; j < data->tree1->tree_type; j++) {
1173  if (node1->children[j]) {
1174  tree_overlap_traverse_cb(data_thread, node1->children[j], node2);
1175  }
1176  }
1177  }
1178  }
1179 }
1180 
1185  const BVHNode *node1,
1186  const BVHNode *node2)
1187 {
1188  BVHOverlapData_Shared *data = data_thread->shared;
1189  int j;
1190 
1191  if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) {
1192  /* check if node1 is a leaf */
1193  if (!node1->node_num) {
1194  /* check if node2 is a leaf */
1195  if (!node2->node_num) {
1196  BVHTreeOverlap *overlap;
1197 
1198  if (UNLIKELY(node1 == node2)) {
1199  return false;
1200  }
1201 
1202  /* only difference to tree_overlap_traverse! */
1203  if (!data->callback ||
1204  data->callback(data->userdata, node1->index, node2->index, data_thread->thread)) {
1205  /* both leafs, insert overlap! */
1206  if (data_thread->overlap) {
1207  overlap = BLI_stack_push_r(data_thread->overlap);
1208  overlap->indexA = node1->index;
1209  overlap->indexB = node2->index;
1210  }
1211  return (--data_thread->max_interactions) == 0;
1212  }
1213  }
1214  else {
1215  for (j = 0; j < node2->node_num; j++) {
1216  if (tree_overlap_traverse_num(data_thread, node1, node2->children[j])) {
1217  return true;
1218  }
1219  }
1220  }
1221  }
1222  else {
1223  const uint max_interactions = data_thread->max_interactions;
1224  for (j = 0; j < node1->node_num; j++) {
1225  if (tree_overlap_traverse_num(data_thread, node1->children[j], node2)) {
1226  data_thread->max_interactions = max_interactions;
1227  }
1228  }
1229  }
1230  }
1231  return false;
1232 }
1233 
1235 {
1236  return (int)MIN2(tree->tree_type, tree->nodes[tree->leaf_num]->node_num);
1237 }
1238 
1239 static void bvhtree_overlap_task_cb(void *__restrict userdata,
1240  const int j,
1241  const TaskParallelTLS *__restrict UNUSED(tls))
1242 {
1243  BVHOverlapData_Thread *data = &((BVHOverlapData_Thread *)userdata)[j];
1244  BVHOverlapData_Shared *data_shared = data->shared;
1245 
1246  if (data->max_interactions) {
1248  data_shared->tree1->nodes[data_shared->tree1->leaf_num]->children[j],
1249  data_shared->tree2->nodes[data_shared->tree2->leaf_num]);
1250  }
1251  else if (data_shared->callback) {
1253  data_shared->tree1->nodes[data_shared->tree1->leaf_num]->children[j],
1254  data_shared->tree2->nodes[data_shared->tree2->leaf_num]);
1255  }
1256  else {
1258  data_shared->tree1->nodes[data_shared->tree1->leaf_num]->children[j],
1259  data_shared->tree2->nodes[data_shared->tree2->leaf_num]);
1260  }
1261 }
1262 
1264  const BVHTree *tree1,
1265  const BVHTree *tree2,
1266  uint *r_overlap_num,
1267  /* optional callback to test the overlap before adding (must be thread-safe!) */
1269  void *userdata,
1270  const uint max_interactions,
1271  const int flag)
1272 {
1273  bool overlap_pairs = (flag & BVH_OVERLAP_RETURN_PAIRS) != 0;
1274  bool use_threading = (flag & BVH_OVERLAP_USE_THREADING) != 0 &&
1276 
1277  /* 'RETURN_PAIRS' was not implemented without 'max_interactions'. */
1278  BLI_assert(overlap_pairs || max_interactions);
1279 
1280  const int root_node_len = BLI_bvhtree_overlap_thread_num(tree1);
1281  const int thread_num = use_threading ? root_node_len : 1;
1282  int j;
1283  size_t total = 0;
1284  BVHTreeOverlap *overlap = NULL, *to = NULL;
1285  BVHOverlapData_Shared data_shared;
1286  BVHOverlapData_Thread *data = BLI_array_alloca(data, (size_t)thread_num);
1287  axis_t start_axis, stop_axis;
1288 
1289  /* check for compatibility of both trees (can't compare 14-DOP with 18-DOP) */
1290  if (UNLIKELY((tree1->axis != tree2->axis) && (tree1->axis == 14 || tree2->axis == 14) &&
1291  (tree1->axis == 18 || tree2->axis == 18))) {
1292  BLI_assert(0);
1293  return NULL;
1294  }
1295 
1296  const BVHNode *root1 = tree1->nodes[tree1->leaf_num];
1297  const BVHNode *root2 = tree2->nodes[tree2->leaf_num];
1298 
1299  start_axis = min_axis(tree1->start_axis, tree2->start_axis);
1300  stop_axis = min_axis(tree1->stop_axis, tree2->stop_axis);
1301 
1302  /* fast check root nodes for collision before doing big splitting + traversal */
1303  if (!tree_overlap_test(root1, root2, start_axis, stop_axis)) {
1304  return NULL;
1305  }
1306 
1307  data_shared.tree1 = tree1;
1308  data_shared.tree2 = tree2;
1309  data_shared.start_axis = start_axis;
1310  data_shared.stop_axis = stop_axis;
1311 
1312  /* can be NULL */
1313  data_shared.callback = callback;
1314  data_shared.userdata = userdata;
1315 
1316  for (j = 0; j < thread_num; j++) {
1317  /* init BVHOverlapData_Thread */
1318  data[j].shared = &data_shared;
1319  data[j].overlap = overlap_pairs ? BLI_stack_new(sizeof(BVHTreeOverlap), __func__) : NULL;
1320  data[j].max_interactions = max_interactions;
1321 
1322  /* for callback */
1323  data[j].thread = j;
1324  }
1325 
1326  if (use_threading) {
1327  TaskParallelSettings settings;
1329  settings.min_iter_per_thread = 1;
1330  BLI_task_parallel_range(0, root_node_len, data, bvhtree_overlap_task_cb, &settings);
1331  }
1332  else {
1333  if (max_interactions) {
1334  tree_overlap_traverse_num(data, root1, root2);
1335  }
1336  else if (callback) {
1337  tree_overlap_traverse_cb(data, root1, root2);
1338  }
1339  else {
1340  tree_overlap_traverse(data, root1, root2);
1341  }
1342  }
1343 
1344  if (overlap_pairs) {
1345  for (j = 0; j < thread_num; j++) {
1346  total += BLI_stack_count(data[j].overlap);
1347  }
1348 
1349  to = overlap = MEM_mallocN(sizeof(BVHTreeOverlap) * total, "BVHTreeOverlap");
1350 
1351  for (j = 0; j < thread_num; j++) {
1352  uint count = (uint)BLI_stack_count(data[j].overlap);
1353  BLI_stack_pop_n(data[j].overlap, to, count);
1354  BLI_stack_free(data[j].overlap);
1355  to += count;
1356  }
1357  *r_overlap_num = (uint)total;
1358  }
1359 
1360  return overlap;
1361 }
1362 
1364  const BVHTree *tree1,
1365  const BVHTree *tree2,
1366  uint *r_overlap_num,
1367  /* optional callback to test the overlap before adding (must be thread-safe!) */
1369  void *userdata)
1370 {
1371  return BLI_bvhtree_overlap_ex(tree1,
1372  tree2,
1373  r_overlap_num,
1374  callback,
1375  userdata,
1376  0,
1378 }
1379 
1382 /* -------------------------------------------------------------------- */
1386 static bool tree_intersect_plane_test(const float *bv, const float plane[4])
1387 {
1388  /* TODO(germano): Support other KDOP geometries. */
1389  const float bb_min[3] = {bv[0], bv[2], bv[4]};
1390  const float bb_max[3] = {bv[1], bv[3], bv[5]};
1391  float bb_near[3], bb_far[3];
1392  aabb_get_near_far_from_plane(plane, bb_min, bb_max, bb_near, bb_far);
1393  if ((plane_point_side_v3(plane, bb_near) > 0.0f) !=
1394  (plane_point_side_v3(plane, bb_far) > 0.0f)) {
1395  return true;
1396  }
1397 
1398  return false;
1399 }
1400 
1402  const BVHNode *node)
1403 {
1404  if (tree_intersect_plane_test(node->bv, data->plane)) {
1405  /* check if node is a leaf */
1406  if (!node->node_num) {
1407  int *intersect = BLI_stack_push_r(data->intersect);
1408  *intersect = node->index;
1409  }
1410  else {
1411  for (int j = 0; j < data->tree->tree_type; j++) {
1412  if (node->children[j]) {
1414  }
1415  }
1416  }
1417  }
1418 }
1419 
1420 int *BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_num)
1421 {
1422  int *intersect = NULL;
1423  size_t total = 0;
1424 
1425  if (tree->leaf_num) {
1427  data.tree = tree;
1428  copy_v4_v4(data.plane, plane);
1429  data.intersect = BLI_stack_new(sizeof(int), __func__);
1430 
1431  BVHNode *root = tree->nodes[tree->leaf_num];
1433 
1434  total = BLI_stack_count(data.intersect);
1435  if (total) {
1436  intersect = MEM_mallocN(sizeof(int) * total, __func__);
1437  BLI_stack_pop_n(data.intersect, intersect, (uint)total);
1438  }
1439  BLI_stack_free(data.intersect);
1440  }
1441  *r_intersect_num = (uint)total;
1442  return intersect;
1443 }
1444 
1447 /* -------------------------------------------------------------------- */
1451 /* Determines the nearest point of the given node BV.
1452  * Returns the squared distance to that point. */
1453 static float calc_nearest_point_squared(const float proj[3], BVHNode *node, float nearest[3])
1454 {
1455  int i;
1456  const float *bv = node->bv;
1457 
1458  /* nearest on AABB hull */
1459  for (i = 0; i != 3; i++, bv += 2) {
1460  float val = proj[i];
1461  if (bv[0] > val) {
1462  val = bv[0];
1463  }
1464  if (bv[1] < val) {
1465  val = bv[1];
1466  }
1467  nearest[i] = val;
1468  }
1469 
1470  return len_squared_v3v3(proj, nearest);
1471 }
1472 
1473 /* Depth first search method */
1475 {
1476  if (node->node_num == 0) {
1477  if (data->callback) {
1478  data->callback(data->userdata, node->index, data->co, &data->nearest);
1479  }
1480  else {
1481  data->nearest.index = node->index;
1482  data->nearest.dist_sq = calc_nearest_point_squared(data->proj, node, data->nearest.co);
1483  }
1484  }
1485  else {
1486  /* Better heuristic to pick the closest node to dive on */
1487  int i;
1488  float nearest[3];
1489 
1490  if (data->proj[node->main_axis] <= node->children[0]->bv[node->main_axis * 2 + 1]) {
1491 
1492  for (i = 0; i != node->node_num; i++) {
1493  if (calc_nearest_point_squared(data->proj, node->children[i], nearest) >=
1494  data->nearest.dist_sq) {
1495  continue;
1496  }
1497  dfs_find_nearest_dfs(data, node->children[i]);
1498  }
1499  }
1500  else {
1501  for (i = node->node_num - 1; i >= 0; i--) {
1502  if (calc_nearest_point_squared(data->proj, node->children[i], nearest) >=
1503  data->nearest.dist_sq) {
1504  continue;
1505  }
1506  dfs_find_nearest_dfs(data, node->children[i]);
1507  }
1508  }
1509  }
1510 }
1511 
1513 {
1514  float nearest[3], dist_sq;
1515  dist_sq = calc_nearest_point_squared(data->proj, node, nearest);
1516  if (dist_sq >= data->nearest.dist_sq) {
1517  return;
1518  }
1520 }
1521 
1522 /* Priority queue method */
1524 {
1525  if (node->node_num == 0) {
1526  if (data->callback) {
1527  data->callback(data->userdata, node->index, data->co, &data->nearest);
1528  }
1529  else {
1530  data->nearest.index = node->index;
1531  data->nearest.dist_sq = calc_nearest_point_squared(data->proj, node, data->nearest.co);
1532  }
1533  }
1534  else {
1535  float nearest[3];
1536 
1537  for (int i = 0; i != node->node_num; i++) {
1538  float dist_sq = calc_nearest_point_squared(data->proj, node->children[i], nearest);
1539 
1540  if (dist_sq < data->nearest.dist_sq) {
1541  BLI_heapsimple_insert(heap, dist_sq, node->children[i]);
1542  }
1543  }
1544  }
1545 }
1546 
1548 {
1549  float nearest[3];
1550  float dist_sq = calc_nearest_point_squared(data->proj, root, nearest);
1551 
1552  if (dist_sq < data->nearest.dist_sq) {
1553  HeapSimple *heap = BLI_heapsimple_new_ex(32);
1554 
1555  heap_find_nearest_inner(data, heap, root);
1556 
1557  while (!BLI_heapsimple_is_empty(heap) &&
1558  BLI_heapsimple_top_value(heap) < data->nearest.dist_sq) {
1561  }
1562 
1563  BLI_heapsimple_free(heap, NULL);
1564  }
1565 }
1566 
1568  const float co[3],
1569  BVHTreeNearest *nearest,
1571  void *userdata,
1572  int flag)
1573 {
1574  axis_t axis_iter;
1575 
1577  BVHNode *root = tree->nodes[tree->leaf_num];
1578 
1579  /* init data to search */
1580  data.tree = tree;
1581  data.co = co;
1582 
1583  data.callback = callback;
1584  data.userdata = userdata;
1585 
1586  for (axis_iter = data.tree->start_axis; axis_iter != data.tree->stop_axis; axis_iter++) {
1587  data.proj[axis_iter] = dot_v3v3(data.co, bvhtree_kdop_axes[axis_iter]);
1588  }
1589 
1590  if (nearest) {
1591  memcpy(&data.nearest, nearest, sizeof(*nearest));
1592  }
1593  else {
1594  data.nearest.index = -1;
1595  data.nearest.dist_sq = FLT_MAX;
1596  }
1597 
1598  /* dfs search */
1599  if (root) {
1600  if (flag & BVH_NEAREST_OPTIMAL_ORDER) {
1601  heap_find_nearest_begin(&data, root);
1602  }
1603  else {
1604  dfs_find_nearest_begin(&data, root);
1605  }
1606  }
1607 
1608  /* copy back results */
1609  if (nearest) {
1610  memcpy(nearest, &data.nearest, sizeof(*nearest));
1611  }
1612 
1613  return data.nearest.index;
1614 }
1615 
1617  const float co[3],
1618  BVHTreeNearest *nearest,
1620  void *userdata)
1621 {
1622  return BLI_bvhtree_find_nearest_ex(tree, co, nearest, callback, userdata, 0);
1623 }
1624 
1627 /* -------------------------------------------------------------------- */
1631 static bool isect_aabb_v3(BVHNode *node, const float co[3])
1632 {
1633  const BVHTreeAxisRange *bv = (const BVHTreeAxisRange *)node->bv;
1634 
1635  if (co[0] > bv[0].min && co[0] < bv[0].max && co[1] > bv[1].min && co[1] < bv[1].max &&
1636  co[2] > bv[2].min && co[2] < bv[2].max) {
1637  return true;
1638  }
1639 
1640  return false;
1641 }
1642 
1644 {
1645  if (node->node_num == 0) {
1646  if (isect_aabb_v3(node, data->co)) {
1647  if (data->callback) {
1648  const float dist_sq = data->nearest.dist_sq;
1649  data->callback(data->userdata, node->index, data->co, &data->nearest);
1650  return (data->nearest.dist_sq < dist_sq);
1651  }
1652  data->nearest.index = node->index;
1653  return true;
1654  }
1655  }
1656  else {
1657  /* Better heuristic to pick the closest node to dive on */
1658  int i;
1659 
1660  if (data->proj[node->main_axis] <= node->children[0]->bv[node->main_axis * 2 + 1]) {
1661  for (i = 0; i != node->node_num; i++) {
1662  if (isect_aabb_v3(node->children[i], data->co)) {
1663  if (dfs_find_duplicate_fast_dfs(data, node->children[i])) {
1664  return true;
1665  }
1666  }
1667  }
1668  }
1669  else {
1670  for (i = node->node_num; i--;) {
1671  if (isect_aabb_v3(node->children[i], data->co)) {
1672  if (dfs_find_duplicate_fast_dfs(data, node->children[i])) {
1673  return true;
1674  }
1675  }
1676  }
1677  }
1678  }
1679  return false;
1680 }
1681 
1683  const float co[3],
1684  const float dist_sq,
1686  void *userdata)
1687 {
1689  BVHNode *root = tree->nodes[tree->leaf_num];
1690 
1691  /* init data to search */
1692  data.tree = tree;
1693  data.co = co;
1694 
1695  data.callback = callback;
1696  data.userdata = userdata;
1697  data.nearest.index = -1;
1698  data.nearest.dist_sq = dist_sq;
1699 
1700  /* dfs search */
1701  if (root) {
1703  }
1704 
1705  return data.nearest.index;
1706 }
1707 
1710 /* -------------------------------------------------------------------- */
1717 /* Determines the distance that the ray must travel to hit the bounding volume of the given node */
1718 static float ray_nearest_hit(const BVHRayCastData *data, const float bv[6])
1719 {
1720  int i;
1721 
1722  float low = 0, upper = data->hit.dist;
1723 
1724  for (i = 0; i != 3; i++, bv += 2) {
1725  if (data->ray_dot_axis[i] == 0.0f) {
1726  /* axis aligned ray */
1727  if (data->ray.origin[i] < bv[0] - data->ray.radius ||
1728  data->ray.origin[i] > bv[1] + data->ray.radius) {
1729  return FLT_MAX;
1730  }
1731  }
1732  else {
1733  float ll = (bv[0] - data->ray.radius - data->ray.origin[i]) / data->ray_dot_axis[i];
1734  float lu = (bv[1] + data->ray.radius - data->ray.origin[i]) / data->ray_dot_axis[i];
1735 
1736  if (data->ray_dot_axis[i] > 0.0f) {
1737  if (ll > low) {
1738  low = ll;
1739  }
1740  if (lu < upper) {
1741  upper = lu;
1742  }
1743  }
1744  else {
1745  if (lu > low) {
1746  low = lu;
1747  }
1748  if (ll < upper) {
1749  upper = ll;
1750  }
1751  }
1752 
1753  if (low > upper) {
1754  return FLT_MAX;
1755  }
1756  }
1757  }
1758  return low;
1759 }
1760 
1768 {
1769  const float *bv = node->bv;
1770 
1771  float t1x = (bv[data->index[0]] - data->ray.origin[0]) * data->idot_axis[0];
1772  float t2x = (bv[data->index[1]] - data->ray.origin[0]) * data->idot_axis[0];
1773  float t1y = (bv[data->index[2]] - data->ray.origin[1]) * data->idot_axis[1];
1774  float t2y = (bv[data->index[3]] - data->ray.origin[1]) * data->idot_axis[1];
1775  float t1z = (bv[data->index[4]] - data->ray.origin[2]) * data->idot_axis[2];
1776  float t2z = (bv[data->index[5]] - data->ray.origin[2]) * data->idot_axis[2];
1777 
1778  if ((t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) ||
1779  (t2x < 0.0f || t2y < 0.0f || t2z < 0.0f) ||
1780  (t1x > data->hit.dist || t1y > data->hit.dist || t1z > data->hit.dist)) {
1781  return FLT_MAX;
1782  }
1783  return max_fff(t1x, t1y, t1z);
1784 }
1785 
1787 {
1788  int i;
1789 
1790  /* ray-bv is really fast.. and simple tests revealed its worth to test it
1791  * before calling the ray-primitive functions */
1792  /* XXX: temporary solution for particles until fast_ray_nearest_hit supports ray.radius */
1793  float dist = (data->ray.radius == 0.0f) ? fast_ray_nearest_hit(data, node) :
1794  ray_nearest_hit(data, node->bv);
1795  if (dist >= data->hit.dist) {
1796  return;
1797  }
1798 
1799  if (node->node_num == 0) {
1800  if (data->callback) {
1801  data->callback(data->userdata, node->index, &data->ray, &data->hit);
1802  }
1803  else {
1804  data->hit.index = node->index;
1805  data->hit.dist = dist;
1806  madd_v3_v3v3fl(data->hit.co, data->ray.origin, data->ray.direction, dist);
1807  }
1808  }
1809  else {
1810  /* pick loop direction to dive into the tree (based on ray direction and split axis) */
1811  if (data->ray_dot_axis[node->main_axis] > 0.0f) {
1812  for (i = 0; i != node->node_num; i++) {
1813  dfs_raycast(data, node->children[i]);
1814  }
1815  }
1816  else {
1817  for (i = node->node_num - 1; i >= 0; i--) {
1818  dfs_raycast(data, node->children[i]);
1819  }
1820  }
1821  }
1822 }
1823 
1828 {
1829  int i;
1830 
1831  /* ray-bv is really fast.. and simple tests revealed its worth to test it
1832  * before calling the ray-primitive functions */
1833  /* XXX: temporary solution for particles until fast_ray_nearest_hit supports ray.radius */
1834  float dist = (data->ray.radius == 0.0f) ? fast_ray_nearest_hit(data, node) :
1835  ray_nearest_hit(data, node->bv);
1836  if (dist >= data->hit.dist) {
1837  return;
1838  }
1839 
1840  if (node->node_num == 0) {
1841  /* no need to check for 'data->callback' (using 'all' only makes sense with a callback). */
1842  dist = data->hit.dist;
1843  data->callback(data->userdata, node->index, &data->ray, &data->hit);
1844  data->hit.index = -1;
1845  data->hit.dist = dist;
1846  }
1847  else {
1848  /* pick loop direction to dive into the tree (based on ray direction and split axis) */
1849  if (data->ray_dot_axis[node->main_axis] > 0.0f) {
1850  for (i = 0; i != node->node_num; i++) {
1851  dfs_raycast_all(data, node->children[i]);
1852  }
1853  }
1854  else {
1855  for (i = node->node_num - 1; i >= 0; i--) {
1856  dfs_raycast_all(data, node->children[i]);
1857  }
1858  }
1859  }
1860 }
1861 
1863 {
1864  int i;
1865 
1866  for (i = 0; i < 3; i++) {
1867  data->ray_dot_axis[i] = dot_v3v3(data->ray.direction, bvhtree_kdop_axes[i]);
1868 
1869  if (fabsf(data->ray_dot_axis[i]) < FLT_EPSILON) {
1870  data->ray_dot_axis[i] = 0.0f;
1871  /* Sign is not important in this case, `data->index` is adjusted anyway. */
1872  data->idot_axis[i] = FLT_MAX;
1873  }
1874  else {
1875  data->idot_axis[i] = 1.0f / data->ray_dot_axis[i];
1876  }
1877 
1878  data->index[2 * i] = data->idot_axis[i] < 0.0f ? 1 : 0;
1879  data->index[2 * i + 1] = 1 - data->index[2 * i];
1880  data->index[2 * i] += 2 * i;
1881  data->index[2 * i + 1] += 2 * i;
1882  }
1883 
1884 #ifdef USE_KDOPBVH_WATERTIGHT
1885  if (flag & BVH_RAYCAST_WATERTIGHT) {
1886  isect_ray_tri_watertight_v3_precalc(&data->isect_precalc, data->ray.direction);
1887  data->ray.isect_precalc = &data->isect_precalc;
1888  }
1889  else {
1890  data->ray.isect_precalc = NULL;
1891  }
1892 #else
1893  UNUSED_VARS(flag);
1894 #endif
1895 }
1896 
1898  const float co[3],
1899  const float dir[3],
1900  float radius,
1901  BVHTreeRayHit *hit,
1903  void *userdata,
1904  int flag)
1905 {
1907  BVHNode *root = tree->nodes[tree->leaf_num];
1908 
1909  BLI_ASSERT_UNIT_V3(dir);
1910 
1911  data.tree = tree;
1912 
1913  data.callback = callback;
1914  data.userdata = userdata;
1915 
1916  copy_v3_v3(data.ray.origin, co);
1917  copy_v3_v3(data.ray.direction, dir);
1918  data.ray.radius = radius;
1919 
1921 
1922  if (hit) {
1923  memcpy(&data.hit, hit, sizeof(*hit));
1924  }
1925  else {
1926  data.hit.index = -1;
1927  data.hit.dist = BVH_RAYCAST_DIST_MAX;
1928  }
1929 
1930  if (root) {
1931  dfs_raycast(&data, root);
1932  // iterative_raycast(&data, root);
1933  }
1934 
1935  if (hit) {
1936  memcpy(hit, &data.hit, sizeof(*hit));
1937  }
1938 
1939  return data.hit.index;
1940 }
1941 
1943  const float co[3],
1944  const float dir[3],
1945  float radius,
1946  BVHTreeRayHit *hit,
1948  void *userdata)
1949 {
1950  return BLI_bvhtree_ray_cast_ex(
1951  tree, co, dir, radius, hit, callback, userdata, BVH_RAYCAST_DEFAULT);
1952 }
1953 
1954 float BLI_bvhtree_bb_raycast(const float bv[6],
1955  const float light_start[3],
1956  const float light_end[3],
1957  float pos[3])
1958 {
1960  float dist;
1961 
1962  data.hit.dist = BVH_RAYCAST_DIST_MAX;
1963 
1964  /* get light direction */
1965  sub_v3_v3v3(data.ray.direction, light_end, light_start);
1966 
1967  data.ray.radius = 0.0;
1968 
1969  copy_v3_v3(data.ray.origin, light_start);
1970 
1971  normalize_v3(data.ray.direction);
1972  copy_v3_v3(data.ray_dot_axis, data.ray.direction);
1973 
1974  dist = ray_nearest_hit(&data, bv);
1975 
1976  madd_v3_v3v3fl(pos, light_start, data.ray.direction, dist);
1977 
1978  return dist;
1979 }
1980 
1982  const float co[3],
1983  const float dir[3],
1984  float radius,
1985  float hit_dist,
1987  void *userdata,
1988  int flag)
1989 {
1991  BVHNode *root = tree->nodes[tree->leaf_num];
1992 
1993  BLI_ASSERT_UNIT_V3(dir);
1994  BLI_assert(callback != NULL);
1995 
1996  data.tree = tree;
1997 
1998  data.callback = callback;
1999  data.userdata = userdata;
2000 
2001  copy_v3_v3(data.ray.origin, co);
2002  copy_v3_v3(data.ray.direction, dir);
2003  data.ray.radius = radius;
2004 
2006 
2007  data.hit.index = -1;
2008  data.hit.dist = hit_dist;
2009 
2010  if (root) {
2011  dfs_raycast_all(&data, root);
2012  }
2013 }
2014 
2016  const float co[3],
2017  const float dir[3],
2018  float radius,
2019  float hit_dist,
2021  void *userdata)
2022 {
2024  tree, co, dir, radius, hit_dist, callback, userdata, BVH_RAYCAST_DEFAULT);
2025 }
2026 
2029 /* -------------------------------------------------------------------- */
2038 typedef struct RangeQueryData {
2040  const float *center;
2041  float radius_sq; /* squared radius */
2042 
2043  int hits;
2044 
2046  void *userdata;
2048 
2050 {
2051  if (node->node_num == 0) {
2052 #if 0 /*UNUSED*/
2053  /* Calculate the node min-coords
2054  * (if the node was a point then this is the point coordinates) */
2055  float co[3];
2056  co[0] = node->bv[0];
2057  co[1] = node->bv[2];
2058  co[2] = node->bv[4];
2059 #endif
2060  }
2061  else {
2062  int i;
2063  for (i = 0; i != node->node_num; i++) {
2064  float nearest[3];
2065  float dist_sq = calc_nearest_point_squared(data->center, node->children[i], nearest);
2066  if (dist_sq < data->radius_sq) {
2067  /* Its a leaf.. call the callback */
2068  if (node->children[i]->node_num == 0) {
2069  data->hits++;
2070  data->callback(data->userdata, node->children[i]->index, data->center, dist_sq);
2071  }
2072  else {
2073  dfs_range_query(data, node->children[i]);
2074  }
2075  }
2076  }
2077  }
2078 }
2079 
2081  BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
2082 {
2083  BVHNode *root = tree->nodes[tree->leaf_num];
2084 
2086  data.tree = tree;
2087  data.center = co;
2088  data.radius_sq = radius * radius;
2089  data.hits = 0;
2090 
2091  data.callback = callback;
2092  data.userdata = userdata;
2093 
2094  if (root != NULL) {
2095  float nearest[3];
2096  float dist_sq = calc_nearest_point_squared(data.center, root, nearest);
2097  if (dist_sq < data.radius_sq) {
2098  /* Its a leaf.. call the callback */
2099  if (root->node_num == 0) {
2100  data.hits++;
2101  data.callback(data.userdata, root->index, co, dist_sq);
2102  }
2103  else {
2104  dfs_range_query(&data, root);
2105  }
2106  }
2107  }
2108 
2109  return data.hits;
2110 }
2111 
2114 /* -------------------------------------------------------------------- */
2119  const BVHNode *node)
2120 {
2121  if (node->node_num == 0) {
2122  if (data->callback) {
2123  data->callback(data->userdata, node->index, &data->precalc, NULL, 0, &data->nearest);
2124  }
2125  else {
2126  data->nearest.index = node->index;
2127  data->nearest.dist_sq = dist_squared_to_projected_aabb(
2128  &data->precalc,
2129  (float[3]){node->bv[0], node->bv[2], node->bv[4]},
2130  (float[3]){node->bv[1], node->bv[3], node->bv[5]},
2131  data->closest_axis);
2132  }
2133  }
2134  else {
2135  /* First pick the closest node to recurse into */
2136  if (data->closest_axis[node->main_axis]) {
2137  for (int i = 0; i != node->node_num; i++) {
2138  const float *bv = node->children[i]->bv;
2139 
2140  if (dist_squared_to_projected_aabb(&data->precalc,
2141  (float[3]){bv[0], bv[2], bv[4]},
2142  (float[3]){bv[1], bv[3], bv[5]},
2143  data->closest_axis) <= data->nearest.dist_sq) {
2145  }
2146  }
2147  }
2148  else {
2149  for (int i = node->node_num; i--;) {
2150  const float *bv = node->children[i]->bv;
2151 
2152  if (dist_squared_to_projected_aabb(&data->precalc,
2153  (float[3]){bv[0], bv[2], bv[4]},
2154  (float[3]){bv[1], bv[3], bv[5]},
2155  data->closest_axis) <= data->nearest.dist_sq) {
2157  }
2158  }
2159  }
2160  }
2161 }
2162 
2164  BVHNearestProjectedData *__restrict data, const BVHNode *node)
2165 {
2166  if (node->node_num == 0) {
2167  if (data->callback) {
2168  data->callback(data->userdata,
2169  node->index,
2170  &data->precalc,
2171  data->clip_plane,
2172  data->clip_plane_len,
2173  &data->nearest);
2174  }
2175  else {
2176  data->nearest.index = node->index;
2177  data->nearest.dist_sq = dist_squared_to_projected_aabb(
2178  &data->precalc,
2179  (float[3]){node->bv[0], node->bv[2], node->bv[4]},
2180  (float[3]){node->bv[1], node->bv[3], node->bv[5]},
2181  data->closest_axis);
2182  }
2183  }
2184  else {
2185  /* First pick the closest node to recurse into */
2186  if (data->closest_axis[node->main_axis]) {
2187  for (int i = 0; i != node->node_num; i++) {
2188  const float *bv = node->children[i]->bv;
2189  const float bb_min[3] = {bv[0], bv[2], bv[4]};
2190  const float bb_max[3] = {bv[1], bv[3], bv[5]};
2191 
2192  int isect_type = isect_aabb_planes_v3(
2193  data->clip_plane, data->clip_plane_len, bb_min, bb_max);
2194 
2195  if ((isect_type != ISECT_AABB_PLANE_BEHIND_ANY) &&
2196  dist_squared_to_projected_aabb(&data->precalc, bb_min, bb_max, data->closest_axis) <=
2197  data->nearest.dist_sq) {
2198  if (isect_type == ISECT_AABB_PLANE_CROSS_ANY) {
2200  }
2201  else {
2202  /* ISECT_AABB_PLANE_IN_FRONT_ALL */
2204  }
2205  }
2206  }
2207  }
2208  else {
2209  for (int i = node->node_num; i--;) {
2210  const float *bv = node->children[i]->bv;
2211  const float bb_min[3] = {bv[0], bv[2], bv[4]};
2212  const float bb_max[3] = {bv[1], bv[3], bv[5]};
2213 
2214  int isect_type = isect_aabb_planes_v3(
2215  data->clip_plane, data->clip_plane_len, bb_min, bb_max);
2216 
2217  if (isect_type != ISECT_AABB_PLANE_BEHIND_ANY &&
2218  dist_squared_to_projected_aabb(&data->precalc, bb_min, bb_max, data->closest_axis) <=
2219  data->nearest.dist_sq) {
2220  if (isect_type == ISECT_AABB_PLANE_CROSS_ANY) {
2222  }
2223  else {
2224  /* ISECT_AABB_PLANE_IN_FRONT_ALL */
2226  }
2227  }
2228  }
2229  }
2230  }
2231 }
2232 
2234  float projmat[4][4],
2235  float winsize[2],
2236  float mval[2],
2237  float clip_plane[6][4],
2238  int clip_plane_len,
2239  BVHTreeNearest *nearest,
2241  void *userdata)
2242 {
2243  BVHNode *root = tree->nodes[tree->leaf_num];
2244  if (root != NULL) {
2246  dist_squared_to_projected_aabb_precalc(&data.precalc, projmat, winsize, mval);
2247 
2248  data.callback = callback;
2249  data.userdata = userdata;
2250 
2251  if (clip_plane) {
2252  data.clip_plane_len = clip_plane_len;
2253  for (int i = 0; i < data.clip_plane_len; i++) {
2254  copy_v4_v4(data.clip_plane[i], clip_plane[i]);
2255  }
2256  }
2257  else {
2258  data.clip_plane_len = 1;
2259  planes_from_projmat(projmat, NULL, NULL, NULL, NULL, data.clip_plane[0], NULL);
2260  }
2261 
2262  if (nearest) {
2263  memcpy(&data.nearest, nearest, sizeof(*nearest));
2264  }
2265  else {
2266  data.nearest.index = -1;
2267  data.nearest.dist_sq = FLT_MAX;
2268  }
2269  {
2270  const float bb_min[3] = {root->bv[0], root->bv[2], root->bv[4]};
2271  const float bb_max[3] = {root->bv[1], root->bv[3], root->bv[5]};
2272 
2273  int isect_type = isect_aabb_planes_v3(data.clip_plane, data.clip_plane_len, bb_min, bb_max);
2274 
2275  if (isect_type != 0 &&
2276  dist_squared_to_projected_aabb(&data.precalc, bb_min, bb_max, data.closest_axis) <=
2277  data.nearest.dist_sq) {
2278  if (isect_type == 1) {
2280  }
2281  else {
2283  }
2284  }
2285  }
2286 
2287  if (nearest) {
2288  memcpy(nearest, &data.nearest, sizeof(*nearest));
2289  }
2290 
2291  return data.nearest.index;
2292  }
2293  return -1;
2294 }
2295 
2298 /* -------------------------------------------------------------------- */
2302 typedef struct BVHTree_WalkData {
2306  void *userdata;
2308 
2316 {
2317  if (node->node_num == 0) {
2318  return walk_data->walk_leaf_cb(
2319  (const BVHTreeAxisRange *)node->bv, node->index, walk_data->userdata);
2320  }
2321 
2322  /* First pick the closest node to recurse into */
2323  if (walk_data->walk_order_cb(
2324  (const BVHTreeAxisRange *)node->bv, node->main_axis, walk_data->userdata)) {
2325  for (int i = 0; i != node->node_num; i++) {
2326  if (walk_data->walk_parent_cb((const BVHTreeAxisRange *)node->children[i]->bv,
2327  walk_data->userdata)) {
2328  if (!bvhtree_walk_dfs_recursive(walk_data, node->children[i])) {
2329  return false;
2330  }
2331  }
2332  }
2333  }
2334  else {
2335  for (int i = node->node_num - 1; i >= 0; i--) {
2336  if (walk_data->walk_parent_cb((const BVHTreeAxisRange *)node->children[i]->bv,
2337  walk_data->userdata)) {
2338  if (!bvhtree_walk_dfs_recursive(walk_data, node->children[i])) {
2339  return false;
2340  }
2341  }
2342  }
2343  }
2344  return true;
2345 }
2346 
2348  BVHTree_WalkParentCallback walk_parent_cb,
2349  BVHTree_WalkLeafCallback walk_leaf_cb,
2350  BVHTree_WalkOrderCallback walk_order_cb,
2351  void *userdata)
2352 {
2353  const BVHNode *root = tree->nodes[tree->leaf_num];
2354  if (root != NULL) {
2355  BVHTree_WalkData walk_data = {walk_parent_cb, walk_leaf_cb, walk_order_cb, userdata};
2356  /* first make sure the bv of root passes in the test too */
2357  if (walk_parent_cb((const BVHTreeAxisRange *)root->bv, userdata)) {
2358  bvhtree_walk_dfs_recursive(&walk_data, root);
2359  }
2360  }
2361 }
2362 
typedef float(TangentPoint)[2]
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_assert_unreachable()
Definition: BLI_assert.h:93
#define BLI_assert(a)
Definition: BLI_assert.h:46
A min-heap / priority queue ADT.
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
float BLI_heapsimple_top_value(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
HeapSimple * BLI_heapsimple_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
int BLI_bvhtree_range_query(BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
Definition: BLI_kdopbvh.c:2080
static void bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(BVHNearestProjectedData *__restrict data, const BVHNode *node)
Definition: BLI_kdopbvh.c:2163
static void dfs_raycast_all(BVHRayCastData *data, BVHNode *node)
Definition: BLI_kdopbvh.c:1827
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1363
unsigned char axis_t
Definition: BLI_kdopbvh.c:61
static void bvhtree_ray_cast_data_precalc(BVHRayCastData *data, int flag)
Definition: BLI_kdopbvh.c:1862
static void bvhtree_node_inflate(const BVHTree *tree, BVHNode *node, const float dist)
Definition: BLI_kdopbvh.c:969
int BLI_bvhtree_get_tree_type(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1039
int BLI_bvhtree_find_nearest_projected(BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], float clip_plane[6][4], int clip_plane_len, BVHTreeNearest *nearest, BVHTree_NearestProjectedCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:2233
struct BVHNearestProjectedData BVHNearestProjectedData
struct BVHIntersectPlaneData BVHIntersectPlaneData
void BLI_bvhtree_ray_cast_all_ex(BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata, int flag)
Definition: BLI_kdopbvh.c:1981
int BLI_bvhtree_find_nearest_first(BVHTree *tree, const float co[3], const float dist_sq, BVHTree_NearestPointCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1682
struct RangeQueryData RangeQueryData
struct BVHRayCastData BVHRayCastData
static void heap_find_nearest_begin(BVHNearestData *data, BVHNode *root)
Definition: BLI_kdopbvh.c:1547
static void bvh_insertionsort(BVHNode **a, int lo, int hi, int axis)
Definition: BLI_kdopbvh.c:245
#define KDOPBVH_THREAD_LEAF_THRESHOLD
Definition: BLI_kdopbvh.c:54
static bool bvhtree_walk_dfs_recursive(BVHTree_WalkData *walk_data, const BVHNode *node)
Definition: BLI_kdopbvh.c:2315
int BLI_bvhtree_find_nearest_ex(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
Definition: BLI_kdopbvh.c:1567
static void non_recursive_bvh_div_nodes(const BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int leafs_num)
Definition: BLI_kdopbvh.c:774
static bool tree_intersect_plane_test(const float *bv, const float plane[4])
Definition: BLI_kdopbvh.c:1386
static void tree_overlap_traverse_cb(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
Definition: BLI_kdopbvh.c:1137
static char get_largest_axis(const float *bv)
Definition: BLI_kdopbvh.c:404
const float bvhtree_kdop_axes[13][3]
Definition: BLI_kdopbvh.c:170
static void build_implicit_tree_helper(const BVHTree *tree, BVHBuildHelper *data)
Definition: BLI_kdopbvh.c:570
static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node)
Definition: BLI_kdopbvh.c:1512
static bool tree_overlap_test(const BVHNode *node1, const BVHNode *node2, axis_t start_axis, axis_t stop_axis)
Definition: BLI_kdopbvh.c:1074
static bool tree_overlap_traverse_num(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
Definition: BLI_kdopbvh.c:1184
void BLI_bvhtree_balance(BVHTree *tree)
Definition: BLI_kdopbvh.c:937
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
Definition: BLI_kdopbvh.c:854
static void heap_find_nearest_inner(BVHNearestData *data, HeapSimple *heap, BVHNode *node)
Definition: BLI_kdopbvh.c:1523
void BLI_bvhtree_update_tree(BVHTree *tree)
Definition: BLI_kdopbvh.c:1021
int BLI_bvhtree_ray_cast_ex(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata, int flag)
Definition: BLI_kdopbvh.c:1897
static bool isect_aabb_v3(BVHNode *node, const float co[3])
Definition: BLI_kdopbvh.c:1631
MINLINE axis_t min_axis(axis_t a, axis_t b)
Definition: BLI_kdopbvh.c:207
float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
Definition: BLI_kdopbvh.c:1954
static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
Definition: BLI_kdopbvh.c:1786
static float ray_nearest_hit(const BVHRayCastData *data, const float bv[6])
Definition: BLI_kdopbvh.c:1718
struct BVHOverlapData_Thread BVHOverlapData_Thread
struct BVHNearestData BVHNearestData
void BLI_bvhtree_free(BVHTree *tree)
Definition: BLI_kdopbvh.c:926
static void dfs_range_query(RangeQueryData *data, BVHNode *node)
Definition: BLI_kdopbvh.c:2049
static void refit_kdop_hull(const BVHTree *tree, BVHNode *node, int start, int end)
Definition: BLI_kdopbvh.c:374
static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node)
Definition: BLI_kdopbvh.c:1767
static bool dfs_find_duplicate_fast_dfs(BVHNearestData *data, BVHNode *node)
Definition: BLI_kdopbvh.c:1643
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
Definition: BLI_kdopbvh.c:979
static int bvh_partition(BVHNode **a, int lo, int hi, BVHNode *x, int axis)
Definition: BLI_kdopbvh.c:260
static void node_join(BVHTree *tree, BVHNode *node)
Definition: BLI_kdopbvh.c:426
struct BVHTree_WalkData BVHTree_WalkData
bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
Definition: BLI_kdopbvh.c:997
static void tree_overlap_traverse(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
Definition: BLI_kdopbvh.c:1093
void BLI_bvhtree_walk_dfs(BVHTree *tree, BVHTree_WalkParentCallback walk_parent_cb, BVHTree_WalkLeafCallback walk_leaf_cb, BVHTree_WalkOrderCallback walk_order_cb, void *userdata)
Definition: BLI_kdopbvh.c:2347
struct BVHDivNodesData BVHDivNodesData
static void non_recursive_bvh_div_nodes_task_cb(void *__restrict userdata, const int j, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: BLI_kdopbvh.c:690
static void node_minmax_init(const BVHTree *tree, BVHNode *node)
Definition: BLI_kdopbvh.c:225
int BLI_bvhtree_get_len(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1034
static const float bvhtree_kdop_axes_length[13]
Definition: BLI_kdopbvh.c:187
int BLI_bvhtree_overlap_thread_num(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1234
#define MAX_TREETYPE
Definition: BLI_kdopbvh.c:46
static void partition_nth_element(BVHNode **a, int begin, int end, const int n, const int axis)
Definition: BLI_kdopbvh.c:305
static void split_leafs(BVHNode **leafs_array, const int nth[], const int partitions, const int split_axis)
Definition: BLI_kdopbvh.c:660
int * BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_num)
Definition: BLI_kdopbvh.c:1420
float BLI_bvhtree_get_epsilon(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1044
BVHTreeOverlap * BLI_bvhtree_overlap_ex(const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, const uint max_interactions, const int flag)
Definition: BLI_kdopbvh.c:1263
static void bvhtree_nearest_projected_dfs_recursive(BVHNearestProjectedData *__restrict data, const BVHNode *node)
Definition: BLI_kdopbvh.c:2118
BVHOverlapData_Shared
Definition: BLI_kdopbvh.c:102
static float calc_nearest_point_squared(const float proj[3], BVHNode *node, float nearest[3])
Definition: BLI_kdopbvh.c:1453
void BLI_bvhtree_get_bounding_box(BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
Definition: BLI_kdopbvh.c:1049
struct BVHNode BVHNode
static int implicit_needed_branches(int tree_type, int leafs)
Definition: BLI_kdopbvh.c:643
void BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:2015
BLI_STATIC_ASSERT((sizeof(void *)==8 &&sizeof(BVHTree)<=48)||(sizeof(void *)==4 &&sizeof(BVHTree)<=32), "over sized")
Definition: BLI_kdopbvh.c:90
static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
Definition: BLI_kdopbvh.c:1474
int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1942
static void bvhtree_overlap_task_cb(void *__restrict userdata, const int j, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: BLI_kdopbvh.c:1239
struct BVHBuildHelper BVHBuildHelper
static void create_kdop_hull(const BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving)
Definition: BLI_kdopbvh.c:344
static void bvhtree_intersect_plane_dfs_recursive(BVHIntersectPlaneData *__restrict data, const BVHNode *node)
Definition: BLI_kdopbvh.c:1401
static int implicit_leafs_index(const BVHBuildHelper *data, const int depth, const int child_index)
Definition: BLI_kdopbvh.c:600
int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1616
static BVHNode * bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis)
Definition: BLI_kdopbvh.c:280
@ BVH_OVERLAP_USE_THREADING
Definition: BLI_kdopbvh.h:77
@ BVH_OVERLAP_RETURN_PAIRS
Definition: BLI_kdopbvh.h:78
#define BVH_RAYCAST_DIST_MAX
Definition: BLI_kdopbvh.h:89
#define BVH_RAYCAST_DEFAULT
Definition: BLI_kdopbvh.h:88
@ BVH_RAYCAST_WATERTIGHT
Definition: BLI_kdopbvh.h:86
bool(* BVHTree_WalkLeafCallback)(const BVHTreeAxisRange *bounds, int index, void *userdata)
Definition: BLI_kdopbvh.h:136
bool(* BVHTree_WalkOrderCallback)(const BVHTreeAxisRange *bounds, char axis, void *userdata)
Definition: BLI_kdopbvh.h:142
void(* BVHTree_RayCastCallback)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: BLI_kdopbvh.h:102
@ BVH_NEAREST_OPTIMAL_ORDER
Definition: BLI_kdopbvh.h:82
bool(* BVHTree_WalkParentCallback)(const BVHTreeAxisRange *bounds, void *userdata)
Definition: BLI_kdopbvh.h:132
void(* BVHTree_NearestPointCallback)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition: BLI_kdopbvh.h:94
bool(* BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b, int thread)
Definition: BLI_kdopbvh.h:110
void(* BVHTree_RangeQuery)(void *userdata, int index, const float co[3], float dist_sq)
Definition: BLI_kdopbvh.h:115
void(* BVHTree_NearestProjectedCallback)(void *userdata, int index, const struct DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest)
Definition: BLI_kdopbvh.h:120
MINLINE float max_fff(float a, float b, float c)
MINLINE float max_ff(float a, float b)
MINLINE int min_ii(int a, int b)
MINLINE int max_ii(int a, int b)
#define BLI_ASSERT_UNIT_V3(v)
void isect_ray_tri_watertight_v3_precalc(struct IsectRayPrecalc *isect_precalc, const float ray_direction[3])
Definition: math_geom.c:1784
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.c:823
MINLINE float plane_point_side_v3(const float plane[4], const float co[3])
#define ISECT_AABB_PLANE_CROSS_ANY
#define ISECT_AABB_PLANE_BEHIND_ANY
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.c:772
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.c:615
int isect_aabb_planes_v3(const float(*planes)[4], int totplane, const float bbmin[3], const float bbmax[3])
Definition: math_geom.c:2604
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])
Definition: math_geom.c:4615
#define MINLINE
MINLINE void copy_v4_v4(float r[4], const float a[4])
MINLINE float normalize_v3(float r[3])
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
MINLINE void zero_v3(float r[3])
void * BLI_stack_push_r(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: stack.c:101
void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
Definition: stack.c:144
size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: stack.c:225
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition: stack.c:94
#define BLI_stack_new(esize, descr)
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
Definition: task_range.cc:94
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
Definition: BLI_task.h:293
#define UNUSED_VARS(...)
#define SWAP(type, a, b)
#define UNUSED(x)
#define UNLIKELY(x)
#define MIN2(a, b)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble right
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
Read Guarded memory(de)allocation.
#define MEM_SAFE_FREE(v)
__forceinline ssef low(const avxf &a)
Definition: avxf.h:264
__forceinline BoundBox intersect(const BoundBox &a, const BoundBox &b)
Definition: boundbox.h:179
OperationNode * node
DEGForeachIDComponentCallback callback
void * tree
uint pos
int count
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
size_t(* MEM_allocN_len)(const void *vmemh)
Definition: mallocn.c:26
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static int left
#define fabsf(x)
Definition: metal/compat.h:219
static unsigned a[3]
Definition: RandGen.cpp:78
static double epsilon
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
#define min(a, b)
Definition: sort.c:35
int leafs_per_child[32]
Definition: BLI_kdopbvh.c:561
int branches_on_level[32]
Definition: BLI_kdopbvh.c:563
BVHNode ** leafs_array
Definition: BLI_kdopbvh.c:678
const BVHTree * tree
Definition: BLI_kdopbvh.c:676
const BVHBuildHelper * data
Definition: BLI_kdopbvh.c:683
BVHNode * branches_array
Definition: BLI_kdopbvh.c:677
const BVHTree * tree
Definition: BLI_kdopbvh.c:155
struct BLI_Stack * intersect
Definition: BLI_kdopbvh.c:157
const BVHTree * tree
Definition: BLI_kdopbvh.c:113
const float * co
Definition: BLI_kdopbvh.c:114
float proj[13]
Definition: BLI_kdopbvh.c:117
BVHTreeNearest nearest
Definition: BLI_kdopbvh.c:118
BVHTree_NearestPointCallback callback
Definition: BLI_kdopbvh.c:115
const BVHTree * tree
Definition: BLI_kdopbvh.c:143
struct DistProjectedAABBPrecalc precalc
Definition: BLI_kdopbvh.c:144
BVHTree_NearestProjectedCallback callback
Definition: BLI_kdopbvh.c:148
BVHTreeNearest nearest
Definition: BLI_kdopbvh.c:150
struct BVHNode * parent
Definition: BLI_kdopbvh.c:65
struct BVHNode ** children
Definition: BLI_kdopbvh.c:64
char node_num
Definition: BLI_kdopbvh.c:71
char main_axis
Definition: BLI_kdopbvh.c:72
int index
Definition: BLI_kdopbvh.c:70
float * bv
Definition: BLI_kdopbvh.c:69
struct BLI_Stack * overlap
Definition: BLI_kdopbvh.c:106
BVHOverlapData_Shared * shared
Definition: BLI_kdopbvh.c:105
BVHTree_RayCastCallback callback
Definition: BLI_kdopbvh.c:125
const BVHTree * tree
Definition: BLI_kdopbvh.c:123
float idot_axis[13]
Definition: BLI_kdopbvh.c:136
BVHTreeRayHit hit
Definition: BLI_kdopbvh.c:139
float ray_dot_axis[13]
Definition: BLI_kdopbvh.c:135
BVHTreeRay ray
Definition: BLI_kdopbvh.c:128
BVHTree_WalkOrderCallback walk_order_cb
Definition: BLI_kdopbvh.c:2305
BVHTree_WalkLeafCallback walk_leaf_cb
Definition: BLI_kdopbvh.c:2304
BVHTree_WalkParentCallback walk_parent_cb
Definition: BLI_kdopbvh.c:2303
axis_t axis
Definition: BLI_kdopbvh.c:85
float * nodebv
Definition: BLI_kdopbvh.c:80
axis_t start_axis
Definition: BLI_kdopbvh.c:84
int leaf_num
Definition: BLI_kdopbvh.c:82
BVHNode * nodearray
Definition: BLI_kdopbvh.c:78
float epsilon
Definition: BLI_kdopbvh.c:81
int branch_num
Definition: BLI_kdopbvh.c:83
BVHNode ** nodechild
Definition: BLI_kdopbvh.c:79
BVHNode ** nodes
Definition: BLI_kdopbvh.c:77
axis_t stop_axis
Definition: BLI_kdopbvh.c:84
char tree_type
Definition: BLI_kdopbvh.c:86
BVHTree_RangeQuery callback
Definition: BLI_kdopbvh.c:2045
const float * center
Definition: BLI_kdopbvh.c:2040
BVHTree * tree
Definition: BLI_kdopbvh.c:2039
float max