From dc3a165ae0f22a4ff36bf9c7cc7fc189c351b35a Mon Sep 17 00:00:00 2001 From: mano-wii Date: Wed, 11 Dec 2019 22:21:24 -0300 Subject: BLI_bvhtree_overlap_ex: add 'max_interactions' parameter No functional changes. Allows more performance control and is important for Weld Modifier. --- source/blender/blenlib/BLI_kdopbvh.h | 4 +-- source/blender/blenlib/intern/BLI_kdopbvh.c | 41 ++++++++++++---------- source/blender/bmesh/tools/bmesh_intersect_edges.c | 2 +- 3 files changed, 26 insertions(+), 21 deletions(-) (limited to 'source/blender') 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); } /* -------------------------------------------------------------------- */ -- cgit v1.2.3