[Bf-blender-cvs] [1ba15f1f7f9] master: Speedup for usual non-manifold exact boolean case.
Howard Trickey
noreply at git.blender.org
Mon Mar 8 00:17:17 CET 2021
Commit: 1ba15f1f7f94616d52e8bbd80e22c9e34e45a81e
Author: Howard Trickey
Date: Sun Mar 7 18:13:19 2021 -0500
Branches: master
https://developer.blender.org/rB1ba15f1f7f94616d52e8bbd80e22c9e34e45a81e
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.
===================================================================
M release/scripts/addons
M source/blender/blenkernel/BKE_mesh_boolean_convert.h
M source/blender/blenkernel/intern/mesh_boolean_convert.cc
M source/blender/blenlib/BLI_mesh_boolean.hh
M source/blender/blenlib/intern/mesh_boolean.cc
M source/blender/blenlib/tests/BLI_mesh_boolean_test.cc
M source/blender/bmesh/tools/bmesh_boolean.cc
M source/blender/bmesh/tools/bmesh_boolean.h
M source/blender/editors/mesh/editmesh_intersect.c
M source/blender/editors/sculpt_paint/paint_mask.c
M source/blender/makesdna/DNA_modifier_types.h
M source/blender/makesrna/intern/rna_modifier.c
M source/blender/modifiers/intern/MOD_boolean.c
M source/blender/nodes/geometry/nodes/node_geo_boolean.cc
M source/tools
===================================================================
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<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
-
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list