• Home
• About GAMMA
• News
• Papers
• People
• Research
• Software
• Sponsors
• Videos
• Internal

Collision Detection and Proximity Queries  

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.

Collision Detection and Proximity Query Packages

We have designed and implemented the following collision detection systems.

• Collision detection between deformable models
• Fast proximity computation using discrete Voronoi diagrams
• CULLIDE
• DEEP
• H-COLLIDE
• I-COLLIDE
• IMMPACT
• PIVOT
• PQP
• RAPID
• SWIFT
• SWIFT++
• V-COLLIDE

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 collision detection system for haptic interaction has been used in an interactive multi-resolution modeling and 3D painting system, called inTouch. The PIVOT system, 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 our packages click here.

Other Recent Projects in Collision Detection and Proximity Queries

• Multi-core collision detection
• Collision avoidance between multiple agents
• Fast collision detection 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 virtual environments
• CAB: Fast collision culling for articulated bodies
• CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware
• CLODs: Dual hierarchies for multi-resolution 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

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.