blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 747 Projects 19 Wiki Activity

BLI BVHTree Walk DFS: Decreases the size of the stack space used for the recursive function. 

Each parameter of the function is copied into the memory stack.
This also brought an improvement in peformance of snapping functions between 5% and 12% in my tests.
This commit is contained in:
Germano Cavalcante 2018-04-24 09:48:14 -03:00
parent f1e6838376
commit bb92d9a946
1 changed files with 17 additions and 17 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

34
source/blender/blenlib/intern/BLI_kdopbvh.c
View File

@ -2015,29 +2015,31 @@ int BLI_bvhtree_range_query(
/** \name BLI_bvhtree_walk_dfs
* \{ */
typedef struct BVHTree_WalkData {
BVHTree_WalkParentCallback walk_parent_cb;
BVHTree_WalkLeafCallback walk_leaf_cb;
BVHTree_WalkOrderCallback walk_order_cb;
void *userdata;
} BVHTree_WalkData;
/**
* 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)
BVHTree_WalkData *walk_data,
const BVHNode *node)
{
if (node->totnode == 0) {
return walk_leaf_cb((const BVHTreeAxisRange *)node->bv, node->index, userdata);
return walk_data->walk_leaf_cb((const BVHTreeAxisRange *)node->bv, node->index, walk_data->userdata);
}
else {
/* First pick the closest node to recurse into */
if (walk_order_cb((const BVHTreeAxisRange *)node->bv, node->main_axis, userdata)) {
if (walk_data->walk_order_cb((const BVHTreeAxisRange *)node->bv, node->main_axis, walk_data->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))
{
if (walk_data->walk_parent_cb((const BVHTreeAxisRange *)node->children[i]->bv, walk_data->userdata)) {
if (!bvhtree_walk_dfs_recursive(walk_data, node->children[i])) {
return false;
}
}
@ -2045,11 +2047,8 @@ static bool bvhtree_walk_dfs_recursive(
}
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))
{
if (walk_data->walk_parent_cb((const BVHTreeAxisRange *)node->children[i]->bv, walk_data->userdata)) {
if (!bvhtree_walk_dfs_recursive(walk_data, node->children[i])) {
return false;
}
}
@ -2079,9 +2078,10 @@ void BLI_bvhtree_walk_dfs(
{
const BVHNode *root = tree->nodes[tree->totleaf];
if (root != NULL) {
BVHTree_WalkData walk_data = {walk_parent_cb, walk_leaf_cb, walk_order_cb, userdata};
/* 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);
bvhtree_walk_dfs_recursive(&walk_data, root);
}
}
}