diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-08-20 10:32:25 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-08-20 10:52:26 +0300 |
commit | 176b806626ed62cb1bb9f609f927dc27e6e9c268 (patch) | |
tree | 7967f49985257e4b3ddd0a247157a2c46f0223ef /source/blender | |
parent | 67e32b31951b8b570148bd8b456afac27bb9645a (diff) |
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.
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenkernel/intern/collision.c | 8 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_kdopbvh.h | 9 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 140 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_intersect.c | 2 | ||||
-rw-r--r-- | source/blender/editors/mesh/editmesh_knife.c | 2 | ||||
-rw-r--r-- | source/blender/python/mathutils/mathutils_bvhtree.c | 72 |
6 files changed, 172 insertions, 61 deletions
diff --git a/source/blender/blenkernel/intern/collision.c b/source/blender/blenkernel/intern/collision.c index db3642ae183..d35762a6f13 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 9f16b02da33..6fc93ca9cdb 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 790a7879403..81d23a0692d 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 (j = 0; j < thread_num; j++) total += BLI_stack_count(data[j].overlap); to = overlap = MEM_mallocN(sizeof(BVHTreeOverlap) * total, "BVHTreeOverlap"); - for (j = 0; j < tree_type; j++) { + for (j = 0; j < thread_num; j++) { unsigned int count = (unsigned int)BLI_stack_count(data[j].overlap); BLI_stack_pop_n(data[j].overlap, to, count); BLI_stack_free(data[j].overlap); diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c index fc12bce8563..169ad49195c 100644 --- a/source/blender/bmesh/tools/bmesh_intersect.c +++ b/source/blender/bmesh/tools/bmesh_intersect.c @@ -885,7 +885,7 @@ bool BM_mesh_intersect( tree_b = tree_a; } - overlap = BLI_bvhtree_overlap(tree_b, tree_a, &tree_overlap_tot); + overlap = BLI_bvhtree_overlap(tree_b, tree_a, &tree_overlap_tot, NULL, NULL); if (overlap) { unsigned int i; diff --git a/source/blender/editors/mesh/editmesh_knife.c b/source/blender/editors/mesh/editmesh_knife.c index 930dba229d4..caafaf06e9e 100644 --- a/source/blender/editors/mesh/editmesh_knife.c +++ b/source/blender/editors/mesh/editmesh_knife.c @@ -1590,7 +1590,7 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd) BLI_bvhtree_insert(planetree, 0, plane_cos, 4); BLI_bvhtree_balance(planetree); - results = BLI_bvhtree_overlap(tree, planetree, &tot); + results = BLI_bvhtree_overlap(tree, planetree, &tot, NULL, NULL); if (!results) { BLI_bvhtree_free(planetree); return; diff --git a/source/blender/python/mathutils/mathutils_bvhtree.c b/source/blender/python/mathutils/mathutils_bvhtree.c index e74964481e6..a3b1d6d3e30 100644 --- a/source/blender/python/mathutils/mathutils_bvhtree.c +++ b/source/blender/python/mathutils/mathutils_bvhtree.c @@ -446,6 +446,24 @@ BLI_INLINE bool overlap_cmp(const void *a_v, const void *b_v) return (memcmp(a, b, sizeof(*a)) != 0); } +struct PyBVHTree_OverlapData { + PyBVHTree *tree_pair[2]; + float epsilon; +}; + +static bool py_bvhtree_overlap_cb(void *userdata, int index_a, int index_b, unsigned int UNUSED(thread)) +{ + struct PyBVHTree_OverlapData *data = userdata; + PyBVHTree *tree_a = data->tree_pair[0]; + PyBVHTree *tree_b = data->tree_pair[1]; + const unsigned int *tri_a = tree_a->tris[index_a]; + const unsigned int *tri_b = tree_b->tris[index_b]; + const float *tri_a_co[3] = {tree_a->coords[tri_a[0]], tree_a->coords[tri_a[1]], tree_a->coords[tri_a[2]]}; + const float *tri_b_co[3] = {tree_b->coords[tri_b[0]], tree_b->coords[tri_b[1]], tree_b->coords[tri_b[2]]}; + + return isect_tri_tri_epsilon_v3(UNPACK3(tri_a_co), UNPACK3(tri_b_co), NULL, NULL, data->epsilon); +} + PyDoc_STRVAR(py_bvhtree_overlap_doc, ".. method:: overlap(other_tree)\n" "\n" @@ -459,6 +477,7 @@ PyDoc_STRVAR(py_bvhtree_overlap_doc, ); static PyObject *py_bvhtree_overlap(PyBVHTree *self, PyBVHTree *other) { + struct PyBVHTree_OverlapData data; BVHTreeOverlap *overlap; unsigned int overlap_len = 0; PyObject *ret; @@ -468,7 +487,11 @@ static PyObject *py_bvhtree_overlap(PyBVHTree *self, PyBVHTree *other) return NULL; } - overlap = BLI_bvhtree_overlap(self->tree, other->tree, &overlap_len); + data.tree_pair[0] = self; + data.tree_pair[1] = other; + data.epsilon = max_ff(self->epsilon, other->epsilon); + + overlap = BLI_bvhtree_overlap(self->tree, other->tree, &overlap_len, py_bvhtree_overlap_cb, &data); ret = PyList_New(0); @@ -476,43 +499,34 @@ static PyObject *py_bvhtree_overlap(PyBVHTree *self, PyBVHTree *other) /* pass */ } else { - const float epsilon = max_ff(self->epsilon, other->epsilon); bool use_unique = (self->orig_index || other->orig_index); GSet *pair_test = use_unique ? BLI_gset_new_ex(overlap_hash, overlap_cmp, __func__, overlap_len) : NULL; /* simple case, no index remapping */ unsigned int i; for (i = 0; i < overlap_len; i++) { - const unsigned int *tri_a = self->tris[overlap[i].indexA]; - const unsigned int *tri_b = other->tris[overlap[i].indexB]; - const float *tri_a_co[3] = {self->coords[tri_a[0]], self->coords[tri_a[1]], self->coords[tri_a[2]]}; - const float *tri_b_co[3] = {other->coords[tri_b[0]], other->coords[tri_b[1]], other->coords[tri_b[2]]}; - - if (isect_tri_tri_epsilon_v3(UNPACK3(tri_a_co), UNPACK3(tri_b_co), NULL, NULL, epsilon)) { - PyObject *item; - - if (use_unique) { - if (self->orig_index) { - overlap[i].indexA = self->orig_index[overlap[i].indexA]; - } - if (other->orig_index) { - overlap[i].indexB = other->orig_index[overlap[i].indexB]; - } - - /* skip if its already added */ - if (!BLI_gset_add(pair_test, &overlap[i])) { - continue; - } + PyObject *item; + if (use_unique) { + if (self->orig_index) { + overlap[i].indexA = self->orig_index[overlap[i].indexA]; + } + if (other->orig_index) { + overlap[i].indexB = other->orig_index[overlap[i].indexB]; } - item = PyTuple_New(2); - PyTuple_SET_ITEMS(item, - PyLong_FromLong(overlap[i].indexA), - PyLong_FromLong(overlap[i].indexB)); - - PyList_Append(ret, item); - Py_DECREF(item); + /* skip if its already added */ + if (!BLI_gset_add(pair_test, &overlap[i])) { + continue; + } } + + item = PyTuple_New(2); + PyTuple_SET_ITEMS(item, + PyLong_FromLong(overlap[i].indexA), + PyLong_FromLong(overlap[i].indexB)); + + PyList_Append(ret, item); + Py_DECREF(item); } if (pair_test) { |