diff options
author | Germano <germano.costa@ig.com.br> | 2018-04-24 15:48:14 +0300 |
---|---|---|
committer | Germano <germano.costa@ig.com.br> | 2018-04-24 15:48:14 +0300 |
commit | bb92d9a9466e4eb924d8be90ec5ddd4be2b70d95 (patch) | |
tree | c2a7db4e46fff9d16be5cafda35fef3b895b9ef7 /source/blender | |
parent | f1e6838376a0a07b5ce45d70ad18357c7c6cc2eb (diff) |
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.
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 34 |
1 files changed, 17 insertions, 17 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 06e8ade68a2..44ff78ea71a 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -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); } } } |