manifold: #528 causes invalid `UpdateVert` calls

I think I mentioned this before, but this is another reason I’d like to switch SparseIndices from relying on sort and unique to just using a hash table. It should be faster, simpler, and probably allow us to remove these weird thrust calls entirely.

Alternatively we can use sort, but only dedupe the smaller indices:

diff --git a/src/manifold/src/edge_op.cpp b/src/manifold/src/edge_op.cpp
index 4e3db36..cae7f74 100644
--- a/src/manifold/src/edge_op.cpp
+++ b/src/manifold/src/edge_op.cpp
@@ -162,7 +162,8 @@ void Manifold::Impl::SimplifyTopology() {
   for (int i = 0; i < nbEdges - 1; ++i) {
     if (entries[i].start == entries[i + 1].start &&
         entries[i].end == entries[i + 1].end) {
-      DedupeEdge(entries[i].index);
+      DedupeEdge(std::min(entries[i].index, entries[i + 1].index));
+      entries[i + 1].index = std::max(entries[i].index, entries[i + 1].index);
       numFlagged++;
     }
   }

And I can confirm that 1, 2 and 3 are all independent from each other. Fixing one will not fix another.

I feel like I am starting to use my brain now.

I sometimes got this as well:

Error in file: /home/pca006132/code/manifold/src/polygon/src/polygon.cpp (103): 'std::distance(forward.begin(), end) == n_edges' is false: Half of halfedges should be forward.
polys.push_back({
    {20.1267338, 2.00670671},  //
    {20.12673, 2.00670576},  //
    {19.7702141, 1.63188827},  //
    {19.7702141, 1.63188827},  //
    {19.7702141, 1.63188827},  //
    {19.5752983, 1.81728792},  //
    {19.5623493, 1.81283963},  //
    {19.7630997, 1.54846776},  //
    {19.7630997, 1.54846776},  //
});
polys.push_back({
    {19.7702141, 1.63188827},  //
    {19.898922, 1.92845321},  //
    {19.5752983, 1.81728792},  //
});
polys.push_back({
    {19.7630997, 1.54846776},  //
    {19.7630997, 1.54846776},  //
    {19.7630997, 1.54846776},  //
});
array([
  [20.1267338, 2.00670671],
  [20.12673, 2.00670576],
  [19.7702141, 1.63188827],
  [19.7702141, 1.63188827],
  [19.7702141, 1.63188827],
  [19.5752983, 1.81728792],
  [19.5623493, 1.81283963],
  [19.7630997, 1.54846776],
  [19.7630997, 1.54846776],
])
array([
  [19.7702141, 1.63188827],
  [19.898922, 1.92845321],
  [19.5752983, 1.81728792],
])
array([
  [19.7630997, 1.54846776],
  [19.7630997, 1.54846776],
  [19.7630997, 1.54846776],
])

Indeed, that should work. I was thinking about using pair as the key type but it is not really needed.

OK I got a simpler reproduce, but it is non-deterministic… Boolean.Sweep under the correct condition will trigger the out of bound bug in FormLoop, basically you need to run the test 5 times or more, and add the following patch so the debugger can be triggered (as tbb will mess up with the stack trace otherwise…):

--- a/src/utilities/include/vec.h
+++ b/src/utilities/include/vec.h
@@ -59,12 +59,20 @@ class VecView {
   operator VecView<const T>() const { return {ptr_, size_}; }
 
   inline const T &operator[](int i) const {
-    if (i < 0 || i >= size_) throw std::out_of_range("Vec out of range");
+    if (i < 0 || i >= size_) {
+      printf("i: %d, size: %d\n", i, size_);
+      __builtin_trap();
+      throw std::out_of_range("Vec out of range");
+    }
     return ptr_[i];
   }
 
   inline T &operator[](int i) {
-    if (i < 0 || i >= size_) throw std::out_of_range("Vec out of range");
+    if (i < 0 || i >= size_) {
+      printf("i: %d, size: %d\n", i, size_);
+      __builtin_trap();
+      throw std::out_of_range("Vec out of range");
+    }
     return ptr_[i];
   }

The out of range are always -1 or -3, so I think we should probably add more check to make sure that the halfedge is not already removed…

Also, I implemented multithreaded CollapseEdge, but the performance is not great: the performance is slightly better on my machine with 20 cores (50ms faster on average? over something that took 2400ms), and slower when the number of cores decreases. I double checked to make sure that my partition implementation should be pretty fast, so I guess the problem is just too hard to parallelize (at least for now).