Real-Time Collision Detection Mpegs
Based on Hierarchical Incremental Computation

Collision detection is a fundamental problem in computer animation, computer graphics, physically-based modeling, and robotics. For applications and simulations in these domains to be convincing, they need to not only render realistic images, but also precisely model object interactions in the simulated environments.

We present several animations employing our collision detection work. The original sequences were generated at NTSC resolution and ran somewhere between 10 and 30 frames per second (i.e. "real time"). The performance you see when playing them back is clearly unrelated to their run-time performance.

Architectural Kitchen Simulation

Multi-body Simulation

This shows a real-time multi-body simulation of 300 objects of about 60 faces each colliding in a dense environment. The objects turn red when struck and bounce off each other. You can run the actual simulation using our free software.

Tori Simulation

This shows a complex simulation of a chain of interlinked tori of 400 faces each. The tori bounce off each other while computing the contact points. Notice this is a particularly difficult example involving non-convex objects in a dynamic simulation environment.

Composite Simulation

This shows a composite mpeg of the previous sections. It goes over the convex polytope distance tracking algorithm (Lin-Canny), multiple moving bodies algorithm, and non-convex collision detection algorithm. The simulations in this are all run in real-time.

Non-convex Simulation

This shows our approach for non-convex objects. We use a hierarchical incremental approach. We first determine if the convex hulls of the objects are intersecting, then we determine which features underneath the convex hulls are in contact. We classify the features of the object coincident with the convex hull as hull features (blue features), those within the concavity as cavity features (red features), and those on boundaries of these as boundary features .

Threaded Screw Simulation

This shows a threaded screw insertion using collision detection.

I_COLLIDE Collision Detection Package

Papers and Technical Reports

This research is supported by Alfred P. Sloan Research Foundation, DARPA ISTO Order No. A410, NSF Grant No. MIP-9306208, University Research Award, NSF Grant CCR-9319957, ARPA Contract DABT63-93-C-0048 and NSF/ARPA Science and Technology Center for Computer Graphics and Scientific Visualization, NSF Prime Contract No. 8920219 and Office of Naval Research contract, ONR N00014-94-1-0738.