Collision Detection

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.

Publications

• .
Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring  2018.
Eurographics

PDF Google Scholar Collision Detection

• .
I-Cloth: Incremental Collision Handling for GPU-Based Interactive Cloth Simulation  2018.
ACM Transactions on Graphics

PDF Project Video Google Scholar Animation Collision Detection

• .
Multi-contact Frictional Rigid Dynamics using Impulse Decomposition  2017.
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2017)

PDF Google Scholar Geometric Collision Detection

• .
Efficient Penetration Depth Computation between Rigid Models using Contact Space Propagation Sampling  2016.
IEEE Robotics and Automation Letters

PDF Project Google Scholar Collision Detection

• .
CAMA: Contact-Aware Matrix Assembly with Unified Collision Handling for GPU-based Cloth Simulation  2016.
Computer Graphics Forum, (Proceedings of Eurographics 2016)

PDF Project Video Google Scholar GPGPU Collision Detection Geometric

• .
Interactive Continuous Collision Detection for Topology Changing Models Using Dynamic Clustering  2015.
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games

PDF Google Scholar Collision Detection Robotics Animation

• .
Efficient Global Penetration Depth Computation for Articulated Models  2015.
Computer-Aided Design (Proceedings of GDSPM, Geometric Design and Solid and Physical Modeling)

PDF Google Scholar Collision Detection Robotics

• .
TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds  2015.
Pacific Graphics 2015

PDF Project Video Google Scholar Collision Detection

• .
Efficient Configuration Space Construction and Optimization for Motion Planning  2015.
Engineering

Project Google Scholar Robotics Collision Detection Collision Avoidance GPGPU

• .
Ped-Air: a Simulator for Loading, Unloading, and Evacuating Aircraft  2014.
Pedestrian and Evacuation Dynamics 2014

PDF Video Google Scholar Crowd Simulation Robotics Collision Avoidance Collision Detection

• .
Real-time Collision Detection and Distance Computation on Point Cloud Sensor Data  2013.
ICRA

PDF Google Scholar Collision Detection

• .
A GPU-based Streaming Algorithm for High-Resolution Cloth Simulation  2013.
Computer Graphics Forum (Proc. of Pacific Graphics)

PDF Project Video Google Scholar Animation Collision Detection

• .
Efficient Penetration Depth Computation using Active Learning  2013.
ACM Trans. on Graphics (Proc. of SIGGRAPH ASIA)

PDF Project Google Scholar Collision Detection Animation

• .
Continuous Penetration Depth  2013.
Computer-Aided Design (Proc. of SIAM Conference on Geometric and Physical Modeling)

PDF Project Google Scholar Collision Detection Robotics Animation

• .
GPU-based Parallel Collision Detection for Fast Motion Planning  2012.
International Journal of Robotics Research (IJRR)

PDF Project Google Scholar GPGPU Collision Detection Robotics

• .
FCL: A General Purpose Library for Collision and Proximity Queries  2012.
IEEE International Conference on Robotics and Automation (ICRA)

PDF Project Google Scholar Collision Detection

• .
Technical Perspective: Building Robust Dynamical Simulation Systems  2012.
Communications of the ACM (CACM)

PDF Project Google Scholar Collision Detection Animation

• .
Continuous Penalty Forces  2012.
ACM Transactions on Graphics (Proc ACM SIGGRAPH)

PDF Project Video Google Scholar Animation Collision Detection

• .
Collision-free and Smooth Trajectory Computation in Cluttered Environments  2012.
International Journal of Robotics Research (IJRR)

PDF Project Video Google Scholar Collision Detection Robotics

• .
CCQ: Efficient Local Planning Using Connection Collision Query  2011.
Algorithmic Foundations of Robotics IX: Selected Contributions of the Ninth International Workshop on the Algorithmic Foundations of Robotics (WAFR), Springer Tracts in Advanced Robotics (STAR)

PDF Project Google Scholar Collision Detection Robotics

• .
GPU-based Parallel Collision Detection for Real-time Motion Planning  2011.
Algorithmic Foundations of Robotics IX: Selected Contributions of the Ninth International Workshop on the Algorithmic Foundations of Robotics (WAFR), Springer Tracts in Advanced Robotics (STAR)

PDF Project Google Scholar GPGPU Robotics Collision Detection

• .
Collision-streams: Fast GPU-based Collision Detection for Deformable Models  2011.
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D)

PDF Project Video Google Scholar Collision Detection GPGPU

• .
VolCCD: Fast Continuous Collision Culling Between Deforming Volume Meshes  2011.
ACM Transactions on Graphics

PDF Project Google Scholar Collision Detection Animation

• .
Probabilistic Collision Detection Between Noisy Point Clouds Using Robust Classification  2011.
International Journal of Robotics Research (IJRR)

PDF Project Google Scholar Collision Detection

• .
gProximity: Hierarchical GPU-based Operations for Collision and Distance Queries  2010.
Computer Graphics Forum (Proc Eurographics)

PDF Project Video Google Scholar Collision Detection GPGPU

• .
Fast Continuous Collision Detection Using Deforming Non-penetration Filters  2010.
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D)

PDF Project Video Google Scholar Collision Detection

• .
MCCD: Multi-core Collision Detection Between Deformable Models Using Front-based Decomposition  2010.
Graphical Models

PDF Project Video Google Scholar Collision Detection

• .
Continuous Collision Detection for Non-rigid Contact Computations Using Local Advancement  2010.
IEEE International Conference on Robotics and Automation (ICRA)

PDF Google Scholar Collision Detection Robotics

• .
Constrained Motion Interpolation with Distance Constraints  2009.
Algorithmic Foundation of Robotics VIII: Selected Contributions of the Eighth International Workshop on the Algorithmic Foundations of Robotics (WAFR), Springer Tracts in Advanced Robotics (STAR)

PDF Project Google Scholar Robotics Collision Detection

• .
Path Planning Among Movable Obstacles: A Probabilistically Complete Approach  2009.
Algorithmic Foundation of Robotics VIII: Selected Contributions of the Eighth International Workshop on the Algorithmic Foundations of Robotics (WAFR), Springer Tracts in Advanced Robotics (STAR)

PDF Google Scholar Robotics Collision Detection

• .
Global Vector Field Computation for Feedback Motion Planning  2009.
IEEE International Conference on Robotics and Automation (ICRA)

PDF Project Video Google Scholar Robotics Collision Detection

• .
C2A: Controlled Conservative Advancement for Interactive Continuous Collision Detection of Polygonal Models  2009.
IEEE International Conference on Robotics and Automation (ICRA)

PDF Project Google Scholar Collision Detection Animation Robotics

• .
ICCD: Interactive Continuous Collision Detection Between Deformable Models Using Connectivity-based Culling  2009.
IEEE Transactions on Visualization and Computer Graphics (TVCG)

PDF Project Video YouTube Google Scholar Collision Detection

• .
Centralized Path Planning for Multiple Robots: Optimal Decoupling into Sequential Plans  2009.
Robotics: Science and Systems (RSS)

PDF Google Scholar Robotics Collision Detection

• .
Multi-core Collision Detection between Deformable Models  2009.
SIAM/ACM Joint Conference on Geometric and Physical Modeling

PDF Project YouTube Google Scholar Collision Detection

• .
Fast Hierarchy Operations on GPU Architectures  2009.

Project Google Scholar GPGPU Collision Detection

• .
A Simple Path Non-Existence Algorithm Using C-obstacle Query  2008.
Algorithmic Foundation of Robotics VII: Selected Contributions of the Seventh International Workshop on the Algorithmic Foundations of Robotics (WAFR), Springer Tracts in Advanced Robotics (STAR)

PDF Google Scholar Robotics Collision Detection Geometric

• .
Fast Collision Detection for Deformable Models Using Representative-Triangles  2008.
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D)

PDF Project Video Google Scholar Collision Detection Animation

• .
D-Plan: Efficient Collision-free Path Computation for Part Removal and Disassembly  2008.
International CAD Conference (Best Paper)

PDF Project Google Scholar Robotics Collision Detection Geometric

• .
Real-time Path Planning in Dynamic Virtual Environments Using Multi-agent Navigation Graphs  2008.
IEEE Transactions on Visualization and Computer Graphics (TVCG)

Project Google Scholar Crowd Simulation Robotics Collision Detection

• .
Efficient Distance Computation in Configuration Space  2008.
Computer Aided Geometric Design (CAGD)

Project Google Scholar Collision Detection

• .
Adjacency-based Culling for Continuous Collision Detection  2008.
Visual Computer (Proc CGI)

Google Scholar Collision Detection

• .
Efficient Cell Labelling and Path Non-existence Computation Using C-obstacle Query  2008.
International Journal of Robotics Research (IJRR)

Project Google Scholar Collision Detection Robotics

• .
Interactive Continuous Collision Detection Between Deformable Models Using Connectivity-based Culling  2008.
ACM Symposium on Solid and Physical Modeling (SPM)

PDF Project Video YouTube Google Scholar Collision Detection Animation

• .
Interactive Continuous Collision Detection Using Swept Volume for Avatars  2007.
Presence: Teleoperators and Virtual Environments

Google Scholar Collision Detection GPGPU

• .
Interactive Virtual Hair Salon  2007.
Presence: Teleoperators and Virtual Environments

Project Video Google Scholar Animation Massive Models Collision Detection

• .
Real-time Path Planning for Virtual Agents in Dynamic Environments  2007.
IEEE Virtual Reality (VR)

PDF Project Video Google Scholar Crowd Simulation Animation Collision Detection GPGPU Geometric

• .
C-DIST: Efficient Distance Computation for Rigid and Articulated Models in Configuration Space  2007.
ACM Symposium on Solid and Physical Modeling (SPM)

PDF Project Google Scholar Collision Detection Geometric Robotics

• .
Generalized Penetration Depth Computation  2007.
Computer-Aided Design (CAD)

Project Google Scholar Collision Detection

• .
Surface Distace Maps  2007.
Graphics Interface

PDF Project Video Google Scholar Collision Detection GPGPU Robotics Geometric

• .
A Fast and Practical Algorithm for Generalized Penetration Depth Computation  2007.
Robotics: Science and Systems (RSS)

PDF Project Google Scholar Collision Detection Robotics

• .
Accelerated Proximity Queries for Haptic Rendering of Deformable Models  2007.
World Haptics Conference

PDF Project Video Google Scholar Collision Detection GPGPU Haptics Animation

• .
Real-time Navigation of Independent Agents Using Adaptive Roadmaps  2007.
ACM Symposium on Virtual Reality Software and Technology (VRST)

PDF Project Google Scholar Animation Collision Detection Crowd Simulation

• .
Efficient Collision Detection Among Deformable Objects Using Graphics Processors  2006.
Presence: Teleoperators and Virtual Environments

Project Google Scholar Collision Detection GPGPU Hidden Surface

• .
Interactive 3D Distance Field Computation Using Linear Factorization  2006.
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D)

PDF Project Google Scholar Geometric GPGPU Collision Detection

• .
Fast C-obstacle Query Computation for Motion Planning  2006.
IEEE International Conference on Robotics and Automation (ICRA)

PDF Google Scholar Robotics Collision Detection Geometric

• .
Generalized Penetration Depth Computation  2006.
ACM Symposium on Solid and Physical Modeling (SPM)

PDF Project Google Scholar Geometric Robotics Collision Detection

• .
Fast Proximity Computation Among Deformable Models Using Discrete Voronoi Diagrams  2006.
ACM Transactions on Graphics (Proc ACM SIGGRAPH)

PDF Project Video Google Scholar Collision Detection GPGPU Geometric

• .
Surface Distance Maps  2006.

PDF Project Google Scholar Geometric Collision Detection GPGPU

• .
A Simulation-based VR System for Interactive Hairstyling  2006.
IEEE Virtual Reality (VR)

PDF Project Video Google Scholar Collision Detection Animation Massive Models

• .
Fast Continuous Collision Detection Among Deformable Models Using Graphics Processors  2006.
Eurographics Symposium on Virtual Environments (EGVE)

PDF Google Scholar GPGPU Collision Detection

• .
Cache-efficient Layouts of Bounding Volume Hierarchies  2006.
Eurographics

PDF Project Google Scholar Collision Detection Massive Models

• .
Efficient Computation of Discrete Voronoi Diagram and Homotopy-preserving Simplified Medial Axis of 3D Polyhedron  2006.
Ph.D. Dissertation, University of North Carolina at Chapel Hill

PDF Google Scholar Collision Detection

• .
Fast Continous Collision Detection for Articulated Models  2005.
Journal of Computing and Information Science in Engineering (JCISE)

Project Google Scholar Collision Detection GPGPU

• .
A Fast Method for Local Penetration Depth Computation  2005.
Journal of Graphics Tools (JGT)

Google Scholar Collision Detection

• .
Practical Local Planning in the Contact Space  2005.
IEEE International Conference on Robotics and Automation (ICRA)

PDF Project Google Scholar Robotics Collision Detection

• .
Cache-oblivious Mesh Layouts  2005.
ACM Transactions on Graphics (Proc ACM SIGGRAPH)

PDF Project Google Scholar Massive Models Collision Detection GPGPU Simplification

• .
Multi-resolution Collision Handling Among Cloth-like Objects  2005.
International Conference on Computer Animation and Social Agents (CASA)

Google Scholar Collision Detection GPGPU

• .
Fast and Reliable Collision Culling Using Graphics Hardware  2005.
IEEE Transactions on Visualization and Computer Graphics (TVCG)

PDF Project Google Scholar Collision Detection GPGPU

• .
Interactive Visibility Ordering and Transparency Computations Among Geometric Primitives in Complex Environments  2005.
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D)

PDF Google Scholar GPGPU Collision Detection Hidden Surface

• .
Interactive Collision Detection Between Deformable Models Using Chromatic Decomposition  2005.
ACM SIGGRAPH

PDF Project Google Scholar Collision Detection GPGPU Hidden Surface

• .
Efficient Collision Culling among Deformable Objects Using Graphics Processors  2005.
Presence: Teleoperators and Virtual Environments

Google Scholar GPGPU Collision Detection Geometric

• .
QUICK-CULLIDE: Efficient Inter- and Intra-object Collision Culling Using Graphics Hardware  2005.
IEEE Virtual Reality (VR)

PDF Project Video Google Scholar GPGPU Collision Detection Hidden Surface

• .
Interactive Visualization and Collision Detection using Dynamic Simplification and Cache-coherent Layouts  2005.
Ph.D. Dissertation, University of North Carolina at Chapel Hill

PDF Google Scholar Collision Detection

• .
Fast Update of OBBTrees for Articulated-Body Collision Detection  2004.
Journal of Graphics Tools (JGT)

Google Scholar Collision Detection

• .
DiFi: Fast 3D Distance Field Computation Using Graphics Hardware  2004.
Eurographics

PDF Project Google Scholar GPGPU Collision Detection

• .
Efficient Visibility-based Algorithms for Interactive Walkthrough, Shadow Generation, and Collision Detection.  2004.
Ph.D. Dissertation, University of North Carolina at Chapel Hill

PDF Google Scholar Massive Models Ray Tracing Collision Detection

• .
Fast Continuous Collision Detection for Articulated Models  2004.
ACM Symposium on Solid Modeling and Applications (SMA)

Project Google Scholar Collision Detection

• .
Vis-Sort: Fast Visibility Ordering of 3-D Geometric Primitives  2004.

PDF Project Google Scholar Collision Detection GPGPU Hidden Surface

• .
Interactive and Continuous Collision Detection for Avatars in Virtual Environments  2004.
IEEE Virtual Reality (VR)

PDF Project Google Scholar Collision Detection

• .
Simulating and Rendering Wet Hair  2004.
ACM SIGGRAPH Sketches and Applications

PDF Project Video Google Scholar Collision Detection Animation Massive Models

• .
Fast Collision Detection Between Massive Models Using Dynamic Simplification  2004.
Eurographics Symposium on Geometry Processing (SGP)

PDF Project Google Scholar Collision Detection

• .
Fast Distance Field Computation Using Graphics Hardware  2004.

PDF Google Scholar GPGPU Collision Detection

• .
Fast and Reliable Collision Culling using Graphics Processors  2004.
ACM Symposium on Virtual Reality Software and Technology (VRST)

PDF Project Google Scholar GPGPU Collision Detection Hidden Surface

• .
Haptic Display of Interaction between Textured Models  2004.
IEEE Visualization (VIS)

PDF Project Google Scholar Haptics GPGPU Collision Detection

• .
Modeling Hair Influenced by Water and Styling Products  2004.
International Conference on Computer Animation and Social Agents (CASA)

PDF Project Google Scholar Animation Collision Detection

• .
Fast Penetration Depth Estimation Using Rasterization Hardware and Hierarchical Refinement  2004.
Algorithmic Foundations of Robotics V: Selected Contributions of the Fifth International Workshop on the Algorithmic Foundations of Robotics (WAFR), Springer Tracts in Advanced Robotics (STAR)

PDF Project Google Scholar GPGPU Collision Detection

• .
CULLIDE: Interactive Collision Detection Between Complex Models in Large Environments using Graphics Hardware  2003.
ACM SIGGRAPH/Eurographics Workshop on Graphics Hardware (EGGH)

PDF Project Google Scholar Hidden Surface Collision Detection

• .
ESOLID - A System for Exact Boundary Evaluation  2003.
Computer-Aided Design (CAD)

Google Scholar Collision Detection

• .
Fast Self-collision Detection in General Environments Using Graphics Processors  2003.

Project Google Scholar Collision Detection

• .
Image Retrieval with Embedded Region Relationships  2003.
ACM Symposium on Applied Computing (SAC)

Google Scholar Collision Detection

• .
Sensation Preserving Simplification for Haptic Rendering  2003.
ACM Transactions on Graphics (Proc ACM SIGGRAPH)

PDF Project Google Scholar Collision Detection Haptics

• .
Efficient Max-norm Distance Computation and Reliable Voxelization  2003.
Eurographics Symposium on Geometry Processing (SGP)

PDF Project Google Scholar Collision Detection

• .
CLODs: Dual Hierarchies for Multiresolution Collision Detection  2003.
Eurographics Symposium on Geometry Processing (SGP)

PDF Project Google Scholar Collision Detection Haptics

• .
Collision and Proximity Queries  2003.
Handbook of Discrete and Computational Geometry: Collision Detection

PDF Google Scholar Collision Detection

• .
Incremental Penetration Depth Estimation Between Convex Polytopes Using Dual-space Expansion  2003.
IEEE Transactions on Visualization and Computer Graphics (TVCG)

PDF Project Google Scholar Collision Detection

• .
Adaptive Grouping and Subdivision for Simulating Hair Dynamics.  2003.
Pacific Graphics

PDF Project Google Scholar Animation Collision Detection Massive Models

• .
Modeling Hair Using Level-of-detail Representations  2003.
International Conference on Computer Animation and Social Agents (CASA)

PDF Project Google Scholar Animation Massive Models Collision Detection

• .
Simplified Representations for Modeling Hair  2002.

PDF Project Google Scholar Animation Collision Detection Massive Models Geometric

• .
DEEP: Dual-space Expansion for Estimating Penetration Depth Between Convex Polytopes  2002.
IEEE International Conference on Robotics and Automation (ICRA)

PDF Project Google Scholar Collision Detection

• .
Fast 3D Geometric Proximity Queries between Rigid and Deformable Models Using Graphics Hardware Acce  2002.

PDF Project Google Scholar Collision Detection GPGPU

• .
Accurate and Fast Proximity Queries between Polyhedra Using Surface Decomposition  2001.
Eurographics

PDF Project Google Scholar Collision Detection

• .
SWIFT: Accelerated Proximity Queries Using Multi-level Voronoi Marching  2000.

PDF Project Video Google Scholar Collision Detection

• .
Computing the Medial Axis of a Polyhedron Reliably and Efficiently  2000.
Ph.D. Dissertation, University of North Carolina at Chapel Hill

PDF Google Scholar Collision Detection

• .
Accelerated Proximity Queries Between Convex Polyhedra by Multi-level Voronoi Marching  2000.
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

PDF Project Google Scholar Collision Detection

• .
Fast Distance Queries using Rectangular Swept Sphere Volumes  2000.
IEEE International Conference on Robotics and Automation (ICRA)

Project Google Scholar Collision Detection

• .
Collision Queries Using Oriented Bounding Boxes  2000.
Ph.D. Dissertation, University of North Carolina at Chapel Hill

PDF Google Scholar Collision Detection

• .
Hierarchical Back-face Computation  1999.
Computers and Graphics

Google Scholar Collision Detection

• .
Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware  1999.
ACM SIGGRAPH

PDF Project Google Scholar Collision Detection GPGPU

• .
IMMPACT: A System for Interactive Proximity Queries on Massive Models  1999.
Eurographics

PDF Project Google Scholar Collision Detection

• .
H-COLLIDE: A Framework for Fast and Accurate Collision Detection for Haptic Interaction  1998.

Google Scholar Collision Detection

• .
Collision Detection Between Geometric Models: A Survey  1998.
IMA Conference on Mathematics of Surfaces

PDF Google Scholar Collision Detection

• .
Rapid and Accurate Contact Determination between Spline Models using ShellTrees.  1998.
Eurographics

Google Scholar Collision Detection

• .
Spherical Shell: A Higher Order Bounding Volume for Fast Proximity Queries  1998.
Workshop on the Algorithmic Foundations of Robotics (WAFR)

PDF Google Scholar Collision Detection

• .
V-COLLIDE: Accelerated Collision Detection for VRML  1997.
Virtual Reality Modeling Language Symposium (VRML)

Project Google Scholar Collision Detection

• .
Incremental Algorithms for Collision Detection Between Solid Models  1997.
IEEE Transactions on Visualization and Computer Graphics (TVCG)

PDF Project Google Scholar Collision Detection Geometric

• .
Efficient Contact Determination Between Geometric Models  1997.
International Journal of Computational Geometry and Applications (IJCGA)

Google Scholar Collision Detection

• .
OBB-Tree: A Hierarchical Structure for Rapid Interference Detection  1996.
ACM SIGGRAPH

Project Google Scholar Collision Detection

• .
Efficient and Accurate Interference Detection for Polynomial Deformation and Soft Object Animation  1996.
Conference on Computer Animation (CA)

Google Scholar Collision Detection

• .
Collision Detection: Algorithms and Applications  1996.
Algorithms for Robot Motion and Manipulation

PDF Google Scholar Collision Detection

• .
I-COLLIDE: An Interactive and Exact Collision Detection System for Large-scaled Environments  1995.
ACM SIGGRAPH Symposium on Interactive 3D Graphics (I3D)

PDF Project Google Scholar Collision Detection

• .
Efficient Contact Determination Between Geometric Models  1994.

PDF Google Scholar Collision Detection

• .
An Efficient Surface Intersection Algorithm Based on Lower Dimensional Formulation  1994.

PDF Google Scholar Collision Detection

• .
Efficient Collision Detection for Animation and Robotics  1993.
Ph.D. Thesis, University of California, Berkeley

PDF Google Scholar Collision Detection