Abstract:

We present a fast GPU-based streaming algorithm to perform collision queries between deformable models. Our approach is based on hierarchical culling and reduces the computation to generating different streams. We present a novel stream registration method to compact the streams and efficiently compute the potentially colliding pairs of primitives. We also use a deferred front tracking method to lower the memory overhead. The overall algorithm has been implemented on different GPUs and we have evaluated its performance on non-rigid and deformable simulations. We highlight our speedups over prior GPU-based and CPU-based algorithms. In practice, our algorithm can perform inter-object and intra-object computations on models composed of hundreds of thousands of triangles in tens of milliseconds.

(Min Tang, Dinesh Manocha, Jiang Lin, Ruofeng Tong, Collision-Streams: “Fast GPU-based Collision Detection for Deformable Models”, in Proceedings of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (i3D 2011), San Fransisco, CA, Feb. 18-20, 2011. http://gamma.cs.unc.edu/CSTREAMS)

This paper by Govindaraju et al. describes an approach for collision detection between multiple deformable and breakable objects in a large environment using graphics hardware. The algorithm uses a two-pass rendering scheme to compute a potentially colliding set (PCS) in linear time using visibility queries with no precomputation or frame buffer read back. ( CULLIDE: Interactive Collision Detection Between Complex Models in Large Environments Using Graphics Hardware. Naga Govindaraju, Stephane Redon, Ming C. Lin and Dinesh Manocha. To appear in Proceedings of Graphics Hardware 2003)

This SIGGRAPH 2002 course, organized by Dinesh Manocha of UNC Chapel Hill, covered approaches to using graphics hardware for various geometric problems, including voronoi computation, proximity
queries, motion planning, and more.