Collision Detection and Proximity Query Packages

We have designed and implemented the following collision detection and proximity query packages. 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 three-dimensional 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.

• CULLIDE: Interactive Collision Detection Between Complex Models in Large Environments Using Graphics Hardware
• DEEP: Dual-space Expansion for Estimating Penetration Depth
• DEFORMCD: Collision Detection for Deforming Objects
• H-COLLIDE: Fast and Accurate Collision Detection for Haptic Interaction
• I-COLLIDE: Interactive and Exact Collision Detection for Large-scaled Environments
• IMMPACT: Partitioning and Handling Massive Models for Interactive Collision Detection
• PIVOT: Proximity Information from Voronoi Techniques
• PQP: Fast Proximity Queries with Swept Sphere Volumes
• RAPID: Robust and Accurate Polygon Interference Detection
• SELF-CCD: Continuous Collision Detection for Deforming Objects
• Reliable Continuous Collision Detection
• SWIFT: Speedy Walking Via Improved Feature Testing
• SWIFT++: Speedy Walking Via Improved Feature Testing for Non-convex Objects
• V-COLLIDE: Accelerated Collision Detection for VRML
• DVD: Fast Proximity Computation Among Deformable Models Using Discrete Voronoi Diagrams