Merge branch 'blender-v2.91-release'

Bring in exact boolean fix.

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<bool> face_pos_erase, IMeshArena *arena);
+  bool erase_face_positions(int f_index, Span<bool> face_pos_erase, IMeshArena *arena);
+
+  void remove_null_faces();
 };
 
 std::ostream &operator<<(std::ostream &os, const IMesh &mesh);

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<bool> dissolve, IMeshArena
 {
   constexpr int inline_face_size = 100;
   Vector<bool, inline_face_size> 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<bool> 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;
 }

source/blender/blenlib/intern/mesh_intersect.cc

@@ -81,11 +81,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;
 }
 
@@ -259,10 +263,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 << " ";
     }
@@ -650,7 +651,7 @@ void IMesh::populate_vert(int max_verts)
   vert_populated_ = true;
 }
 
-void IMesh::erase_face_positions(int f_index, Span<bool> face_pos_erase, IMeshArena *arena)
+bool IMesh::erase_face_positions(int f_index, Span<bool> face_pos_erase, IMeshArena *arena)
 {
   const Face *cur_f = this->face(f_index);
   int cur_len = cur_f->size();
@@ -661,12 +662,18 @@ void IMesh::erase_face_positions(int f_index, Span<bool> 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<const Vert *> new_vert(new_len);
   Array<int> new_edge_orig(new_len);
@@ -682,6 +689,31 @@ void IMesh::erase_face_positions(int f_index, Span<bool> 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<Face *> 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)

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