Commit: d605a63cdc3ecc7c8efd73f72dab0cb8f606dcd7 Author: Alexander Gavrilov Date: Thu Dec 29 21:13:16 2022 +0200 Branches: temp-angavrilov https://developer.blender.org/rBd605a63cdc3ecc7c8efd73f72dab0cb8f606dcd7
BVH: recurse into the larger node in overlap computation. Currently the overlap computation code always recurses into the left node if possible, only entering the right one once the left is a leaf. This effectively tests every left leaf against the whole tree on the right. Similarly to the self overlap optimization it probably makes sense to recurse into children more evenly. An obvious heuristic is to compare the spatial dimensions of the nodes. To make sure it is up to date, recompute the main axis when updating the tree for a change of coordinates, and reorder children to match just in case (this matters for raycast). =================================================================== M source/blender/blenlib/intern/BLI_kdopbvh.c =================================================================== diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 174a53be6da..e8de19bb7c5 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -449,6 +449,15 @@ static void node_join(BVHTree *tree, BVHNode *node) break; } } + + /* Update the main axis and reorder children along it. + * The expectation is that the coordinates change slowly and thus + * no changes are required in most of the cases. */ + const char split_axis = get_largest_axis(node->bv); + + node->main_axis = split_axis / 2; + + bvh_insertionsort(node->children, 0, node->node_num, split_axis); } #ifdef USE_PRINT_TREE @@ -1091,6 +1100,13 @@ static bool tree_overlap_test(const BVHNode *node1, return 1; } +/** Dimension of the node along the main axis. */ +MINLINE float tree_node_main_dimension(const BVHNode *node) +{ + const float *bv = node->bv + (node->main_axis << 1); + return bv[1] - bv[0]; +} + static void tree_overlap_traverse(BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2) @@ -1122,6 +1138,14 @@ static void tree_overlap_traverse(BVHOverlapData_Thread *data_thread, } } } + else if (node2->node_num && + tree_node_main_dimension(node2) > tree_node_main_dimension(node1)) { + for (j = 0; j < data->tree2->tree_type; j++) { + if (node2->children[j]) { + tree_overlap_traverse(data_thread, node1, node2->children[j]); + } + } + } else { for (j = 0; j < data->tree1->tree_type; j++) { if (node1->children[j]) { @@ -1169,6 +1193,14 @@ static void tree_overlap_traverse_cb(BVHOverlapData_Thread *data_thread, } } } + else if (node2->node_num && + tree_node_main_dimension(node2) > tree_node_main_dimension(node1)) { + for (j = 0; j < data->tree2->tree_type; j++) { + if (node2->children[j]) { + tree_overlap_traverse_cb(data_thread, node1, node2->children[j]); + } + } + } else { for (j = 0; j < data->tree1->tree_type; j++) { if (node1->children[j]) { _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org List details, subscription details or unsubscribe: https://lists.blender.org/mailman/listinfo/bf-blender-cvs