Speedup for usual non-manifold exact boolean case.

The commit rB6f63417b500d that made exact boolean work on meshes
with holes (like Suzanne) unfortunately dramatically slowed things
down on other non-manifold meshes that don't have holes and didn't
need the per-triangle insideness test.
This adds a hole_tolerant parameter, false by default, that the user
can enable to get good results on non-manifold meshes with holes.
Using false for this parameter speeds up the time from 90 seconds
to 10 seconds on an example with 1.2M triangles.

15 files changed, 289 insertions, 84 deletions

diff --git a/release/scripts/addons b/release/scripts/addons
-Subproject 24e756c0da89bdbf88dc22163ae3b7ef4f1fbb7
+Subproject 117faa96af35685d72e5e01f9a386d163d87413
diff --git a/source/blender/blenkernel/BKE_mesh_boolean_convert.h b/source/blender/blenkernel/BKE_mesh_boolean_convert.h
index be5cbb305fa..a87f2609e46 100644
--- a/source/blender/blenkernel/BKE_mesh_boolean_convert.h
+++ b/source/blender/blenkernel/BKE_mesh_boolean_convert.h
@@ -31,6 +31,7 @@ Mesh *BKE_mesh_boolean(const Mesh **meshes,
                        const float (*obmats[])[4][4],
                        const int meshes_len,
                        const bool use_self,
+                       const bool hole_tolerant,
                        const int boolean_mode);
 
 #ifdef __cplusplus
diff --git a/source/blender/blenkernel/intern/mesh_boolean_convert.cc b/source/blender/blenkernel/intern/mesh_boolean_convert.cc
index a179d39a9d2..61c9f74531d 100644
--- a/source/blender/blenkernel/intern/mesh_boolean_convert.cc
+++ b/source/blender/blenkernel/intern/mesh_boolean_convert.cc
@@ -762,6 +762,7 @@ static Mesh *imesh_to_mesh(IMesh *im, MeshesToIMeshInfo &mim)
 static Mesh *direct_mesh_boolean(Span<const Mesh *> meshes,
                                  Span<const float4x4 *> obmats,
                                  const bool use_self,
+                                 const bool hole_tolerant,
                                  const BoolOpType boolean_mode)
 {
   const int dbg_level = 0;
@@ -784,7 +785,8 @@ static Mesh *direct_mesh_boolean(Span<const Mesh *> meshes,
     }
     return static_cast<int>(mim.mesh_poly_offset.size()) - 1;
   };
-  IMesh m_out = boolean_mesh(m_in, boolean_mode, meshes_len, shape_fn, use_self, nullptr, &arena);
+  IMesh m_out = boolean_mesh(
+      m_in, boolean_mode, meshes_len, shape_fn, use_self, hole_tolerant, nullptr, &arena);
   if (dbg_level > 1) {
     std::cout << m_out;
     write_obj_mesh(m_out, "m_out");
@@ -808,6 +810,7 @@ Mesh *BKE_mesh_boolean(const Mesh **meshes,
                        const float (*obmats[])[4][4],
                        const int meshes_len,
                        const bool use_self,
+                       const bool hole_tolerant,
                        const int boolean_mode)
 {
   const blender::float4x4 **transforms = (const blender::float4x4 **)obmats;
@@ -815,6 +818,7 @@ Mesh *BKE_mesh_boolean(const Mesh **meshes,
       blender::Span(meshes, meshes_len),
       blender::Span(transforms, meshes_len),
       use_self,
+      hole_tolerant,
       static_cast<blender::meshintersect::BoolOpType>(boolean_mode));
 }
 
@@ -823,6 +827,7 @@ Mesh *BKE_mesh_boolean(const Mesh **UNUSED(meshes),
                        const float (*obmats[])[4][4],
                        const int UNUSED(meshes_len),
                        const bool UNUSED(use_self),
+                       const bool UNUSED(hole_tolerant),
                        const int UNUSED(boolean_mode))
 {
   UNUSED_VARS(obmats);
diff --git a/source/blender/blenlib/BLI_mesh_boolean.hh b/source/blender/blenlib/BLI_mesh_boolean.hh
index 94b2694893b..a55b2175527 100644
--- a/source/blender/blenlib/BLI_mesh_boolean.hh
+++ b/source/blender/blenlib/BLI_mesh_boolean.hh
@@ -59,6 +59,7 @@ IMesh boolean_mesh(IMesh &imesh,
                    int nshapes,
                    std::function<int(int)> shape_fn,
                    bool use_self,
+                   bool hole_tolerant,
                    IMesh *imesh_triangulated,
                    IMeshArena *arena);
 
@@ -72,6 +73,7 @@ IMesh boolean_trimesh(IMesh &tm_in,
                       int nshapes,
                       std::function<int(int)> shape_fn,
                       bool use_self,
+                      bool hole_tolerant,
                       IMeshArena *arena);
 
 }  // namespace blender::meshintersect
diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc
index 68d7ddec7ef..cd7d0a812e4 100644
--- a/source/blender/blenlib/intern/mesh_boolean.cc
+++ b/source/blender/blenlib/intern/mesh_boolean.cc
@@ -2484,29 +2484,14 @@ static void test_tri_inside_shapes(const IMesh &tm,
 }
 
 /**
- * Use the RayCast method for deciding if a triangle of the
- * mesh is supposed to be included or excluded in the boolean result,
- * and return the mesh that is the boolean result.
- * The reason this is done on a triangle-by-triangle basis is that
- * when the input is not PWN, some patches can be both inside and outside
- * some shapes (e.g., a plane cutting through Suzanne's open eyes).
+ * Return a BVH Tree that contains all of the triangles of \a tm.
+ * The caller must free it.
+ * (We could possible reuse the BVH tree(s) built in TriOverlaps,
+ * in the mesh intersect function. A future TODO.)
  */
-static IMesh raycast_boolean(const IMesh &tm,
-                             BoolOpType op,
-                             int nshapes,
-                             std::function<int(int)> shape_fn,
-                             IMeshArena *arena)
+static BVHTree *raycast_tree(const IMesh &tm)
 {
-  constexpr int dbg_level = 0;
-  if (dbg_level > 0) {
-    std::cout << "RAYCAST_BOOLEAN\n";
-  }
-  IMesh ans;
-
-  /* Build a BVH tree of tm's triangles.
-   * We could possibly reuse the BVH tree(s) build in TriOverlaps in
-   * the mesh intersect function. A future TODO. */
-  BVHTree *tree = BLI_bvhtree_new(tm.face_size(), FLT_EPSILON, 8, 8);
+  BVHTree *tree = BLI_bvhtree_new(tm.face_size(), FLT_EPSILON, 4, 6);
   for (int i : tm.face_index_range()) {
     const Face *f = tm.face(i);
     float t_cos[9];
@@ -2519,7 +2504,70 @@ static IMesh raycast_boolean(const IMesh &tm,
     BLI_bvhtree_insert(tree, i, t_cos, 3);
   }
   BLI_bvhtree_balance(tree);
+  return tree;
+}
+
+/**
+ * Should a face with given shape and given winding array be removed for given boolean op?
+ * Also return true in *r_do_flip if it retained by normals need to be flipped.
+ */
+static bool raycast_test_remove(BoolOpType op, Array<int> &winding, int shape, bool *r_do_flip)
+{
+  constexpr int dbg_level = 0;
+  /* Find out the "in the output volume" flag for each of the cases of winding[shape] == 0
+   * and winding[shape] == 1. If the flags are different, this patch should be in the output.
+   * Also, if this is a Difference and the shape isn't the first one, need to flip the normals.
+   */
+  winding[shape] = 0;
+  bool in_output_volume_0 = apply_bool_op(op, winding);
+  winding[shape] = 1;
+  bool in_output_volume_1 = apply_bool_op(op, winding);
+  bool do_remove = in_output_volume_0 == in_output_volume_1;
+  bool do_flip = !do_remove && op == BoolOpType::Difference && shape != 0;
+  if (dbg_level > 0) {
+    std::cout << "winding = ";
+    for (int i = 0; i < winding.size(); ++i) {
+      std::cout << winding[i] << " ";
+    }
+    std::cout << "\niv0=" << in_output_volume_0 << ", iv1=" << in_output_volume_1 << "\n";
+    std::cout << " remove=" << do_remove << ", flip=" << do_flip << "\n";
+  }
+  *r_do_flip = do_flip;
+  return do_remove;
+}
 
+/** Add triangle a flipped version of tri to out_faces. */
+static void raycast_add_flipped(Vector<Face *> &out_faces, Face &tri, IMeshArena *arena)
+{
+
+  Array<const Vert *> flipped_vs = {tri[0], tri[2], tri[1]};
+  Array<int> flipped_e_origs = {tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]};
+  Array<bool> flipped_is_intersect = {
+      tri.is_intersect[2], tri.is_intersect[1], tri.is_intersect[0]};
+  Face *flipped_f = arena->add_face(flipped_vs, tri.orig, flipped_e_origs, flipped_is_intersect);
+  out_faces.append(flipped_f);
+}
+
+/**
+ * Use the RayCast method for deciding if a triangle of the
+ * mesh is supposed to be included or excluded in the boolean result,
+ * and return the mesh that is the boolean result.
+ * The reason this is done on a triangle-by-triangle basis is that
+ * when the input is not PWN, some patches can be both inside and outside
+ * some shapes (e.g., a plane cutting through Suzanne's open eyes).
+ */
+static IMesh raycast_tris_boolean(const IMesh &tm,
+                                  BoolOpType op,
+                                  int nshapes,
+                                  std::function<int(int)> shape_fn,
+                                  IMeshArena *arena)
+{
+  constexpr int dbg_level = 0;
+  if (dbg_level > 0) {
+    std::cout << "RAYCAST_TRIS_BOOLEAN\n";
+  }
+  IMesh ans;
+  BVHTree *tree = raycast_tree(tm);
   Vector<Face *> out_faces;
   out_faces.reserve(tm.face_size());
   Array<float> in_shape(nshapes, 0);
@@ -2541,6 +2589,7 @@ static IMesh raycast_boolean(const IMesh &tm,
        * 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;
@@ -2551,38 +2600,84 @@ static IMesh raycast_boolean(const IMesh &tm,
       }
       winding[other_shape] = inside;
     }
-    /* Find out the "in the output volume" flag for each of the cases of winding[shape] == 0
-     * and winding[shape] == 1. If the flags are different, this patch should be in the output.
-     * Also, if this is a Difference and the shape isn't the first one, need to flip the normals.
-     */
-    winding[shape] = 0;
-    bool in_output_volume_0 = apply_bool_op(op, winding);
-    winding[shape] = 1;
-    bool in_output_volume_1 = apply_bool_op(op, winding);
-    bool do_remove = in_output_volume_0 == in_output_volume_1;
-    bool do_flip = !do_remove && op == BoolOpType::Difference && shape != 0;
-    if (dbg_level > 0) {
-      std::cout << "winding = ";
-      for (int i = 0; i < nshapes; ++i) {
-        std::cout << winding[i] << " ";
-      }
-      std::cout << "\niv0=" << in_output_volume_0 << ", iv1=" << in_output_volume_1 << "\n";
-      std::cout << "result for tri " << t << ": remove=" << do_remove << ", flip=" << do_flip
-                << "\n";
-    }
+    bool do_flip;
+    bool do_remove = raycast_test_remove(op, winding, shape, &do_flip);
     if (!do_remove) {
       if (!do_flip) {
         out_faces.append(&tri);
       }
       else {
-        /* We need flipped version of tri. */
-        Array<const Vert *> flipped_vs = {tri[0], tri[2], tri[1]};
-        Array<int> flipped_e_origs = {tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]};
-        Array<bool> flipped_is_intersect = {
-            tri.is_intersect[2], tri.is_intersect[1], tri.is_intersect[0]};
-        Face *flipped_f = arena->add_face(
-            flipped_vs, tri.orig, flipped_e_origs, flipped_is_intersect);
-        out_faces.append(flipped_f);
+        raycast_add_flipped(out_faces, tri, arena);
+      }
+    }
+  }
+  BLI_bvhtree_free(tree);
+  ans.set_faces(out_faces);
+  return ans;
+}
+
+/* This is (sometimes much faster) version of raycast boolean
+ * that does it per patch rather than per triangle.
+ * It may fail in cases where raycast_tri_boolean will succeed,
+ * but the latter can be very slow on huge meshes. */
+static IMesh raycast_patches_boolean(const IMesh &tm,
+                                     BoolOpType op,
+                                     int nshapes,
+                                     std::function<int(int)> shape_fn,
+                                     const PatchesInfo &pinfo,
+                                     IMeshArena *arena)
+{
+  constexpr int dbg_level = 0;
+  if (dbg_level > 0) {
+    std::cout << "RAYCAST_PATCHES_BOOLEAN\n";
+  }
+  IMesh ans;
+  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 p : pinfo.index_range()) {
+    const Patch &patch = pinfo.patch(p);
+    /* For test triangle, choose one in the middle of patch list
+     * as the ones near the beginning may be very near other patches. */
+    int test_t_index = patch.tri(patch.tot_tri() / 2);
+    Face &tri_test = *tm.face(test_t_index);
+    /* Assume all triangles in a patch are in the same shape. */
+    int shape = shape_fn(tri_test.orig);
+    if (dbg_level > 0) {
+      std::cout << "process patch " << p << " = " << patch << "\n";
+      std::cout << "test tri = " << test_t_index << " = " << &tri_test << "\n";
+      std::cout << "shape = " << shape << "\n";
+    }
+    if (shape == -1) {
+      continue;
+    }
+    test_tri_inside_shapes(tm, shape_fn, nshapes, test_t_index, tree, in_shape);
+    for (int other_shape = 0; other_shape < nshapes; ++other_shape) {
+      if (other_shape == shape) {
+        continue;
+      }
+      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;
+    }
+    bool do_flip;
+    bool do_remove = raycast_test_remove(op, winding, shape, &do_flip);
+    if (!do_remove) {
+      for (int t : patch.tris()) {
+        Face *f = tm.face(t);
+        if (!do_flip) {
+          out_faces.append(f);
+        }
+        else {
+          raycast_add_flipped(out_faces, *f, arena);
+        }
       }
     }
   }
@@ -3342,6 +3437,7 @@ IMesh boolean_trimesh(IMesh &tm_in,
                       int nshapes,
                       std::function<int(int)> shape_fn,
                       bool use_self,
+                      bool hole_tolerant,
                       IMeshArena *arena)
 {
   constexpr int dbg_level = 0;
@@ -3392,7 +3488,13 @@ IMesh boolean_trimesh(IMesh &tm_in,
     if (dbg_level > 0) {
       std::cout << "Input is not PWN, using raycast method\n";
     }
-    tm_out = raycast_boolean(tm_si, op, nshapes, shape_fn, arena);
+    if (hole_tolerant) {
+      tm_out = raycast_tris_boolean(tm_si, op, nshapes, shape_fn, arena);
+    }
+    else {
+      PatchesInfo pinfo = find_patches(tm_si, tm_si_topo);
+      tm_out = raycast_patches_boolean(tm_si, op, nshapes, shape_fn, pinfo, arena);
+    }
 #  ifdef PERFDEBUG
     double raycast_time = PIL_check_seconds_timer();
     std::cout << "  raycast_boolean done, time = " << raycast_time - pwn_time << "\n";
@@ -3487,6 +3589,7 @@ IMesh boolean_mesh(IMesh &imesh,
                    int nshapes,
                    std::function<int(int)> shape_fn,
                    bool use_self,
+                   bool hole_tolerant,
                    IMesh *imesh_triangulated,
                    IMeshArena *arena)
 {
@@ -3520,7 +3623,7 @@ IMesh boolean_mesh(IMesh &imesh,
   if (dbg_level > 1) {
     write_obj_mesh(*tm_in, "boolean_tm_in");
   }
-  IMesh tm_out = boolean_trimesh(*tm_in, op, nshapes, shape_fn, use_self, arena);
+  IMesh tm_out = boolean_trimesh(*tm_in, op, nshapes, shape_fn, use_self, hole_tolerant, arena);
 #  ifdef PERFDEBUG
   double bool_tri_time = PIL_check_seconds_timer();
   std::cout << "boolean_trimesh done, time = " << bool_tri_time - tri_time << "\n";
diff --git a/source/blender/blenlib/tests/BLI_mesh_boolean_test.cc b/source/blender/blenlib/tests/BLI_mesh_boolean_test.cc
index e503ef8f264..d759f0c3be4 100644
--- a/source/blender/blenlib/tests/BLI_mesh_boolean_test.cc
+++ b/source/blender/blenlib/tests/BLI_mesh_boolean_test.cc
@@ -113,7 +113,7 @@ TEST(boolean_trimesh, Empty)
 {
   IMeshArena arena;
   IMesh in;
-  IMesh out = boolean_trimesh(in, BoolOpType::None, 1, all_shape_zero, true, &arena);
+  IMesh out = boolean_trimesh(in, BoolOpType::None, 1, all_shape_zero, true, false, &arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 0);
   EXPECT_EQ(out.face_size(), 0);
@@ -141,7 +141,8 @@ TEST(boolean_trimesh, TetTetTrimesh)
   )";
 
   IMeshBuilder mb(spec);
-  IMesh out = boolean_trimesh(mb.imesh, BoolOpType::None, 1, all_shape_zero, true, &mb.arena);
+  IMesh out = boolean_trimesh(
+      mb.imesh, BoolOpType::None, 1, all_shape_zero, true, false, &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 11);
   EXPECT_EQ(out.face_size(), 20);
@@ -150,7 +151,8 @@ TEST(boolean_trimesh, TetTetTrimesh)
   }
 
   IMeshBuilder mb2(spec);
-  IMesh out2 = boolean_trimesh(mb2.imesh, BoolOpType::Union, 1, all_shape_zero, true, &mb2.arena);
+  IMesh out2 = boolean_trimesh(
+      mb2.imesh, BoolOpType::Union, 1, all_shape_zero, true, false, &mb2.arena);
   out2.populate_vert();
   EXPECT_EQ(out2.vert_size(), 10);
   EXPECT_EQ(out2.face_size(), 16);
@@ -160,7 +162,13 @@ TEST(boolean_trimesh, TetTetTrimesh)
 
   IMeshBuilder mb3(spec);
   IMesh out3 = boolean_trimesh(
-      mb3.imesh, BoolOpType::Union, 2, [](int t) { return t < 4 ? 0 : 1; }, false, &mb3.arena);
+      mb3.imesh,
+      BoolOpType::Union,
+      2,
+      [](int t) { return t < 4 ? 0 : 1; },
+      false,
+      false,
+      &mb3.arena);
   out3.populate_vert();
   EXPECT_EQ(out3.vert_size(), 10);
   EXPECT_EQ(out3.face_size(), 16);
@@ -170,7 +178,13 @@ TEST(boolean_trimesh, TetTetTrimesh)
 
   IMeshBuilder mb4(spec);
   IMesh out4 = boolean_trimesh(
-      mb4.imesh, BoolOpType::Union, 2, [](int t) { return t < 4 ? 0 : 1; }, true, &mb4.arena);
+      mb4.imesh,
+      BoolOpType::Union,
+      2,
+      [](int t) { return t < 4 ? 0 : 1; },
+      true,
+      false,
+      &mb4.arena);
   out4.populate_vert();
   EXPECT_EQ(out4.vert_size(), 10);
   EXPECT_EQ(out4.face_size(), 16);
@@ -180,7 +194,13 @@ TEST(boolean_trimesh, TetTetTrimesh)
 
   IMeshBuilder mb5(spec);
   IMesh out5 = boolean_trimesh(
-      mb5.imesh, BoolOpType::Intersect, 2, [](int t) { return t < 4 ? 0 : 1; }, false, &mb5.arena);
+      mb5.imesh,
+      BoolOpType::Intersect,
+      2,
+      [](int t) { return t < 4 ? 0 : 1; },
+      false,
+      false,
+      &mb5.arena);
   out5.populate_vert();
   EXPECT_EQ(out5.vert_size(), 4);
   EXPECT_EQ(out5.face_size(), 4);
@@ -195,6 +215,7 @@ TEST(boolean_trimesh, TetTetTrimesh)
       2,
       [](int t) { return t < 4 ? 0 : 1; },
       false,
+      false,
       &mb6.arena);
   out6.populate_vert();
   EXPECT_EQ(out6.vert_size(), 6);
@@ -210,6 +231,7 @@ TEST(boolean_trimesh, TetTetTrimesh)
       2,
       [](int t) { return t < 4 ? 1 : 0; },
       false,
+      false,
       &mb7.arena);
   out7.populate_vert();
   EXPECT_EQ(out7.vert_size(), 8);
@@ -241,7 +263,8 @@ TEST(boolean_trimesh, TetTet2Trimesh)
   )";
 
   IMeshBuilder mb(spec);
-  IMesh out = boolean_trimesh(mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, &mb.arena);
+  IMesh out = boolean_trimesh(
+      mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, false, &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 10);
   EXPECT_EQ(out.face_size(), 16);
@@ -284,7 +307,8 @@ TEST(boolean_trimesh, CubeTetTrimesh)
   )";
 
   IMeshBuilder mb(spec);
-  IMesh out = boolean_trimesh(mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, &mb.arena);
+  IMesh out = boolean_trimesh(
+      mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, false, &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 14);
   EXPECT_EQ(out.face_size(), 24);
@@ -316,7 +340,13 @@ TEST(boolean_trimesh, BinaryTetTetTrimesh)
 
   IMeshBuilder mb(spec);
   IMesh out = boolean_trimesh(
-      mb.imesh, BoolOpType::Intersect, 2, [](int t) { return t < 4 ? 0 : 1; }, false, &mb.arena);
+      mb.imesh,
+      BoolOpType::Intersect,
+      2,
+      [](int t) { return t < 4 ? 0 : 1; },
+      false,
+      false,
+      &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 4);
   EXPECT_EQ(out.face_size(), 4);
@@ -347,7 +377,8 @@ TEST(boolean_trimesh, TetTetCoplanarTrimesh)
   )";
 
   IMeshBuilder mb(spec);
-  IMesh out = boolean_trimesh(mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, &mb.arena);
+  IMesh out = boolean_trimesh(
+      mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, false, &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 5);
   EXPECT_EQ(out.face_size(), 6);
@@ -378,7 +409,8 @@ TEST(boolean_trimesh, TetInsideTetTrimesh)
   )";
 
   IMeshBuilder mb(spec);
-  IMesh out = boolean_trimesh(mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, &mb.arena);
+  IMesh out = boolean_trimesh(
+      mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, false, &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 4);
   EXPECT_EQ(out.face_size(), 4);
@@ -409,7 +441,8 @@ TEST(boolean_trimesh, TetBesideTetTrimesh)
   )";
 
   IMeshBuilder mb(spec);
-  IMesh out = boolean_trimesh(mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, &mb.arena);
+  IMesh out = boolean_trimesh(
+      mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, false, &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 8);
   EXPECT_EQ(out.face_size(), 8);
@@ -445,7 +478,13 @@ TEST(boolean_trimesh, DegenerateTris)
 
   IMeshBuilder mb(spec);
   IMesh out = boolean_trimesh(
-      mb.imesh, BoolOpType::Intersect, 2, [](int t) { return t < 5 ? 0 : 1; }, false, &mb.arena);
+      mb.imesh,
+      BoolOpType::Intersect,
+      2,
+      [](int t) { return t < 5 ? 0 : 1; },
+      false,
+      false,
+      &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 4);
   EXPECT_EQ(out.face_size(), 4);
@@ -477,7 +516,7 @@ TEST(boolean_polymesh, TetTet)
 
   IMeshBuilder mb(spec);
   IMesh out = boolean_mesh(
-      mb.imesh, BoolOpType::None, 1, all_shape_zero, true, nullptr, &mb.arena);
+      mb.imesh, BoolOpType::None, 1, all_shape_zero, true, false, nullptr, &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 11);
   EXPECT_EQ(out.face_size(), 13);
@@ -492,6 +531,7 @@ TEST(boolean_polymesh, TetTet)
       2,
       [](int t) { return t < 4 ? 0 : 1; },
       false,
+      false,
       nullptr,
       &mb2.arena);
   out2.populate_vert();
@@ -540,7 +580,7 @@ TEST(boolean_polymesh, CubeCube)
     write_obj_mesh(mb.imesh, "cube_cube_in");
   }
   IMesh out = boolean_mesh(
-      mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, nullptr, &mb.arena);
+      mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, false, nullptr, &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 20);
   EXPECT_EQ(out.face_size(), 12);
@@ -555,6 +595,7 @@ TEST(boolean_polymesh, CubeCube)
       2,
       [](int t) { return t < 6 ? 0 : 1; },
       false,
+      false,
       nullptr,
       &mb2.arena);
   out2.populate_vert();
@@ -597,7 +638,7 @@ TEST(boolean_polymesh, CubeCone)
 
   IMeshBuilder mb(spec);
   IMesh out = boolean_mesh(
-      mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, nullptr, &mb.arena);
+      mb.imesh, BoolOpType::Union, 1, all_shape_zero, true, false, nullptr, &mb.arena);
   out.populate_vert();
   EXPECT_EQ(out.vert_size(), 14);
   EXPECT_EQ(out.face_size(), 12);
@@ -646,6 +687,7 @@ TEST(boolean_polymesh, CubeCubeCoplanar)
       2,
       [](int t) { return t < 6 ? 0 : 1; },
       false,
+      false,
       nullptr,
       &mb.arena);
   out.populate_vert();
@@ -684,6 +726,7 @@ TEST(boolean_polymesh, TetTeTCoplanarDiff)
       2,
       [](int t) { return t < 4 ? 0 : 1; },
       false,
+      false,
       nullptr,
       &mb.arena);
   out.populate_vert();
@@ -734,6 +777,7 @@ TEST(boolean_polymesh, CubeCubeStep)
       2,
       [](int t) { return t < 6 ? 0 : 1; },
       false,
+      false,
       nullptr,
       &mb.arena);
   out.populate_vert();
@@ -784,6 +828,7 @@ TEST(boolean_polymesh, CubeCyl4)
       2,
       [](int t) { return t < 6 ? 1 : 0; },
       false,
+      false,
       nullptr,
       &mb.arena);
   out.populate_vert();
@@ -855,6 +900,7 @@ TEST(boolean_polymesh, CubeCubesubdivDiff)
       2,
       [](int t) { return t < 16 ? 1 : 0; },
       false,
+      false,
       nullptr,
       &mb.arena);
   out.populate_vert();
@@ -896,6 +942,7 @@ TEST(boolean_polymesh, CubePlane)
       2,
       [](int t) { return t >= 1 ? 0 : 1; },
       false,
+      false,
       nullptr,
       &mb.arena);
   out.populate_vert();
diff --git a/source/blender/bmesh/tools/bmesh_boolean.cc b/source/blender/bmesh/tools/bmesh_boolean.cc
index ea5d66e195c..fec33a04e6f 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.cc
+++ b/source/blender/bmesh/tools/bmesh_boolean.cc
@@ -354,6 +354,7 @@ static bool bmesh_boolean(BMesh *bm,
                           const bool use_self,
                           const bool use_separate_all,
                           const bool keep_hidden,
+                          const bool hole_tolerant,
                           const BoolOpType boolean_mode)
 {
   IMeshArena arena;
@@ -389,7 +390,7 @@ static bool bmesh_boolean(BMesh *bm,
     };
   }
   IMesh m_out = boolean_mesh(
-      m_in, boolean_mode, nshapes, shape_fn, use_self, &m_triangulated, &arena);
+      m_in, boolean_mode, nshapes, shape_fn, use_self, hole_tolerant, &m_triangulated, &arena);
 #  ifdef PERF_DEBUG
   double boolean_time = PIL_check_seconds_timer();
   std::cout << "boolean done, time = " << boolean_time - mesh_time << "\n";
@@ -437,6 +438,7 @@ bool BM_mesh_boolean(BMesh *bm,
                      const int nshapes,
                      const bool use_self,
                      const bool keep_hidden,
+                     const bool hole_tolerant,
                      const int boolean_mode)
 {
   return blender::meshintersect::bmesh_boolean(
@@ -449,6 +451,7 @@ bool BM_mesh_boolean(BMesh *bm,
       use_self,
       false,
       keep_hidden,
+      hole_tolerant,
       static_cast<blender::meshintersect::BoolOpType>(boolean_mode));
 }
 
@@ -468,6 +471,7 @@ bool BM_mesh_boolean_knife(BMesh *bm,
                            const int nshapes,
                            const bool use_self,
                            const bool use_separate_all,
+                           const bool hole_tolerant,
                            const bool keep_hidden)
 {
   return blender::meshintersect::bmesh_boolean(bm,
@@ -479,6 +483,7 @@ bool BM_mesh_boolean_knife(BMesh *bm,
                                                use_self,
                                                use_separate_all,
                                                keep_hidden,
+                                               hole_tolerant,
                                                blender::meshintersect::BoolOpType::None);
 }
 #else
@@ -490,6 +495,7 @@ bool BM_mesh_boolean(BMesh *UNUSED(bm),
                      const int UNUSED(nshapes),
                      const bool UNUSED(use_self),
                      const bool UNUSED(keep_hidden),
+                     const bool UNUSED(hole_tolerant),
                      const int UNUSED(boolean_mode))
 {
   UNUSED_VARS(looptris, test_fn);
@@ -512,6 +518,7 @@ bool BM_mesh_boolean_knife(BMesh *UNUSED(bm),
                            const int UNUSED(nshapes),
                            const bool UNUSED(use_self),
                            const bool UNUSED(use_separate_all),
+                           const bool UNUSED(hole_tolerant),
                            const bool UNUSED(keep_hidden))
 {
   UNUSED_VARS(looptris, test_fn);
diff --git a/source/blender/bmesh/tools/bmesh_boolean.h b/source/blender/bmesh/tools/bmesh_boolean.h
index 2cc32e143fc..ed77242e14c 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.h
+++ b/source/blender/bmesh/tools/bmesh_boolean.h
@@ -32,6 +32,7 @@ bool BM_mesh_boolean(BMesh *bm,
                      const int nshapes,
                      const bool use_self,
                      const bool keep_hidden,
+                     const bool hole_tolerant,
                      const int boolean_mode);
 
 bool BM_mesh_boolean_knife(BMesh *bm,
@@ -42,6 +43,7 @@ bool BM_mesh_boolean_knife(BMesh *bm,
                            const int nshapes,
                            const bool use_self,
                            const bool use_separate_all,
+                           const bool hole_tolerant,
                            const bool keep_hidden);
 
 #ifdef __cplusplus
diff --git a/source/blender/editors/mesh/editmesh_intersect.c b/source/blender/editors/mesh/editmesh_intersect.c
index b269a4f0514..0e3cc22d358 100644
--- a/source/blender/editors/mesh/editmesh_intersect.c
+++ b/source/blender/editors/mesh/editmesh_intersect.c
@@ -212,6 +212,7 @@ static int edbm_intersect_exec(bContext *C, wmOperator *op)
                                         nshapes,
                                         use_self,
                                         use_separate_all,
+                                        false,
                                         true);
     }
     else {
@@ -375,8 +376,16 @@ static int edbm_intersect_boolean_exec(bContext *C, wmOperator *op)
     }
 
     if (use_exact) {
-      has_isect = BM_mesh_boolean(
-          em->bm, em->looptris, em->tottri, test_fn, NULL, 2, use_self, true, boolean_operation);
+      has_isect = BM_mesh_boolean(em->bm,
+                                  em->looptris,
+                                  em->tottri,
+                                  test_fn,
+                                  NULL,
+                                  2,
+                                  use_self,
+                                  true,
+                                  false,
+                                  boolean_operation);
     }
     else {
       has_isect = BM_mesh_intersect(em->bm,
diff --git a/source/blender/editors/sculpt_paint/paint_mask.c b/source/blender/editors/sculpt_paint/paint_mask.c
index 26e2bcc42cf..966f2ace931 100644
--- a/source/blender/editors/sculpt_paint/paint_mask.c
+++ b/source/blender/editors/sculpt_paint/paint_mask.c
@@ -1292,7 +1292,8 @@ static void sculpt_gesture_apply_trim(SculptGestureContext *sgcontext)
         BLI_assert(false);
         break;
     }
-    BM_mesh_boolean(bm, looptris, tottri, bm_face_isect_pair, NULL, 2, true, true, boolean_mode);
+    BM_mesh_boolean(
+        bm, looptris, tottri, bm_face_isect_pair, NULL, 2, true, true, false, boolean_mode);
   }
 
   MEM_freeN(looptris);
diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h
index dbcb6ce45ea..368b1f93e4a 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -904,6 +904,7 @@ enum {
   eBooleanModifierFlag_Self = (1 << 0),
   eBooleanModifierFlag_Object = (1 << 1),
   eBooleanModifierFlag_Collection = (1 << 2),
+  eBooleanModifierFlag_HoleTolerant = (1 << 3),
 };
 
 /* bm_flag only used when G_DEBUG. */
diff --git a/source/blender/makesrna/intern/rna_modifier.c b/source/blender/makesrna/intern/rna_modifier.c
index 5008240ea33..55d81bd3155 100644
--- a/source/blender/makesrna/intern/rna_modifier.c
+++ b/source/blender/makesrna/intern/rna_modifier.c
@@ -2789,6 +2789,11 @@ static void rna_def_modifier_boolean(BlenderRNA *brna)
   RNA_def_property_ui_text(prop, "Self", "Allow self-intersection in operands");
   RNA_def_property_update(prop, 0, "rna_Modifier_update");
 
+  prop = RNA_def_property(srna, "hole_tolerant", PROP_BOOLEAN, PROP_NONE);
+  RNA_def_property_boolean_sdna(prop, NULL, "flag", eBooleanModifierFlag_HoleTolerant);
+  RNA_def_property_ui_text(prop, "Hole tolerant", "Better results when there are holes (slower)");
+  RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
   /* BMesh debugging options, only used when G_DEBUG is set */
 
   /* BMesh intersection options */
diff --git a/source/blender/modifiers/intern/MOD_boolean.c b/source/blender/modifiers/intern/MOD_boolean.c
index 070ba3a1bcf..0bfd0e54304 100644
--- a/source/blender/modifiers/intern/MOD_boolean.c
+++ b/source/blender/modifiers/intern/MOD_boolean.c
@@ -21,7 +21,7 @@
  * \ingroup modifiers
  */
 
-// #ifdef DEBUG_TIME
+// #define DEBUG_TIME
 
 #include <stdio.h>
 
@@ -422,7 +422,7 @@ static void BMD_mesh_intersection(BMesh *bm,
 
   if (use_exact) {
     BM_mesh_boolean(
-        bm, looptris, tottri, bm_face_isect_pair, NULL, 2, use_self, false, bmd->operation);
+        bm, looptris, tottri, bm_face_isect_pair, NULL, 2, use_self, false, false, bmd->operation);
   }
   else {
     BM_mesh_intersect(bm,
@@ -587,8 +587,16 @@ static Mesh *collection_boolean_exact(BooleanModifierData *bmd,
   }
 
   BM_mesh_elem_index_ensure(bm, BM_FACE);
-  BM_mesh_boolean(
-      bm, looptris, tottri, bm_face_isect_nary, shape, num_shapes, true, false, bmd->operation);
+  BM_mesh_boolean(bm,
+                  looptris,
+                  tottri,
+                  bm_face_isect_nary,
+                  shape,
+                  num_shapes,
+                  true,
+                  false,
+                  false,
+                  bmd->operation);
 
   result = BKE_mesh_from_bmesh_for_eval_nomain(bm, NULL, mesh);
   BM_mesh_free(bm);
@@ -651,10 +659,12 @@ static Mesh *exact_boolean_mesh(BooleanModifierData *bmd,
   }
 
   const bool use_self = (bmd->flag & eBooleanModifierFlag_Self) != 0;
+  const bool hole_tolerant = (bmd->flag & eBooleanModifierFlag_HoleTolerant) != 0;
   result = BKE_mesh_boolean((const Mesh **)meshes,
                             (const float(**)[4][4])obmats,
                             BLI_array_len(meshes),
                             use_self,
+                            hole_tolerant,
                             bmd->operation);
 
   BLI_array_free(meshes);
@@ -846,31 +856,43 @@ static void panel_draw(const bContext *UNUSED(C), Panel *panel)
     uiItemR(layout, ptr, "collection", 0, NULL, ICON_NONE);
   }
 
-  const bool use_exact = RNA_enum_get(ptr, "solver") == eBooleanModifierSolver_Exact;
-
   uiItemR(layout, ptr, "solver", UI_ITEM_R_EXPAND, NULL, ICON_NONE);
 
+  modifier_panel_end(layout, ptr);
+}
+
+static void solver_options_panel_draw(const bContext *UNUSED(C), Panel *panel)
+{
+  uiLayout *layout = panel->layout;
+  uiLayout *col = uiLayoutColumn(layout, true);
+
+  PointerRNA *ptr = modifier_panel_get_property_pointers(panel, NULL);
+
+  const bool use_exact = RNA_enum_get(ptr, "solver") == eBooleanModifierSolver_Exact;
+  const bool operand_object = RNA_enum_get(ptr, "operand_type") == eBooleanModifierFlag_Object;
+
   if (use_exact) {
     /* When operand is collection, we always use_self. */
     if (operand_object) {
-      uiItemR(layout, ptr, "use_self", 0, NULL, ICON_NONE);
+      uiItemR(col, ptr, "use_self", 0, NULL, ICON_NONE);
     }
+    uiItemR(col, ptr, "hole_tolerant", 0, NULL, ICON_NONE);
   }
   else {
-    uiItemR(layout, ptr, "double_threshold", 0, NULL, ICON_NONE);
+    uiItemR(col, ptr, "double_threshold", 0, NULL, ICON_NONE);
   }
 
   if (G.debug) {
-    uiLayout *col = uiLayoutColumn(layout, true);
+    col = uiLayoutColumn(layout, true);
     uiItemR(col, ptr, "debug_options", 0, NULL, ICON_NONE);
   }
-
-  modifier_panel_end(layout, ptr);
 }
 
 static void panelRegister(ARegionType *region_type)
 {
-  modifier_panel_register(region_type, eModifierType_Boolean, panel_draw);
+  PanelType *panel = modifier_panel_register(region_type, eModifierType_Boolean, panel_draw);
+  modifier_subpanel_register(
+      region_type, "solver_options", "Solver Options", NULL, solver_options_panel_draw, panel);
 }
 
 ModifierTypeInfo modifierType_Boolean = {
diff --git a/source/blender/nodes/geometry/nodes/node_geo_boolean.cc b/source/blender/nodes/geometry/nodes/node_geo_boolean.cc
index 38215b54640..9f331190420 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_boolean.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_boolean.cc
@@ -100,7 +100,7 @@ static Mesh *mesh_boolean_calc(const Mesh *mesh_a, const Mesh *mesh_b, int boole
   }
 
   BM_mesh_boolean(
-      bm, looptris, tottri, bm_face_isect_pair, nullptr, 2, false, false, boolean_mode);
+      bm, looptris, tottri, bm_face_isect_pair, nullptr, 2, false, false, false, boolean_mode);
 
   Mesh *result = BKE_mesh_from_bmesh_for_eval_nomain(bm, nullptr, mesh_a);
   BM_mesh_free(bm);
diff --git a/source/tools b/source/tools
-Subproject dc4ccc3bfb646ef2a558bd3565f84080e99b0e8
+Subproject c37d8bd28ddddb8f1b0dff5739d75f8004e8034