BLI_bvhtree_overlap_ex: add 'max_interactions' parameter

No functional changes.
Allows more performance control and is important for Weld Modifier.

1 files changed, 23 insertions, 18 deletions

diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index ae862c5ece5..71f276bc68f 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -122,6 +122,7 @@ typedef struct BVHOverlapData_Shared {
 typedef struct BVHOverlapData_Thread {
   BVHOverlapData_Shared *shared;
   struct BLI_Stack *overlap; /* store BVHTreeOverlap */
+  uint max_interactions;
   /* use for callbacks */
   int thread;
 } BVHOverlapData_Thread;
@@ -1186,9 +1187,9 @@ static void tree_overlap_traverse_cb(BVHOverlapData_Thread *data_thread,
 /**
  * a version of #tree_overlap_traverse_cb that that break on first true return.
  */
-static bool tree_overlap_traverse_first_cb(BVHOverlapData_Thread *data_thread,
-                                           const BVHNode *node1,
-                                           const BVHNode *node2)
+static bool tree_overlap_num_recursive(BVHOverlapData_Thread *data_thread,
+                                       const BVHNode *node1,
+                                       const BVHNode *node2)
 {
   BVHOverlapData_Shared *data = data_thread->shared;
   int j;
@@ -1213,20 +1214,23 @@ static bool tree_overlap_traverse_first_cb(BVHOverlapData_Thread *data_thread,
             overlap->indexA = node1->index;
             overlap->indexB = node2->index;
           }
-          return true;
+          return (--data_thread->max_interactions) == 0;
         }
       }
       else {
         for (j = 0; j < node2->totnode; j++) {
-          if (tree_overlap_traverse_first_cb(data_thread, node1, node2->children[j])) {
+          if (tree_overlap_num_recursive(data_thread, node1, node2->children[j])) {
             return true;
           }
         }
       }
     }
     else {
+      const uint max_interactions = data_thread->max_interactions;
       for (j = 0; j < node1->totnode; j++) {
-        tree_overlap_traverse_first_cb(data_thread, node1->children[j], node2);
+        if (tree_overlap_num_recursive(data_thread, node1->children[j], node2)) {
+          data_thread->max_interactions = max_interactions;
+        }
       }
     }
   }
@@ -1262,17 +1266,16 @@ static void bvhtree_overlap_task_cb(void *__restrict userdata,
   }
 }
 
-static void bvhtree_overlap_first_task_cb(void *__restrict userdata,
-                                          const int j,
-                                          const TaskParallelTLS *__restrict UNUSED(tls))
+static void bvhtree_overlap_num_task_cb(void *__restrict userdata,
+                                        const int j,
+                                        const TaskParallelTLS *__restrict UNUSED(tls))
 {
   BVHOverlapData_Thread *data = &((BVHOverlapData_Thread *)userdata)[j];
   BVHOverlapData_Shared *data_shared = data->shared;
 
-  tree_overlap_traverse_first_cb(
-      data,
-      data_shared->tree1->nodes[data_shared->tree1->totleaf]->children[j],
-      data_shared->tree2->nodes[data_shared->tree2->totleaf]);
+  tree_overlap_num_recursive(data,
+                             data_shared->tree1->nodes[data_shared->tree1->totleaf]->children[j],
+                             data_shared->tree2->nodes[data_shared->tree2->totleaf]);
 }
 
 BVHTreeOverlap *BLI_bvhtree_overlap_ex(
@@ -1282,14 +1285,14 @@ BVHTreeOverlap *BLI_bvhtree_overlap_ex(
     /* optional callback to test the overlap before adding (must be thread-safe!) */
     BVHTree_OverlapCallback callback,
     void *userdata,
-    int flag)
+    const uint max_interactions,
+    const int flag)
 {
   bool use_threading = (flag & BVH_OVERLAP_USE_THREADING) != 0;
   bool overlap_pairs = (flag & BVH_OVERLAP_RETURN_PAIRS) != 0;
-  bool break_on_first = (flag & BVH_OVERLAP_BREAK_ON_FIRST) != 0;
 
-  /* `RETURN_PAIRS` was not implemented without `BREAK_ON_FIRST`. */
-  BLI_assert(overlap_pairs || break_on_first);
+  /* `RETURN_PAIRS` was not implemented without `max_interations`. */
+  BLI_assert(overlap_pairs || max_interactions);
 
   const int thread_num = BLI_bvhtree_overlap_thread_num(tree1);
   int j;
@@ -1328,6 +1331,7 @@ BVHTreeOverlap *BLI_bvhtree_overlap_ex(
     /* init BVHOverlapData_Thread */
     data[j].shared = &data_shared;
     data[j].overlap = overlap_pairs ? BLI_stack_new(sizeof(BVHTreeOverlap), __func__) : NULL;
+    data[j].max_interactions = max_interactions;
 
     /* for callback */
     data[j].thread = j;
@@ -1339,7 +1343,7 @@ BVHTreeOverlap *BLI_bvhtree_overlap_ex(
   BLI_task_parallel_range(0,
                           thread_num,
                           data,
-                          break_on_first ? bvhtree_overlap_first_task_cb : bvhtree_overlap_task_cb,
+                          max_interactions ? bvhtree_overlap_num_task_cb : bvhtree_overlap_task_cb,
                           &settings);
 
   if (overlap_pairs) {
@@ -1374,6 +1378,7 @@ BVHTreeOverlap *BLI_bvhtree_overlap(
                                 r_overlap_tot,
                                 callback,
                                 userdata,
+                                0,
                                 BVH_OVERLAP_USE_THREADING | BVH_OVERLAP_RETURN_PAIRS);
 }