Union produces result with self-intersections

[dpapavas]

This zip file contains a test program that loads two OFF files (contained in the zip), computes their union, writes it to a file named c.off and finally tests for self-intersecting faces. The files are loaded as Polyhedron_3 or Surface_mesh objects (switchable) and Nef polyhedrons are used for the union.

The result contains self-intersections in both cases according to Meshalb, although they're detected only in one case. I believe that Meshlab is likely correct in both cases because when I try to remesh the result with some edges, selected via detect_sharp_edges, constrained, I get an assertion violation ('!get(ecmap_, edge(hf, mesh_))'), which I don't get when Meshlab detects no self-intersecting faces.

I think self-intersections are produced even when I use corefinement for the union, but I can't get a working test application right now. I can try again, if you think that would help.

[sloriot]

You must increase the stream precision to avoid even more rounding on the data.

CGAL::IO::write_OFF("c17.off", C, CGAL::parameters::stream_precision(17));

Also does_self_intersect() works on triangle meshes only. Calling PMP::triangulate_faces() first, I got a non self-intersecting C

[dpapavas]

Thanks for the quick response and please excuse my delay in replying. I thought I had checked with is_triangle_mesh() that the result was already a triangle mesh, but perhaps that was only the case for one of the mesh types, or perhaps I got confused altogether.

As I said, the reason I suspected the geometry, was because remeshing with edges constraints based on sharp edge detection led to an assertion violation. I had a hard time replicating the problem because, as it turns out, it only happens when the union is produced by corefinement and in debug build mode.

So, while I have no doubt that Meshlab is likley producing false positives on those self-intersecting faces, the assertion violation does seem to depend on some aspect of the geometry, since it only happens with corefinement.

I have created a new test application that illustrates the problem. If you build with -DCMAKE_BUILD_TYPE=Debug, it should throw an exception if USE_NEF is not defined. With Nef unions, or with -DCMAKE_BUILD_TYPE=Release, it should be fine. The mesh type doesn't seem to make a difference.

Let me know if you'd like me to close this issue and start a new one.

[sloriot]

If you add something like:

CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces(C, CGAL::parameters::collapse_length_threshold(1e-3).flip_triangle_height_threshold(1e-3));

before calling detect sharp features it should work.

There is actually a bug in isotropic_remeshing() that is having issues with dealing with close to degenerate elements while neighboring edges being constraints. @janetournois I tried to create a minimal example but it seems that it depends on the order of the elements in the mesh C.

[dpapavas]

Note that I could also provide with you with the original mesh with exact vertices, i.e. serialized with exact rational numbers, if that would help. I could also try to reduce vertices eges and faces as much as possible, although after a point, it stops exhibiting the problem.

[sloriot]

I mean, I can reproduce the bug with the full pipeline, but not if I'm reading only the generated mesh C (because I guess simplices are reordered).

[dpapavas]

I see. Again, if it helps here's a version where the finaly geometry (C) is loaded from a custom format using rationals and which does cause the assertion violation.