Failed to test mesh self-intersection using CGAL::Polygon_mesh_processing::does_self_intersect

[PickyBrownie]

Issue Details

Hi there!

I've been working with the Polygon Mesh Processing Package and attempted to test whether a triangulated surface mesh has any self-intersections. However, I ran into an issue where it seems to have failed to detect the intersections between two triangles within the mesh.

This particular triangulated surface mesh consists of 5 vertices and 2 faces. Strangely enough, when I used the bool CGAL::Polygon_mesh_processing::does_self_intersect function, it indicated that this mesh does not self-intersect, which is contrary to what I expected based on my visual inspection of the mesh.

Here are the coordinates of the vertices for reference:

• Vertices_1 coordinates: (97.1358, -291.711, 132.143)
• Vertices_2 coordinates: (97.14, -291.719, 132.147)
• Vertices_3 coordinates: (97.1361, -291.711, 132.144)
• Vertices_4 coordinates: (97.1298, -291.719, 132.145)
• Vertices_5 coordinates: (97.1289, -291.709, 132.148)

Mesh file was attached. Any help would be greatly appreciated!

intersection.zip

Source Code:

SurfaceMesh mesh1;
CGAL::IO::read_polygon_mesh(".../two_triangles.stl", mesh1);
if (PMP::does_self_intersect(mesh1))
	std::cout << "Input mesh self-intersects" << std::endl;
else
	std::cout << "Input mesh does not self-intersect" << std::endl;

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Linux
• CGAL version: CGAL 6.0.1

[sloriot]

In the file attached, you have two triangles that shares a point. So the triangle soup does not self-intersect. If you want to turn it into a mesh, you need to "orient" it so that non-manifold features are duplicated, creating a self-intersection then.

[sloriot]

The screenshot attached is not correctly representing the situation. Maybe a display issue of the software used (or a different rounding in the file provided)

[PickyBrownie]

In the file attached, you have two triangles that shares a point. So the triangle soup does not self-intersect. If you want to turn it into a mesh, you need to "orient" it so that non-manifold features are duplicated, creating a self-intersection then.

Thank you for your prompt response and kind help. In the previous file that I uploaded, I included just two triangles to simplify the problem.

In order to make the question clearer, I have uploaded a mesh file which actually has self-intersections.

When using Materialise Magics software, 6 self-intersecting triangles were detected in this mesh. However, when I applied the 'bool CGAL::Polygon_mesh_processing::does_self_intersect' function to check, it surprisingly returned false.

I'm confused about this discrepancy and would appreciate it if you could offer some insights or suggestions. Thanks again.
mesh.zip

[sloriot]

As you spotted there are some really badly shaped triangles but the mesh does not self-intersect. The other software is reporting a false positive. You can use the function CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces to get rid of those bad elements. MM might then be happy.

Actually checking the output I noticed that there is an issue in the aforementioned function. Indeed there is such a bad triangle that it is both a needle and a cap. But it cannot be handled as a needle due to topological constraints and the code moves away without trying to fix it as a cap (with a flip). I'll open a PR soon to fix that. Patch available in #8609. In the meantime, you can check the expected output with the attached file.
fd_copy_fixed.stl.gz