vtkCollisionDetectionFilter minimum distance between surfaces

I am using the vtkCollisionDetectionFilter to know if two meshes intersect or not. This works fine (GetNumberOfContacts).

In the case where they do not interesect, I would be interested in calculating the minimum distance between those meshes (closest approach). → A full C++ implementation of min distance between triangles is contained in the TriDist.cpp of the just mentioned link.

Is there an algorithm in VTK to obtain this taking into account not only the vertices of each triangle but also their surfaces? Or do you know any other Python package / script that works with two vtkPolyData and performs this calculation?

I found this post from 2013 mentioning the possibility of using pybullet, but not sure if things have changed in VTK since.

Thanks in advance!

You can use vtkImplicitPolyDataDistance to get closest point on a surface. It properly takes into account all the surfaces, not just the points.

Thanks for the suggestion. However this would require passing a point X to get the nearest distance to a surface? I was looking more into a more general algorithm, as the minimum distance might be between two inside points in the respective surfaces of mesh A and mesh B.

Specifically, as I am using STL files, I would be interested in this algorithm is implemented in VTK (or could be in the future).

What is your overall goal?

I have a module that ensures there is no collision between a patient surface and a radiotherapy equipment. However, i do not want to be super-close to the patient, a security margin is needed. Thus I want to calculate the minimum distance between the equipment and the patient.

Both the patient and the machine are STL model files. The equipment is sometimes a big rectangular surface, with only a couple of tesselated triangles, thus it is needed to calculate not only collision with the vertices but the overall minimum distance including areas inside the respective triangles of each mesh.

The STL files that you export from a CAD software are typically intended for visualization and 3D printing and not for analysis. Since you need to have a dense mesh for storing closest distances anyway, I would recommend to remesh the low-quality meshes to have fairly uniform cell sizes.

In general, I agree with your statement.

However, for the patient’s couch 3d model, which is usually a large flat surface 3m long x 0.7m wide, it would be an overhead (extra memory, more computation time) to split it in a dense mesh of small triangles.
Also, the treatment head is usually already a large file (>10Mb) and some parts of it are flat also large (1m).

In those cases, having a PQP function to compare the minimum distance between two “big” 3D triangles would be more efficient than remeshing everything into small triangles and looping over all vertices. Note that the idea is to use interactive sliders to rotate in real-time gantry angle, couch position, and report immediately distance of approach, so the calculation efficiency is important.

VTK has so many methods for representing the data (as polygons, distance maps, label maps), you have fast locators, contour filters, implicit modeler, implicit polydata distance, etc. several of them are highly optimized, so it is unlikely that you would benefit from using an external library for any of your computations.

There are many approaches that can give you accurate and fast detection of near misses. The details depend on what exactly you want to show to the user and how, but assuming you want to highlight points where the pieces may come closer than a given distance then this will probably work well:

  • Keep the CAD-exported non-uniform mesh for display, but create a low-resolution mesh(es) with uniform cell sizes for distance computation and collision detection.
  • Generate the uniform mesh by using vtkImplicitModeller + a contour filter (such as the fast vtkFlyingEdges3D filter).
  • Use multiple meshes: compute the meshes with multiple distance thresholds (e.g., low-risk, high-risk, collision) by adjusting the distance in vtkImplicitModeller.
  • Use the mesh resolution appropriate for the distance threshold. Large distance threshold allows you to use a coarser mesh. Resolution can be set using sample dimensions property of vtkImplicitModeller.
1 Like