52#define MAX_TREETYPE 32
56# define KDOPBVH_THREAD_LEAF_THRESHOLD 0
58# define KDOPBVH_THREAD_LEAF_THRESHOLD 1024
96 (
sizeof(
void *) == 4 &&
sizeof(
BVHTree) <= 36),
100struct BVHOverlapData_Shared {
102 axis_t start_axis, stop_axis;
135#ifdef USE_KDOPBVH_WATERTIGHT
213 return (a <
b) ? a :
b;
218 return (
b < a) ? a :
b;
232 float (*bv)[2] =
reinterpret_cast<float (*)[2]
>(
node->bv);
235 bv[axis_iter][0] = FLT_MAX;
236 bv[axis_iter][1] = -FLT_MAX;
253 for (i = lo; i < hi; i++) {
256 while ((j != lo) && (t->
bv[axis] < (a[j - 1])->bv[axis])) {
268 while (a[i]->bv[axis] <
x->bv[axis]) {
272 while (
x->bv[axis] < a[j]->
bv[axis]) {
286 if ((a[mid])->bv[axis] < (a[lo])->bv[axis]) {
287 if ((a[hi])->bv[axis] < (a[mid])->bv[axis]) {
290 if ((a[hi])->bv[axis] < (a[lo])->bv[axis]) {
296 if ((a[hi])->bv[axis] < (a[mid])->bv[axis]) {
297 if ((a[hi])->bv[axis] < (a[lo])->bv[axis]) {
312 while (end -
begin > 3) {
330 node->skip[0] = left;
331 node->skip[1] = right;
333 for (i = 0; i <
node->node_num; i++) {
334 if (i + 1 <
node->node_num) {
335 build_skip_links(tree,
node->children[i], left,
node->children[i + 1]);
338 build_skip_links(tree,
node->children[i], left, right);
341 left =
node->children[i];
353 float *bv =
node->bv;
362 for (k = 0; k < numpoints; k++) {
364 for (axis_iter = tree->
start_axis; axis_iter < tree->stop_axis; axis_iter++) {
366 bv[2 * axis_iter] = std::min(newminmax, bv[2 * axis_iter]);
367 bv[(2 * axis_iter) + 1] = std::max(newminmax, bv[(2 * axis_iter) + 1]);
377 float newmin, newmax;
378 float *__restrict bv =
node->bv;
384 for (j = start; j < end; j++) {
385 const float *__restrict node_bv = tree->
nodes[j]->
bv;
388 for (axis_iter = tree->
start_axis; axis_iter < tree->stop_axis; axis_iter++) {
389 newmin = node_bv[(2 * axis_iter)];
390 bv[(2 * axis_iter)] = std::min(newmin, bv[(2 * axis_iter)]);
392 newmax = node_bv[(2 * axis_iter) + 1];
393 bv[(2 * axis_iter) + 1] = std::max(newmax, bv[(2 * axis_iter) + 1]);
404 float middle_point[3];
406 middle_point[0] = (bv[1]) - (bv[0]);
407 middle_point[1] = (bv[3]) - (bv[2]);
408 middle_point[2] = (bv[5]) - (bv[4]);
409 if (middle_point[0] > middle_point[1]) {
410 if (middle_point[0] > middle_point[2]) {
415 if (middle_point[1] > middle_point[2]) {
433 if (
node->children[i]) {
434 for (axis_iter = tree->
start_axis; axis_iter < tree->stop_axis; axis_iter++) {
436 node->bv[(2 * axis_iter)] = std::min(
node->children[i]->bv[(2 * axis_iter)],
437 node->bv[(2 * axis_iter)]);
440 node->bv[(2 * axis_iter) + 1] = std::max(
node->children[i]->bv[(2 * axis_iter) + 1],
441 node->bv[(2 * axis_iter) + 1]);
458static void bvhtree_print_tree(BVHTree *tree,
BVHNode *
node,
int depth)
463 for (i = 0; i < depth; i++) {
466 printf(
" - %d (%ld): ",
node->index, (
long int)(
node - tree->nodearray));
467 for (axis_iter = (
axis_t)(2 * tree->start_axis); axis_iter < (
axis_t)(2 * tree->stop_axis);
474 for (i = 0; i < tree->tree_type; i++) {
475 if (
node->children[i]) {
476 bvhtree_print_tree(tree,
node->children[i], depth + 1);
481static void bvhtree_info(
BVHTree *tree)
483 printf(
"BVHTree Info: tree_type = %d, axis = %d, epsilon = %f\n",
487 printf(
"nodes = %d, branches = %d, leafs = %d\n",
488 tree->branch_num + tree->leaf_num,
491 printf(
"Memory per node = %ubytes\n",
492 uint(
sizeof(
BVHNode) +
sizeof(
BVHNode *) * tree->tree_type +
sizeof(
float) * tree->axis));
493 const size_t nodebv_len =
sizeof(
float) *
size_t(tree->axis) * size_t(tree->nodes_num_alloc);
494 const size_t nodes_len =
sizeof(
BVHNode *) *
size_t(tree->nodes_num_alloc);
495 const size_t nodearray_len =
sizeof(
BVHNode) *
size_t(tree->nodes_num_alloc);
496 const size_t nodechild_len =
sizeof(
BVHNode *) *
size_t(tree->tree_type) *
497 size_t(tree->nodes_num_alloc);
499 printf(
"BV memory = %ubytes\n",
uint(nodebv_len));
501 printf(
"Total memory = %ubytes\n",
502 uint(
sizeof(
BVHTree) + nodes_len + nodearray_len + nodechild_len + nodebv_len));
504 bvhtree_print_tree(tree, tree->nodes[tree->leaf_num], 0);
511#ifdef USE_VERIFY_TREE
513static void bvhtree_verify(
BVHTree *tree)
518 for (i = 0; i < tree->leaf_num; i++) {
519 if (tree->nodes[i]->parent ==
nullptr) {
520 printf(
"Leaf has no parent: %d\n", i);
523 for (j = 0; j < tree->tree_type; j++) {
524 if (tree->nodes[i]->parent->children[j] == tree->nodes[i]) {
529 printf(
"Parent child relationship doesn't match: %d\n", i);
536 for (i = 0; i < tree->leaf_num; i++) {
537 if (tree->nodearray[i].parent ==
nullptr) {
538 printf(
"Leaf has no parent: %d\n", i);
541 for (j = 0; j < tree->tree_type; j++) {
542 if (tree->nodearray[i].parent->children[j] == &tree->nodearray[i]) {
547 printf(
"Parent child relationship doesn't match: %d\n", i);
553 printf(
"branches: %d, leafs: %d, total: %d\n",
556 tree->branch_num + tree->leaf_num);
590 for (
data->leafs_per_child[0] = 1;
data->leafs_per_child[0] <
data->leafs_num;
591 data->leafs_per_child[0] *=
data->tree_type)
596 data->branches_on_level[0] = 1;
598 for (depth = 1; (depth < 32) &&
data->leafs_per_child[depth - 1]; depth++) {
599 data->branches_on_level[depth] =
data->branches_on_level[depth - 1] *
data->tree_type;
600 data->leafs_per_child[depth] =
data->leafs_per_child[depth - 1] /
data->tree_type;
603 remain =
data->leafs_num -
data->leafs_per_child[1];
604 nnodes = (remain +
data->tree_type - 2) / (
data->tree_type - 1);
605 data->remain_leafs = remain + nnodes;
613 int min_leaf_index = child_index *
data->leafs_per_child[depth - 1];
614 if (min_leaf_index <= data->remain_leafs) {
615 return min_leaf_index;
617 if (
data->leafs_per_child[depth]) {
618 return data->leafs_num -
619 (
data->branches_on_level[depth - 1] - child_index) *
data->leafs_per_child[depth];
621 return data->remain_leafs;
656 return max_ii(1, (leafs + tree_type - 3) / (tree_type - 1));
673 const int partitions,
674 const int split_axis)
677 for (i = 0; i < partitions - 1; i++) {
678 if (nth[i] >= nth[partitions]) {
708 const int parent_level_index = j -
data->i;
728 nth_positions[0] = parent_leafs_begin;
729 nth_positions[
data->tree_type] = parent_leafs_end;
730 for (k = 1; k <
data->tree_type; k++) {
731 const int child_index = j *
data->tree_type +
data->tree_offset + k;
733 const int child_level_index = child_index -
data->first_of_next_level;
742 for (k = 0; k <
data->tree_type; k++) {
743 const int child_index = j *
data->tree_type +
data->tree_offset + k;
745 const int child_level_index = child_index -
data->first_of_next_level;
748 data->data,
data->depth + 1, child_level_index);
750 data->data,
data->depth + 1, child_level_index + 1);
752 if (child_leafs_end - child_leafs_begin > 1) {
753 parent->
children[k] = &
data->branches_array[child_index];
756 else if (child_leafs_end - child_leafs_begin == 1) {
757 parent->
children[k] =
data->leafs_array[child_leafs_begin];
794 const int tree_offset = 2 - tree->
tree_type;
803 BVHNode *root = &branches_array[1];
808 if (leafs_num == 1) {
832 for (i = 1, depth = 1; i <= branches_num; i = i * tree_type + tree_offset, depth++) {
833 const int first_of_next_level = i * tree_type + tree_offset;
835 const int i_stop =
min_ii(first_of_next_level, branches_num + 1);
840 cb_data.
depth = depth;
851 for (
int i_task = i; i_task < i_stop; i_task++) {
885 else if (axis == 18) {
889 else if (axis == 14) {
893 else if (axis == 8) {
897 else if (axis == 6) {
923 for (
int i = 0; i < numnodes; i++) {
938 MEM_SAFE_DELETE(tree->
nodes);
940 MEM_SAFE_DELETE(tree->
nodebv);
966 build_skip_links(tree, tree->
nodes[tree->
leaf_num],
nullptr,
nullptr);
969#ifdef USE_VERIFY_TREE
970 bvhtree_verify(tree);
981 for (axis_iter = tree->
start_axis; axis_iter < tree->stop_axis; axis_iter++) {
983 node->bv[(2 * axis_iter)] -= dist_corrected;
984 node->bv[(2 * axis_iter) + 1] += dist_corrected;
1007 BVHTree *tree,
int index,
const float co[3],
const float co_moving[3],
int numpoints)
1061 if (root !=
nullptr) {
1062 const float bb_min[3] = {root->
bv[0], root->
bv[2], root->
bv[4]};
1063 const float bb_max[3] = {root->
bv[1], root->
bv[3], root->
bv[5]};
1088 const float *bv1 = node1->
bv + (start_axis << 1);
1089 const float *bv2 = node2->
bv + (start_axis << 1);
1090 const float *bv1_end = node1->
bv + (stop_axis << 1);
1093 for (; bv1 != bv1_end; bv1 += 2, bv2 += 2) {
1094 if ((bv1[0] > bv2[1]) || (bv2[0] > bv1[1])) {
1106 const BVHOverlapData_Shared *
data = data_thread->
shared;
1116 if (node1 == node2) [[unlikely]] {
1126 for (j = 0; j <
data->tree2->tree_type; j++) {
1134 for (j = 0; j <
data->tree1->tree_type; j++) {
1150 BVHOverlapData_Shared *
data = data_thread->
shared;
1160 if (node1 == node2) [[unlikely]] {
1173 for (j = 0; j <
data->tree2->tree_type; j++) {
1181 for (j = 0; j <
data->tree1->tree_type; j++) {
1197 BVHOverlapData_Shared *
data = data_thread->
shared;
1207 if (node1 == node2) [[unlikely]] {
1212 if (!
data->callback ||
1225 for (j = 0; j < node2->
node_num; j++) {
1234 for (j = 0; j < node1->
node_num; j++) {
1249 if (
data->max_interactions) {
1252 else if (
data->shared->callback) {
1263 for (
int i = 0; i <
node->node_num; i++) {
1268 for (
int j = i + 1; j <
node->node_num; j++) {
1277 for (
int i = 0; i <
node->node_num; i++) {
1282 for (
int j = i + 1; j <
node->node_num; j++) {
1292 if (data_thread->
shared->callback) {
1310 BVHOverlapData_Shared *data_shared =
data->shared;
1312 const BVHNode *root1 = data_shared->tree1->nodes[data_shared->tree1->leaf_num];
1314 if (data_shared->use_self) {
1318 for (
int k = j + 1; k < root1->
node_num; k++) {
1323 const BVHNode *root2 = data_shared->tree2->nodes[data_shared->tree2->leaf_num];
1332 uint *r_overlap_num,
1336 const uint max_interactions,
1345 BLI_assert(overlap_pairs || max_interactions);
1347 BLI_assert(!use_self || (tree1 == tree2 && !max_interactions));
1350 const int thread_num = use_threading ? root_node_len : 1;
1354 BVHOverlapData_Shared data_shared;
1356 axis_t start_axis, stop_axis;
1359 if ((tree1->
axis != tree2->
axis) && (tree1->
axis == 14 || tree2->
axis == 14) &&
1360 (tree1->
axis == 18 || tree2->
axis == 18)) [[unlikely]]
1366 if (use_self && tree1 != tree2) [[unlikely]] {
1381 data_shared.tree1 = tree1;
1382 data_shared.tree2 = tree2;
1384 data_shared.stop_axis = stop_axis;
1385 data_shared.use_self = use_self;
1388 data_shared.callback = callback;
1389 data_shared.userdata = userdata;
1391 for (j = 0; j < thread_num; j++) {
1393 data[j].shared = &data_shared;
1395 data[j].max_interactions = use_self ? 0 : max_interactions;
1401 if (use_threading) {
1407 else if (use_self) {
1414 if (overlap_pairs) {
1415 for (j = 0; j < thread_num; j++) {
1421 for (j = 0; j < thread_num; j++) {
1427 *r_overlap_num =
uint(total);
1436 uint *r_overlap_num,
1452 uint *r_overlap_num,
1476 const float bb_min[3] = {bv[0], bv[2], bv[4]};
1477 const float bb_max[3] = {bv[1], bv[3], bv[5]};
1478 float bb_near[3], bb_far[3];
1493 if (!
node->node_num) {
1498 for (
int j = 0; j <
data->tree->tree_type; j++) {
1499 if (
node->children[j]) {
1528 *r_intersect_num =
uint(total);
1543 const float *bv =
node->bv;
1546 for (i = 0; i != 3; i++, bv += 2) {
1547 float val = proj[i];
1548 val = std::max(bv[0], val);
1549 val = std::min(bv[1], val);
1559 if (
node->node_num == 0) {
1560 if (
data->callback) {
1573 if (
data->proj[
node->main_axis] <=
node->children[0]->bv[
node->main_axis * 2 + 1]) {
1575 for (i = 0; i !=
node->node_num; i++) {
1577 data->nearest.dist_sq)
1585 for (i =
node->node_num - 1; i >= 0; i--) {
1587 data->nearest.dist_sq)
1599 float nearest[3], dist_sq;
1601 if (dist_sq >=
data->nearest.dist_sq) {
1610 if (
node->node_num == 0) {
1611 if (
data->callback) {
1622 for (
int i = 0; i !=
node->node_num; i++) {
1625 if (dist_sq < data->nearest.dist_sq) {
1637 if (dist_sq < data->nearest.dist_sq) {
1669 data.callback = callback;
1670 data.userdata = userdata;
1672 for (axis_iter =
data.tree->start_axis; axis_iter !=
data.tree->stop_axis; axis_iter++) {
1677 memcpy(&
data.nearest, nearest,
sizeof(*nearest));
1680 data.nearest.index = -1;
1696 memcpy(nearest, &
data.nearest,
sizeof(*nearest));
1699 return data.nearest.index;
1721 if (co[0] > bv[0].
min && co[0] < bv[0].
max && co[1] > bv[1].
min && co[1] < bv[1].
max &&
1722 co[2] > bv[2].
min && co[2] < bv[2].
max)
1732 if (
node->node_num == 0) {
1734 if (
data->callback) {
1735 const float dist_sq =
data->nearest.dist_sq;
1737 return (
data->nearest.dist_sq < dist_sq);
1747 if (
data->proj[
node->main_axis] <=
node->children[0]->bv[
node->main_axis * 2 + 1]) {
1748 for (i = 0; i !=
node->node_num; i++) {
1757 for (i =
node->node_num; i--;) {
1771 const float dist_sq,
1782 data.callback = callback;
1783 data.userdata = userdata;
1784 data.nearest.index = -1;
1785 data.nearest.dist_sq = dist_sq;
1792 return data.nearest.index;
1809 float low = 0, upper =
data->hit.dist;
1811 for (i = 0; i != 3; i++, bv += 2) {
1812 if (
data->ray_dot_axis[i] == 0.0f) {
1814 if (
data->ray.origin[i] < bv[0] -
data->ray.radius ||
1815 data->ray.origin[i] > bv[1] +
data->ray.radius)
1821 float ll = (bv[0] -
data->ray.radius -
data->ray.origin[i]) /
data->ray_dot_axis[i];
1822 float lu = (bv[1] +
data->ray.radius -
data->ray.origin[i]) /
data->ray_dot_axis[i];
1824 if (
data->ray_dot_axis[i] > 0.0f) {
1825 low = std::max(ll, low);
1826 upper = std::min(lu, upper);
1829 low = std::max(lu, low);
1830 upper = std::min(ll, upper);
1850 const float *bv =
node->bv;
1852 float t1x = (bv[
data->index[0]] -
data->ray.origin[0]) *
data->idot_axis[0];
1853 float t2x = (bv[
data->index[1]] -
data->ray.origin[0]) *
data->idot_axis[0];
1854 float t1y = (bv[
data->index[2]] -
data->ray.origin[1]) *
data->idot_axis[1];
1855 float t2y = (bv[
data->index[3]] -
data->ray.origin[1]) *
data->idot_axis[1];
1856 float t1z = (bv[
data->index[4]] -
data->ray.origin[2]) *
data->idot_axis[2];
1857 float t2z = (bv[
data->index[5]] -
data->ray.origin[2]) *
data->idot_axis[2];
1859 if ((t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) ||
1860 (t2x < 0.0f || t2y < 0.0f || t2z < 0.0f) ||
1861 (t1x >
data->hit.dist || t1y >
data->hit.dist || t1z >
data->hit.dist))
1865 return std::max({t1x, t1y, t1z});
1877 if (dist >=
data->hit.dist) {
1881 if (
node->node_num == 0) {
1882 if (
data->callback) {
1887 data->hit.dist = dist;
1893 if (
data->ray_dot_axis[
node->main_axis] > 0.0f) {
1894 for (i = 0; i !=
node->node_num; i++) {
1899 for (i =
node->node_num - 1; i >= 0; i--) {
1918 if (dist >=
data->hit.dist) {
1922 if (
node->node_num == 0) {
1924 dist =
data->hit.dist;
1926 data->hit.index = -1;
1927 data->hit.dist = dist;
1931 if (
data->ray_dot_axis[
node->main_axis] > 0.0f) {
1932 for (i = 0; i !=
node->node_num; i++) {
1937 for (i =
node->node_num - 1; i >= 0; i--) {
1948 for (i = 0; i < 3; i++) {
1952 data->ray_dot_axis[i] = 0.0f;
1957 data->idot_axis[i] = 1.0f /
data->ray_dot_axis[i];
1960 data->index[2 * i] =
data->idot_axis[i] < 0.0f ? 1 : 0;
1961 data->index[2 * i + 1] = 1 -
data->index[2 * i];
1962 data->index[2 * i] += 2 * i;
1963 data->index[2 * i + 1] += 2 * i;
1966#ifdef USE_KDOPBVH_WATERTIGHT
1969 data->ray.isect_precalc = &
data->isect_precalc;
1972 data->ray.isect_precalc =
nullptr;
1995 data.callback = callback;
1996 data.userdata = userdata;
2000 data.ray.radius = radius;
2005 memcpy(&
data.hit, hit,
sizeof(*hit));
2008 data.hit.index = -1;
2018 memcpy(hit, &
data.hit,
sizeof(*hit));
2021 return data.hit.index;
2037 const float light_start[3],
2038 const float light_end[3],
2049 data.ray.radius = 0.0;
2080 data.callback = callback;
2081 data.userdata = userdata;
2085 data.ray.radius = radius;
2089 data.hit.index = -1;
2090 data.hit.dist = hit_dist;
2133 if (
node->node_num == 0) {
2138 co[0] =
node->bv[0];
2139 co[1] =
node->bv[2];
2140 co[2] =
node->bv[4];
2145 for (i = 0; i !=
node->node_num; i++) {
2148 if (dist_sq < data->radius_sq) {
2150 if (
node->children[i]->node_num == 0) {
2152 data->callback(
data->userdata,
node->children[i]->index,
data->center, dist_sq);
2173 data.radius_sq = radius * radius;
2176 data.callback = callback;
2177 data.userdata = userdata;
2179 if (root !=
nullptr) {
2182 if (dist_sq <
data.radius_sq) {
2206 if (
node->node_num == 0) {
2207 if (
data->callback) {
2214 float3{node->bv[0], node->bv[2], node->bv[4]},
2215 float3{node->bv[1], node->bv[3], node->bv[5]},
2216 data->closest_axis);
2221 if (
data->closest_axis[
node->main_axis]) {
2222 for (
int i = 0; i !=
node->node_num; i++) {
2223 const float *bv =
node->children[i]->bv;
2226 float3{bv[0], bv[2], bv[4]},
2227 float3{bv[1], bv[3], bv[5]},
2228 data->closest_axis) <=
data->nearest.dist_sq)
2235 for (
int i =
node->node_num; i--;) {
2236 const float *bv =
node->children[i]->bv;
2239 float3{bv[0], bv[2], bv[4]},
2240 float3{bv[1], bv[3], bv[5]},
2241 data->closest_axis) <=
data->nearest.dist_sq)
2253 if (
node->node_num == 0) {
2254 if (
data->callback) {
2259 data->clip_plane_len,
2266 float3{node->bv[0], node->bv[2], node->bv[4]},
2267 float3{node->bv[1], node->bv[3], node->bv[5]},
2268 data->closest_axis);
2273 if (
data->closest_axis[
node->main_axis]) {
2274 for (
int i = 0; i !=
node->node_num; i++) {
2275 const float *bv =
node->children[i]->bv;
2276 const float bb_min[3] = {bv[0], bv[2], bv[4]};
2277 const float bb_max[3] = {bv[1], bv[3], bv[5]};
2280 data->clip_plane,
data->clip_plane_len, bb_min, bb_max);
2284 data->nearest.dist_sq)
2297 for (
int i =
node->node_num; i--;) {
2298 const float *bv =
node->children[i]->bv;
2299 const float bb_min[3] = {bv[0], bv[2], bv[4]};
2300 const float bb_max[3] = {bv[1], bv[3], bv[5]};
2303 data->clip_plane,
data->clip_plane_len, bb_min, bb_max);
2307 data->nearest.dist_sq)
2323 float projmat[4][4],
2326 float (*clip_plane)[4],
2333 if (root !=
nullptr) {
2335 alloca(
sizeof(*
data) + (
sizeof(*clip_plane) *
size_t(
max_ii(1, clip_plane_len)))));
2339 data->callback = callback;
2340 data->userdata = userdata;
2343# pragma GCC diagnostic push
2344# pragma GCC diagnostic ignored "-Warray-bounds"
2347 data->clip_plane_len = clip_plane_len;
2348 for (
int i = 0; i < clip_plane_len; i++) {
2353 data->clip_plane_len = 1;
2355 projmat,
nullptr,
nullptr,
nullptr,
nullptr,
data->clip_plane[0],
nullptr);
2358# pragma GCC diagnostic pop
2362 memcpy(&
data->nearest, nearest,
sizeof(*nearest));
2365 data->nearest.index = -1;
2369 const float bb_min[3] = {root->
bv[0], root->
bv[2], root->
bv[4]};
2370 const float bb_max[3] = {root->
bv[1], root->
bv[3], root->
bv[5]};
2373 data->clip_plane,
data->clip_plane_len, bb_min, bb_max);
2375 if (isect_type != 0 &&
2377 data->nearest.dist_sq)
2379 if (isect_type == 1) {
2389 memcpy(nearest, &
data->nearest,
sizeof(*nearest));
2392 return data->nearest.index;
#define BLI_array_alloca(arr, realsize)
A min-heap / priority queue ADT.
#define KDOPBVH_THREAD_LEAF_THRESHOLD
#define BVH_RAYCAST_DIST_MAX
#define BVH_RAYCAST_DEFAULT
#define BLI_ASSERT_UNIT_V3(v)
#define ISECT_AABB_PLANE_CROSS_ANY
#define ISECT_AABB_PLANE_BEHIND_ANY
Read Blender memory allocation and freeing.
#define BLI_assert_unreachable()
bool intersect(IsectPyramid i_pyramid, Box box)
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void(*)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) BVHTree_RayCastCallback
BVHTreeOverlap * BLI_bvhtree_overlap_ex(const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, uint max_interactions, int flag)
static char get_largest_axis(const float *bv)
void BLI_bvhtree_get_bounding_box(const BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
static int implicit_needed_branches(int tree_type, int leafs)
const float bvhtree_kdop_axes[13][3]
BLI_STATIC_ASSERT(ARRAY_SIZE(data_mode_strings)==CTX_MODE_NUM+1, "Must have a string for each context mode") const char *CTX_data_mode_string(const bContext *C)
static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node)
@ BVH_NEAREST_OPTIMAL_ORDER
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
void(*)(void *userdata, int index, const float co[3], float dist_sq) BVHTree_RangeQuery
int * BLI_bvhtree_intersect_plane(const BVHTree *tree, float plane[4], uint *r_intersect_num)
MINLINE void copy_v3_v3(float r[3], const float a[3])
static BVHNode * bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
int BLI_bvhtree_get_tree_type(const BVHTree *tree)
int BLI_bvhtree_find_nearest(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
HeapSimple * BLI_heapsimple_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
float BLI_bvhtree_get_epsilon(const BVHTree *tree)
int isect_aabb_planes_v3(const float(*planes)[4], int totplane, const float bbmin[3], const float bbmax[3])
void BLI_bvhtree_free(BVHTree *tree)
static void bvh_insertionsort(BVHNode **a, int lo, int hi, int axis)
void planes_from_projmat(const float mat[4][4], float left[4], float right[4], float bottom[4], float top[4], float near[4], float far[4])
int BLI_bvhtree_ray_cast_ex(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata, int flag)
void BLI_bvhtree_balance(BVHTree *tree)
static const float bvhtree_kdop_axes_length[13]
static void bvhtree_ray_cast_data_precalc(BVHRayCastData *data, int flag)
static void bvhtree_nearest_projected_dfs_recursive(BVHNearestProjectedData *__restrict data, const BVHNode *node)
static void split_leafs(BVHNode **leafs_array, const int nth[], const int partitions, const int split_axis)
MINLINE int max_ii(int a, int b)
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
static void dfs_range_query(RangeQueryData *data, BVHNode *node)
static bool isect_aabb_v3(BVHNode *node, const float co[3])
static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
int BLI_bvhtree_ray_cast(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
void * BLI_stack_push_r(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
static void node_minmax_init(const BVHTree *tree, BVHNode *node)
void dist_squared_to_projected_aabb_precalc(struct DistProjectedAABBPrecalc *precalc, const float projmat[4][4], const float winsize[2], const float mval[2])
static void bvhtree_intersect_plane_dfs_recursive(BVHIntersectPlaneData *__restrict data, const BVHNode *node)
static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
static void tree_overlap_traverse_self(BVHOverlapData_Thread *data_thread, const BVHNode *node)
static void bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(BVHNearestProjectedData *__restrict data, const BVHNode *node)
int BLI_bvhtree_find_nearest_ex(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
void BLI_bvhtree_update_tree(BVHTree *tree)
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void heap_find_nearest_inner(BVHNearestData *data, HeapSimple *heap, BVHNode *node)
BMesh const char void * data
static int implicit_leafs_index(const BVHBuildHelper *data, const int depth, const int child_index)
static void build_implicit_tree_helper(const BVHTree *tree, BVHBuildHelper *data)
int BLI_bvhtree_range_query(const BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
int BLI_bvhtree_get_len(const BVHTree *tree)
MINLINE axis_t min_axis(axis_t a, axis_t b)
static int bvh_partition(BVHNode **a, int lo, int hi, const BVHNode *x, int axis)
static void dfs_raycast_all(BVHRayCastData *data, BVHNode *node)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
void aabb_get_near_far_from_plane(const float plane_no[3], const float bbmin[3], const float bbmax[3], float bb_near[3], float bb_afar[3])
static void tree_overlap_traverse(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
MINLINE float plane_point_side_v3(const float plane[4], const float co[3])
void isect_ray_tri_watertight_v3_precalc(struct IsectRayPrecalc *isect_precalc, const float ray_direction[3])
float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
static void tree_overlap_invoke_traverse_self(BVHOverlapData_Thread *data_thread, const BVHNode *node)
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
BVHTreeOverlap * BLI_bvhtree_overlap_self(const BVHTree *tree, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node)
@ BVH_OVERLAP_USE_THREADING
@ BVH_OVERLAP_RETURN_PAIRS
void BLI_bvhtree_ray_cast_all(const BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata)
static void partition_nth_element(BVHNode **a, int begin, int end, const int n, const int axis)
MINLINE void zero_v3(float r[3])
static void tree_overlap_traverse_cb(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
void BLI_bvhtree_ray_cast_all_ex(const BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata, int flag)
static void non_recursive_bvh_div_nodes(const BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int leafs_num)
int BLI_bvhtree_overlap_thread_num(const BVHTree *tree)
static bool tree_overlap_test(const BVHNode *node1, const BVHNode *node2, axis_t start_axis, axis_t stop_axis)
float BLI_heapsimple_top_value(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
MINLINE float normalize_v3(float n[3])
bool(*)(void *userdata, int index_a, int index_b, int thread) BVHTree_OverlapCallback
static void bvhtree_node_inflate(const BVHTree *tree, BVHNode *node, const float dist)
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
static void heap_find_nearest_begin(BVHNearestData *data, BVHNode *root)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
static void create_kdop_hull(const BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving)
static bool dfs_find_duplicate_fast_dfs(BVHNearestData *data, BVHNode *node)
static void bvhtree_overlap_task_cb(void *__restrict userdata, const int j, const TaskParallelTLS *__restrict)
static void non_recursive_bvh_div_nodes_task_cb(void *__restrict userdata, const int j, const TaskParallelTLS *__restrict)
MINLINE float max_ff(float a, float b)
static void tree_overlap_invoke_traverse(BVHOverlapData_Thread *data, const BVHNode *node1, const BVHNode *node2)
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
static float ray_nearest_hit(const BVHRayCastData *data, const float bv[6])
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
static bool tree_intersect_plane_test(const float *bv, const float plane[4])
static float calc_nearest_point_squared(const float proj[3], BVHNode *node, float nearest[3])
MINLINE void copy_v4_v4(float r[4], const float a[4])
VecBase< float, 3 > float3
float dist_squared_to_projected_aabb(struct DistProjectedAABBPrecalc *data, const float bbmin[3], const float bbmax[3], bool r_axis_closest[3])
static void refit_kdop_hull(const BVHTree *tree, BVHNode *node, int start, int end)
void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
BLI_Stack * BLI_stack_new(size_t elem_size, const char *description) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void node_join(BVHTree *tree, BVHNode *node)
MINLINE int min_ii(int a, int b)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void(*)(void *userdata, int index, const DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest) BVHTree_NearestProjectedCallback
int BLI_bvhtree_find_nearest_first(const BVHTree *tree, const float co[3], float dist_sq, BVHTree_NearestPointCallback callback, void *userdata)
static bool tree_overlap_traverse_num(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
int BLI_bvhtree_find_nearest_projected(const BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], float(*clip_planes)[4], int clip_plane_len, BVHTreeNearest *nearest, BVHTree_NearestProjectedCallback callback, void *userdata)
static void tree_overlap_traverse_self_cb(BVHOverlapData_Thread *data_thread, const BVHNode *node)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void(*)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest) BVHTree_NearestPointCallback
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
int branches_on_level[32]
const BVHBuildHelper * data
BVHTree_NearestPointCallback callback
DistProjectedAABBPrecalc precalc
BVHTree_NearestProjectedCallback callback
BVHOverlapData_Shared * shared
BVHTree_RayCastCallback callback
BVHTree_RangeQuery callback