Surface_mesh_simplification stuck in infinite loop

[Ylannl]

Issue Details

I am using the Surface_mesh_simplification package to simplify meshes with constraint edges. This has been working quite well for me so far. But, I have now stumbled upon a mesh that causes the edge_collapse algorithm to get stuck in an infinite loop.

Every time the program gets stuck here when the remaining edges is 80807 (out of an initial 139835, mesh provided below). Both in Release and Debug mode, and on two different machines. Before debugging we have tried waiting for over 10 hours for this mesh to simplify.

My debugger points me to this loop: https://github.com/CGAL/cgal/blob/c1ba814e4a05155094eb4b3ac02d794938efb2f1/Surface_mesh_simplification/include/CGAL/Surface_mesh_simplification/internal/Edge_collapse.h#LL765C26-L765C26

I have not investigated the issue further. But my suspicion is that the topology of the mesh is broken at some point during the simplification. And the assumption that we can circle around the edges incident to a vertex and come back to the starting edge at some point is violated.

The problematic mesh and minimal code to reproduce are given below. Notice that this is one of several million meshes that we are processing and only a dozen meshes cause this issue, so this is probably some exotic edge case. Nevertheless it would be really great if this can be fixed.

Source Code and problematic mesh to reproduce

I put everything needed to reproduce this issue in a repository: https://github.com/Ylannl/CGAL_Surface_mesh_simplification_inf_loop

This includes

• bacb.off: problematic mesh.
• CMakeLists.txt generated with cgal_create_CMakeLists utility.
• simplify.cpp source code to reproduce issue. Need to give path to bacb.off file as first argument.

Environment

• Operating system: Linux, 64 bits:
• Compiler: gcc 13.1.1
• Release or debug mode: both give the same issue
• CGAL version: 5.5.2
• Boost version: 1.81.0

[sloriot]

Could you try adding a call to duplicate_non_manifold_vertices() (and optionally to remove_isolated_vertices()) before doing the simplifcation?

[Ylannl]

This does indeed fix the issue. I added a call to duplicate_non_manifold_vertices() and now it runs through.

Thank you for you swift and helpful reply!

[Ylannl]

We have now stumbled upon a new geometry that causes this error, despite having the calls to duplicate_non_manifold_vertices() and remove_isolated_vertices() in place. I have tested with the latest CGAL master (40eccb897acd0634499692e1c3f918ff5a32ea7e), but this does not solve it.

I have updated my minimal example to add the new geometry: b9fe.off. This is the only feature out of the millions that we processed that leads to this infinite loop now.

[sloriot]

Could you try remove_isolated_vertices() and let us know if it helps?

[Ylannl]

Thanks again for your quick response! I have already tried remove_isolated_vertices(), because you had suggested it earlier as well, unfortunately it does not help in this case.

[sloriot]

OK I'll run it to check if I can reproduce then.

[MaelRL]

The issue is probably with the reader managing to create a broken mesh. It reminds me of https://github.com/CGAL/cgal/issues/4919, which also says it's valid even though it's broken.

Here is an alternative pipeline that works: https://gist.github.com/MaelRL/a67b593e5ddaa669427c1c24aa4543eb. It always goes through a polygon soup to perform a few fixes first, before converting to a mesh and proceeding as before (duplicate nm vertices, simplify, etc.).

[Ylannl]

Thanks for looking into it! I'm actually not using the OFF reader in my own software since the mesh comes from another file format (CityJSON, which does however store the mesh in the same way as OFF). I just add the vertices and faces manually to the SurfaceMesh, so fixing the OFF reader would not make a difference for my case. I only created the OFF file for my minimal example, so that the issue could be reproduced easily.

I could just adopt your pipeline and always go through the polygon soup repair functions, if this is not too expensive computationally. Or would you recommend another approach? Ie. would you just call those repair function from the OFF reader to fix this, or is there an alternative approach?

[MaelRL]

Thanks for looking into it! I'm actually not using the OFF reader in my own software since the mesh comes from another file format (CityJSON, which does however store the mesh in the same way as OFF). I just add the vertices and faces manually to the SurfaceMesh, so fixing the OFF reader would not make a difference for my case. I only created the OFF file for my minimal example, so that the issue could be reproduced easily.

What I meant with "fix of the reader" would actually affect you: there are two phases in read_polygon_mesh, one to read the file, one to build the mesh. There is no issue with the former. However, in the latter, we use Euler::add_face(vertex_range) and we think the problem here might be the other known issue where the builder adds a face and breaks the mesh whereas it should have rejected this new face.

Even if you build your Surface_mesh through Surface_mesh::add_face(), it's in fact the same function:

template <typename P>
template <typename Range>
typename Surface_mesh<P>::Face_index
Surface_mesh<P>::add_face(const Range& r)
{
  return CGAL::Euler::add_face(r, *this);
}

I could just adopt your pipeline and always go through the polygon soup repair functions, if this is not too expensive computationally. Or would you recommend another approach? Ie. would you just call those repair function from the OFF reader to fix this, or is there an alternative approach?

If we fix Euler::add_face and this affects some of your meshes, you will have no other choice than first go through a polygon soup because read_polygon_mesh() will return a reading failure.

You should of course bench it, but going through a polygon soup first and duplicating non-manifold elements before converting to a polygon mesh should be a barely noticeable change in runtime: when you read directly into a surface mesh, internally it's being read into a soup, and then we create the mesh from the soup. The function read_polygon_soup() does the former, and PMP::polygon_soup_to_polygon_mesh() is the latter part of CGAL::IO::read_polygon_mesh(). Thus, you would in fact be only adding duplicate_non_manifold_edges(), which has linear complexity.

You could maybe avoid PMP::repair_polygon_soup() - if you remove it, you should add back the isolated vertex removal -, but it will improve the robustness of your pipeline, and its cost should be negligible compared to the simplification function. Check its doc to see the list of performed operations.

And if your mesh has no issue, this is the same as doing CGAL::IO::read_polygon_mesh().

[Ylannl]

Thank you for your comprehensive reply @MaelRL. I really appreciate it.