Department of Computer Science and Engineering Ewha Womans University, Seoul, Korea {zhangxy,kimy}@ewha.ac.kr 
Abstract
We present an interactive and accurate collision detection algorithm for deformable, polygonal objects based on the streaming computational model. Our algorithm can detect all possible pairwise primitivelevel intersections between two severely deforming models at highly interactive rates.
In our streaming computational model, we consider a set of axis aligned bounding boxes (AABBs) that bound each of the given deformable objects as an input stream and perform massivelyparallel pairwise, overlapping tests onto the incoming streams. As a result, we are able to prevent performance stalls in the streaming pipeline that can be caused by expensive indexing mechanism required by bounding volume hierarchybased streaming algorithms. At runtime, as the underlying models deform over time, we employ a novel, streaming algorithm to update the geometric changes in the AABB streams. Moreover, in order to get only the computed result (i.e., collision results between AABBs) without reading back the entire output streams, we propose a streaming en/decoding strategy that can be performed in a hierarchical fashion. After determining overlapped AABBs, we perform a primitivelevel (e.g., triangle) intersection checking on a serial computational model such as CPUs.
We implemented the entire pipeline of our algorithm using offtheshelf graphics processors (GPUs), such as nVIDIA GeForce 6800, for streaming computations, and Intel Pentium 4 processors for serial computations. We benchmarked our algorithm with different models of varying complexities, ranging from 15K up to 50K triangles, under various deformation motions, and the timings were obtained as 30~100 FPS depending on the complexity of models and their relative configurations. Finally, we made extensive comparisons with a wellknown GPUbased collision detection algorithm, CULLIDE and observed about three times performance improvement over the earlier approach. 
Key Words
Collision Detection, Deformable Models, Programmable Graphics Hardware, Streaming Computations, AABB 
Full Text
Download Video

Benchmarking Scenarios
Benchmark Set I: Each torus consists of 15K triangles and the wave deformation is adopted to simulate the deformation. (a) Interlocking torii: our algorithm can exactly compute all the colliding triangle pairs at update rate of 6080 FPS. (b) Touching torii: our algorithm can exactly compute all the colliding triangle pairs at update rate of 90100 FPS. (c) Merging torii: our algorithm can exactly compute all the colliding triangle pairs at update rate of 2530 FPS.
Benchmark Set II: The pulsating deformation is adopted to simulate the deformation. (a) Bump Bunnies: Each bunny consists of 15K triangles. Our algorithm can exactly compute all the colliding triangle pairs at update rate of 5060 FPS. (b) Happy Buddhas: Each Buddha consists of 20K triangles. Our algorithm can exactly compute all the colliding triangle pairs at update rate of 2540 FPS. (c) Intimate Animals: Each animal consists of 50K triangles. Our algorithm can exactly compute all the colliding triangle pairs at update rate of 2035 FPS.
Copyright 2005 Computer Graphics Laboratory Dept of Computer Science & Engineering Ewha Womans University, Seoul, Korea Last update: December 24, 2005 