[Bf-blender-cvs] [176b806] master: BVH-overlap: add callback to BLI_bvhtree_overlap
Campbell Barton
noreply at git.blender.org
Thu Aug 20 09:57:32 CEST 2015
Commit: 176b806626ed62cb1bb9f609f927dc27e6e9c268
Author: Campbell Barton
Date: Thu Aug 20 17:32:25 2015 +1000
Branches: master
https://developer.blender.org/rB176b806626ed62cb1bb9f609f927dc27e6e9c268
BVH-overlap: add callback to BLI_bvhtree_overlap
The callback checks if 2 nodes intersect (not just their AABB).
Advantages:
- theres no need to allocate overlaps which are later ignored.
- expensive intersection tests will run multi-threaded.
Currently only used for Python API.
===================================================================
M source/blender/blenkernel/intern/collision.c
M source/blender/blenlib/BLI_kdopbvh.h
M source/blender/blenlib/intern/BLI_kdopbvh.c
M source/blender/bmesh/tools/bmesh_intersect.c
M source/blender/editors/mesh/editmesh_knife.c
M source/blender/python/mathutils/mathutils_bvhtree.c
===================================================================
diff --git a/source/blender/blenkernel/intern/collision.c b/source/blender/blenkernel/intern/collision.c
index db3642a..d35762a 100644
--- a/source/blender/blenkernel/intern/collision.c
+++ b/source/blender/blenkernel/intern/collision.c
@@ -723,7 +723,7 @@ int cloth_bvh_objcollision(Object *ob, ClothModifierData *clmd, float step, floa
continue;
/* search for overlapping collision pairs */
- overlap = BLI_bvhtree_overlap ( cloth_bvh, collmd->bvhtree, &result );
+ overlap = BLI_bvhtree_overlap(cloth_bvh, collmd->bvhtree, &result, NULL, NULL);
// go to next object if no overlap is there
if ( result && overlap ) {
@@ -785,7 +785,7 @@ int cloth_bvh_objcollision(Object *ob, ClothModifierData *clmd, float step, floa
if ( cloth->bvhselftree ) {
// search for overlapping collision pairs
- overlap = BLI_bvhtree_overlap ( cloth->bvhselftree, cloth->bvhselftree, &result );
+ overlap = BLI_bvhtree_overlap(cloth->bvhselftree, cloth->bvhselftree, &result, NULL, NULL);
// #pragma omp parallel for private(k, i, j) schedule(static)
for ( k = 0; k < result; k++ ) {
@@ -1248,7 +1248,7 @@ int cloth_points_objcollision(Object *ob, ClothModifierData *clmd, float step, f
continue;
/* search for overlapping collision pairs */
- overlap = BLI_bvhtree_overlap ( cloth_bvh, collmd->bvhtree, &result );
+ overlap = BLI_bvhtree_overlap(cloth_bvh, collmd->bvhtree, &result, NULL, NULL);
epsilon = BLI_bvhtree_getepsilon(collmd->bvhtree);
// go to next object if no overlap is there
@@ -1374,7 +1374,7 @@ void cloth_find_point_contacts(Object *ob, ClothModifierData *clmd, float step,
continue;
/* search for overlapping collision pairs */
- overlap = BLI_bvhtree_overlap(cloth_bvh, collmd->bvhtree, &result);
+ overlap = BLI_bvhtree_overlap(cloth_bvh, collmd->bvhtree, &result, NULL, NULL);
epsilon = BLI_bvhtree_getepsilon(collmd->bvhtree);
// go to next object if no overlap is there
diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index 9f16b02..6fc93ca 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -74,6 +74,9 @@ typedef void (*BVHTree_NearestPointCallback)(void *userdata, int index, const fl
/* callback must update hit in case it finds a nearest successful hit */
typedef void (*BVHTree_RayCastCallback)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit);
+/* callback to check if 2 nodes overlap (use thread if intersection results need to be stored) */
+typedef bool (*BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b, unsigned int thread);
+
/* callback to range search query */
typedef void (*BVHTree_RangeQuery)(void *userdata, int index, float dist_sq);
@@ -88,8 +91,12 @@ void BLI_bvhtree_balance(BVHTree *tree);
bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints);
void BLI_bvhtree_update_tree(BVHTree *tree);
+unsigned int BLI_bvhtree_overlap_thread_num(const BVHTree *tree);
+
/* collision/overlap: check two trees if they overlap, alloc's *overlap with length of the int return value */
-BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *r_overlap_tot);
+BVHTreeOverlap *BLI_bvhtree_overlap(
+ const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_tot,
+ BVHTree_OverlapCallback callback, void *userdata);
float BLI_bvhtree_getepsilon(const BVHTree *tree);
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 790a787..81d23a0 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -36,7 +36,7 @@
* - Nearest point on surface:
* #BLI_bvhtree_find_nearest, #BVHNearestData
* - Overlapping 2 trees:
- * #BLI_bvhtree_overlap, #BVHOverlapData
+ * #BLI_bvhtree_overlap, #BVHOverlapData_Shared, #BVHOverlapData_Thread
*/
#include <assert.h>
@@ -103,11 +103,22 @@ BLI_STATIC_ASSERT((sizeof(void *) == 8 && sizeof(BVHTree) <= 48) ||
(sizeof(void *) == 4 && sizeof(BVHTree) <= 32),
"over sized")
-typedef struct BVHOverlapData {
- BVHTree *tree1, *tree2;
- struct BLI_Stack *overlap; /* store BVHTreeOverlap */
+/* avoid duplicating vars in BVHOverlapData_Thread */
+typedef struct BVHOverlapData_Shared {
+ const BVHTree *tree1, *tree2;
axis_t start_axis, stop_axis;
-} BVHOverlapData;
+
+ /* use for callbacks */
+ BVHTree_OverlapCallback callback;
+ void *userdata;
+} BVHOverlapData_Shared;
+
+typedef struct BVHOverlapData_Thread {
+ BVHOverlapData_Shared *shared;
+ struct BLI_Stack *overlap; /* store BVHTreeOverlap */
+ /* use for callbacks */
+ unsigned int thread;
+} BVHOverlapData_Thread;
typedef struct BVHNearestData {
BVHTree *tree;
@@ -1059,8 +1070,11 @@ static bool tree_overlap_test(const BVHNode *node1, const BVHNode *node2, axis_t
return 1;
}
-static void tree_overlap_traverse(BVHOverlapData *data, const BVHNode *node1, const BVHNode *node2)
+static void tree_overlap_traverse(
+ BVHOverlapData_Thread *data_thread,
+ const BVHNode *node1, const BVHNode *node2)
{
+ BVHOverlapData_Shared *data = data_thread->shared;
int j;
if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) {
@@ -1075,34 +1089,96 @@ static void tree_overlap_traverse(BVHOverlapData *data, const BVHNode *node1, co
}
/* both leafs, insert overlap! */
- overlap = BLI_stack_push_r(data->overlap);
+ overlap = BLI_stack_push_r(data_thread->overlap);
overlap->indexA = node1->index;
overlap->indexB = node2->index;
}
else {
for (j = 0; j < data->tree2->tree_type; j++) {
- if (node2->children[j])
- tree_overlap_traverse(data, node1, node2->children[j]);
+ if (node2->children[j]) {
+ tree_overlap_traverse(data_thread, node1, node2->children[j]);
+ }
}
}
}
else {
for (j = 0; j < data->tree2->tree_type; j++) {
- if (node1->children[j])
- tree_overlap_traverse(data, node1->children[j], node2);
+ if (node1->children[j]) {
+ tree_overlap_traverse(data_thread, node1->children[j], node2);
+ }
}
}
}
- return;
}
-BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *r_overlap_tot)
+/**
+ * a version of #tree_overlap_traverse that runs a callback to check if the nodes really intersect.
+ */
+static void tree_overlap_traverse_cb(
+ BVHOverlapData_Thread *data_thread,
+ const BVHNode *node1, const BVHNode *node2)
{
- const unsigned int tree_type = (unsigned int)tree1->tree_type;
+ BVHOverlapData_Shared *data = data_thread->shared;
+ int j;
+
+ if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) {
+ /* check if node1 is a leaf */
+ if (!node1->totnode) {
+ /* check if node2 is a leaf */
+ if (!node2->totnode) {
+ BVHTreeOverlap *overlap;
+
+ if (UNLIKELY(node1 == node2)) {
+ return;
+ }
+
+ /* only difference to tree_overlap_traverse! */
+ if (data->callback(data->userdata, node1->index, node2->index, data_thread->thread)) {
+ /* both leafs, insert overlap! */
+ overlap = BLI_stack_push_r(data_thread->overlap);
+ overlap->indexA = node1->index;
+ overlap->indexB = node2->index;
+ }
+ }
+ else {
+ 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->tree2->tree_type; j++) {
+ if (node1->children[j]) {
+ tree_overlap_traverse_cb(data_thread, node1->children[j], node2);
+ }
+ }
+ }
+ }
+}
+
+/**
+ * Use to check the total number of threads #BLI_bvhtree_overlap will use.
+ *
+ * \warning Must be the first tree passed to #BLI_bvhtree_overlap!
+ */
+unsigned int BLI_bvhtree_overlap_thread_num(const BVHTree *tree)
+{
+ return (unsigned int)MIN2(tree->tree_type, tree->nodes[tree->totleaf]->totnode);
+}
+
+BVHTreeOverlap *BLI_bvhtree_overlap(
+ const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_tot,
+ /* optional callback to test the overlap before adding (must be thread-safe!) */
+ BVHTree_OverlapCallback callback, void *userdata)
+{
+ const unsigned int thread_num = BLI_bvhtree_overlap_thread_num(tree1);
unsigned int j;
size_t total = 0;
BVHTreeOverlap *overlap = NULL, *to = NULL;
- BVHOverlapData *data = BLI_array_alloca(data, tree_type);
+ BVHOverlapData_Shared data_shared;
+ BVHOverlapData_Thread *data = BLI_array_alloca(data, thread_num);
axis_t start_axis, stop_axis;
/* check for compatibility of both trees (can't compare 14-DOP with 18-DOP) */
@@ -1122,26 +1198,40 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int
return NULL;
}
- for (j = 0; j < tree_type; j++) {
- /* init BVHOverlapData */
- data[j].tree1 = tree1;
- data[j].tree2 = tree2;
+ data_shared.tree1 = tree1;
+ data_shared.tree2 = tree2;
+ data_shared.start_axis = start_axis;
+ data_shared.stop_axis = stop_axis;
+
+ /* can be NULL */
+ data_shared.callback = callback;
+ data_shared.userdata = userdata;
+
+ for (j = 0; j < thread_num; j++) {
+ /* init BVHOverlapData_Thread */
+ data[j].shared = &data_shared;
data[j].overlap = BLI_stack_new(sizeof(BVHTreeOverlap), __func__);
- data[j].start_axis = start_axis;
- data[j].stop_axis = stop_axis;
+
+ /* for callback */
+ data[j].thread = j;
}
#pragma omp parallel for private(j) schedule(static) if (tree1->totleaf > KDOPBVH_OMP_LIMIT)
- for (j = 0; j < MIN2(tree1->tree_type, tree1->nodes[tree1->totleaf]->totnode); j++) {
- tree_overlap_traverse(&data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]);
+ for (j = 0; j < thread_num; j++) {
+ if (callback) {
+ tree_overlap_traverse_cb(&data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]);
+ }
+ else {
+ tree_overlap_traverse(&data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]);
+ }
}
- for (j = 0; j < tree_type; j++)
+ for
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list