Speedups for finding cells in new boolean.

In case where there are coplanar instersections where
each part has a lot of triangles, the finding-cells algorithm was
very inefficient. This uses a Set instead of a Vector to keep track
of a cell's patches, avoids going through all patch x patch combinations,
avoids going through all patches to renumber after a merge, and
merges smaller patch-sixe cells into larger ones.
All this reduces the time to find cells in the cited case by a factor of 10.

1 files changed, 70 insertions, 27 deletions

diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc
index 403fe089ecb..f1510355160 100644
--- a/source/blender/blenlib/intern/mesh_boolean.cc
+++ b/source/blender/blenlib/intern/mesh_boolean.cc
@@ -371,6 +371,11 @@ class PatchesInfo {
   {
     return pp_edge_.lookup_default(std::pair<int, int>(p1, p2), Edge());
   }
+
+  const Map<std::pair<int, int>, Edge> &patch_patch_edge_map()
+  {
+    return pp_edge_;
+  }
 };
 
 static bool apply_bool_op(BoolOpType bool_optype, const Array<int> &winding);
@@ -381,7 +386,7 @@ static bool apply_bool_op(BoolOpType bool_optype, const Array<int> &winding);
  * One cell, the Ambient cell, contains all other cells.
  */
 class Cell {
-  Vector<int> patches_;
+  Set<int> patches_;
   Array<int> winding_;
   int merged_to_{NO_INDEX};
   bool winding_assigned_{false};
@@ -396,17 +401,31 @@ class Cell {
 
   void add_patch(int p)
   {
-    patches_.append(p);
+    patches_.add_new(p);
   }
 
   void add_patch_non_duplicates(int p)
   {
-    patches_.append_non_duplicates(p);
+    patches_.add(p);
   }
 
-  Span<int> patches() const
+  const Set<int> &patches() const
   {
-    return Span<int>(patches_);
+    return patches_;
+  }
+
+  /** In a set of 2, which is patch that is not p? */
+  int patch_other(int p) const
+  {
+    if (patches_.size() != 2) {
+      return NO_INDEX;
+    }
+    for (int pother : patches_) {
+      if (pother != p) {
+        return pother;
+      }
+    }
+    return NO_INDEX;
   }
 
   Span<int> winding() const
@@ -472,12 +491,16 @@ class Cell {
 
 static std::ostream &operator<<(std::ostream &os, const Cell &cell)
 {
-  os << "Cell patches " << cell.patches();
+  os << "Cell patches";
+  for (int p : cell.patches()) {
+    std::cout << " " << p;
+  }
   if (cell.winding().size() > 0) {
     os << " winding=" << cell.winding();
     os << " in_output_volume=" << cell.in_output_volume();
   }
   os << " zv=" << cell.zero_volume();
+  std::cout << "\n";
   return os;
 }
 
@@ -509,8 +532,19 @@ static bool tris_have_same_verts(const IMesh &mesh, int t1, int t2)
 void Cell::check_for_zero_volume(const PatchesInfo &pinfo, const IMesh &mesh)
 {
   if (patches_.size() == 2) {
-    const Patch &p1 = pinfo.patch(patches_[0]);
-    const Patch &p2 = pinfo.patch(patches_[1]);
+    int p1_index = NO_INDEX;
+    int p2_index = NO_INDEX;
+    for (int p : patches_) {
+      if (p1_index == NO_INDEX) {
+        p1_index = p;
+      }
+      else {
+        p2_index = p;
+      }
+    }
+    BLI_assert(p1_index != NO_INDEX && p2_index != NO_INDEX);
+    const Patch &p1 = pinfo.patch(p1_index);
+    const Patch &p2 = pinfo.patch(p2_index);
     if (p1.tot_tri() == 1 && p2.tot_tri() == 1) {
       if (tris_have_same_verts(mesh, p1.tri(0), p2.tri(0))) {
         zero_volume_ = true;
@@ -658,17 +692,16 @@ static void merge_cells(int merge_to, int merge_from, CellsInfo &cinfo, PatchesI
     final_merge_to = merge_to_cell.merged_to();
     merge_to_cell = cinfo.cell(final_merge_to);
   }
-  for (Patch &patch : pinfo) {
+  for (int cell_p : merge_from_cell.patches()) {
+    merge_to_cell.add_patch_non_duplicates(cell_p);
+    Patch &patch = pinfo.patch(cell_p);
     if (patch.cell_above == merge_from) {
-      patch.cell_above = final_merge_to;
+      patch.cell_above = merge_to;
     }
     if (patch.cell_below == merge_from) {
-      patch.cell_below = final_merge_to;
+      patch.cell_below = merge_to;
     }
   }
-  for (int cell_p : merge_from_cell.patches()) {
-    merge_to_cell.add_patch_non_duplicates(cell_p);
-  }
   merge_from_cell.set_merged_to(final_merge_to);
 }
 
@@ -1113,11 +1146,22 @@ static void find_cells_from_edge(const IMesh &tm,
     }
     else {
       if (*r_follow_cell != *rnext_prev_cell) {
+        int follow_cell_num_patches = cinfo.cell(*r_follow_cell).patches().size();
+        int prev_cell_num_patches = cinfo.cell(*rnext_prev_cell).patches().size();
+        if (follow_cell_num_patches >= prev_cell_num_patches) {
+          if (dbg_level > 0) {
+            std::cout << " merge cell " << *rnext_prev_cell << " into cell " << *r_follow_cell
+                      << "\n";
+          }
+          merge_cells(*r_follow_cell, *rnext_prev_cell, cinfo, pinfo);
+        }
+      }
+      else {
         if (dbg_level > 0) {
-          std::cout << " merge cell " << *rnext_prev_cell << " into cell " << *r_follow_cell
+          std::cout << " merge cell " << *r_follow_cell << " into cell " << *rnext_prev_cell
                     << "\n";
         }
-        merge_cells(*r_follow_cell, *rnext_prev_cell, cinfo, pinfo);
+        merge_cells(*rnext_prev_cell, *r_follow_cell, cinfo, pinfo);
       }
     }
   }
@@ -1136,15 +1180,14 @@ static CellsInfo find_cells(const IMesh &tm, const TriMeshTopology &tmtopo, Patc
   CellsInfo cinfo;
   /* For each unique edge shared between patch pairs, process it. */
   Set<Edge> processed_edges;
-  int np = pinfo.tot_patch();
-  for (int p = 0; p < np; ++p) {
-    for (int q = p + 1; q < np; ++q) {
-      Edge e = pinfo.patch_patch_edge(p, q);
-      if (e.v0() != nullptr) {
-        if (!processed_edges.contains(e)) {
-          processed_edges.add_new(e);
-          find_cells_from_edge(tm, tmtopo, pinfo, cinfo, e);
-        }
+  for (const auto item : pinfo.patch_patch_edge_map().items()) {
+    int p = item.key.first;
+    int q = item.key.second;
+    if (p < q) {
+      const Edge &e = item.value;
+      if (!processed_edges.contains(e)) {
+        processed_edges.add_new(e);
+        find_cells_from_edge(tm, tmtopo, pinfo, cinfo, e);
       }
     }
   }
@@ -2134,7 +2177,7 @@ static void extract_zero_volume_cell_tris(Vector<Face *> &r_tris,
     while (cell->zero_volume()) {
       /* In zero-volume cells, the cell should have exactly two patches. */
       BLI_assert(cell->patches().size() == 2);
-      int pother = cell->patches()[0] == pwalk ? cell->patches()[1] : cell->patches()[0];
+      int pother = cell->patch_other(pwalk);
       bool flip = pinfo.patch(pother).cell_above == c;
       flipped.append(flip);
       stack.append(pother);
@@ -2152,7 +2195,7 @@ static void extract_zero_volume_cell_tris(Vector<Face *> &r_tris,
     cell = &cinfo.cell(c);
     while (cell->zero_volume()) {
       BLI_assert(cell->patches().size() == 2);
-      int pother = cell->patches()[0] == pwalk ? cell->patches()[1] : cell->patches()[0];
+      int pother = cell->patch_other(pwalk);
       bool flip = pinfo.patch(pother).cell_below == c;
       flipped.append(flip);
       stack.append(pother);