Naga K. Govindaraju, Stephane Redon, Ming C. Lin, and Dinesh Manocha
Environment with breakable objects: As the bunny (with 35K triangles), falls through the dragon (with 250K), the number of objects in the scene (shown with a yellow outline) and the triangle count within each object change. Our algorithm computes all the overlapping triangles during each frame. The average collision query time is 35 milliseconds per frame.
We present a novel approach for collision detection between multiple deformable and breakable objects in a large environment using graphics hardware. Our algorithm takes into account low bandwidth to and from the graphics cards and computes a potentially colliding set (PCS) using visibility queries. It involves no precomputation and proceeds in multiple stages: PCS computation at an object level and PCS computation at sub-object level, followed by exact collision detection. We use a linear time two-pass rendering algorithm to compute each PCS efficiently. The overall approach makes no assumption about the input primitives or the object's motion and is directly applicable to all triangulated models. It has been implemented on a PC with NVIDIA GeForce FX 5800 Ultra graphics card and applied to different environments composed of a high number of moving objects with tens of thousands of triangles. It is able to compute all the overlapping primitives up to image-space resolution in a few milliseconds.
Environment 1: This scene consists of 100 dynamically deforming open cylinders moving randomly in a room. Each cylinder is composed of 200 triangles.
 |
 |
| Environment 3: Wired frame of dragon and bunny rendered in the following colors - {cyan,blue} highlight triangles in the PCS, {red, white} illustrate portions not in the PCS. Dragon consists of 250K triangles and the bunny consists of 35K faces. | Environment 3: Zoomed view highlighting the exact intersections between the triangles in the PCS. The configuration of the two objects is the same as wireframe view. The cyan and blue regions are the overlapping triangles of the dragon and bunny respectively. |
Snapshots of simulations on two complex environments. Our collision detection algorithm takes 4, 40ms respectively on each benchmark to perform collision queries on a GeForce FX 5800 Ultra with an image resolution of 800 x 800.
CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
(919) 962-1749
geom@cs.unc.edu