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.

release/scripts/addons

@@ -1 +1 @@
-Subproject commit 24e756c0da89bdbf88dc22163ae3b7ef4f1fbb73
+Subproject commit 117faa96af35685d72e5e01f9a386d163d874133

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

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);

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

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";

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();

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);

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

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,

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);

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. */

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 */

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);
 
-  if (use_exact) {
-    /* When operand is collection, we always use_self. */
-    if (operand_object) {
-      uiItemR(layout, ptr, "use_self", 0, NULL, ICON_NONE);
-    }
-  }
-  else {
-    uiItemR(layout, ptr, "double_threshold", 0, NULL, ICON_NONE);
-  }
-
-  if (G.debug) {
-    uiLayout *col = uiLayoutColumn(layout, true);
-    uiItemR(col, ptr, "debug_options", 0, 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(col, ptr, "use_self", 0, NULL, ICON_NONE);
+    }
+    uiItemR(col, ptr, "hole_tolerant", 0, NULL, ICON_NONE);
+  }
+  else {
+    uiItemR(col, ptr, "double_threshold", 0, NULL, ICON_NONE);
+  }
+
+  if (G.debug) {
+    col = uiLayoutColumn(layout, true);
+    uiItemR(col, ptr, "debug_options", 0, NULL, ICON_NONE);
+  }
+}
+
 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 = {

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);

source/tools

@@ -1 +1 @@
-Subproject commit dc4ccc3bfb646ef2a558bd3565f84080e99b0e8b
+Subproject commit c37d8bd28ddddb8f1b0dff5739d75f8004e8034f