Naga K. Govindaraju, Ming C. Lin, and Dinesh Manocha
Environment with breakable objects: As the bunny (with 35K triangles), falls through the dragon (with 112K), 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 reliable culling algorithm that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs to eliminate a subset of primitives that are not in close proximity. To overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. Our algorithm can perform reliable GPU-based collision queries at interactive rates on all types of models, including non-manifold geometry, deformable models, and breaking objects.
Reliable interference computation: This image highlights the intersection set between two bunnies, each with 68K triangles. The top right image (b) shows the output of FAR and the top left image (a) highlights the output of CULLIDE running at a resolution of 1400 x 1400. CULLIDE misses many collisions due to the viewport resolution and sampling errors.
Tree with falling leaves: In this scene, leaves fall from the tree and undergo non-rigid motion. They collide with other leaves and branches. The environment consists of more than 40K triangles and 150 leaves. FAR can compute all the collisions in about 35 msec per time step.
CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
(919) 962-1749
geom@cs.unc.edu