From e8573a59f66281f1d590e3c8b1888cfc7935b1cf Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Thu, 1 Apr 2021 15:00:47 -0500 Subject: Geometry Nodes: Improve speed of boolean node, use multi-input socket This commit improves the performance of the node by up to 40% in some cases when there are only two input meshes, mainly by skipping the conversion to and from BMesh. When there are more than two input meshes (note the distinction from "Geometries", a geometry set can have many mesh instances), the performance is actually worse, since boolean currently always does self intersection in that case. Theoretically this could be improved in the boolean code, or another option is automatically realizing instances for each input geometry set. Another improvement is using multi-input sockets for the inputs, which removes the need to have a separate boolean node for every operation, which can hopefully simplify some node trees. The changes necessary for transforms in `mesh_boolean_convert.cc` are somewhat subtle; they come from the fact that the collecting the geometry set instances already gives transforms in the local space of the modifier object. There is also a very small amount of cleanup to those lines, using `float4x4::identity()`. This commit also fixes T87078, where overlapping difference meshes makes the operation not work, though I haven't investigated why. Differential Revision: https://developer.blender.org/D10599 --- .../blenkernel/intern/mesh_boolean_convert.cc | 130 +++++++++++---------- 1 file changed, 69 insertions(+), 61 deletions(-) (limited to 'source/blender/blenkernel/intern/mesh_boolean_convert.cc') diff --git a/source/blender/blenkernel/intern/mesh_boolean_convert.cc b/source/blender/blenkernel/intern/mesh_boolean_convert.cc index 824f791d400..de9ad00ebde 100644 --- a/source/blender/blenkernel/intern/mesh_boolean_convert.cc +++ b/source/blender/blenkernel/intern/mesh_boolean_convert.cc @@ -51,8 +51,9 @@ constexpr int estimated_max_facelen = 100; /* Used for initial size of some Vect * so this is a hack to clean up such matrices. * Would be better to change the transformation code itself. */ -static void clean_obmat(float4x4 &cleaned, const float4x4 &mat) +static float4x4 clean_obmat(const float4x4 &mat) { + float4x4 cleaned; const float fuzz = 1e-6f; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { @@ -69,6 +70,7 @@ static void clean_obmat(float4x4 &cleaned, const float4x4 &mat) cleaned.values[i][j] = f; } } + return cleaned; } /* `MeshesToIMeshInfo` keeps track of information used when combining a number @@ -92,7 +94,7 @@ class MeshesToIMeshInfo { Array mesh_to_imesh_face; /* Transformation matrix to transform a coordinate in the corresponding * Mesh to the local space of the first Mesh. */ - Array to_obj0; + Array to_target_transform; /* For each input mesh, how to remap the material slot numbers to * the material slots in the first mesh. */ Array material_remaps; @@ -242,6 +244,7 @@ const MEdge *MeshesToIMeshInfo::input_medge_for_orig_index(int orig_index, static IMesh meshes_to_imesh(Span meshes, Span obmats, Span material_remaps, + const float4x4 &target_transform, IMeshArena &arena, MeshesToIMeshInfo *r_info) { @@ -270,7 +273,7 @@ static IMesh meshes_to_imesh(Span meshes, r_info->mesh_vert_offset = Array(nmeshes); r_info->mesh_edge_offset = Array(nmeshes); r_info->mesh_poly_offset = Array(nmeshes); - r_info->to_obj0 = Array(nmeshes); + r_info->to_target_transform = Array(nmeshes); r_info->material_remaps = Array(nmeshes); int v = 0; int e = 0; @@ -283,19 +286,10 @@ static IMesh meshes_to_imesh(Span meshes, Vector face_edge_orig; /* To convert the coordinates of objects 1, 2, etc. into the local space - * of object 0, we multiply each object's `obmat` by the inverse of - * object 0's `obmat`. Exact Boolean works better if these matrices - * are 'cleaned' -- see the comment for the `clean_obmat` function, above. */ - float4x4 obj0_mat; - float4x4 inv_obj0_mat; - if (obmats[0] == nullptr) { - unit_m4(obj0_mat.values); - unit_m4(inv_obj0_mat.values); - } - else { - clean_obmat(obj0_mat, *obmats[0]); - invert_m4_m4(inv_obj0_mat.values, obj0_mat.values); - } + * of the target. We multiply each object's `obmat` by the inverse of the + * target matrix. Exact Boolean works better if these matrices are 'cleaned' + * -- see the comment for the `clean_obmat` function, above. */ + const float4x4 inv_target_mat = clean_obmat(target_transform).inverted(); /* For each input `Mesh`, make `Vert`s and `Face`s for the corresponding * `MVert`s and `MPoly`s, and keep track of the original indices (using the @@ -303,45 +297,41 @@ static IMesh meshes_to_imesh(Span meshes, * When making `Face`s, we also put in the original indices for `MEdge`s that * make up the `MPoly`s using the same scheme. */ for (int mi : meshes.index_range()) { - float4x4 objn_to_obj0_mat; const Mesh *me = meshes[mi]; - if (mi == 0) { - r_info->mesh_vert_offset[mi] = 0; - r_info->mesh_edge_offset[mi] = 0; - r_info->mesh_poly_offset[mi] = 0; - unit_m4(r_info->to_obj0[0].values); - r_info->material_remaps[0] = nullptr; + r_info->mesh_vert_offset[mi] = v; + r_info->mesh_edge_offset[mi] = e; + r_info->mesh_poly_offset[mi] = f; + /* Get matrix that transforms a coordinate in objects[mi]'s local space + * to the target space space.*/ + const float4x4 objn_mat = (obmats[mi] == nullptr) ? float4x4::identity() : + clean_obmat(*obmats[mi]); + r_info->to_target_transform[mi] = inv_target_mat * objn_mat; + + if (mi < material_remaps.size() && mi != 0) { + r_info->material_remaps[mi] = material_remaps[mi]; } else { - r_info->mesh_vert_offset[mi] = v; - r_info->mesh_edge_offset[mi] = e; - r_info->mesh_poly_offset[mi] = f; - /* Get matrix that transforms a coordinate in objects[mi]'s local space - * to object[0]'s local space.*/ - float4x4 objn_mat; - if (obmats[mi] == nullptr) { - unit_m4(objn_mat.values); - } - else { - clean_obmat(objn_mat, *obmats[mi]); - } - objn_to_obj0_mat = inv_obj0_mat * objn_mat; - r_info->to_obj0[mi] = objn_to_obj0_mat; - if (mi < material_remaps.size()) { - r_info->material_remaps[mi] = material_remaps[mi]; - } - else { - r_info->material_remaps[mi] = nullptr; + r_info->material_remaps[mi] = nullptr; + } + + /* Skip the matrix multiplication for each point when there is no transform for a mesh, + * for example when the first mesh is already in the target space. (Note the logic directly + * above, which uses an identity matrix with a null input transform). */ + if (obmats[mi] == nullptr) { + for (const MVert &vert : Span(me->mvert, me->totvert)) { + const float3 co = float3(vert.co); + r_info->mesh_to_imesh_vert[v] = arena.add_or_find_vert(mpq3(co.x, co.y, co.z), v); + ++v; } } - for (int vi = 0; vi < me->totvert; ++vi) { - float3 co = me->mvert[vi].co; - if (mi > 0) { - co = objn_to_obj0_mat * co; + else { + for (const MVert &vert : Span(me->mvert, me->totvert)) { + const float3 co = r_info->to_target_transform[mi] * float3(vert.co); + r_info->mesh_to_imesh_vert[v] = arena.add_or_find_vert(mpq3(co.x, co.y, co.z), v); + ++v; } - r_info->mesh_to_imesh_vert[v] = arena.add_or_find_vert(mpq3(co.x, co.y, co.z), v); - ++v; } + for (const MPoly &poly : Span(me->mpoly, me->totpoly)) { int flen = poly.totloop; face_vert.clear(); @@ -596,7 +586,7 @@ static void copy_or_interp_loop_attributes(Mesh *dest_mesh, cos_2d = (float(*)[2])BLI_array_alloca(cos_2d, orig_mp->totloop); weights = Array(orig_mp->totloop); src_blocks_ofs = Array(orig_mp->totloop); - get_poly2d_cos(orig_me, orig_mp, cos_2d, mim.to_obj0[orig_me_index], axis_mat); + get_poly2d_cos(orig_me, orig_mp, cos_2d, mim.to_target_transform[orig_me_index], axis_mat); } CustomData *target_cd = &dest_mesh->ldata; for (int i = 0; i < mp->totloop; ++i) { @@ -778,17 +768,21 @@ static Mesh *imesh_to_mesh(IMesh *im, MeshesToIMeshInfo &mim) return result; } +#endif // WITH_GMP + /** * Do Exact Boolean directly, without a round trip through #BMesh. * The Mesh operands are in `meshes`, with corresponding transforms in in `obmats`. */ -static Mesh *direct_mesh_boolean(Span meshes, - Span obmats, - Span material_remaps, - const bool use_self, - const bool hole_tolerant, - const BoolOpType boolean_mode) +Mesh *direct_mesh_boolean(Span meshes, + Span obmats, + const float4x4 &target_transform, + Span material_remaps, + const bool use_self, + const bool hole_tolerant, + const int boolean_mode) { +#ifdef WITH_GMP const int dbg_level = 0; BLI_assert(meshes.size() == obmats.size()); const int meshes_len = meshes.size(); @@ -800,7 +794,7 @@ static Mesh *direct_mesh_boolean(Span meshes, } MeshesToIMeshInfo mim; IMeshArena arena; - IMesh m_in = meshes_to_imesh(meshes, obmats, material_remaps, arena, &mim); + IMesh m_in = meshes_to_imesh(meshes, obmats, material_remaps, target_transform, arena, &mim); std::function shape_fn = [&mim](int f) { for (int mi = 0; mi < mim.mesh_poly_offset.size() - 1; ++mi) { if (f < mim.mesh_poly_offset[mi + 1]) { @@ -809,17 +803,27 @@ 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, hole_tolerant, nullptr, &arena); + IMesh m_out = boolean_mesh(m_in, + static_cast(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"); } return imesh_to_mesh(&m_out, mim); +#else // WITH_GMP + UNUSED_VARS( + meshes, obmats, material_remaps, target_transform, use_self, hole_tolerant, boolean_mode); + return nullptr; +#endif // WITH_GMP } -#endif // WITH_GMP } // namespace blender::meshintersect extern "C" { @@ -835,6 +839,7 @@ extern "C" { * for the pointers to be nullptr, meaning the transformation is the identity. */ Mesh *BKE_mesh_boolean(const Mesh **meshes, const float (*obmats[])[4][4], + const float (*target_transform)[4][4], const short **material_remaps, const int meshes_len, const bool use_self, @@ -842,25 +847,28 @@ Mesh *BKE_mesh_boolean(const Mesh **meshes, const int boolean_mode) { const blender::float4x4 **transforms = (const blender::float4x4 **)obmats; + const blender::float4x4 &target_float4x4 = *(const blender::float4x4 *)target_transform; return blender::meshintersect::direct_mesh_boolean( blender::Span(meshes, meshes_len), blender::Span(transforms, meshes_len), + target_float4x4, blender::Span(material_remaps, material_remaps ? meshes_len : 0), use_self, hole_tolerant, - static_cast(boolean_mode)); + boolean_mode); } #else Mesh *BKE_mesh_boolean(const Mesh **UNUSED(meshes), const float (*obmats[])[4][4], + const float (*target_transform)[4][4], const short **UNUSED(material_remaps), const int UNUSED(meshes_len), const bool UNUSED(use_self), const bool UNUSED(hole_tolerant), const int UNUSED(boolean_mode)) { - UNUSED_VARS(obmats); + UNUSED_VARS(obmats, target_transform); return NULL; } -- cgit v1.2.3