Potential boolean bug

[pca006132]

See #666 (comment)

Just to remind us not to forget about this after finishing v3.0 release.

[elalish]

Yeah, I feel like we could use an approximate IsOverlapping function that we can run in debug mode after each Boolean so we can figure out where the problem first occurs, and dump out a test case of those meshes.

[pca006132]

For the record: We now check for self-intersection in

manifold/src/properties.cpp

Line 213 in 3a0c251

bool Manifold::Impl::IsSelfIntersecting() const {

and has a simple fuzzer in https://github.com/elalish/manifold/blob/master/test/manifold_fuzz.cpp that can fuzz this quickly.

[pca006132]

It seems that this may be related to the mesh simplification pass. For

manifold/test/boolean_complex_test.cpp

Lines 1040 to 1057 in ac82767

	TEST(BooleanComplex, DISABLED_OffsetSelfIntersect) {
	const bool intermediateChecks = ManifoldParams().intermediateChecks;
	ManifoldParams().intermediateChecks = true;
	std::string file = __FILE__;
	std::string dir = file.substr(0, file.rfind('/'));
	Manifold a, b;
	std::ifstream f;
	f.open(dir + "/models/Offset3.obj");
	a = Manifold::ImportMeshGL64(f);
	f.close();
	f.open(dir + "/models/Offset4.obj");
	b = Manifold::ImportMeshGL64(f);
	f.close();
	Manifold result = a + b;
	EXPECT_EQ(result.Status(), Manifold::Error::NoError);
	ManifoldParams().intermediateChecks = intermediateChecks;
	}

The result is not self-intersecting (doesn't even require epsilon-valid!) if we disable the mesh simplification pass, the part that flags redundant edges for collapsing. I think this suggests that the redundant edge removal may produce self-intersection.

However, disabling mesh simplification doesn't fix all the test cases. For example, the following case is still failing:

manifold/test/boolean_test.cpp

Lines 425 to 435 in ac82767

	TEST(Boolean, DISABLED_SimpleCubeRegression) {
	ManifoldParams().intermediateChecks = true;
	ManifoldParams().processOverlaps = false;
	Manifold result =
	Manifold::Cube().Rotate(-0.10000000000000001, 0.10000000000000001, -1.) +
	Manifold::Cube() -
	Manifold::Cube().Rotate(-0.10000000000000001, -0.10000000000066571, -1.);
	EXPECT_EQ(result.Status(), Manifold::Error::NoError);
	ManifoldParams().intermediateChecks = false;
	ManifoldParams().processOverlaps = true;
	}

Probably two issues at play here.

---

Also, about the edge flagging code, why don't we do the following, which updates ref1 to make sure ref1 never points to the same triangle as ref0? The old code will not flag more edges, but it may flag less.

  bool operator()(int edge) const {
    if (halfedge[edge].pairedHalfedge < 0) return false;
    // Flag redundant edges - those where the startVert is surrounded by only
    // two original triangles.
    const TriRef ref0 = triRef[edge / 3];
    int current = NextHalfedge(halfedge[edge].pairedHalfedge);
    TriRef ref1 = triRef[current / 3];
    bool ref1Updated = !ref0.SameFace(ref1);
    while (current != edge) {
      current = NextHalfedge(halfedge[current].pairedHalfedge);
      int tri = current / 3;
      const TriRef ref = triRef[tri];
      if (!ref.SameFace(ref0) && !ref.SameFace(ref1)) {
        if (!ref1Updated) {
          ref1 = ref;
          ref1Updated = true;
        } else {
          return false;
        }
      }
    }
    return true;
  }