What is the reason that a boolean operation between two almost identical 3D triangular meshes fails?

Question

I have been trying to detect defects on "before-and-after" meshes, by finding the boolean difference between them, to no avail.

I tried these two Python libraries(algorithms run in C++) but their boolean operations would produce error or never finish:

• PyVista(VTK wrapper) : https://docs.pyvista.org
• Pymesh : https://pymesh.readthedocs.io

More specifically, some testing and findings that I had:

• The libraries would operate normally in any other case of boolean operations between two different meshes.
• The 2 almost-identical meshes I wanted to use were clean and water-tight. I even used an example shape which I subtracted from itself. It crashed too.
• These 2 similar meshes are originating from the same mesh, but with a small difference, like a dent or some noise. I tried to introduce stronger noise or bigger changes, but it still would not work if the 2 meshes had their biggest part identical.
• by enlarging 1 of the 2 meshes by more than 0.1%, or by transforming/moving(see attached picture) it by a similar amount, the algorithm starts working. But by that point, the shapes are too different to be useful.

To reproduce the error with Pyvista with an example shape from their website:

import pyvista as pv
mesh_knot = pv.read("knot.ply")
mesh_knot2 = pv.read("knot.ply")
mesh =  mesh_knot.boolean_difference(mesh_knot2)
mesh.plot(eye_dome_lighting=True)

To conclude, has anyone any idea why this would happen? Do you think that there is a way to bypass the problem if no solution is found? Any other ideas of how I should approach my initial problem?

Answer 1

Without debugging the routines with the offending data, it's impossible to say conclusively. However given the examples you have given it sounds like the libraries are falling foul of the coplanar triangle cases when evaluating the meshes. This is certainly an Achilles heel of many CSG implementations out there (far to many in my experience). In many cases, both theory and implementations seem to fail to address these coplanar cases in many CSG libs.

Certainly the fact that it crashes or fails to produce the desired result implies that the libraries you use are buggy or incomplete in this regard.

The libraries would operate normally in any other case of Boolean operations between two different meshes.

When there are no coplanar triangles between manifolds, the result is well defined and since CSG operations use triangle/triangle intersections fundamentally, if the case of coplanar triangle intersections is not accounted for, everything should be fine and dandy when there are no coplanar triangle tests between meshes. Of course this is not what you require, but makes sense that this operates normally in these scenarios.

The 2 almost-identical meshes I wanted to use were clean and water-tight. I even used an example shape which I subtracted from itself. It crashed too.

This is certainly not correct and I would say a bug. A crash implies something is very wrong and either the coplanar triangle support is buggy, limited, or simply not implemented at all.

I suspect the latter unless you can get a result out with something simple such as diff'ing one cube from another... if you can get a result in some sandboxed cases, then it could be any of the former possibilities.

To see if your CSG routines can handle the coplanar cases, subtracting one cube from another should produce nothing (which as you said it fails). You could also attempt to subtract one cube from another which has a single face coplanar. e.g. Two cubes, both of length length. One positioned at x - length should produce a cube which is a closed manifold. i.e. Cube A (1x1x1) positioned at 0,0,0... and cube B (1x1x1) positioned at 1,0,0.

These 2 similar meshes are originating from the same mesh, but with a small difference, like a dent or some noise. I tried to introduce stronger noise or bigger changes, but it still would not work if the 2 meshes had their biggest part identical.

Probably just one triangle in a mesh is coplanar to another triangle in the other mesh which you are operating on, and thus failing. This may be a way to test by creating two meshes with only one triangle from each mesh being coplanar to another in the other mesh. If this fails then It might indicate that this corner case of coplanar intersection is not catered for at all. As said above, if it does work, then this may point to buggy behaviour at much higher level when dealing with coplanar triangles.

By enlarging 1 of the 2 meshes by more than 0.1%, or by transforming/moving(see attached picture) it by a similar amount, the algorithm starts working. But by that point, the shapes are too different to be useful.

I presume these libs work on floating point numbers, in which case this sounds like the FP equality tolerances are kicking in and evaluating 'almost' coplanar triangles as coplanar, and then subsequently failing to result in the CSG operation. Of course this is problematic for you if the tolerances are high since the input geometry is expected to be 'different enough' to not fall within these tolerances.

Unfortunately, there is nothing you can really do which I think you would find satisfactory since you are effectively at the mercy of the accuracy of the implementation.

If you suspect the libs can handle coplanar triangles between meshes, and its just failing in many cases, you might need to find out how you can kludge the input geometry to not fall foul of the shortcomings that may or may not be present for these corner cases in the implementations:

• Remeshing the input geometry may help, although this may result is varying quality of input data in comparison to your measured data, which kind of defeats the purpose and will result in loss of accuracy wrt the original input meshes, but may at least give a result.

• Re-tessellating triangles while retaining the mesh features may help. This involves inserting Steiner points into a given triangle and re-tessellating into more triangles. This will result in larger meshes (mem footprint, not geometrically speaking) but may help the routines to resolve coplanar intersections. Unlike the previous suggestion, It will retain the accuracy of the topology of the original meshes though.

• Change the FP tolerance (if applicable) that the routines use which may allow you to keep meshes a similar size. However the problem is still there, but this may be satisfactory for your needs allowing you to not have to scale as much. Certainly from a visual standpoint this would be satisfactory I would have thought, however from a numerical point of view this may not be. However this does not fix the issue, rather attempt to circumvent it.

Given that the majority of the meshes will perhaps be similar, if the vertices are what are similar (i.e coplanar triangles have the SAME vertex values, although that screen shot you posted suggests otherwise) you could perhaps simply diff the meshes yourself, finding all the vertices that are not equal when comparing and then tessellating these. This is far more complex though as you would need to keep track of the edges around the different vertices (these edges will use vertices which are equal to others in the other mesh, so not a quick and dirty fix, rather a slightly different approach avoiding the libs you use) so that you can tessellate the different vertices into a meaningful manifold. I wouldn't recommend this as it is quite a specialised case, and may not be generalised enough for your needs.

Ultimately, if you can't circumvent the issue present with the current libs. You may have to find another. I certainly wasn't able to find many that matched my needs with a correct lic that was applicable to work, however I think there are certainly libs out there that would cater for this. Look for CAD libs as this is an important operation in many CAD programs.

A few years ago I spent some time testing and evaluating various different C++ CSG libs for our needs at work as we required a fairly robust implementation for production. While there were various success, they all failed at some point, and coplanar triangles were usually the culprit. It's quite frustrating as the answer is actually quite straight forward and simply requires the Boolean operation to be performed in 2D between the coplanar triangles and then testing if the resulting split triangles are within the 'other' triangle. Why this rather crucial point is missed in a lot of implementations and theory is beyond me. /rant