# Real-Time Collision Detection Mpegs Based on Hierarchical Incremental Computation

### Research Team

Jonathan D. Cohen
Ming C. Lin
Dinesh Manocha

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

This shows a hand interacting with hundreds of objects in a kitchen architectural environment. Note we detect the exact contact points (the hand's fingers turning red indicates contact).

## 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 .