Difference of meshes sometimes an empty mesh

[lassoan]

In some cases we get an error message like "Contact ends suddenly at point ..." and the resulting mesh is empty.

For example:

• subtracting fibula.vtk from guide.vtk results in an empty mesh
• subtracting fibula-dec.vtk from guide-dec.vtk (decimated versions of the two larger data sets) results in an empty mesh

Download meshes from here.

[zippy84]

Hi.

"Contact ends suddenly at point xy" is a common error when intersection lines are missing. They are often missing when involved polygons are almost parallel. In your example it is located here:

It's not really a bug. It is something like a missing feature.

[lassoan]

I understand that Boolean operation on meshes are almost impossible to solve (it is a little wonder that your library works so well). But at the same time, it would be important to get some result (even if it is approximation) for all inputs.

What do you recommend to do when we run into such problem? Or how such errors can be avoided?

Is it possible to adjust the tolerance value? Or would it be possible to get the cell or point index and add a small random displacement there (e.g., adding 0.01 mm random displacement may make the polygons non-parallel enough, yet it would not harm the meshing operation). Or do you have any other solution in mind? If you have an exact idea in mind of what you would want to do just did not have the time to work on it then we might be able to help implementing it.

[zippy84]

To avoid them is nearly impossible. When you try to alter the mesh, the problem can occurs on an another place.

The missing line could be constructed from the points of the adjacent lines. The missing line must be detected first. And then, the two points must be connected. But what if there are more than two points without a second intersection line?! The research for that is complicated and takes some time. I will try to add this feature in the refactored version.

Adjustable tolarances are btw not a good idea, because there are many and all of them are connected in some way. I already tried it.

[lassoan]

To avoid them is nearly impossible.

Have you tried something like adding random noise that is larger than the position tolerance but below the acceptable error for the user?

Adjustable tolarances are btw not a good idea, because there are many and all of them are connected in some way.

I agree that adjusting individual tolerances is hopeless and there is not much to tune on angle tolerances. However, it could be useful to have a general position tolerance error, as you cannot use the same tolerance on a model that has point coordinates in the range of -1000 to 1000, and on a model with points in the range of -1.0 to 1.0. You can try to get an approximate scale of the model by using the bounding box diameter (this is what most scale-dependent VTK filters do by default), but it may give misleading results if your structure is long and there may be other reasons why you want to use a smaller or larger tolerance value.

I will try to add this feature in the refactored version.

That would be awesome.

[zippy84]

you cannot use the same tolerance on a model that has point coordinates in the range of -1000 to 1000, and on a model with points in the range of -1.0 to 1.0

Absolutely. But up- and downscaling can cause other problems. Tolerances are very tricky for complex tasks.

You should also keep in mind, that the lib does not have any mesh optimization routines. Very sharp triangles for instance can also be a reason for the mentioned error.

[zippy84]

Not just one line is missing:

Exporting contLines.vtk
Exporting modPdA_1.vtk
Exporting modPdB_1.vtk
lineId 395, polyB 157939, edge (0, 1)
Missing line between 265328 and 158410.
lineId 396, polyB 158403, edge (1, 2)
Missing line between 265328 and 158410.
lineId 413, polyB 157465, edge (0, 1)
Missing line between 265030 and 157930.
lineId 414, polyB 157927, edge (0, 1)
Missing line between 265030 and 157930.
lineId 601, polyB 156572, edge (1, 2)
Missing line between 264495 and 157033.
lineId 604, polyA 264496, edge (0, 1)
Missing line between 264495 and 157033.
lineId 620, polyB 156546, edge (1, 2)
Missing line between 264463 and 157005.
lineId 623, polyA 264464, edge (0, 1)
Missing line between 264463 and 157005.

[zippy84]

A first result.

[lassoan]

Awesome! Thanks a lot for working on this. Let us know if there is a new version that we can test.

[zippy84]

I merged the changes into master.

[lassoan]

Thanks a lot. It gives perfect results for the meshes submitted in #39. For the meshes submitted in this issue it is much better:

• subtracting fibula.vtk from guide.vtk now returns an almost-perfect result (instead of just an empty mesh), there are only a few "blades" left

• unfortunately, subtracting fibula-dec.vtk from guide-dec.vtk (decimated versions of the two larger data sets) still results in an empty mesh

[zippy84]

Unfortunately I never tried the decimated versions. But I'm sure I can fix this, but not today.

[lassoan]

Sounds great, thank you for all your help.

[zippy84]

guide-dec.vtk is invalid. I figured out, that it contains some boundary edges. And one of them is involved in the intersection of the boolean operation. Therefore the filter cannot work properly. This is not fixable.

[lassoan]

Thanks for investigating this. What do you mean by "boundary edge" and what is the problem with them? It is fine if vtkbool has certain requirements for the input meshes as long as we have a recipe for detecting (and preferably fixing) any errors using VTK filters. If there are no existing VTK filters for this then we may be able to help with implementing them, but we need to know exactly what the problem is

[zippy84]

I meant non-manifold edges. Boundary edges are not a problem. Here is the non-manifold edge:

You can examine it by yourself. Select this cells: 35609, 22896, 35462 within modPdB_1. 35462 causing the problem. The intersection line of that ends abruptly. It is line 3658 in newLines.

non_manifold_edges.zip

[lassoan]

OK, thans for the clarification. I'll check if vtkFeatureEdges can correctly detect this edge and if we can fix this by removing the edge and fill holes.

[zippy84]

I'm closing this as the issue has been resolved.

[lassoan]

Great! Thank you for working on it.