Collision detection has been a fundamental problem in computer animation, physically-based modeling, geometric modeling, and robotics. In these applications, interactions between moving objects are modeled by dynamic constraints and contact analysis. The objects' motions are constrained by various interactions, including collisions.

A virtual environment, like a walkthrough, creates a computer-generated world, filled with virtual objects. Such an environment should give the user a feeling of presence, which includes making the images of both the user and the surrounding objects feel solid. For example, the objects should not pass through each other, and things should move as expected when pushed, pulled or grasped. Such actions require accurate collision detection, if they are to achieve any degree of realism. However, there may be hundreds, even thousands of objects in the virtual world, so a naive algorithm could take a long time just to check for possible collisions as the user moves. This is not acceptable for virtual environments, where the issues of interactivity impose fundamental constraints on the system. A fast and interactive collision detection algorithm is a fundamental component of a complex virtual environment.

Physically based modeling simulations depend highly on the physical interaction between objects in a scene. Complex physics engines require fast, accurate, and robust proximity queries to maintain a realistic simulation at interactive rates. We couple our proximity query research with physically based modeling to ensure that our packages provide the capabilities of today's physics engines.

    We have designed and implemented the following collision detection systems.

• Fast Proximity Computation using Discrete Voronoi Diagrams
• CULLIDE
• DEEP
• SWIFT++
• PIVOT
• SWIFT
• H-COLLIDE
• PQP
• V-COLLIDE
• RAPID
• I-COLLIDE
• IMMPACT

  These systems have been applied to large-scaled interactive environments and simulations. None of the algorithms make any 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 constraints for an object in a complex simulation. We have been working on issues related to collision detection between massive models composed of millions of primitives. Our H-COLLIDE, a collision detection system for haptic interaction, has been used in an interactive multiresolution modeling and 3D painting system, called inTouch. Our PIVOT, Proximity Information from VOronoi Techniques, has been used in rigid- and deformable-body simulations, providing intersecting points, penetration depth, and separation distance in a penalty-based dynamics simulator.

For a brief description of all packages click here.

Papers and technical reports about the packages and related work.

These systems have been applied to large-scaled interactive environments and simulations. None of the algorithms make any 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 constraints for an object in a complex simulation. We have been working on issues related to collision detection between massive models composed of millions of primitives. Our H-COLLIDE, a collision detection system for haptic interaction, has been used in an interactive multiresolution modeling and 3D painting system, called inTouch. Our PIVOT, Proximity Information from VOronoi Techniques, has been used in rigid- and deformable-body simulations, providing intersecting points, penetration depth, and separation distance in a penalty-based dynamics simulator.

Other Recent Projects in Proximity Queries

• Fast Collision Detetion for Deformable Models using Representative-Triangles
  
• Generalized Penetration Depth Computation and Applications to Motion Planning
  
• Fast Proximity Computation Among Deformable Models using Discrete Voronoi Diagrams
• Collision Detection between Deformable Models using Chromatic Decomposition
• Quick-CULLIDE: Efficient Inter- and Intra-Object Collision Culling Using Graphics Hardware
• R-CULLIDE: Fast and Reliable Collision Culling using Graphics Hardware
• Fast Collision Detection between Massive Models using Dynamic Simplification
• Fast Continuous Collision Detection for Articulated Models
• Interactive, Continuous Collision Detection for Avatars in VEs
• CAB: Fast Collision Culling for Articulated Bodies
• CULLIDE: Interactive Collision Detection Between Complex Models in Large Environments Using Graphics Hardware
• CLODs: Dual Hierarchies for Multiresolution Collision Detection
• Fast Penetration Depth Estimation Using Rasterization Hardware and Hierarchical Refinement
• Dual-space Expansion for Estimating Penetration Depth
• Fast Penetration Depth Estimation for Elastic Bodies Using Deformed Distance Fields

• Ming C. Lin
• Dinesh Manocha
• Naga Govindraju
  

• Intel
  
• Honda
  
• National Science Foundation
  
• Office of Naval Research
  
• Army Research Office
• Department of Energy ASCI Program
  
• Alfred P. Sloan Foundation Fellowship
  
• University Research Award

• Young Kim
  
• Stephane Redon
  
• Nolan Walker
• Jon Cohen
  
• Stephen Ehmann
  
• Stefan Gottschalk
  
• Arthur Gregory
  
• Kenneth E. Hoff III
  
• Thomas Hudson
  
• Eric Larsen
  
• Amol Pattekar
  
• Madhav K. Ponamgi
  
• Andy Wilson
  
• Andrew Zaferakis