diff options
Diffstat (limited to 'source/blender/blenlib/intern/BLI_kdopbvh.c')
| -rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 498 |
1 files changed, 388 insertions, 110 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index ddb61e415ac..bba3fdb37bc 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -29,7 +29,12 @@ * \ingroup bli * \brief BVH-tree implementation. * - * KD-Overlap-BVH, implements a bvh-tree structure with support for: + * k-DOP BVH (Discrete Oriented Polytope, Bounding Volume Hierarchy). + * A k-DOP is represented as k/2 pairs of min , max values for k/2 directions (intervals, "slabs"). + * + * See: http://www.gris.uni-tuebingen.de/people/staff/jmezger/papers/bvh.pdf + * + * implements a bvh-tree structure with support for: * * - Ray-cast: * #BLI_bvhtree_ray_cast, #BVHRayCastData @@ -37,6 +42,8 @@ * #BLI_bvhtree_find_nearest, #BVHNearestData * - Overlapping 2 trees: * #BLI_bvhtree_overlap, #BVHOverlapData_Shared, #BVHOverlapData_Thread + * - Range Query: + * #BLI_bvhtree_range_query */ #include <assert.h> @@ -49,27 +56,28 @@ #include "BLI_kdopbvh.h" #include "BLI_math.h" #include "BLI_strict_flags.h" - -#ifdef _OPENMP -#include <omp.h> -#endif +#include "BLI_task.h" /* used for iterative_raycast */ // #define USE_SKIP_LINKS #define MAX_TREETYPE 32 -/* Setting zero so we can catch bugs in OpenMP/KDOPBVH. +/* Setting zero so we can catch bugs in BLI_task/KDOPBVH. * TODO(sergey): Deduplicate the limits with PBVH from BKE. */ -#ifdef _OPENMP -# ifdef DEBUG -# define KDOPBVH_OMP_LIMIT 0 -# else -# define KDOPBVH_OMP_LIMIT 1024 -# endif +#ifdef DEBUG +# define KDOPBVH_THREAD_LEAF_THRESHOLD 0 +#else +# define KDOPBVH_THREAD_LEAF_THRESHOLD 1024 #endif + +/* -------------------------------------------------------------------- */ + +/** \name Struct Definitions + * \{ */ + typedef unsigned char axis_t; typedef struct BVHNode { @@ -93,7 +101,7 @@ struct BVHTree { float epsilon; /* epslion is used for inflation of the k-dop */ int totleaf; /* leafs */ int totbranch; - axis_t start_axis, stop_axis; /* KDOP_AXES array indices according to axis */ + axis_t start_axis, stop_axis; /* bvhtree_kdop_axes array indices according to axis */ axis_t axis; /* kdop type (6 => OBB, 7 => AABB, ...) */ char tree_type; /* type of tree (4 => quadtree) */ }; @@ -151,6 +159,20 @@ typedef struct BVHRayCastData { BVHTreeRayHit hit; } BVHRayCastData; +typedef struct BVHNearestRayData { + BVHTree *tree; + BVHTree_NearestToRayCallback callback; + void *userdata; + BVHTreeRay ray; + + struct NearestRayToAABB_Precalc nearest_precalc; + + bool pick_smallest[3]; + BVHTreeNearest nearest; +} BVHNearestRayData; + +/** \} */ + /** * Bounding Volume Hierarchy Definition @@ -160,12 +182,18 @@ typedef struct BVHRayCastData { * Notes: You can choose the tree type --> binary, quad, octree, choose below */ -static const float KDOP_AXES[13][3] = { +const float bvhtree_kdop_axes[13][3] = { {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0}, {1.0, -1.0, -1.0}, {1.0, 1.0, 0}, {1.0, 0, 1.0}, {0, 1.0, 1.0}, {1.0, -1.0, 0}, {1.0, 0, -1.0}, {0, 1.0, -1.0} }; + +/* -------------------------------------------------------------------- */ + +/** \name Utility Functions + * \{ */ + MINLINE axis_t min_axis(axis_t a, axis_t b) { return (a < b) ? a : b; @@ -275,6 +303,14 @@ static void node_minmax_init(const BVHTree *tree, BVHNode *node) } } +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name Balance Utility Functions + * \{ */ + /** * Insertion sort algorithm */ @@ -455,7 +491,7 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, const float *co, int for (k = 0; k < numpoints; k++) { /* for all Axes. */ for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) { - newminmax = dot_v3v3(&co[k * 3], KDOP_AXES[axis_iter]); + newminmax = dot_v3v3(&co[k * 3], bvhtree_kdop_axes[axis_iter]); if (newminmax < bv[2 * axis_iter]) bv[2 * axis_iter] = newminmax; if (newminmax > bv[(2 * axis_iter) + 1]) @@ -740,6 +776,81 @@ static void split_leafs(BVHNode **leafs_array, int *nth, int partitions, int spl } } +typedef struct BVHDivNodesData { + BVHTree *tree; + BVHNode *branches_array; + BVHNode **leafs_array; + + int tree_type; + int tree_offset; + + BVHBuildHelper *data; + + int depth; + int i; + int first_of_next_level; +} BVHDivNodesData; + +static void non_recursive_bvh_div_nodes_task_cb(void *userdata, const int j) +{ + BVHDivNodesData *data = userdata; + + int k; + const int parent_level_index = j - data->i; + BVHNode *parent = data->branches_array + j; + int nth_positions[MAX_TREETYPE + 1]; + char split_axis; + + int parent_leafs_begin = implicit_leafs_index(data->data, data->depth, parent_level_index); + int parent_leafs_end = implicit_leafs_index(data->data, data->depth, parent_level_index + 1); + + /* This calculates the bounding box of this branch + * and chooses the largest axis as the axis to divide leafs */ + refit_kdop_hull(data->tree, parent, parent_leafs_begin, parent_leafs_end); + split_axis = get_largest_axis(parent->bv); + + /* Save split axis (this can be used on raytracing to speedup the query time) */ + parent->main_axis = split_axis / 2; + + /* Split the childs along the split_axis, note: its not needed to sort the whole leafs array + * Only to assure that the elements are partitioned on a way that each child takes the elements + * it would take in case the whole array was sorted. + * Split_leafs takes care of that "sort" problem. */ + nth_positions[0] = parent_leafs_begin; + nth_positions[data->tree_type] = parent_leafs_end; + for (k = 1; k < data->tree_type; k++) { + const int child_index = j * data->tree_type + data->tree_offset + k; + const int child_level_index = child_index - data->first_of_next_level; /* child level index */ + nth_positions[k] = implicit_leafs_index(data->data, data->depth + 1, child_level_index); + } + + split_leafs(data->leafs_array, nth_positions, data->tree_type, split_axis); + + /* Setup children and totnode counters + * Not really needed but currently most of BVH code relies on having an explicit children structure */ + for (k = 0; k < data->tree_type; k++) { + const int child_index = j * data->tree_type + data->tree_offset + k; + const int child_level_index = child_index - data->first_of_next_level; /* child level index */ + + const int child_leafs_begin = implicit_leafs_index(data->data, data->depth + 1, child_level_index); + const int child_leafs_end = implicit_leafs_index(data->data, data->depth + 1, child_level_index + 1); + + if (child_leafs_end - child_leafs_begin > 1) { + parent->children[k] = data->branches_array + child_index; + parent->children[k]->parent = parent; + } + else if (child_leafs_end - child_leafs_begin == 1) { + parent->children[k] = data->leafs_array[child_leafs_begin]; + parent->children[k]->parent = parent; + } + else { + break; + } + + parent->totnode = (char)(k + 1); + } +} + /** * This functions builds an optimal implicit tree from the given leafs. * Where optimal stands for: @@ -787,77 +898,35 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array, build_implicit_tree_helper(tree, &data); + BVHDivNodesData cb_data = { + .tree = tree, .branches_array = branches_array, .leafs_array = leafs_array, + .tree_type = tree_type, .tree_offset = tree_offset, .data = &data, + .first_of_next_level = 0, .depth = 0, .i = 0, + }; + /* Loop tree levels (log N) loops */ for (i = 1, depth = 1; i <= num_branches; i = i * tree_type + tree_offset, depth++) { const int first_of_next_level = i * tree_type + tree_offset; const int end_j = min_ii(first_of_next_level, num_branches + 1); /* index of last branch on this level */ - int j; /* Loop all branches on this level */ + cb_data.first_of_next_level = first_of_next_level; + cb_data.i = i; + cb_data.depth = depth; -#pragma omp parallel for private(j) schedule(static) if (num_leafs > KDOPBVH_OMP_LIMIT) - for (j = i; j < end_j; j++) { - int k; - const int parent_level_index = j - i; - BVHNode *parent = branches_array + j; - int nth_positions[MAX_TREETYPE + 1]; - char split_axis; - - int parent_leafs_begin = implicit_leafs_index(&data, depth, parent_level_index); - int parent_leafs_end = implicit_leafs_index(&data, depth, parent_level_index + 1); - - /* This calculates the bounding box of this branch - * and chooses the largest axis as the axis to divide leafs */ - refit_kdop_hull(tree, parent, parent_leafs_begin, parent_leafs_end); - split_axis = get_largest_axis(parent->bv); - - /* Save split axis (this can be used on raytracing to speedup the query time) */ - parent->main_axis = split_axis / 2; - - /* Split the childs along the split_axis, note: its not needed to sort the whole leafs array - * Only to assure that the elements are partitioned on a way that each child takes the elements - * it would take in case the whole array was sorted. - * Split_leafs takes care of that "sort" problem. */ - nth_positions[0] = parent_leafs_begin; - nth_positions[tree_type] = parent_leafs_end; - for (k = 1; k < tree_type; k++) { - int child_index = j * tree_type + tree_offset + k; - int child_level_index = child_index - first_of_next_level; /* child level index */ - nth_positions[k] = implicit_leafs_index(&data, depth + 1, child_level_index); - } - - split_leafs(leafs_array, nth_positions, tree_type, split_axis); - - - /* Setup children and totnode counters - * Not really needed but currently most of BVH code relies on having an explicit children structure */ - for (k = 0; k < tree_type; k++) { - int child_index = j * tree_type + tree_offset + k; - int child_level_index = child_index - first_of_next_level; /* child level index */ - - int child_leafs_begin = implicit_leafs_index(&data, depth + 1, child_level_index); - int child_leafs_end = implicit_leafs_index(&data, depth + 1, child_level_index + 1); - - if (child_leafs_end - child_leafs_begin > 1) { - parent->children[k] = branches_array + child_index; - parent->children[k]->parent = parent; - } - else if (child_leafs_end - child_leafs_begin == 1) { - parent->children[k] = leafs_array[child_leafs_begin]; - parent->children[k]->parent = parent; - } - else { - break; - } - - parent->totnode = (char)(k + 1); - } - } + BLI_task_parallel_range( + i, end_j, &cb_data, non_recursive_bvh_div_nodes_task_cb, + num_leafs > KDOPBVH_THREAD_LEAF_THRESHOLD); } } +/** \} */ + + /* -------------------------------------------------------------------- */ -/* BLI_bvhtree api */ + +/** \name BLI_bvhtree API + * \{ */ /** * \note many callers don't check for ``NULL`` return. @@ -1051,9 +1120,13 @@ float BLI_bvhtree_getepsilon(const BVHTree *tree) return tree->epsilon; } +/** \} */ + /* -------------------------------------------------------------------- */ -/* BLI_bvhtree_overlap */ + +/** \name BLI_bvhtree_overlap + * \{ */ /** * overlap - is it possible for 2 bv's to collide ? @@ -1172,6 +1245,23 @@ int BLI_bvhtree_overlap_thread_num(const BVHTree *tree) return (int)MIN2(tree->tree_type, tree->nodes[tree->totleaf]->totnode); } +static void bvhtree_overlap_task_cb(void *userdata, const int j) +{ + BVHOverlapData_Thread *data = &((BVHOverlapData_Thread *)userdata)[j]; + BVHOverlapData_Shared *data_shared = data->shared; + + if (data_shared->callback) { + tree_overlap_traverse_cb( + data, data_shared->tree1->nodes[data_shared->tree1->totleaf]->children[j], + data_shared->tree2->nodes[data_shared->tree2->totleaf]); + } + else { + tree_overlap_traverse( + data, data_shared->tree1->nodes[data_shared->tree1->totleaf]->children[j], + data_shared->tree2->nodes[data_shared->tree2->totleaf]); + } +} + BVHTreeOverlap *BLI_bvhtree_overlap( const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_tot, /* optional callback to test the overlap before adding (must be thread-safe!) */ @@ -1220,15 +1310,9 @@ BVHTreeOverlap *BLI_bvhtree_overlap( data[j].thread = j; } -#pragma omp parallel for private(j) schedule(static) if (tree1->totleaf > KDOPBVH_OMP_LIMIT) - for (j = 0; j < thread_num; j++) { - if (callback) { - tree_overlap_traverse_cb(&data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]); - } - else { - tree_overlap_traverse(&data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]); - } - } + BLI_task_parallel_range( + 0, thread_num, data, bvhtree_overlap_task_cb, + tree1->totleaf > KDOPBVH_THREAD_LEAF_THRESHOLD); for (j = 0; j < thread_num; j++) total += BLI_stack_count(data[j].overlap); @@ -1246,6 +1330,14 @@ BVHTreeOverlap *BLI_bvhtree_overlap( return overlap; } +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name BLI_bvhtree_find_nearest + * \{ */ + /* Determines the nearest point of the given node BV. Returns the squared distance to that point. */ static float calc_nearest_point_squared(const float proj[3], BVHNode *node, float nearest[3]) { @@ -1266,15 +1358,15 @@ static float calc_nearest_point_squared(const float proj[3], BVHNode *node, floa /* nearest on a general hull */ copy_v3_v3(nearest, data->co); for (i = data->tree->start_axis; i != data->tree->stop_axis; i++, bv += 2) { - float proj = dot_v3v3(nearest, KDOP_AXES[i]); + float proj = dot_v3v3(nearest, bvhtree_kdop_axes[i]); float dl = bv[0] - proj; float du = bv[1] - proj; if (dl > 0) { - madd_v3_v3fl(nearest, KDOP_AXES[i], dl); + madd_v3_v3fl(nearest, bvhtree_kdop_axes[i], dl); } else if (du < 0) { - madd_v3_v3fl(nearest, KDOP_AXES[i], du); + madd_v3_v3fl(nearest, bvhtree_kdop_axes[i], du); } } #endif @@ -1352,7 +1444,7 @@ POP_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size) * It may make sense to use this function if the callback queries are very slow.. or if its impossible * to get a nice heuristic * - * this function uses "malloc/free" instead of the MEM_* because it intends to be openmp safe */ + * this function uses "malloc/free" instead of the MEM_* because it intends to be thread safe */ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) { int i; @@ -1420,8 +1512,9 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) #endif -int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, - BVHTree_NearestPointCallback callback, void *userdata) +int BLI_bvhtree_find_nearest( + BVHTree *tree, const float co[3], BVHTreeNearest *nearest, + BVHTree_NearestPointCallback callback, void *userdata) { axis_t axis_iter; @@ -1436,7 +1529,7 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *n data.userdata = userdata; for (axis_iter = data.tree->start_axis; axis_iter != data.tree->stop_axis; axis_iter++) { - data.proj[axis_iter] = dot_v3v3(data.co, KDOP_AXES[axis_iter]); + data.proj[axis_iter] = dot_v3v3(data.co, bvhtree_kdop_axes[axis_iter]); } if (nearest) { @@ -1459,12 +1552,16 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *n return data.nearest.index; } +/** \} */ -/** - * Raycast - BLI_bvhtree_ray_cast + +/* -------------------------------------------------------------------- */ + +/** \name BLI_bvhtree_ray_cast * - * raycast is done by performing a DFS on the BVHTree and saving the closest hit - */ + * raycast is done by performing a DFS on the BVHTree and saving the closest hit. + * + * \{ */ /* Determines the distance that the ray must travel to hit the bounding volume of the given node */ @@ -1577,7 +1674,7 @@ static void dfs_raycast_all(BVHRayCastData *data, BVHNode *node) if (node->totnode == 0) { if (data->callback) { data->hit.index = -1; - data->hit.dist = FLT_MAX; + data->hit.dist = BVH_RAYCAST_DIST_MAX; data->callback(data->userdata, node->index, &data->ray, &data->hit); } else { @@ -1635,7 +1732,7 @@ static void bvhtree_ray_cast_data_precalc(BVHRayCastData *data, int flag) int i; for (i = 0; i < 3; i++) { - data->ray_dot_axis[i] = dot_v3v3(data->ray.direction, KDOP_AXES[i]); + data->ray_dot_axis[i] = dot_v3v3(data->ray.direction, bvhtree_kdop_axes[i]); data->idot_axis[i] = 1.0f / data->ray_dot_axis[i]; if (fabsf(data->ray_dot_axis[i]) < FLT_EPSILON) { @@ -1686,7 +1783,7 @@ int BLI_bvhtree_ray_cast_ex( } else { data.hit.index = -1; - data.hit.dist = FLT_MAX; + data.hit.dist = BVH_RAYCAST_DIST_MAX; } if (root) { @@ -1713,7 +1810,7 @@ float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], cons BVHRayCastData data; float dist; - data.hit.dist = FLT_MAX; + data.hit.dist = BVH_RAYCAST_DIST_MAX; /* get light direction */ sub_v3_v3v3(data.ray.direction, light_end, light_start); @@ -1758,7 +1855,7 @@ int BLI_bvhtree_ray_cast_all_ex( bvhtree_ray_cast_data_precalc(&data, flag); data.hit.index = -1; - data.hit.dist = FLT_MAX; + data.hit.dist = BVH_RAYCAST_DIST_MAX; if (root) { dfs_raycast_all(&data, root); @@ -1774,12 +1871,112 @@ int BLI_bvhtree_ray_cast_all( return BLI_bvhtree_ray_cast_all_ex(tree, co, dir, radius, callback, userdata, BVH_RAYCAST_DEFAULT); } -/** - * Range Query - as request by broken :P + +/* -------------------------------------------------------------------- */ + +/** \name BLI_bvhtree_find_nearest_to_ray + * + * \{ */ + +static float calc_dist_sq_to_ray(BVHNearestRayData *data, BVHNode *node) +{ + const float *bv = node->bv; + const float bb_min[3] = {bv[0], bv[2], bv[4]}; + const float bb_max[3] = {bv[1], bv[3], bv[5]}; + return dist_squared_ray_to_aabb_v3(&data->nearest_precalc, bb_min, bb_max, data->pick_smallest); +} + +static void dfs_find_nearest_to_ray_dfs(BVHNearestRayData *data, BVHNode *node) +{ + if (node->totnode == 0) { + if (data->callback) { + data->callback(data->userdata, node->index, &data->ray, &data->nearest); + } + else { + const float dist_sq = calc_dist_sq_to_ray(data, node); + if (dist_sq != FLT_MAX) { /* not an invalid ray */ + data->nearest.index = node->index; + data->nearest.dist_sq = dist_sq; + /* TODO: return a value to the data->nearest.co + * not urgent however since users currently define own callbacks */ + } + } + } + else { + int i; + /* First pick the closest node to dive on */ + if (data->pick_smallest[node->main_axis]) { + for (i = 0; i != node->totnode; i++) { + if (calc_dist_sq_to_ray(data, node->children[i]) >= data->nearest.dist_sq) { + continue; + } + dfs_find_nearest_to_ray_dfs(data, node->children[i]); + } + } + else { + for (i = node->totnode - 1; i >= 0; i--) { + if (calc_dist_sq_to_ray(data, node->children[i]) >= data->nearest.dist_sq) { + continue; + } + dfs_find_nearest_to_ray_dfs(data, node->children[i]); + } + } + } +} + +int BLI_bvhtree_find_nearest_to_ray( + BVHTree *tree, const float co[3], const float dir[3], BVHTreeNearest *nearest, + BVHTree_NearestToRayCallback callback, void *userdata) +{ + BVHNearestRayData data; + BVHNode *root = tree->nodes[tree->totleaf]; + + data.tree = tree; + + data.callback = callback; + data.userdata = userdata; + + copy_v3_v3(data.ray.origin, co); + copy_v3_v3(data.ray.direction, dir); + data.ray.radius = 0.0f; /* unused here */ + + dist_squared_ray_to_aabb_v3_precalc(&data.nearest_precalc, co, dir); + + if (nearest) { + memcpy(&data.nearest, nearest, sizeof(*nearest)); + } + else { + data.nearest.index = -1; + data.nearest.dist_sq = FLT_MAX; + } + + /* dfs search */ + if (root) { + if (calc_dist_sq_to_ray(&data, root) < data.nearest.dist_sq) { + dfs_find_nearest_to_ray_dfs(&data, root); + } + } + + /* copy back results */ + if (nearest) { + memcpy(nearest, &data.nearest, sizeof(*nearest)); + } + + return data.nearest.index; +} + +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name BLI_bvhtree_range_query * - * Allocs and fills an array with the indexs of node that are on the given spherical range (center, radius) + * Allocs and fills an array with the indexs of node that are on the given spherical range (center, radius). * Returns the size of the array. - */ + * + * \{ */ + typedef struct RangeQueryData { BVHTree *tree; const float *center; @@ -1789,8 +1986,6 @@ typedef struct RangeQueryData { BVHTree_RangeQuery callback; void *userdata; - - } RangeQueryData; @@ -1814,7 +2009,7 @@ static void dfs_range_query(RangeQueryData *data, BVHNode *node) /* Its a leaf.. call the callback */ if (node->children[i]->totnode == 0) { data->hits++; - data->callback(data->userdata, node->children[i]->index, dist_sq); + data->callback(data->userdata, node->children[i]->index, data->center, dist_sq); } else dfs_range_query(data, node->children[i]); @@ -1823,7 +2018,9 @@ static void dfs_range_query(RangeQueryData *data, BVHNode *node) } } -int BLI_bvhtree_range_query(BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata) +int BLI_bvhtree_range_query( + BVHTree *tree, const float co[3], float radius, + BVHTree_RangeQuery callback, void *userdata) { BVHNode *root = tree->nodes[tree->totleaf]; @@ -1843,7 +2040,7 @@ int BLI_bvhtree_range_query(BVHTree *tree, const float co[3], float radius, BVHT /* Its a leaf.. call the callback */ if (root->totnode == 0) { data.hits++; - data.callback(data.userdata, root->index, dist_sq); + data.callback(data.userdata, root->index, co, dist_sq); } else dfs_range_query(&data, root); @@ -1852,3 +2049,84 @@ int BLI_bvhtree_range_query(BVHTree *tree, const float co[3], float radius, BVHT return data.hits; } + +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name BLI_bvhtree_walk_dfs + * \{ */ + +/** + * Runs first among nodes children of the first node before going to the next node in the same layer. + * + * \return false to break out of the search early. + */ +static bool bvhtree_walk_dfs_recursive( + BVHTree_WalkParentCallback walk_parent_cb, + BVHTree_WalkLeafCallback walk_leaf_cb, + BVHTree_WalkOrderCallback walk_order_cb, + const BVHNode *node, void *userdata) +{ + if (node->totnode == 0) { + return walk_leaf_cb((const BVHTreeAxisRange *)node->bv, node->index, userdata); + } + else { + /* First pick the closest node to recurse into */ + if (walk_order_cb((const BVHTreeAxisRange *)node->bv, node->main_axis, userdata)) { + for (int i = 0; i != node->totnode; i++) { + if (walk_parent_cb((const BVHTreeAxisRange *)node->children[i]->bv, userdata)) { + if (!bvhtree_walk_dfs_recursive( + walk_parent_cb, walk_leaf_cb, walk_order_cb, + node->children[i], userdata)) + { + return false; + } + } + } + } + else { + for (int i = node->totnode - 1; i >= 0; i--) { + if (walk_parent_cb((const BVHTreeAxisRange *)node->children[i]->bv, userdata)) { + if (!bvhtree_walk_dfs_recursive( + walk_parent_cb, walk_leaf_cb, walk_order_cb, + node->children[i], userdata)) + { + return false; + } + } + } + } + } + return true; +} + +/** + * This is a generic function to perform a depth first search on the BVHTree + * where the search order and nodes traversed depend on callbacks passed in. + * + * \param tree: Tree to walk. + * \param walk_parent_cb: Callback on a parents bound-box to test if it should be traversed. + * \param walk_leaf_cb: Callback to test leaf nodes, callback must store its own result, + * returning false exits early. + * \param walk_order_cb: Callback that indicates which direction to search, + * either from the node with the lower or higher k-dop axis value. + * \param userdata: Argument passed to all callbacks. + */ +void BLI_bvhtree_walk_dfs( + BVHTree *tree, + BVHTree_WalkParentCallback walk_parent_cb, + BVHTree_WalkLeafCallback walk_leaf_cb, + BVHTree_WalkOrderCallback walk_order_cb, void *userdata) +{ + const BVHNode *root = tree->nodes[tree->totleaf]; + if (root != NULL) { + /* first make sure the bv of root passes in the test too */ + if (walk_parent_cb((const BVHTreeAxisRange *)root->bv, userdata)) { + bvhtree_walk_dfs_recursive(walk_parent_cb, walk_leaf_cb, walk_order_cb, root, userdata); + } + } +} + +/** \} */ |