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.

1 files changed, 43 insertions, 29 deletions

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) {