Crashes due to error in manifold::UnionFind.

[fire]

godotengine/godot#99888

https://github.com/elalish/manifold/releases/tag/v3.0.0

Was wondering how to narrow this bug.

Crashes due to error in manifold::UnionFind.

[pca006132]

Is it possible to turn this into a test case in boolean_complex_test? Export the mesh and the associated boolean operation.

[fire]

We’re not able to export for test case recreation because the construction of the csg shape crashes.

[pca006132]

What would happen if you try to compile with MANIFOLD_DEBUG=ON?

[fire]

Will try

[fire]

Added bounds checking in unionfindxy

  void unionXY(I x, I y) {
    # Add check here.
    if (x < 0 || x >= parents.size() || y < 0 || y >= parents.size()) return;
    if (ranks[x] == 0) ranks[x] = 1;
    if (ranks[y] == 0) ranks[y] = 1;
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (ranks[x] < ranks[y]) std::swap(x, y);
    if (ranks[x] == ranks[y]) ranks[x]++;
    parents[y] = x;
  }

[pca006132]

The issue is, why can we have invalid x and y?

[fire]

node_3d.zip

It is unknown, but here's the mesh as a glb.

[pca006132]

I guess there is something wrong in CreateFaces. @elalish

[fire]

The fix does not convince me, but here's the code commit. V-Sekai/godot@ad8d1d6

[elalish]

Well, the good news is I'm already overhauling CreateFaces in #1040 to use a totally different algorithm. The bad news is it's going to need some work still.

[elalish]

@fire I made a simple test with your object and it seems to work just fine:

TEST(Manifold, Merge2) {
  std::string file = __FILE__;
  std::string dir = file.substr(0, file.rfind('/'));
  MeshGL cylinder = ImportMesh(dir + "/models/" + "node_3d.glb");
  EXPECT_TRUE(cylinder.Merge());
  Manifold fixed(cylinder);
  EXPECT_NEAR(fixed.Volume(), 2.83, 0.01);
}

Can you send a PR with a test that actually fails so we can track down the problem?

[fire]

I am having trouble. Can you supply code that dumps the entire triangle mesh before the two crash condition in unionxy if (x < 0 || x >= parents.size() || y < 0 || y >= parents.size()) return; and label2vert !(label >= 0 && label < label2vert.size() && label2vert[label] >= 0)?

So I can place the mesh dumper in this condition? V-Sekai/godot@ad8d1d6#diff-56b5b289049405153f8155e0989091eb012953e0775f43978dcb0fc020f7f696R154

I'll try to dump on the godot engine inputs.

[elalish]

I believe @pca006132 was just working on a function for dumping an OBJ to the command prompt. There's also this (with MANIFOLD_DEUBG=ON):

vertPos_.Dump();
for(int tri=0; tri<NumTri(); ++tri){
  std::cout<<halfedge_[3*tri].startVert<<", "
    <<halfedge_[3*tri+1].startVert<<", "
    <<halfedge_[3*tri+2].startVert<<", "<<std::endl;
}

[pca006132]

Yeah I had that, but considering our meshio code seems to have difficulty loading the obj file and I have no idea if it can load 64 bit floats precisely, I may switch to some custom format which dump things like tolerances as well.

Also, the code will dump early if the boolean result is self-intersecting. Ideally we should be able to check if it is epsilon-valid, but it probably requires a solver if we want to be strict about it (compute some global perturbation such that the constraints as satisfied?).

[pca006132]

The plan is to get this done after the csg tree changes.