Euler::collapse_edge creates invalid Polyhedron_3

[raphaelsulzer]

Issue Details

I am trying to iteratively collapse short edges of a Polyhedron_3 with triangle faces only.
I have used the code below to collapse thousands of examples, but I now have a case where the Polyhedron is_valid() assertion becomes false after a few edge collapses.

Source Code

My Polyhedron_3 is this:

template <class Refs, class Traits>
struct My_face : public CGAL::HalfedgeDS_face_base<Refs> {

    typename Traits::Triangle_2 triangle;
    double area = -1;
    int id = -1;

};

template <class Refs>
struct My_hedge : public CGAL::HalfedgeDS_halfedge_base<Refs> {
    
    int id = -1;
    ppr::Halfedge_type type = ppr::Halfedge_type::unknown;

};

template <class Refs, class Traits>
struct My_vertex : public CGAL::HalfedgeDS_vertex_base<Refs> {

    int id = -1;
    typedef typename Traits::Point_3 Point;

    Point   p;
    My_vertex() {}
    My_vertex( const Point& pp) : p(pp) {}
    Point&                point()                           { return p; }
    const Point&          point() const                     { return p; }

};

// An items type using my face.
struct My_items : public CGAL::Polyhedron_items_3 {
    template <class Refs, class Traits>
    struct Face_wrapper {
        typedef My_face<Refs, Traits> Face;
    };
    template <class Refs, class Traits>
    struct Halfedge_wrapper {
        typedef My_hedge<Refs> Halfedge;
    };
    template <class Refs, class Traits>
    struct Vertex_wrapper {
        typedef My_vertex<Refs,Traits> Vertex;
    };
};

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Polyhedron_3<Kernel,My_items> Polyhedron;

I build up the polyhedron from a CDT, thus I never call triangulate_faces() or anything like that on it.
But for the first few iterations the is_pure_triangle() assertion is true.

My code to collapse is this:

template <typename Kernel>
bool PPRepair<Kernel>::collapse_short_edges(double min_edge_length){

    BOOST_LOG_TRIVIAL(debug) << "Collapse edges shorter than " << min_edge_length;

    bool was_modified_global = false;
    bool was_modified_loop = false;
    Halfedge_type type;

    do{
        assert(!_polyhedron.is_empty());
        if(!_polyhedron.is_valid(false)){
            assert_polyhedron.is_valid(true));
        }
        assert(_polyhedron.is_pure_triangle());

        vector<Polyhedron::Halfedge_handle> hedges;
        for(auto& hedge : _polyhedron.halfedge_handles()){
            boost::graph_traits<Polyhedron>::edge_descriptor e(hedge);
            if(CGAL::is_valid_halfedge_descriptor(hedge,_polyhedron) && CGAL::Euler::does_satisfy_link_condition(e,_polyhedron));
                hedges.push_back(hedge);
        }

        for(auto& hedge : hedges){
            was_modified_loop = false;

            double length = CGAL::Polygon_mesh_processing::edge_length(hedge, _polyhedron);

            if (length < min_edge_length)
            {   

                boost::graph_traits<Polyhedron>::edge_descriptor e(hedge);
                if(!CGAL::Euler::does_satisfy_link_condition(e,_polyhedron))
                    continue;
                
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                ///////// Not relevant here, but the reason why I do not want to use any higher level function //////////

                type = hedge->next()->opposite()->type;
                if(type == Halfedge_type::unknown){
                    hedge->next()->opposite()->type = hedge->prev()->type;
                }
                type = hedge->next()->type;
                if(type == Halfedge_type::unknown){
                    hedge->next()->type = hedge->prev()->opposite()->type;
                }
                type = hedge->opposite()->next()->opposite()->type;
                if(type == Halfedge_type::unknown){
                    hedge->opposite()->next()->opposite()->type = hedge->opposite()->prev()->type;
                }
                type = hedge->opposite()->next()->type;
                if(type == Halfedge_type::unknown){
                    hedge->opposite()->next()->type = hedge->opposite()->prev()->opposite()->type;
                }
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

                CGAL::Euler::collapse_edge(e, _polyhedron);
                was_modified_global = true;
                was_modified_loop = true;
                break;
            }
        }
    }while(was_modified_loop);
    return was_modified_global;
}

After a few collapses the is_valid() assertion is false with:

begin CGAL::HalfedgeDS_const_decorator<HDS>::is_valid( verb=true, level = 3):
halfedge 0
    vertex pointer integrity2 corrupted.
sum border halfedges (2*nb) = 0
end of CGAL::HalfedgeDS_const_decorator<HDS>::is_valid(): structure is NOT VALID.
counting halfedges failed.
end of CGAL::Polyhedron_3<...>::is_valid(): structure is NOT VALID.

I am confused because the code works well for thousands of examples, but now I am not even sure if my Polyhedron_3 definition is correct. Do I need to add a is_border() method to My_hedge and set the value myself? Or what am I doing wrong here?

I am aware that my code can lead to geometric degeneracies, but I am not concerned about them in this function. I simply do not understand why the HDS becomes invalid from the edge collapses.

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Linux 64 bits
• Compiler: GCC 14.2.1
• Release or debug mode: Debug
• Specific flags used (if any):
• CGAL version: 6.0.1
• Boost version: 1.83
• Other libraries versions if used (Eigen, TBB, etc.):

[sloriot]

Could it be that you have non-manifold vertices?