blender
/
blender
135
403
Fork 585
Code Issues 6.3k Pull Requests 760 Projects 19 Wiki Activity

BLI_bvhtree_overlap_ex: add 'max_interactions' parameter 

No functional changes.
Allows more performance control and is important for Weld Modifier.
This commit is contained in:
Germano Cavalcante 2019-12-11 22:21:24 -03:00
parent b03066f7ee
commit dc3a165ae0
3 changed files with 26 additions and 21 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

4
source/blender/blenlib/BLI_kdopbvh.h
View File

@ -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,

41
source/blender/blenlib/intern/BLI_kdopbvh.c
View File

@ -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);
}

2
source/blender/bmesh/tools/bmesh_intersect_edges.c
View File

@ -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);
}
/* -------------------------------------------------------------------- */