Awesome Collision Detection
A curated list of collision detection libraries, algorithms, papers, and related resources.
Contents
Legend: 🟢 Active (<1yr) · 🟡 Slow (1-2yr) · 🔴 Stale (>2yr) · 💀 Archived
Libraries
Active
Collision detection, distance query, and proximity query libraries. See also Comparisons.
- 🔴 BEPUphysics 1 - Pure C# physics engine with broadphase and narrowphase collision detection. ⭐ 425
- 🟢 Box2D - 2D physics engine with collision, distance, ray cast, and shape cast queries. ⭐ 9.7k
- 🟢 Bullet - Real-time physics SDK with collision detection for games, robotics, and simulation. ⭐ 14.5k
- 🔴 CCD-Wrapper - Wrapper and benchmark for continuous collision detection algorithms. ⭐ 60
- 🟢 coal (HPP-FCL) - Collision detection and distance query library derived from HPP-FCL. ⭐ 586
- 🔴 collision-rs - Rust collision detection library with broadphase and narrowphase queries. ⭐ 130
- 🟢 FCL - Flexible Collision Library for collision, distance, and continuous collision queries. ⭐ 1.7k
- 🔴 JitterPhysics - C# rigid body physics engine with collision detection support. ⭐ 47
- 🟢 Kraft - Object Pascal physics engine with discrete and optional continuous collision detection. ⭐ 126
- 🔴 libccd - Small C library for collision detection between convex shapes using GJK and EPA. ⭐ 639
- 🟢 MuJoCo - Physics simulator with contact, collision, and distance queries for robotics and control. ⭐ 13.4k
- 🔴 ncollide - Rust collision detection library for 2D and 3D geometric queries. ⭐ 934
- ODE - Open Dynamics Engine with rigid body simulation and collision detection. [bitbucket]
- 🟢 OpenGJK - GJK-based minimum distance library with bindings for multiple languages. ⭐ 197
- 🟢 Parry - Rust collision detection and geometric query library from Dimforge. ⭐ 819
- 🟢 PhysX - NVIDIA physics SDK with scene queries, contact generation, and collision detection. ⭐ 4.5k
- 🟢 python-fcl - Python bindings for FCL collision, distance, and continuous collision queries. ⭐ 269
- 🟢 pytorch_volumetric - PyTorch utilities for volumetric signed distance fields and differentiable collision queries. ⭐ 246
- 💀 qu3e - Lightweight 3D rigid body physics engine with collision detection. ⭐ 991
- 🟡 ReactPhysics3d - C++ 3D physics engine with rigid body collision detection. ⭐ 1.7k
- 🟢 Tight-Inclusion - Conservative continuous collision detection library with minimum separation support. ⭐ 157
- 🟢 tinyc2 - Single-header 2D collision detection library for primitive shapes. ⭐ 5k
Some libraries, such as ODE and Bullet, are physics engines that can also be used as collision detection libraries.
Inactive
- ColDet - 3D Collision Detection.
- GIMPACT - Tools for geometry processing and collision detection.
- OPCODE - Optimized Collision Detection.
- 🔴 OZCollide - Legacy collision detection library. ⭐ 4
- SOLID - Collision detection of 3D objects undergoing rigid motion and deformation.
Mesh Processing
Geometry processing libraries useful for collision-ready meshes and convex approximations.
- 🔴 bounding-mesh - Implementation of the bounding mesh and bounding convex decomposition algorithms for single-sided mesh approximation. ⭐ 349
- 🟢 cinolib - A generic programming header only C++ library for processing polygonal and polyhedral meshes. ⭐ 1.1k
- 🟢 CoACD - Approximate convex decomposition for collision-aware mesh approximation. ⭐ 1k
- 🟢 libigl - A simple C++ geometry processing library. ⭐ 5k
Papers
Collision Detection and Distance Computation
- GJK++: Leveraging Acceleration Methods for Faster Collision Detection (2023), Montaut et al. [pdf, code, benchmarks]
- Collision Detection Accelerated: An Optimization Perspective (2022), Montaut et al. [pdf, code, benchmarks]
- A fast procedure for computing the distance between complex objects in three-dimensional space (1988) Gilbert, Johnson and Keerthi [pdf]
Differentiable Collision Detection
- Differentiable Collision Detection: a Randomized Smoothing Approach (2022), Montaut et al. [pdf, code]
Triangle-triangle Test
- A faster triangle-to-triangle intersection test algorithm (2013), L.-Y. Wei.
- Efficient triangle-triangle intersection test for OBB-based collision detection (2009), J.-W. Chang et al. [pdf]
- A fast triangle to triangle intersection test for collision detection (2006), O. Tropp et al. [pdf]
- A failure case was reported in Stack Overflow.
- Faster Triangle-Triangle Intersection Tests (2006), O. Devillers et al. [pdf, code]
- A Fast Triangle-Triangle Intersecion Test (1997), T. Muller. [pdf, code]
Mesh Collision
- Robust contact generation for robot simulation with unstructured meshes (2013), K. Hauser. [pdf, web]
- Approximate Convex Decomposition for 3D Meshes with Collision-Aware Concavity and Tree Search (2022), X. Wei et al. [pdf, project, code, video]
Penetration Depth Computation
- PolyDepth: Real-time Penetration Depth Computation using Iterative Contact-Space Projection (2012), C. Je et al. [pdf]
Proximity Query / Signed Distance Field
- Local Optimization for Robust Signed Distance Field Collision (2020), M. Macklin et al. [pdf, slides, video]
- Hierarchical hp-Adaptive Signed Distance Fields (2016), D. Koschier et al. [pdf, video]
- Voxblox: Building 3d signed distance fields for planning (2016), H Oleynikova et al. [pdf, code]
- Signed distance fields for polygon soup meshes (2014), H. Xu and Jernej Barbic. [pdf]
- Fast Proximity Queries with Swept Sphere Volumes (1999), E. Larsen et al. [pdf, web]
Continuous Collision Detection
- Hierarchical and Controlled Advancement for Continuous Collision Detection of Rigid and Articulated Models (2013), M. Tang et al. [pdf, web]
- Efficient Geometrically Exact Continuous Collision Detection (2012), T. Brochu et al. [pdf]
- C2A: Controlled Conservative Advancement for Continuous Collision Detection of Polygonal Models (2009), M. Tang et al. [pdf]
- Continuous Collision Detection for Articulated Models using Taylor Models and Temporal Culling (2007), X. Zhang et al. [pdf, web]
- Interactive continuous collision detection for non-convex polyhedra (2006), X. Zhang et al. [pdf, web]
Nearest Neighbor
- Faster cover tree (2015), M. Izbicki et al. [pdf, code]
- Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration (2009), M. Muja and D. Lowe. [pdf, code]
- Cover Tree for Nearest Neighbor (2006), A. Beygelzimer et al. [pdf, web, code]
Comprehensive Collision Detection Library
- FCL: A General Purpose Library for Collision and Proximity Queries (2012), J. Pan et al. [pdf, code]
Survey
- Collision Detection: A Survey (2007), S. Kockara et al. [pdf]
- 3D collision detection: a survey (2001), P. Jiménez et al. [pdf]
Books
- Real-Time Collision Detection, CRC Press 2004 (amazon)
- Collision Detection in Interactive 3D Environments, CRC Press 2003 (amazon)
Articles
Overview & Tutorial
- Video Game Physics Tutorial - Part II: Collision Detection for Solid Objects by Nilson Souto
- GPU Rigid Body Simulation (GDC 2013), Erwin Coumans
- OpenCL accelerated rigid body and collision detection (RSS 2011), Erwin Coumans
- Contact Generation (GDC 2010), Erwin Coumans
Benchmark
- spatial-collision-datastructures - Benchmark of various spatial data structures for collision detection.
- Continuous Collision Detection (code) Project page for continuous collision detection papers, implementations, benchmarks, and datasets.
Narrow-phase
- Algorithm table for narrowphase algorithms
- 3D Collision detection by Miguel Casillas
- Collision Detection (code) by Jeff Thompson - This book explains the algorithms behind those collisions using basic shapes like circles, rectangles, and lines so you can implement them into your own projects.
- Note: The Gibert-Jonson-Keerthi algorithm by Christer Ericson
Space Partitioning
- Benchmark of various spatial data structures for collision detection
- Bounding volume hierarchy
- Bounding Volume Hierarchy Optimization through Agglomerative Treelet Restructuring (paper, code) by Leonardo R. Domingues and Helio Pedrini.
- Dynamic AABB Tree by Randy Gaul
- Efficient BVH Construction via Approximate Agglomerative Clustering (pdf) by Yan Gu et al.
- Octree vs BVH by Thomas Diewald
Other Awesome Lists
- Awesome Robotics Libraries ⭐ 2.9k - This is a list of various libraries and software for robotics. It’s also attempting to provide some comparisons for selected libraries and software.
Contributing
Contributions are very welcome! Please read the contribution guidelines first. Also, please feel free to report any error.
Star History
License
