Morvan, T.Reimers, M.Samset, E.Holly Rushmeier and Oliver Deussen2015-02-282015-02-2820121467-8659https://doi.org/10.1111/j.1467-8659.2011.02084.xWe present an efficient algorithm for object-space proximity queries between multiple deformable triangular meshes. Our approach uses the rasterization capabilities of the GPU to produce an image-space representation of the vertices. Using this image-space representation, inter-object vertex-triangle distances and closest points lying under a user-defined threshold are computed in parallel by conservative rasterization of bounding primitives and sorted using atomic operations. We additionally introduce a similar technique to detect penetrating vertices. We show how mechanisms of modern GPUs such as mipmapping, Early-Z and Early-Stencil culling can optimize the performance of our method. Our algorithm is able to compute dense proximity information for complex scenes made of more than a hundred thousand triangles in real time, outperforming a CPU implementation based on bounding volume hierarchies by more than an order of magnitude.10.1111/j.1467-8659.2011.02084.x