Physics-Based Animation

Min Tang, Zhongyuan Liu,, Ruofeng Tong, Dinesh Manocha

We present a GPU-based self-collision culling method (PSCC) based on a combination of normal cone culling and spatial hashing techniques. We first describe a normal cone test front (NCTF) based parallel algorithm that maps well to GPU architectures. We use sprouting and shrinking operators to maintain compact NCTFs. Moreover, we use the NCTF nodes to efficient build an enhanced spatial hashing for triangles meshes and use that for inter-object and intra-object collisions. Compared with conventional spatial hashing, our approach provides higher culling efficiency and reduces the cost of narrow phrase culling. As compared to prior GPU-based parallel collision detection algorithm, our approach demonstrates 6?8X speedup. We also present an efficient approach for GPU-based cloth simulation based on PSCC. In practice, our GPU-based cloth simulation takes about one second per frame on complex scenes with tens or hundreds of thousands of triangles, and is about 4-6X faster than prior GPU-based simulation algorithms.

PSCC: Parallel Self-Collision Culling with Spatial Hashing on GPUs

X. L. Wang, M. Tang, D. Manocha, Ruo-Feng Tong

Bounding volume hierarchy (BVH) has been widely adopted as the acceleration structure in broad-phase collision detection. Previous state-of-the-art BVH-based collision detection approaches exploited the spatio-temporal coherence of simulations by maintaining a bounding volume test tree (BVTT) front. A major drawback of these algorithms is that large deformations in the scenes decrease culling efficiency and slow down collision queries. Moreover, for front-based methods, the inefficient caching on GPU caused by the arbitrary layout of BVH and BVTT front nodes becomes a critical performance issue. We present a fast and robust BVH-based collision detection scheme on GPU that addresses the above problems by ordering and restructuring BVHs and BVTT fronts. Our techniques are based on the use of histogram sort and an auxiliary structure BVTT front log, through which we analyze the dynamic status of BVTT front and BVH quality. Our approach efficiently handles inter- and intra-object collisions and performs especially well in simulations where there is considerable spatio-temporal coherence. The benchmark results demonstrate that our approach is significantly faster than the previous BVH-based method, and also outperforms other state-of-the-art spatial subdivision schemes in terms of speed.

Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring