A same Surface_mesh randomly got self intersections

[AlbertDeTerre]

Hello guys, I've got an issue that I can't understand while trying to compute intersection between two meshes.

Issue Details

My issue is that I got a "Self_intersection_exception" when trying to process a corefine_and_compute_intersection() method into a recursive function. Selft intersecting mesh appears to be "original_mesh". The weird thing is that "original_mesh" is not changing at all through my recursion process (See code below).

Source Code

Call of 'process_reshape' function

vector<Surface_mesh> remaining_cubes = process_reshape(obb_sm, mesh1, 0.2, 0.8, 5, 0);

Content of 'process_reshape' function

vector<Surface_mesh> process_reshape(Surface_mesh mesh_to_divide, Surface_mesh & original_mesh, double min_threshold, double max_threshold, int depth, int current_depth = 0){

    cout << "\nNEW ITERATION\n===============" << endl;

    // Check if depth has been reached --> return the current mesh if it has
    if (current_depth == depth){
        cout << "Depth reached !" << endl;
        return vector<Surface_mesh>{mesh_to_divide};
    }

    // Compute the intersection_mesh and calculate the volume ratio
    Surface_mesh intersection_mesh;

    cout << "Does original_mesh intersect ? " << PMP::does_self_intersect(original_mesh) << endl;
    cout << "Does mesh_to_divide intersect ? " << PMP::does_self_intersect(mesh_to_divide) << endl;

    bool has_intersection = CGAL::Polygon_mesh_processing::corefine_and_compute_intersection(original_mesh, mesh_to_divide, intersection_mesh, CGAL::parameters::throw_on_self_intersection(true));
    double volume_ratio = has_intersection ? (CGAL::Polygon_mesh_processing::volume(intersection_mesh) / CGAL::Polygon_mesh_processing::volume(mesh_to_divide)) : 0.0;

    cout << "Has intersection : " << (has_intersection ? "yes" : "no") << " --> Volume ratio = " << volume_ratio << endl;

    // If the volume ratio is between min and max threshold
    if (volume_ratio > min_threshold){

        // If it's greater than max threshold --> return the current mesh
        if (volume_ratio > max_threshold){
            cout << "ENDED --> Volume ratio > max_threshold" << endl;
            return vector<Surface_mesh>{mesh_to_divide};
        }

        // If not --> divide the mesh into 8 equal children
        cout << "Dividing mesh into 8 equal children" << endl;
        array<Surface_mesh, 8> created_children = divide_equally(mesh_to_divide);

        vector<Surface_mesh> to_return{};

        // Iterate through children to call the recursion for each child
        for (Surface_mesh child : created_children){
            vector<Surface_mesh> returned = process_reshape(child, original_mesh, min_threshold, max_threshold, depth, current_depth + 1);
            to_return.insert(to_return.end(), returned.begin(), returned.end());
        }

        cout << "ENDED --> Children list has been entirely processed" << endl;
        return to_return;
    }else{
        // If the volume ratio is less than the min threshold, it means that we don't want to keep the current mesh 
        cout << "ENDED --> Ratio is less than the min threshold" << endl;
        return vector<Surface_mesh>{};
    }

}

Output before the error is thrown

NEW ITERATION
===============
Does original_mesh intersect ? 1
Does mesh_to_divide intersect ? 0
terminate called after throwing an instance of 'CGAL::Polygon_mesh_processing::Corefinement::Self_intersection_exception'
  what():  Self-intersection detected in input mesh
Aborted (core dumped)

Environment

• Operating system: Linux 64bits
• Compiler: GCC (g++)
• CGAL version: 5.6.1
• Boost version: 1.75.0
• Other libraries versions if used (Eigen, TBB, etc.): Eigen 3.4.0

[MaelRL]

PMP::corefine_and_compute_intersection corefines both original_mesh and mesh_to_divide, meaning it modifies those meshes to add their intersection points and edges.

The kernel is missing from your snippet above, but likely you have an inexact construction kernel, and while the corefinement process is performed exactly, self-intersections can appear once you are back into your inexact kernel. Thus on your first iteration, everything is well, but at a further iteration (not necessarily the second), the mesh now has self-intersections and the throw mechanism rejects any further corefinement.

You can either:

• duplicate the mesh at each iteration if you are not interested in having original_mesh be modified by corefinement operations at all iterations.
• do everything with an exact kernel if you are.

[AlbertDeTerre]

Thanks for your fast answer ! Duplicating the mesh resolved the issue.

Have a nice day !