MeshAnalysis: Optimize the detection of intersecting geometry

For the self overlap result, each intersection pair does not need to
be tested twice.

3 files changed, 27 insertions, 1 deletions

diff --git a/source/blender/blenkernel/BKE_editmesh_bvh.h b/source/blender/blenkernel/BKE_editmesh_bvh.h
index 8f8e573ee2f..8c800ea9529 100644
--- a/source/blender/blenkernel/BKE_editmesh_bvh.h
+++ b/source/blender/blenkernel/BKE_editmesh_bvh.h
@@ -90,6 +90,9 @@ struct BVHTreeOverlap *BKE_bmbvh_overlap(const BMBVHTree *bmtree_a,
                                          const BMBVHTree *bmtree_b,
                                          unsigned int *r_overlap_tot);
 
+struct BVHTreeOverlap *BKE_bmbvh_overlap_self(const BMBVHTree *bmtree,
+                                         unsigned int *r_overlap_tot);
+
 /** #BKE_bmbvh_new flag parameter. */
 enum {
   /** Use with 'cos_cage', returns hits in relation to original geometry. */
diff --git a/source/blender/blenkernel/intern/editmesh_bvh.c b/source/blender/blenkernel/intern/editmesh_bvh.c
index a1e53a1f848..c4f855dd8c2 100644
--- a/source/blender/blenkernel/intern/editmesh_bvh.c
+++ b/source/blender/blenkernel/intern/editmesh_bvh.c
@@ -582,3 +582,26 @@ BVHTreeOverlap *BKE_bmbvh_overlap(const BMBVHTree *bmtree_a,
   return BLI_bvhtree_overlap(
       bmtree_a->tree, bmtree_b->tree, r_overlap_tot, bmbvh_overlap_cb, &data);
 }
+
+static bool bmbvh_overlap_self_cb(void *userdata, int index_a, int index_b, int thread)
+{
+  if (index_a < index_b) {
+    return bmbvh_overlap_cb(userdata, index_a, index_b, thread);
+  }
+  return false;
+}
+
+/**
+ * Overlap indices reference the looptri's
+ */
+BVHTreeOverlap *BKE_bmbvh_overlap_self(const BMBVHTree *bmtree, unsigned int *r_overlap_tot)
+{
+  struct BMBVHTree_OverlapData data;
+
+  data.tree_pair[0] = bmtree;
+  data.tree_pair[1] = bmtree;
+  data.epsilon = BLI_bvhtree_get_epsilon(bmtree->tree);
+
+  return BLI_bvhtree_overlap(
+      bmtree->tree, bmtree->tree, r_overlap_tot, bmbvh_overlap_self_cb, &data);
+}
diff --git a/source/blender/draw/intern/draw_cache_extract_mesh.c b/source/blender/draw/intern/draw_cache_extract_mesh.c
index 657cb2061bd..0d0fadee1a4 100644
--- a/source/blender/draw/intern/draw_cache_extract_mesh.c
+++ b/source/blender/draw/intern/draw_cache_extract_mesh.c
@@ -4268,7 +4268,7 @@ static void statvis_calc_intersect(const MeshRenderData *mr, float *r_intersect)
     BM_mesh_elem_index_ensure(bm, BM_FACE);
 
     struct BMBVHTree *bmtree = BKE_bmbvh_new_from_editmesh(em, 0, NULL, false);
-    BVHTreeOverlap *overlap = BKE_bmbvh_overlap(bmtree, bmtree, &overlap_len);
+    BVHTreeOverlap *overlap = BKE_bmbvh_overlap_self(bmtree, &overlap_len);
 
     if (overlap) {
       for (int i = 0; i < overlap_len; i++) {