Awesome Collision Detection

A curated list of collision detection open resources

Table of Contents

• Libraries
• Articles
• Books
• Other Awesome Lists
• Contributing

Libraries

Active

⚠️ The following table is not complete. Please feel free to report if you find something incorrect or missing.

Name	Shapes	Features	Languages	Licenses	Code	Popularity
Bullet	(todo)	(todo)	C++, Python	Zlib	github
ColDet	(todo)	(todo)	C++	LGPL-2.0	sourceforge	(todo)
FCL	(todo)	(todo)	(todo)	(todo)	github
libccd	(todo)	(todo)	C	BSD-3-Clause	github
ODE	(todo)	(todo)	C++, Python	LGPL-2.1 or BSD-3-Clause	bitbucket
ReactPhysics3d	(todo)	(todo)	C++	Zlib	github
qu3e	(todo)	(todo)	(todo)	Zlib	github

Some libraries (e.g., ODE and Bullet) are physics engines that contain collision detection features, but they can be used just as collision detection libraries.

Inactive

• GIMPACT - A software library with tools for geometry processing and collision detection, focused on solving most common problems on Virtual Reality development.
• OPCODE - Optimized Collision Detection.
• OZCollide [github (unofficial repo)]
• SOLID - A library for collision detection of 3D objects undergoing rigid motion and deformation designed for interactive 3D graphics applications.

Mesh Simplication

• bounding-mesh (github ) - Implementation of the bounding mesh and bounding convex decomposition algorithms for single-sided mesh approximation.

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.

• 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

• 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 | code)
    • A failure case was reported in SO.
  • Faster Triangle-Triangle Intersection Tests (2006), O. Devillers et al. (pdf | code)
  • A Fast Triangle-Triangle Intersecion Test (1997), T. Muller. (pdf | code)

• Space partitioning

  • Benchmark of various spatial data structures for collision detection
  • Bounding volume heirarchy
    • 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 by Yan Gu et al. (pdf)
    • Octree vs BVH by Thomas Diewald

• Mesh collision

  • K. Hauser, Robust contact generation for robot simulation with unstructured meshes, ISRR 2013 (pdf)

• Penetration depth computation

  • C. Je, M. Tang, Y. Lee, M. Lee, and Y Kim, PolyDepth: Real-time Penetration Depth Computation using Iterative Contact-Space Projection, TOG 2012 (pdf)

• Nearest neighbor

  • Cover tree
    • Wikipedia
    • Cover Tree for Nearest Neighbor caclulations by Alina Beygelzimer et al, ICML 2006.
    • https://github.com/DNCrane/Cover-Tree
  • Faster cover tree
    • Faster cover tree by Mike Izbicki et al., ICML 2015.
    • https://github.com/manzilzaheer/CoverTree
  • FLANN - Fast Library for Approximate Nearest Neighbors (github)

Other Awesome Lists

• Awesome Robotics Libraries - This is a list of various libraris 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.

License