46 #define MAX_TREETYPE 32
52 # define KDOPBVH_THREAD_LEAF_THRESHOLD 0
54 # define KDOPBVH_THREAD_LEAF_THRESHOLD 1024
91 (
sizeof(
void *) == 4 &&
sizeof(
BVHTree) <= 32),
97 axis_t start_axis, stop_axis;
130 #ifdef USE_KDOPBVH_WATERTIGHT
209 return (
a <
b) ?
a :
b;
214 return (
b <
a) ?
a :
b;
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;
249 for (i = lo; i < hi; i++) {
252 while ((j != lo) && (
t->bv[axis] < (
a[j - 1])->bv[axis])) {
264 while (
a[i]->bv[axis] <
x->bv[axis]) {
268 while (
x->bv[axis] <
a[j]->bv[axis]) {
282 if ((
a[mid])->bv[axis] < (
a[lo])->bv[axis]) {
283 if ((
a[hi])->bv[axis] < (
a[mid])->bv[axis]) {
286 if ((
a[hi])->bv[axis] < (
a[lo])->bv[axis]) {
292 if ((
a[hi])->bv[axis] < (
a[mid])->bv[axis]) {
293 if ((
a[hi])->bv[axis] < (
a[lo])->bv[axis]) {
307 while (end - begin > 3) {
309 a, begin, end,
bvh_medianof3(
a, begin, (begin + end) / 2, end - 1, axis), axis);
320 #ifdef USE_SKIP_LINKS
328 for (i = 0; i <
node->node_num; i++) {
329 if (i + 1 <
node->node_num) {
348 float *bv =
node->bv;
357 for (k = 0; k < numpoints; k++) {
359 for (axis_iter =
tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
361 if (newminmax < bv[2 * axis_iter]) {
362 bv[2 * axis_iter] = newminmax;
364 if (newminmax > bv[(2 * axis_iter) + 1]) {
365 bv[(2 * axis_iter) + 1] = newminmax;
376 float newmin, newmax;
377 float *__restrict bv =
node->bv;
383 for (j = start; j < end; j++) {
384 float *__restrict node_bv =
tree->nodes[j]->bv;
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;
393 newmax = node_bv[(2 * axis_iter) + 1];
394 if ((newmax > bv[(2 * axis_iter) + 1])) {
395 bv[(2 * axis_iter) + 1] = newmax;
406 float middle_point[3];
408 middle_point[0] = (bv[1]) - (bv[0]);
409 middle_point[1] = (bv[3]) - (bv[2]);
410 middle_point[2] = (bv[5]) - (bv[4]);
411 if (middle_point[0] > middle_point[1]) {
412 if (middle_point[0] > middle_point[2]) {
417 if (middle_point[1] > middle_point[2]) {
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++) {
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)];
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];
453 #ifdef USE_PRINT_TREE
464 for (i = 0; i < depth; i++) {
467 printf(
" - %d (%ld): ",
node->index, (
long int)(
node -
tree->nodearray));
470 printf(
"%.3f ",
node->bv[axis_iter]);
474 for (i = 0; i <
tree->tree_type; i++) {
475 if (
node->children[i]) {
476 bvhtree_print_tree(
tree,
node->children[i], depth + 1);
483 printf(
"BVHTree Info: tree_type = %d, axis = %d, epsilon = %f\n",
487 printf(
"nodes = %d, branches = %d, leafs = %d\n",
492 "Memory per node = %ubytes\n",
496 printf(
"Total memory = %ubytes\n",
500 bvhtree_print_tree(
tree,
tree->nodes[
tree->leaf_num], 0);
504 #ifdef USE_VERIFY_TREE
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);
516 for (j = 0; j <
tree->tree_type; j++) {
517 if (
tree->nodes[i]->parent->children[j] ==
tree->nodes[i]) {
522 printf(
"Parent child relationship doesn't match: %d\n", i);
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);
534 for (j = 0; j <
tree->tree_type; j++) {
535 if (
tree->nodearray[i].parent->children[j] == &
tree->nodearray[i]) {
540 printf(
"Parent child relationship doesn't match: %d\n", i);
546 printf(
"branches: %d, leafs: %d, total: %d\n",
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) {
585 data->branches_on_level[0] = 1;
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;
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;
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;
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];
610 return data->remain_leafs;
645 return max_ii(1, (leafs + tree_type - 3) / (tree_type - 1));
662 const int partitions,
663 const int split_axis)
666 for (i = 0; i < partitions - 1; i++) {
667 if (nth[i] >= nth[partitions]) {
697 const int parent_level_index = j -
data->i;
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;
722 const int child_level_index = child_index -
data->first_of_next_level;
731 for (k = 0; k <
data->tree_type; k++) {
732 const int child_index = j *
data->tree_type +
data->tree_offset + k;
734 const int child_level_index = child_index -
data->first_of_next_level;
737 data->data,
data->depth + 1, child_level_index);
739 data->data,
data->depth + 1, child_level_index + 1);
741 if (child_leafs_end - child_leafs_begin > 1) {
742 parent->
children[k] = &
data->branches_array[child_index];
745 else if (child_leafs_end - child_leafs_begin == 1) {
746 parent->
children[k] =
data->leafs_array[child_leafs_begin];
781 const int tree_type =
tree->tree_type;
783 const int tree_offset = 2 -
tree->tree_type;
792 BVHNode *root = &branches_array[1];
797 if (leafs_num == 1) {
811 .branches_array = branches_array,
812 .leafs_array = leafs_array,
813 .tree_type = tree_type,
814 .tree_offset = tree_offset,
816 .first_of_next_level = 0,
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;
825 const int i_stop =
min_ii(first_of_next_level, branches_num + 1);
830 cb_data.
depth = depth;
841 for (
int i_task = i; i_task < i_stop; i_task++) {
871 tree->tree_type = tree_type;
875 tree->start_axis = 0;
876 tree->stop_axis = 13;
878 else if (axis == 18) {
879 tree->start_axis = 7;
880 tree->stop_axis = 13;
882 else if (axis == 14) {
883 tree->start_axis = 0;
886 else if (axis == 8) {
887 tree->start_axis = 0;
890 else if (axis == 6) {
891 tree->start_axis = 0;
905 tree->nodebv =
MEM_callocN(
sizeof(
float) * (
size_t)(axis * numnodes),
"BVHNodeBV");
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];
952 for (
int i = 0; i <
tree->branch_num; i++) {
956 #ifdef USE_SKIP_LINKS
960 #ifdef USE_VERIFY_TREE
961 bvhtree_verify(
tree);
964 #ifdef USE_PRINT_TREE
972 for (axis_iter =
tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
974 node->bv[(2 * axis_iter)] -= dist_corrected;
975 node->bv[(2 * axis_iter) + 1] += dist_corrected;
998 BVHTree *
tree,
int index,
const float co[3],
const float co_moving[3],
int numpoints)
1003 if (index >
tree->leaf_num) {
1030 for (; index >= root; index--) {
1036 return tree->leaf_num;
1041 return tree->tree_type;
1046 return tree->epsilon;
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]};
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);
1084 for (; bv1 != bv1_end; bv1 += 2, bv2 += 2) {
1085 if ((bv1[0] > bv2[1]) || (bv2[0] > bv1[1])) {
1117 for (j = 0; j <
data->tree2->tree_type; j++) {
1125 for (j = 0; j <
data->tree1->tree_type; j++) {
1164 for (j = 0; j <
data->tree2->tree_type; j++) {
1172 for (j = 0; j <
data->tree1->tree_type; j++) {
1203 if (!
data->callback ||
1215 for (j = 0; j < node2->
node_num; j++) {
1224 for (j = 0; j < node1->
node_num; j++) {
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]);
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]);
1258 data_shared->tree1->nodes[data_shared->tree1->leaf_num]->children[j],
1259 data_shared->tree2->nodes[data_shared->tree2->leaf_num]);
1266 uint *r_overlap_num,
1270 const uint max_interactions,
1278 BLI_assert(overlap_pairs || max_interactions);
1281 const int thread_num = use_threading ? root_node_len : 1;
1287 axis_t start_axis, stop_axis;
1291 (tree1->
axis == 18 || tree2->
axis == 18))) {
1307 data_shared.tree1 = tree1;
1308 data_shared.tree2 = tree2;
1310 data_shared.stop_axis = stop_axis;
1314 data_shared.userdata = userdata;
1316 for (j = 0; j < thread_num; j++) {
1318 data[j].shared = &data_shared;
1320 data[j].max_interactions = max_interactions;
1326 if (use_threading) {
1333 if (max_interactions) {
1344 if (overlap_pairs) {
1345 for (j = 0; j < thread_num; j++) {
1351 for (j = 0; j < thread_num; j++) {
1357 *r_overlap_num = (
uint)total;
1366 uint *r_overlap_num,
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];
1406 if (!
node->node_num) {
1411 for (
int j = 0; j <
data->tree->tree_type; j++) {
1412 if (
node->children[j]) {
1425 if (
tree->leaf_num) {
1441 *r_intersect_num = (
uint)total;
1456 const float *bv =
node->bv;
1459 for (i = 0; i != 3; i++, bv += 2) {
1460 float val = proj[i];
1476 if (
node->node_num == 0) {
1477 if (
data->callback) {
1490 if (
data->proj[
node->main_axis] <=
node->children[0]->bv[
node->main_axis * 2 + 1]) {
1492 for (i = 0; i !=
node->node_num; i++) {
1494 data->nearest.dist_sq) {
1501 for (i =
node->node_num - 1; i >= 0; i--) {
1503 data->nearest.dist_sq) {
1514 float nearest[3], dist_sq;
1516 if (dist_sq >=
data->nearest.dist_sq) {
1525 if (
node->node_num == 0) {
1526 if (
data->callback) {
1537 for (
int i = 0; i !=
node->node_num; i++) {
1540 if (dist_sq < data->nearest.dist_sq) {
1552 if (dist_sq < data->nearest.dist_sq) {
1584 data.userdata = userdata;
1586 for (axis_iter =
data.tree->start_axis; axis_iter !=
data.tree->stop_axis; axis_iter++) {
1591 memcpy(&
data.nearest, nearest,
sizeof(*nearest));
1594 data.nearest.index = -1;
1595 data.nearest.dist_sq = FLT_MAX;
1610 memcpy(nearest, &
data.nearest,
sizeof(*nearest));
1613 return data.nearest.index;
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) {
1645 if (
node->node_num == 0) {
1647 if (
data->callback) {
1648 const float dist_sq =
data->nearest.dist_sq;
1650 return (
data->nearest.dist_sq < dist_sq);
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++) {
1670 for (i =
node->node_num; i--;) {
1684 const float dist_sq,
1696 data.userdata = userdata;
1697 data.nearest.index = -1;
1698 data.nearest.dist_sq = dist_sq;
1705 return data.nearest.index;
1722 float low = 0, upper =
data->hit.dist;
1724 for (i = 0; i != 3; i++, bv += 2) {
1725 if (
data->ray_dot_axis[i] == 0.0f) {
1727 if (
data->ray.origin[i] < bv[0] -
data->ray.radius ||
1728 data->ray.origin[i] > bv[1] +
data->ray.radius) {
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];
1736 if (
data->ray_dot_axis[i] > 0.0f) {
1769 const float *bv =
node->bv;
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];
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)) {
1783 return max_fff(t1x, t1y, t1z);
1795 if (dist >=
data->hit.dist) {
1799 if (
node->node_num == 0) {
1800 if (
data->callback) {
1805 data->hit.dist = dist;
1811 if (
data->ray_dot_axis[
node->main_axis] > 0.0f) {
1812 for (i = 0; i !=
node->node_num; i++) {
1817 for (i =
node->node_num - 1; i >= 0; i--) {
1836 if (dist >=
data->hit.dist) {
1840 if (
node->node_num == 0) {
1842 dist =
data->hit.dist;
1844 data->hit.index = -1;
1845 data->hit.dist = dist;
1849 if (
data->ray_dot_axis[
node->main_axis] > 0.0f) {
1850 for (i = 0; i !=
node->node_num; i++) {
1855 for (i =
node->node_num - 1; i >= 0; i--) {
1866 for (i = 0; i < 3; i++) {
1869 if (
fabsf(
data->ray_dot_axis[i]) < FLT_EPSILON) {
1870 data->ray_dot_axis[i] = 0.0f;
1872 data->idot_axis[i] = FLT_MAX;
1875 data->idot_axis[i] = 1.0f /
data->ray_dot_axis[i];
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;
1884 #ifdef USE_KDOPBVH_WATERTIGHT
1887 data->ray.isect_precalc = &
data->isect_precalc;
1914 data.userdata = userdata;
1918 data.ray.radius = radius;
1923 memcpy(&
data.hit, hit,
sizeof(*hit));
1926 data.hit.index = -1;
1936 memcpy(hit, &
data.hit,
sizeof(*hit));
1939 return data.hit.index;
1955 const float light_start[3],
1956 const float light_end[3],
1967 data.ray.radius = 0.0;
1999 data.userdata = userdata;
2003 data.ray.radius = radius;
2007 data.hit.index = -1;
2008 data.hit.dist = hit_dist;
2051 if (
node->node_num == 0) {
2056 co[0] =
node->bv[0];
2057 co[1] =
node->bv[2];
2058 co[2] =
node->bv[4];
2063 for (i = 0; i !=
node->node_num; i++) {
2066 if (dist_sq < data->radius_sq) {
2068 if (
node->children[i]->node_num == 0) {
2070 data->callback(
data->userdata,
node->children[i]->index,
data->center, dist_sq);
2088 data.radius_sq = radius * radius;
2092 data.userdata = userdata;
2097 if (dist_sq <
data.radius_sq) {
2121 if (
node->node_num == 0) {
2122 if (
data->callback) {
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);
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;
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) {
2149 for (
int i =
node->node_num; i--;) {
2150 const float *bv =
node->children[i]->bv;
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) {
2166 if (
node->node_num == 0) {
2167 if (
data->callback) {
2172 data->clip_plane_len,
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);
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]};
2193 data->clip_plane,
data->clip_plane_len, bb_min, bb_max);
2197 data->nearest.dist_sq) {
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]};
2215 data->clip_plane,
data->clip_plane_len, bb_min, bb_max);
2219 data->nearest.dist_sq) {
2234 float projmat[4][4],
2237 float clip_plane[6][4],
2249 data.userdata = userdata;
2252 data.clip_plane_len = clip_plane_len;
2253 for (
int i = 0; i <
data.clip_plane_len; i++) {
2258 data.clip_plane_len = 1;
2263 memcpy(&
data.nearest, nearest,
sizeof(*nearest));
2266 data.nearest.index = -1;
2267 data.nearest.dist_sq = FLT_MAX;
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]};
2275 if (isect_type != 0 &&
2277 data.nearest.dist_sq) {
2278 if (isect_type == 1) {
2288 memcpy(nearest, &
data.nearest,
sizeof(*nearest));
2291 return data.nearest.index;
2317 if (
node->node_num == 0) {
2325 for (
int i = 0; i !=
node->node_num; i++) {
2335 for (
int i =
node->node_num - 1; i >= 0; i--) {
2355 BVHTree_WalkData walk_data = {walk_parent_cb, walk_leaf_cb, walk_order_cb, userdata};
typedef float(TangentPoint)[2]
#define BLI_array_alloca(arr, realsize)
#define BLI_assert_unreachable()
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)
static void bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(BVHNearestProjectedData *__restrict data, const BVHNode *node)
static void dfs_raycast_all(BVHRayCastData *data, BVHNode *node)
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
static void bvhtree_ray_cast_data_precalc(BVHRayCastData *data, int flag)
static void bvhtree_node_inflate(const BVHTree *tree, BVHNode *node, const float dist)
int BLI_bvhtree_get_tree_type(const BVHTree *tree)
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)
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)
int BLI_bvhtree_find_nearest_first(BVHTree *tree, const float co[3], const float dist_sq, BVHTree_NearestPointCallback callback, void *userdata)
struct RangeQueryData RangeQueryData
struct BVHRayCastData BVHRayCastData
static void heap_find_nearest_begin(BVHNearestData *data, BVHNode *root)
static void bvh_insertionsort(BVHNode **a, int lo, int hi, int axis)
#define KDOPBVH_THREAD_LEAF_THRESHOLD
static bool bvhtree_walk_dfs_recursive(BVHTree_WalkData *walk_data, const BVHNode *node)
int BLI_bvhtree_find_nearest_ex(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
static void non_recursive_bvh_div_nodes(const BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int leafs_num)
static bool tree_intersect_plane_test(const float *bv, const float plane[4])
static void tree_overlap_traverse_cb(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
static char get_largest_axis(const float *bv)
const float bvhtree_kdop_axes[13][3]
static void build_implicit_tree_helper(const BVHTree *tree, BVHBuildHelper *data)
static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node)
static bool tree_overlap_test(const BVHNode *node1, const BVHNode *node2, axis_t start_axis, axis_t stop_axis)
static bool tree_overlap_traverse_num(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
void BLI_bvhtree_balance(BVHTree *tree)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
static void heap_find_nearest_inner(BVHNearestData *data, HeapSimple *heap, BVHNode *node)
void BLI_bvhtree_update_tree(BVHTree *tree)
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)
static bool isect_aabb_v3(BVHNode *node, const float co[3])
MINLINE axis_t min_axis(axis_t a, axis_t b)
float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
static float ray_nearest_hit(const BVHRayCastData *data, const float bv[6])
struct BVHOverlapData_Thread BVHOverlapData_Thread
struct BVHNearestData BVHNearestData
void BLI_bvhtree_free(BVHTree *tree)
static void dfs_range_query(RangeQueryData *data, BVHNode *node)
static void refit_kdop_hull(const BVHTree *tree, BVHNode *node, int start, int end)
static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node)
static bool dfs_find_duplicate_fast_dfs(BVHNearestData *data, BVHNode *node)
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
static int bvh_partition(BVHNode **a, int lo, int hi, BVHNode *x, int axis)
static void node_join(BVHTree *tree, BVHNode *node)
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)
static void tree_overlap_traverse(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
void BLI_bvhtree_walk_dfs(BVHTree *tree, BVHTree_WalkParentCallback walk_parent_cb, BVHTree_WalkLeafCallback walk_leaf_cb, BVHTree_WalkOrderCallback walk_order_cb, void *userdata)
struct BVHDivNodesData BVHDivNodesData
static void non_recursive_bvh_div_nodes_task_cb(void *__restrict userdata, const int j, const TaskParallelTLS *__restrict UNUSED(tls))
static void node_minmax_init(const BVHTree *tree, BVHNode *node)
int BLI_bvhtree_get_len(const BVHTree *tree)
static const float bvhtree_kdop_axes_length[13]
int BLI_bvhtree_overlap_thread_num(const BVHTree *tree)
static void partition_nth_element(BVHNode **a, int begin, int end, const int n, const int axis)
static void split_leafs(BVHNode **leafs_array, const int nth[], const int partitions, const int split_axis)
int * BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_num)
float BLI_bvhtree_get_epsilon(const BVHTree *tree)
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)
static void bvhtree_nearest_projected_dfs_recursive(BVHNearestProjectedData *__restrict data, const BVHNode *node)
static float calc_nearest_point_squared(const float proj[3], BVHNode *node, float nearest[3])
void BLI_bvhtree_get_bounding_box(BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
static int implicit_needed_branches(int tree_type, int leafs)
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)
BLI_STATIC_ASSERT((sizeof(void *)==8 &&sizeof(BVHTree)<=48)||(sizeof(void *)==4 &&sizeof(BVHTree)<=32), "over sized")
static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
static void bvhtree_overlap_task_cb(void *__restrict userdata, const int j, const TaskParallelTLS *__restrict UNUSED(tls))
struct BVHBuildHelper BVHBuildHelper
static void create_kdop_hull(const BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving)
static void bvhtree_intersect_plane_dfs_recursive(BVHIntersectPlaneData *__restrict data, const BVHNode *node)
static int implicit_leafs_index(const BVHBuildHelper *data, const int depth, const int child_index)
int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
static BVHNode * bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis)
@ BVH_OVERLAP_USE_THREADING
@ BVH_OVERLAP_RETURN_PAIRS
#define BVH_RAYCAST_DIST_MAX
#define BVH_RAYCAST_DEFAULT
bool(* BVHTree_WalkLeafCallback)(const BVHTreeAxisRange *bounds, int index, void *userdata)
bool(* BVHTree_WalkOrderCallback)(const BVHTreeAxisRange *bounds, char axis, void *userdata)
void(* BVHTree_RayCastCallback)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
@ BVH_NEAREST_OPTIMAL_ORDER
bool(* BVHTree_WalkParentCallback)(const BVHTreeAxisRange *bounds, void *userdata)
void(* BVHTree_NearestPointCallback)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
bool(* BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b, int thread)
void(* BVHTree_RangeQuery)(void *userdata, int index, const float co[3], float dist_sq)
void(* BVHTree_NearestProjectedCallback)(void *userdata, int index, const struct DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest)
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])
float dist_squared_to_projected_aabb(struct DistProjectedAABBPrecalc *data, const float bbmin[3], const float bbmax[3], bool r_axis_closest[3])
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])
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])
int isect_aabb_planes_v3(const float(*planes)[4], int totplane, const float bbmin[3], const float bbmax[3])
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])
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()
void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
#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...
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
_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.
__forceinline ssef low(const avxf &a)
__forceinline BoundBox intersect(const BoundBox &a, const BoundBox &b)
DEGForeachIDComponentCallback callback
void(* MEM_freeN)(void *vmemh)
size_t(* MEM_allocN_len)(const void *vmemh)
void *(* MEM_callocN)(size_t len, const char *str)
void *(* MEM_mallocN)(size_t len, const char *str)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
int branches_on_level[32]
const BVHBuildHelper * data
struct BLI_Stack * intersect
BVHTree_NearestPointCallback callback
struct DistProjectedAABBPrecalc precalc
BVHTree_NearestProjectedCallback callback
struct BVHNode ** children
struct BLI_Stack * overlap
BVHOverlapData_Shared * shared
BVHTree_RayCastCallback callback
BVHTree_WalkOrderCallback walk_order_cb
BVHTree_WalkLeafCallback walk_leaf_cb
BVHTree_WalkParentCallback walk_parent_cb
BVHTree_RangeQuery callback