Collision Detection for Virtual Environments and Simulations Using 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. The interactions may involve objects in the environment pushing, striking, or deforming other objects. Detecting collisions and determining contact points is of fundamental importance to portray these interactions accurately. Although the collision detection problem has been well-studied in the literature, building a general-purpose robust collision detection system remains an outstanding research challenge.
We have constructed a collision detection system based on incremental computation for large-scaled interactive environments and simulations. At a fundamental level the system's algorithm takes advantage of the coherence that exists from frame to frame to efficiently determine when a pair of objects are colliding. Our system has shown excellent behavior in complex scenes such as walkthrough environments and simulations consisting of hundreds of moving objects . Further, our algorithm makes no assumption on the motions of the objects; that is, their motions are not assumed to be expressible as a closed form function of time. In many applications, this is important because it can be difficult to predict a user's motion in a virtual environment or completely express the dynamic contraints for an object in a complex simulation.
We combine an incremental approach with a hierarchical algorithm to achieve efficiency and accuracy. The algorithm begins by paring down the number of object pair interactions to only those pairs within close proximity by sorting bounding boxes surrounding the objects using a new Sweep and Prune technique. Then for each such pair, it determines whether the convex hulls of these algorithms are colliding by traversing the external and internal Vornoi regions defined by each object's convex hulls. It localizes the intersection on the convex hulls and goes underneath the hulls to see which actual features are colliding by recursively re-applying the Sweep and Prune technique and traversing the pre-computed hierarchies of the objects. Typically, the inter-object's collision status does not change between each iteration so the algorithm solves the problem incrementally, using the previous geometric information as the starting point.
The algorithm's implementation has been successfully used in walkthough applications and simulations such a nut and bolt apparatus.
Current Research Directions
We have a proto-type working collision detection system. We are in the process of refining it to make it a more robust system. There remain many interesting geometric issues to address.
