[Bf-blender-cvs] [dc3a165ae0f] master: BLI_bvhtree_overlap_ex: add 'max_interactions' parameter
mano-wii
noreply at git.blender.org
Thu Dec 12 02:34:22 CET 2019
Commit: dc3a165ae0f22a4ff36bf9c7cc7fc189c351b35a
Author: mano-wii
Date: Wed Dec 11 22:21:24 2019 -0300
Branches: master
https://developer.blender.org/rBdc3a165ae0f22a4ff36bf9c7cc7fc189c351b35a
BLI_bvhtree_overlap_ex: add 'max_interactions' parameter
No functional changes.
Allows more performance control and is important for Weld Modifier.
===================================================================
M source/blender/blenlib/BLI_kdopbvh.h
M source/blender/blenlib/intern/BLI_kdopbvh.c
M source/blender/bmesh/tools/bmesh_intersect_edges.c
===================================================================
diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index b305e919e76..70fa633eeac 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -93,7 +93,6 @@ enum {
/* Use a priority queue to process nodes in the optimal order (for slow callbacks) */
BVH_OVERLAP_USE_THREADING = (1 << 0),
BVH_OVERLAP_RETURN_PAIRS = (1 << 1),
- BVH_OVERLAP_BREAK_ON_FIRST = (1 << 2),
};
enum {
/* Use a priority queue to process nodes in the optimal order (for slow callbacks) */
@@ -167,7 +166,8 @@ 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);
BVHTreeOverlap *BLI_bvhtree_overlap(const BVHTree *tree1,
const BVHTree *tree2,
unsigned int *r_overlap_tot,
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);
}
diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.c b/source/blender/bmesh/tools/bmesh_intersect_edges.c
index ffdcf179491..82e2151dc01 100644
--- a/source/blender/bmesh/tools/bmesh_intersect_edges.c
+++ b/source/blender/bmesh/tools/bmesh_intersect_edges.c
@@ -604,7 +604,7 @@ static void bvhtree_overlap_thread_safe(const BVHTree *tree1,
BVHTree_OverlapCallback callback,
void *userdata)
{
- BLI_bvhtree_overlap_ex(tree1, tree2, NULL, callback, userdata, BVH_OVERLAP_BREAK_ON_FIRST);
+ BLI_bvhtree_overlap_ex(tree1, tree2, NULL, callback, userdata, 1, 0);
}
/* -------------------------------------------------------------------- */
More information about the Bf-blender-cvs
mailing list