From fbffff26e437ad87b644762b340dcddc7ddf16ab Mon Sep 17 00:00:00 2001
From: Howard Trickey <howard.trickey@gmail.com>
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/intern/mesh_boolean.cc   | 12 +++++--
 source/blender/blenlib/intern/mesh_intersect.cc | 48 ++++++++++++++++++++-----
 2 files changed, 50 insertions(+), 10 deletions(-)

(limited to 'source/blender/blenlib/intern')

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<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;
 }
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<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();
@@ -660,12 +661,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);
@@ -681,6 +688,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)
-- 
cgit v1.2.3