Get closest points between (convex) meshes quickly

[JYChen18]

Hi,

I have 100 or even 1000 parallel scenarios, each containing the same two triangle meshes with different poses. I need a fast way to find the closest points between the two meshes in each scenario.

warp.sim.collide() provides an example, but it has to iterate over all vertices and thus is inefficient when the mesh vertice number is large.

I have found some existing libraries for calculating the closest points for convex meshes, e.g. libccd. However, to the best of my knowledge, none of them can handle parallel scenarios on GPU with an easy-to-use Python plug-in.

Is it possible to include libccd (or other methods) in Warp? I am unfamiliar with C++ and CUDA, so I am not sure about the effort it needs. Any help or advice will be appreciated.

[eric-heiden]

Hi @JYChen18,

Here are some potential ideas for finding the closest points efficiently:

You can reduce the mesh resolution and launch Warp kernels for the different poses for the number of vertices in parallel (so each vertex of the simplified mesh is assigned to one GPU thread). This could give you some approximate closest points which you can then use to find the actual closest points on the original meshes by only querying points in the vicinity of the vertices on the simplified meshes.

Perhaps one could leverage some iterative voxelization where you precompute different levels of detail (voxel resolutions) for both meshes and first find the closest voxels (i.e. based on voxel centroids) on the lowest level of detail and successively query voxels at a finer resolution until you reach the level of actual mesh vertices to find the true closest points. This avoids checking all potential pairs of mesh vertices.

Other approaches could leverage the Flexible Collision Library which appears to have Python bindings: https://pypi.org/project/python-fcl/
Check out the section on "broadphase checking" which seems to work with multiple objects at the same time, although the library appears to be written only for CPU support. Perhaps it might be feasibly to implement GJK and EPA to find the closest pairs for convex meshes in Warp.