[Bf-blender-cvs] [d605a63cdc3] temp-angavrilov: BVH: recurse into the larger node in overlap computation.

[Alexander Gavrilov]

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]) {