From 19c9b27ffe55470758637cfbfb11567611170388 Mon Sep 17 00:00:00 2001
From: Howard Trickey <howard.trickey@gmail.com>
Date: Sun, 30 Aug 2020 13:47:18 -0400
Subject: New boolean: another performance improvement.

Instead of calculating exact normals for all faces, just do it
for those that potentially intersect. A big improvement for dense
meshes that only intersect in relatively few places.
---
 source/blender/blenlib/intern/mesh_intersect.cc | 63 ++++++++++---------------
 1 file changed, 25 insertions(+), 38 deletions(-)

(limited to 'source/blender/blenlib/intern/mesh_intersect.cc')

diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index 39611953f37..f70f10ac708 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -48,7 +48,7 @@
 
 #  include "BLI_mesh_intersect.hh"
 
-//#  define PERFDEBUG
+// #  define PERFDEBUG
 
 namespace blender::meshintersect {
 
@@ -2402,6 +2402,7 @@ class TriOverlaps {
   BVHTree *tree_{nullptr};
   BVHTree *tree_b_{nullptr};
   BVHTreeOverlap *overlap_{nullptr};
+  Array<int> first_overlap_;
   uint overlap_tot_{0};
 
   struct CBData {
@@ -2458,12 +2459,8 @@ class TriOverlaps {
     }
     else {
       CBData cbdata{tm, shape_fn, nshapes, use_self};
-      if (nshapes == 1 && use_self) {
-        /* Expect a lot of trivial intersects from quads that are triangulated
-         * and faces that share vertices.
-         * Filter them out with a callback. */
-        overlap_ = BLI_bvhtree_overlap(
-            tree_, tree_, &overlap_tot_, only_nontrivial_intersects, &cbdata);
+      if (nshapes == 1) {
+        overlap_ = BLI_bvhtree_overlap(tree_, tree_, &overlap_tot_, NULL, NULL);
       }
       else {
         overlap_ = BLI_bvhtree_overlap(
@@ -2490,6 +2487,13 @@ class TriOverlaps {
         std::cout << "A: " << ov.indexA << ", B: " << ov.indexB << "\n";
       }
     }
+    first_overlap_ = Array<int>(tm.face_size(), -1);
+    for (int i = 0; i < static_cast<int>(overlap_tot_); ++i) {
+      int t = overlap_[i].indexA;
+      if (first_overlap_[t] == -1) {
+        first_overlap_[t] = i;
+      }
+    }
   }
 
   ~TriOverlaps()
@@ -2510,16 +2514,12 @@ class TriOverlaps {
     return Span<BVHTreeOverlap>(overlap_, overlap_tot_);
   }
 
- private:
-  static bool only_nontrivial_intersects(void *userdata,
-                                         int index_a,
-                                         int index_b,
-                                         int UNUSED(thread))
+  int first_overlap_index(int t) const
   {
-    CBData *cbdata = static_cast<CBData *>(userdata);
-    return may_non_trivially_intersect(cbdata->tm.face(index_a), cbdata->tm.face(index_b));
+    return first_overlap_[t];
   }
 
+ private:
   static bool only_different_shapes(void *userdata, int index_a, int index_b, int UNUSED(thread))
   {
     CBData *cbdata = static_cast<CBData *>(userdata);
@@ -2730,24 +2730,6 @@ static void calc_subdivided_tris(Array<IMesh> &r_tri_subdivided,
       0, overlap_tri_range_tot, &data, calc_subdivided_tri_range_func, &settings);
 }
 
-/* Get first index in ov where indexA == t. Assuming sorted on indexA. */
-static int find_first_overlap_index(const TriOverlaps &ov, int t)
-{
-  Span<BVHTreeOverlap> span = ov.overlap();
-  if (span.size() == 0) {
-    return -1;
-  }
-  BVHTreeOverlap bo{t, -1};
-  const BVHTreeOverlap *p = std::lower_bound(
-      span.begin(), span.end(), bo, [](const BVHTreeOverlap &o1, const BVHTreeOverlap &o2) {
-        return o1.indexA < o2.indexA;
-      });
-  if (p != span.end()) {
-    return p - span.begin();
-  }
-  return -1;
-}
-
 static CDT_data calc_cluster_subdivided(const CoplanarClusterInfo &clinfo,
                                         int c,
                                         const IMesh &tm,
@@ -2771,7 +2753,7 @@ static CDT_data calc_cluster_subdivided(const CoplanarClusterInfo &clinfo,
     if (dbg_level > 0) {
       std::cout << "find intersects with triangle " << t << " of cluster\n";
     }
-    int first_i = find_first_overlap_index(ov, t);
+    int first_i = ov.first_overlap_index(t);
     if (first_i == -1) {
       continue;
     }
@@ -3076,10 +3058,6 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in,
       std::cout << "cleaned input mesh:\n" << tm_cleaned;
     }
   }
-  /* Temporary, while developing: populate all plane normals exactly. */
-  for (Face *f : tm_clean->faces()) {
-    f->populate_plane(true);
-  }
 #  ifdef PERFDEBUG
   double clean_time = PIL_check_seconds_timer();
   std::cout << "cleaned, time = " << clean_time - start_time << "\n";
@@ -3093,6 +3071,15 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in,
 #  ifdef PERFDEBUG
   double overlap_time = PIL_check_seconds_timer();
   std::cout << "intersect overlaps calculated, time = " << overlap_time - bb_calc_time << "\n";
+#  endif
+  for (int t : tm_clean->face_index_range()) {
+    if (tri_ov.first_overlap_index(t) != -1) {
+      tm_clean->face(t)->populate_plane(true);
+    }
+  }
+#  ifdef PERFDEBUG
+  double plane_populate = PIL_check_seconds_timer();
+  std::cout << "planes populated, time = " << plane_populate - overlap_time << "\n";
 #  endif
   /* itt_map((a,b)) will hold the intersection value resulting from intersecting
    * triangles with indices a and b, where a < b. */
@@ -3101,7 +3088,7 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in,
   calc_overlap_itts(itt_map, *tm_clean, tri_ov, arena);
 #  ifdef PERFDEBUG
   double itt_time = PIL_check_seconds_timer();
-  std::cout << "itts found, time = " << itt_time - overlap_time << "\n";
+  std::cout << "itts found, time = " << itt_time - plane_populate << "\n";
 #  endif
   CoplanarClusterInfo clinfo = find_clusters(*tm_clean, tri_bb, itt_map);
   if (dbg_level > 1) {
-- 
cgit v1.2.3