From a1556fa05ca96e43b70aa4f6b6284eb581701e4d Mon Sep 17 00:00:00 2001
From: Howard Trickey <howard.trickey@gmail.com>
Date: Sun, 30 May 2021 16:37:49 -0400
Subject: Boolean: applying patch D11431 to speed up hole-tolerant raycast.

This patch from Erik Abrahamsson uses a parallel_for to speed up
the case where the input is not manifold and the "hole_tolerant"
option is set.
In a test case on a 24 core (48 thread) machine, this sped up a
the boolean part on an object with 221k triangles from 12.06s to 0.46s.
---
 source/blender/blenlib/intern/mesh_boolean.cc | 88 ++++++++++++++++-----------
 1 file changed, 52 insertions(+), 36 deletions(-)

(limited to 'source/blender/blenlib')

diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc
index 25291b8c3b0..431720761bc 100644
--- a/source/blender/blenlib/intern/mesh_boolean.cc
+++ b/source/blender/blenlib/intern/mesh_boolean.cc
@@ -41,6 +41,7 @@
 #  include "BLI_set.hh"
 #  include "BLI_span.hh"
 #  include "BLI_stack.hh"
+#  include "BLI_task.hh"
 #  include "BLI_vector.hh"
 #  include "BLI_vector_set.hh"
 
@@ -48,6 +49,10 @@
 
 #  include "BLI_mesh_boolean.hh"
 
+#  ifdef WITH_TBB
+#    include "tbb/spin_mutex.h"
+#  endif
+
 // #  define PERFDEBUG
 
 namespace blender::meshintersect {
@@ -2567,47 +2572,58 @@ static IMesh raycast_tris_boolean(const IMesh &tm,
   BVHTree *tree = raycast_tree(tm);
   Vector<Face *> out_faces;
   out_faces.reserve(tm.face_size());
-  Array<float> in_shape(nshapes, 0);
-  Array<int> winding(nshapes, 0);
-  for (int t : tm.face_index_range()) {
-    Face &tri = *tm.face(t);
-    int shape = shape_fn(tri.orig);
-    if (dbg_level > 0) {
-      std::cout << "process triangle " << t << " = " << &tri << "\n";
-      std::cout << "shape = " << shape << "\n";
-    }
-    test_tri_inside_shapes(tm, shape_fn, nshapes, t, tree, in_shape);
-    for (int other_shape = 0; other_shape < nshapes; ++other_shape) {
-      if (other_shape == shape) {
-        continue;
-      }
-      /* The in_shape array has a confidence value for "insideness".
-       * For most operations, even a hint of being inside
-       * gives good results, but when shape is a cutter in a Difference
-       * operation, we want to be pretty sure that the point is inside other_shape.
-       * E.g., T75827.
-       * Also, when the operation is intersection, we also want high confidence.
-       */
-      bool need_high_confidence = (op == BoolOpType::Difference && shape != 0) ||
-                                  op == BoolOpType::Intersect;
-      bool inside = in_shape[other_shape] >= (need_high_confidence ? 0.5f : 0.1f);
+#  ifdef WITH_TBB
+  tbb::spin_mutex mtx;
+#  endif
+  const int grainsize = 256;
+  parallel_for(IndexRange(tm.face_size()), grainsize, [&](IndexRange range) {
+    Array<float> in_shape(nshapes, 0);
+    Array<int> winding(nshapes, 0);
+    for (int t : range) {
+      Face &tri = *tm.face(t);
+      int shape = shape_fn(tri.orig);
       if (dbg_level > 0) {
-        std::cout << "test point is " << (inside ? "inside" : "outside") << " other_shape "
-                  << other_shape << " val = " << in_shape[other_shape] << "\n";
+        std::cout << "process triangle " << t << " = " << &tri << "\n";
+        std::cout << "shape = " << shape << "\n";
       }
-      winding[other_shape] = inside;
-    }
-    bool do_flip;
-    bool do_remove = raycast_test_remove(op, winding, shape, &do_flip);
-    if (!do_remove) {
-      if (!do_flip) {
-        out_faces.append(&tri);
+      test_tri_inside_shapes(tm, shape_fn, nshapes, t, tree, in_shape);
+      for (int other_shape = 0; other_shape < nshapes; ++other_shape) {
+        if (other_shape == shape) {
+          continue;
+        }
+        /* The in_shape array has a confidence value for "insideness".
+         * For most operations, even a hint of being inside
+         * gives good results, but when shape is a cutter in a Difference
+         * operation, we want to be pretty sure that the point is inside other_shape.
+         * E.g., T75827.
+         * Also, when the operation is intersection, we also want high confidence.
+         */
+        bool need_high_confidence = (op == BoolOpType::Difference && shape != 0) ||
+                                    op == BoolOpType::Intersect;
+        bool inside = in_shape[other_shape] >= (need_high_confidence ? 0.5f : 0.1f);
+        if (dbg_level > 0) {
+          std::cout << "test point is " << (inside ? "inside" : "outside") << " other_shape "
+                    << other_shape << " val = " << in_shape[other_shape] << "\n";
+        }
+        winding[other_shape] = inside;
       }
-      else {
-        raycast_add_flipped(out_faces, tri, arena);
+      bool do_flip;
+      bool do_remove = raycast_test_remove(op, winding, shape, &do_flip);
+      {
+#  ifdef WITH_TBB
+        tbb::spin_mutex::scoped_lock lock(mtx);
+#  endif
+        if (!do_remove) {
+          if (!do_flip) {
+            out_faces.append(&tri);
+          }
+          else {
+            raycast_add_flipped(out_faces, tri, arena);
+          }
+        }
       }
     }
-  }
+  });
   BLI_bvhtree_free(tree);
   ans.set_faces(out_faces);
   return ans;
-- 
cgit v1.2.3