From 1ba15f1f7f94616d52e8bbd80e22c9e34e45a81e Mon Sep 17 00:00:00 2001 From: Howard Trickey Date: Sun, 7 Mar 2021 18:13:19 -0500 Subject: 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 | 2 +- .../blender/blenkernel/BKE_mesh_boolean_convert.h | 1 + .../blenkernel/intern/mesh_boolean_convert.cc | 7 +- source/blender/blenlib/BLI_mesh_boolean.hh | 2 + source/blender/blenlib/intern/mesh_boolean.cc | 203 ++++++++++++++++----- .../blender/blenlib/tests/BLI_mesh_boolean_test.cc | 79 ++++++-- source/blender/bmesh/tools/bmesh_boolean.cc | 9 +- source/blender/bmesh/tools/bmesh_boolean.h | 2 + source/blender/editors/mesh/editmesh_intersect.c | 13 +- source/blender/editors/sculpt_paint/paint_mask.c | 3 +- source/blender/makesdna/DNA_modifier_types.h | 1 + source/blender/makesrna/intern/rna_modifier.c | 5 + source/blender/modifiers/intern/MOD_boolean.c | 46 +++-- .../nodes/geometry/nodes/node_geo_boolean.cc | 2 +- source/tools | 2 +- 15 files changed, 291 insertions(+), 86 deletions(-) diff --git a/release/scripts/addons b/release/scripts/addons index 24e756c0da8..117faa96af3 160000 --- a/release/scripts/addons +++ b/release/scripts/addons @@ -1 +1 @@ -Subproject commit 24e756c0da89bdbf88dc22163ae3b7ef4f1fbb73 +Subproject commit 117faa96af35685d72e5e01f9a386d163d874133 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 meshes, Span 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 meshes, } return static_cast(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(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 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 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 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 &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 &out_faces, Face &tri, IMeshArena *arena) +{ + + Array flipped_vs = {tri[0], tri[2], tri[1]}; + Array flipped_e_origs = {tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]}; + Array 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 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 out_faces; out_faces.reserve(tm.face_size()); Array 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 flipped_vs = {tri[0], tri[2], tri[1]}; - Array flipped_e_origs = {tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]}; - Array 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 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 out_faces; + out_faces.reserve(tm.face_size()); + Array in_shape(nshapes, 0); + Array 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 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 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(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 @@ -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 index dc4ccc3bfb6..c37d8bd28dd 160000 --- a/source/tools +++ b/source/tools @@ -1 +1 @@ -Subproject commit dc4ccc3bfb646ef2a558bd3565f84080e99b0e8b +Subproject commit c37d8bd28ddddb8f1b0dff5739d75f8004e8034f -- cgit v1.2.3