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 motions of the objects 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.

• Efficient Probabilistic Collision Detection for Non-Convex Shapes, Projects Collection
• CAMA: Contact-Aware Matrix Assembly with Unified Collision Handling for GPU-based Cloth Simulation, EUROGRAPHICS 2016
• Efficient Penetration Depth Computation between Rigid Models using Contact Space Propagation Sampling, IEEE RA-L 2015
• Interactive Continuous Collision Detection for Topology Changing Models Using Dynamic Clustering, I3D 2015
• TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds, PG 2015
• Fast and Exact Continuous Collision Detection with Bernstein Sign Classification, SIGGRAPH Asia 2014
• VolCCD: Fast Continuous Collision Culling between Deforming Volume Meshes, ACM TOG 2011
• Collision-Streams: Fast GPU-based Collision Detection between Deformable Models, I3D 2011
• Fast Continuous Collision Detection using Deforming Non-Penetration Filters, I3D 2010
• CCQ: Efficient Local Planning using Connection Collision Query, WAFR 2010
• Multi-core Collision Detection Between Deformable Models Using Front-based Decomposition, Graphical Models 2010
• Fast Collision Detection for Deformable Models using Representative-Triangles , I3D 2008
• Generalized Penetration Depth Computation and Applications to Motion Planning, Projects Collection
• Interactive Continuous Collision Detection Between Deformable Models Using Connectivity-based Culling, SPM 2008
• Interactive Collision Detection Between Deformable Models Using Chromatic Decomposition, SIGGRAPH 2005
• Efficient Inter- and Intra-object Collision Culling Using Graphics Hardware, IEEE VR 2005
• Fast and Reliable Collision Culling Using Graphics Processors, VRST 2004
• Fast Collision Detection between Massive Models using Dynamic Simplification, SGP 2004
• Fast Continuous Collision Detection for Articulated Models, SM 2004
• Interactive and Continuous Collision Detection for Avatars in Virtual Environments, IEEE VR 2004
• CAB: Fast Update of OBB Trees for Collision Detection Between Articulated Bodies, Journal of Graphics Tools 2004
• CLODs: Dual Hierarchies for Multiresolution Collision Detection, SGP 2003
• Fast Penetration Depth Computation Using Rasterization Hardware and Hierarchical Refinement, Projects Collection
• Fast Penetration Depth Estimation for Elastic Bodies Using Deformed Distance Fields, IROS 2001