Infinite loop in Mean_curvature_flow_skeletonization::contract_geometry

ssapir commented 7 months ago

Issue Details

Function contract_geometry can get stuck in an infinite loop on some meshes. This happens in function Point_inside_vertical_ray_cast::operator() in do-while loop.

Functions trace-back: https://github.com/CGAL/cgal/blob/master/Surface_mesh_skeletonization/include/CGAL/Mean_curvature_flow_skeletonization.h#L959

https://github.com/CGAL/cgal/blob/3b8666323e3daa76227b7ff178d889f375c83737/Polygon_mesh_processing/include/CGAL/Side_of_triangle_mesh.h#L270

https://github.com/CGAL/cgal/blob/3b8666323e3daa76227b7ff178d889f375c83737/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/internal/Side_of_triangle_mesh/Point_inside_vertical_ray_cast.h#L88

The same code works for similar meshes (e.g. with unconnected components etc), and I couldn't find a clear reason why this one is stuck.

Source Code

Can be replicated using Surface_mesh_skeletonization/examples/Surface_mesh_skeletonization/simple_mcfskel_example.cpp with the attached off file (test10.off in the zip file). Get stuck on vd with id 112209 (as calculated by "int id = static_cast(get(m_vertex_id_pmap, vd));").

Which contains the code:

typedef CGAL::Mean_curvature_flow_skeletonization<Polyhedron> Skeletonization;
typedef Skeletonization::Skeleton                             Skeleton;

std::ifstream input_f("test10.off");
Polyhedron tmesh;
input_f >> tmesh;
Skeleton skeleton;
CGAL::extract_mean_curvature_flow_skeleton(tmesh, skeleton);

Data

test10.zip

Environment

Operating system (Windows/Mac/Linux, 32/64 bits): linux 64 bit (gentoo)
Compiler: gcc 9.3.0
Release or debug mode: Release
Specific flags used (if any): none (using eigen3 for Mean_curvature_flow_skeletonization)
CGAL version: 5.5.1
Boost version: 1.75.0
Other libraries versions if used (Eigen, TBB, etc.): Eigen 3.3.7

afabri commented 7 months ago

Your mesh has boundaries, consists of several connected components. So what do you expect????

ssapir commented 7 months ago

I appologize the above wasn't clear. I'm writing an infrastructure that uses the above code, with no control over the input from users. While very similar meshes (with the same features as written in the above answer) works perfetcly, others cause an infinite loop. I wish to add a protection from these cases and to raise relevant and clear errors since it cannot be stuck in an infinite loop, for our usage.

As it's not clear to me when it will be stuck and when it won't (I couldn't find in the documentation or code a reason that could distinct the two cases), I'm asking here to undetstand the specific problem causing an inifinite loop in order to validate and protect the code with a clear error for the user. I can try to continue debugging it myself and add a possible protection / fix when I'll find the reason. Just tried to consult with you first, to get a better direction/understanding of the problem.

Re. this:

The amount of connected compoents is not the problem (your code can deal with this case and find a good skeleton nontheless, I can upload examples).
I forgot to add. Several errors are fixed as part of loading a valid Polyhedron_3 (using functions from here: https://doc.cgal.org/latest/Polygon_mesh_processing/group__PMP__IO__grp.html. I can elaborete if needed). Some of the problems are indeed marked in the figure above... however, these were fixed, but the infinite loop still happens.
I'm not sure what do you mean by boundries. Can you please elaborate? (I can't find in the documentation or example cpp code any relevant assumption/limit on the input mesh)

Thank you for the answer!

afabri commented 2 months ago

We clearly state on the reference manual page that the input mesh tmesh is a triangle mesh without borders and having exactly one connected component. Withut borders means that each triangle has three neighbor triangles.

CGAL / cgal