The program occasionally experiences an infinite loop exception when performing remeshing.

zs0510 commented 4 weeks ago

Please use the following template to help us solving your issue.

Issue Details

I occasionally encounter an infinite loop issue when using Remeshing, and upon investigation, I found that the fix_degenerate_faces function has design flaws. There are two problems with this function: 1. Previously processed degenerate faces are processed repeatedly (because the face becomes degenerate again when processing other degenerate faces); 2. It doesn't avoid introducing new degenerate faces while fixing degenerate faces. On my own computer, I can temporarily avoid the program falling into an infinite loop by recording the processed degenerate faces. Below is my local solution code (with 3 new lines added) for reference only.

template<typename Bimap>
bool fix_degenerate_faces(const vertex_descriptor& v,
                          Bimap& short_edges,
                          const double& sq_low,
                          const bool collapse_constraints)
{
  std::unordered_set<halfedge_descriptor> degenerate_faces;
  std::unordered_set<halfedge_descriptor> visited_faces;// my code
  for(halfedge_descriptor h :
      halfedges_around_target(halfedge(v, mesh_), mesh_))
  {
    if(!is_border(h, mesh_) &&
       is_degenerate_triangle_face(face(h, mesh_), mesh_,
                                   parameters::vertex_point_map(vpmap_)
                                               .geom_traits(gt_)))
      degenerate_faces.insert(h);
  }

  if(degenerate_faces.empty())
    return true;

  bool done = false;
  while(!degenerate_faces.empty())
  {

    halfedge_descriptor h = *(degenerate_faces.begin());
    degenerate_faces.erase(degenerate_faces.begin());
    if (visited_faces.contains(h)) continue;// my code
    visited_faces.insert(h);// my code
    // ...
  }
#ifdef CGAL_PMP_REMESHING_DEBUG
  debug_status_map();
#endif
  return done;
}

Source Code

// at line 1686 of file include/CGAL/Polygon_mesh_processing/internal/Isotropic_remeshing/remesh_impl.h
template<typename Bimap, typename SizingFunction>
bool fix_degenerate_faces(const vertex_descriptor& v,
                                           Bimap& short_edges,
                                           const SizingFunction& sizing,
                                           const bool collapse_constraints)；

Environment

Operating system (Windows/Mac/Linux, 32/64 bits): Linux, 64 bits
Compiler: CLang 18.1.3 x86_64-pc-linux-gnu
Release or debug mode: Release
Specific flags used (if any):
CGAL version: CGAL_VERSION 5.6
Boost version: BOOST_VERSION 108300
Other libraries versions if used (Eigen, TBB, etc.):

afabri commented 4 weeks ago

Thank you for this bug report. Can you please give us a data set and the parameters of the call so that we can try to reproduce and fix.

zs0510 commented 4 weeks ago

Sorry I cannot provide the data. However, this might not affect your debugging, as the issue can already be discovered by examining the code.

afabri commented 4 weeks ago

Note that GeometryFactory can have a look under an NDA if that helps, and in case you use this algorithm professionally for Tencent.

afabri commented 4 weeks ago

The problem is still there. So let's not just put it under the carpet.

afabri commented 4 weeks ago

@zs0510 does your input mesh start with some degenerate faces, or were they produced by the remeshing itself?

zs0510 commented 4 weeks ago

Sorry I didn't see your comment in time. In my previous check, I remembered that the input mesh was without degenerate faces. I will check the input mesh again tomorrow.

zs0510 commented 4 weeks ago

I checked the mesh and found that the number of degenerate faces was 0 before remeshing.

afabri commented 3 weeks ago

What kernel do you use ? I ask as when using Exacxt_predicates_inexact_constructions_kernel no degenerate faces should be created.

sloriot commented 3 weeks ago

@zs0510 could you please try https://github.com/CGAL/cgal/pull/8418 and let us know if it fixes the issue you are having?

zs0510 commented 2 weeks ago

Sorry, I can't test it right now because the previous input data is now unavailable. The tool I'm working on involves a number of steps that are in iterative development. I will get in touch with you in time if this problem still occurs later. Thanks!

CGAL / cgal