From fbffff26e437ad87b644762b340dcddc7ddf16ab Mon Sep 17 00:00:00 2001 From: Howard Trickey Date: Sun, 15 Nov 2020 20:24:59 -0500 Subject: Fix T82736, Exact Boolean fail with repeated subtraction of same object. Two problems were fixed. One, the code for dissolving vertices left a face around if dissolving a vertex would leave less than three vertices. Instead, the face should be deleted. Two, with transformations like "rotate 180 degrees", this should be no problem with exact, but the current transformation matrix has very small non-zero entries where it shouldn't. Cleaning the transformation matrix makes it more likely that user expectations about coplanar faces will be fulfilled. --- source/blender/blenlib/BLI_mesh_intersect.hh | 8 +++- source/blender/blenlib/intern/mesh_boolean.cc | 12 +++++- source/blender/blenlib/intern/mesh_intersect.cc | 48 +++++++++++++++++---- source/blender/modifiers/intern/MOD_boolean.c | 57 ++++++++++++++++++++----- 4 files changed, 103 insertions(+), 22 deletions(-) (limited to 'source') diff --git a/source/blender/blenlib/BLI_mesh_intersect.hh b/source/blender/blenlib/BLI_mesh_intersect.hh index 877363b998a..ddda3edf2ff 100644 --- a/source/blender/blenlib/BLI_mesh_intersect.hh +++ b/source/blender/blenlib/BLI_mesh_intersect.hh @@ -327,8 +327,14 @@ class IMesh { * Replace face at given index with one that elides the * vertices at the positions in face_pos_erase that are true. * Use arena to allocate the new face in. + * This may end up setting the face at f_index to NULL. + * Return true if that is so, else return false. + * The caller may want to use remove_null_faces if any face + * was removed, to avoid the need to check for null faces later. */ - void erase_face_positions(int f_index, Span face_pos_erase, IMeshArena *arena); + bool erase_face_positions(int f_index, Span face_pos_erase, IMeshArena *arena); + + void remove_null_faces(); }; std::ostream &operator<<(std::ostream &os, const IMesh &mesh); diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc index 8b6a7ed65f7..82ccbcc91b6 100644 --- a/source/blender/blenlib/intern/mesh_boolean.cc +++ b/source/blender/blenlib/intern/mesh_boolean.cc @@ -751,7 +751,7 @@ static PatchesInfo find_patches(const IMesh &tm, const TriMeshTopology &tmtopo) if (dbg_level > 1) { std::cout << "\ntriangle map\n"; for (int t : tm.face_index_range()) { - std::cout << t << ": patch " << pinfo.tri_patch(t) << "\n"; + std::cout << t << ": " << tm.face(t) << " patch " << pinfo.tri_patch(t) << "\n"; } } std::cout << "\npatch-patch incidences\n"; @@ -3135,6 +3135,7 @@ static void dissolve_verts(IMesh *imesh, const Array dissolve, IMeshArena { constexpr int inline_face_size = 100; Vector face_pos_erase; + bool any_faces_erased = false; for (int f : imesh->face_index_range()) { const Face &face = *imesh->face(f); face_pos_erase.clear(); @@ -3151,10 +3152,13 @@ static void dissolve_verts(IMesh *imesh, const Array dissolve, IMeshArena } } if (num_erase > 0) { - imesh->erase_face_positions(f, face_pos_erase, arena); + any_faces_erased |= imesh->erase_face_positions(f, face_pos_erase, arena); } } imesh->set_dirty_verts(); + if (any_faces_erased) { + imesh->remove_null_faces(); + } } /** @@ -3376,6 +3380,10 @@ IMesh boolean_mesh(IMesh &imesh, IMesh ans = polymesh_from_trimesh_with_dissolve(tm_out, imesh, arena); if (dbg_level > 0) { std::cout << "boolean_mesh output:\n" << ans; + if (dbg_level > 2) { + ans.populate_vert(); + dump_test_spec(ans); + } } return ans; } diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc index 5f7258ebb6a..785e405b482 100644 --- a/source/blender/blenlib/intern/mesh_intersect.cc +++ b/source/blender/blenlib/intern/mesh_intersect.cc @@ -80,11 +80,15 @@ uint64_t Vert::hash() const std::ostream &operator<<(std::ostream &os, const Vert *v) { + constexpr int dbg_level = 0; os << "v" << v->id; if (v->orig != NO_INDEX) { os << "o" << v->orig; } os << v->co; + if (dbg_level > 0) { + os << "=" << v->co_exact; + } return os; } @@ -258,10 +262,7 @@ std::ostream &operator<<(std::ostream &os, const Face *f) { os << "f" << f->id << "o" << f->orig << "["; for (const Vert *v : *f) { - os << "v" << v->id; - if (v->orig != NO_INDEX) { - os << "o" << v->orig; - } + os << v; if (v != f->vert[f->size() - 1]) { os << " "; } @@ -649,7 +650,7 @@ void IMesh::populate_vert(int max_verts) vert_populated_ = true; } -void IMesh::erase_face_positions(int f_index, Span face_pos_erase, IMeshArena *arena) +bool IMesh::erase_face_positions(int f_index, Span face_pos_erase, IMeshArena *arena) { const Face *cur_f = this->face(f_index); int cur_len = cur_f->size(); @@ -660,12 +661,18 @@ void IMesh::erase_face_positions(int f_index, Span face_pos_erase, IMeshAr } } if (num_to_erase == 0) { - return; + return false; } int new_len = cur_len - num_to_erase; if (new_len < 3) { - /* Invalid erase. Don't do anything. */ - return; + /* This erase causes removal of whole face. + * Because this may be called from a loop over the face array, + * we don't want to compress that array right here; instead will + * mark with null pointer and caller should call remove_null_faces(). + * the loop is done. + */ + this->face_[f_index] = NULL; + return true; } Array new_vert(new_len); Array new_edge_orig(new_len); @@ -681,6 +688,31 @@ void IMesh::erase_face_positions(int f_index, Span face_pos_erase, IMeshAr } BLI_assert(new_index == new_len); this->face_[f_index] = arena->add_face(new_vert, cur_f->orig, new_edge_orig, new_is_intersect); + return false; +} + +void IMesh::remove_null_faces() +{ + int64_t nullcount = 0; + for (Face *f : this->face_) { + if (f == NULL) { + ++nullcount; + } + } + if (nullcount == 0) { + return; + } + int64_t new_size = this->face_.size() - nullcount; + int64_t copy_to_index = 0; + int64_t copy_from_index = 0; + Array new_face(new_size); + while (copy_from_index < face_.size()) { + Face *f_from = face_[copy_from_index++]; + if (f_from) { + new_face[copy_to_index++] = f_from; + } + } + this->face_ = new_face; } std::ostream &operator<<(std::ostream &os, const IMesh &mesh) diff --git a/source/blender/modifiers/intern/MOD_boolean.c b/source/blender/modifiers/intern/MOD_boolean.c index 1cf56d1d30f..8d0c7cd6d49 100644 --- a/source/blender/modifiers/intern/MOD_boolean.c +++ b/source/blender/modifiers/intern/MOD_boolean.c @@ -274,6 +274,27 @@ static BMesh *BMD_mesh_bm_create( return bm; } +/* Snap entries that are near 0 or 1 or -1 to those values. */ +static void clean_obmat(float cleaned[4][4], const float mat[4][4]) +{ + const float fuzz = 1e-6f; + for (int i = 0; i < 4; i++) { + for (int j = 0; j < 4; j++) { + float f = mat[i][j]; + if (fabsf(f) <= fuzz) { + f = 0.0f; + } + else if (fabsf(f - 1.0f) <= fuzz) { + f = 1.0f; + } + else if (fabsf(f + 1.0f) <= fuzz) { + f = -1.0f; + } + cleaned[i][j] = f; + } + } +} + static void BMD_mesh_intersection(BMesh *bm, ModifierData *md, const ModifierEvalContext *ctx, @@ -290,6 +311,14 @@ static void BMD_mesh_intersection(BMesh *bm, int tottri; BMLoop *(*looptris)[3]; +#ifdef WITH_GMP + const bool use_exact = bmd->solver == eBooleanModifierSolver_Exact; + const bool use_self = (bmd->flag & eBooleanModifierFlag_Self) != 0; +#else + const bool use_exact = false; + const bool use_self = false; +#endif + looptris = MEM_malloc_arrayN(looptris_tot, sizeof(*looptris), __func__); BM_mesh_calc_tessellation_beauty(bm, looptris, &tottri); @@ -305,7 +334,18 @@ static void BMD_mesh_intersection(BMesh *bm, float imat[4][4]; float omat[4][4]; - invert_m4_m4(imat, object->obmat); + if (use_exact) { + /* The user-expected coplanar faces will actually be coplanar more + * often if use an object matrix that doesn't multiply by values + * other than 0, -1, or 1 in the scaling part of the matrix. + */ + float cleaned_object_obmat[4][4]; + clean_obmat(cleaned_object_obmat, object->obmat); + invert_m4_m4(imat, cleaned_object_obmat); + } + else { + invert_m4_m4(imat, object->obmat); + } mul_m4_m4m4(omat, imat, operand_ob->obmat); BMVert *eve; @@ -371,14 +411,6 @@ static void BMD_mesh_intersection(BMesh *bm, use_island_connect = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_NoConnectRegions) == 0; } -#ifdef WITH_GMP - const bool use_exact = bmd->solver == eBooleanModifierSolver_Exact; - const bool use_self = (bmd->flag & eBooleanModifierFlag_Self) != 0; -#else - const bool use_exact = false; - const bool use_self = false; -#endif - if (use_exact) { BM_mesh_boolean( bm, looptris, tottri, bm_face_isect_pair, NULL, 2, use_self, false, bmd->operation); @@ -493,7 +525,9 @@ static Mesh *collection_boolean_exact(BooleanModifierData *bmd, * The Exact solver doesn't need normals on the input faces. */ float imat[4][4]; float omat[4][4]; - invert_m4_m4(imat, ctx->object->obmat); + float cleaned_object_obmat[4][4]; + clean_obmat(cleaned_object_obmat, ctx->object->obmat); + invert_m4_m4(imat, cleaned_object_obmat); int curshape = 0; int curshape_vert_end = shape_vert_end[0]; BMVert *eve; @@ -503,7 +537,8 @@ static Mesh *collection_boolean_exact(BooleanModifierData *bmd, if (i == curshape_vert_end) { curshape++; curshape_vert_end = shape_vert_end[curshape]; - mul_m4_m4m4(omat, imat, objects[curshape]->obmat); + clean_obmat(cleaned_object_obmat, objects[curshape]->obmat); + mul_m4_m4m4(omat, imat, cleaned_object_obmat); } if (curshape > 0) { mul_m4_v3(omat, eve->co); -- cgit v1.2.3