Premium
Efficient Image‐Based Proximity Queries with Object‐Space Precision
Author(s) -
Morvan T.,
Reimers M.,
Samset E.
Publication year - 2012
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2011.02084.x
Subject(s) - computer science , bounding volume , polygon mesh , minimum bounding box , bounding overwatch , object (grammar) , vertex (graph theory) , stencil , representation (politics) , triangle mesh , computer graphics (images) , image (mathematics) , computer vision , artificial intelligence , algorithm , theoretical computer science , collision detection , computational science , graph , computer security , politics , law , political science , collision
We 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.