Collision Detection

Introduction to Collision Detection:

Overview:

• Collision Detection between Geometric Models: A Survey;  M. Lin and S. Gottschalk. Appeared in the Proceedings of IMA Conference on Mathematics of Surfaces 1998.
• Collision Detection: Algorithms and Applications; M. Lin, D. Manocha, J. Cohen and S. Gottschalk. Appeared in Proc. of Algorithms for Robotics Motion and Manipulation, pp. 129-142 eds. Jean-Paul Laumond and M. Overmars, A.K. Peters.

Lin-Canny Closest Features Algorithm

• This algorithm maintains the pair of closest features (vertices, edges, or faces) between two convex polyhedra moving through space. By exploiting the fact that the current closest features are probably near the previous closest features, near constant query time is achieved in practice. The distance between two polyhedra is easily found once the closest features are known. A collision is declared when this distance falls below some small epsilon.
• Paper: Efficient Collision Detection for Animation and Robotics; Ph.D. thesis, University of California, Berkeley; M. C. Lin.
• Paper: A fast algorithm for incremental distance calculation; In IEEE Conference on Robotics and Automation, pages 1008-1014, 1991; M. Lin and J. Canny.
• Paper: Efficient collision detection for animation; In Third Eurographics Workshop, 1992; M. Lin and J. Canny.

V-Clip

• The Voronoi-Clip, or V-Clip, algorithm tracks closest pairs of features similarly to the above-mentioned Lin-Canny Closest Features Algorithm. The author claims that V-Clip is not as complex as Lin-Canny to code and that it is a more robust algorithm. V-Clip also handles penetrating polyhedra. This capability allows the algorithm to be extended to nonconvex polyhedra when they are represented as groups of convex polyhedra. Lin-Canny does not handle the case of penetrating polyhedra and, in fact, such a case would result in the Lin-Canny algorithm failing to terminate without some special "tweaks," such as a maximum cycle count.
• Paper: V-Clip: fast and robust polyhedral collision detection; Brian Mirtich; ACM Trans. Graph. 17, 3 (Jul. 1998), Pages 177 - 208.
• Paper: Impulse-based Dynamic Simulation of Rigid Body Systems; Brian Mirtich, Ph.D. thesis, University of California, Berkeley, December, 1996.
• V-Clip Collision Detection Library

I-COLLIDE

• I_COLLIDE is an interactive and exact collision detection library for large environments composed of convex polyhedra. Many non-convex polyhedra may be decomposed into sets of convex polyhedra, which may then be used with this library. I_COLLIDE exploits coherance (the property of a simulation to change very little between consecutive time steps) and the properties of convexity to achieve very fast collision detection that is exact to the accuracy of the input models. The library has been tested in architectural walkthroughs, multi-body simulations, and impulse-based simulations. The time required for collision detection is typically small compared to the time to generate the graphics for these simulations.
• Paper: I-COLLIDE: an interactive and exact collision detection system for large-scale environments; J. D. Cohen, M. C. Lin, D. Manocha, and M. K. Ponamgi, Proc. ACM Interactive 3D Graphics Conf., 189-196 (1995).

OBB-Tree

• An OBB-Tree is a hierarchical representation using oriented bounding boxes (OBBs). An OBB is a rectangular bounding box at an arbitrary orientation in 3-space. In an ideal case, the OBB would be oriented such that it encloses an object as tightly as possible. In other words, the bounding box is the smallest possible bounding box of arbitrary orientation that can enclose the geometry in question. When compared with Axis-Aligned Bounding Boxes (AABBs), OBBs generally allow geometries to be bounded more tightly with a fewer number of boxes. The seminal Siggraph '96 paper (see below) presents some efficient algorithms dealing with hierarchies of OBBs.
• Paper: OBB-Tree: A Hierarchical Structure for Rapid Interference Detection; S. Gottschalk, M. Lin and D.  Manocha, Appeared in Proc. of ACM Siggraph'96.
• Paper: Dynamic Collision Detection using Oriented Bounding Boxes; David Eberly, Magic Software.
• Paper: Intersection of Objects with Linear and Angular Velocities using Oriented Bounding Boxes; David Eberly, Magic Software.
• Paper: Real-time Bounding Box Area Computation; D. Schmalstieg, R. F. Tobler, Institute of Computer Graphics, Vienna University of Technology,

Q-COLLIDE

• Q-COLLIDE is a simple exact collision detection algorithm for convex polytopes. The algorithm finds quickly a separating plane between two polytopes if they are non-colliding, or else reports collision and the pair of closest points between them if it cannot possibly find a separating plane. In the case of non-collision, the separating plane found for one time frame is cached as a witness for the next time frame; this use of time coherence further speeds up the algorithm in dynamic applications. Both temporal and geometric coherences are exploited to make this algorithm run in expected constant time empirically.
• Paper: Quick Elimination of Non-Interference Polytopes in Virtual Environments, Kelvin Chung and Wenping Wang, 3rd European Workshop on Virtual Environments, 19-20, Feb, 96, Monte Carlo, Monaco. Also appear in the book Virtual Environments'96, Springer-Verlag Wien New York, 1996.
• Paper: Quick Collision Detection of Polytopes in Virtual Environments, Kelvin Chung and Wenping Wang, ACM Symposium on Virtual Reality Software and Technology 1996, 1-4, July, 96, University of Hong Kong, Hong Kong.
• Paper: Discrete Moving Frames for Sweep Surface Modeling, Kelvin Chung and Wenping Wang, Pacific Graphics '96. 19-22, August, 96, Hsinchu, Taiwan.

QuickCD

• This method is based upon constructing hierarchies of bounding volumes (BV-trees) to approximate the input models. The choice of bounding volumes is made using "discrete orientation polytopes'', or k-dops, which are convex polytopes whose facets have normals from a given discrete set of k vectors.
• Efficient Collision Detection for Interactive 3D Graphics and Virtual Environments; J.T. Klosowski (1998), Ph.D. Dissertation, State University of New York at Stony Brook, May 1998.
• Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs; J.T. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, K. Zikan (1997): IEEE Transactions on Visualization and Computer Graphics, March 1998, Volume 4, Number 1.
• Evaluation of Collision Detection Methods for Virtual Reality Fly-Throughs; M. Held, J.T. Klosowski, J.S.B. Mitchell (1995), Presented at the Seventh Canadian Conference on Computational Geometry C. Gold, J.-M. Robert (eds.), pp 205-210; Québec City, Québec, Canada, Aug 10-13, 1995.

Kinetic Data Structure for collision detection:

• "Kinetic Data Structure(KDS) is built on the idea of maintaining a discrete attribute of objects in motion by animating a proof of its correctness through time. The proof consists of a set of elementary conditions, or certificates, based on the kinds of tests performed by orfinary geometric algorithms. Those of the certificates that can fail as a result of the rigid motion of the polygons are placed in an event queue, ordered according to their earliest failure time. When a certificate fails, the proof needs to be updated. Unless a collision has occured, we perform this update and continue the simulation. In constrast to fixed time step methods, for which the fastest moving object determines the time step for the entire system, a kinetic method is based on events that have a natural significance in terms of the problem being addressed.The kinetic model allows us to perform a rigorous combinatorial time-cost analysis and obtain practical solutions at the same time. " -- from paper "kinetic collision detection between two simple polygons".
• Paper: Kinetic collision detection between two simple polygons; Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger and Li Zhang; Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms , 1999, Pages 102 - 111.
• Paper: Separation-sensitive collision detection for convex objects; Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi and Li Zhang; Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms , 1999, Pages 327 - 336.
• Paper: Fast Collision Detection among Multiple Moving Spheres; Dong-Jin Kim and Sung-Yong Shin, Korea Advanced Institute of Science and Technology, Leonidas J. Guibas, Stanford University.

Other Papers:

• Dynamic Plane Shifting BSP Traversal, Stan Melax, Boiware, 2001.(Thanks Eric Haines for providing the info.)
• Incremental collision detection for polygonal models, Madhav K. Ponamgi, Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, Department of Computer Science, University of North Carolina.
• Real-Time Four-Dimensional Collision Detection for an Industrial Robot Manipulator, Harry H. Cheng.
• Collision detection in aspect and scale bounded polyhedra; Subhash Suri, Philip M. Hubbard and John F. Hughes; Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms , 1998, Pages 127 - 136.
• Fast collision detection using QuOSPO trees; Taosong He; Proceedings of the 1999 symposium on Interactive 3D graphics, 1999, Pages 55 -62.
• Incremental 3D collision detection with hierarchical data structures; Tsai-Yen Li and Jin-Shin Chen; Proceedings of the ACM Symposium on Virtual reality software and technology 1998 , 1998, Pages 139 - 144.
• A Fast Procedure for Computing the Distance Between Complex Objects, E. G. Gilbert, D. W. Johnson, and S. S. Keerthi. IEEE Journal of Robotics and Automation, 4, 1988, pp. 193-203.
• Rapid and Accurate Contact Determination between Spline Models using ShellTrees; S. Krishnan, M. Gopi, M. Lin, D. Manocha and A. Pattekar. To Appear in Proceedings of Eurographics'98.
• Spherical Shell: A Higher Order Bounding Volume for Fast Proximity Queries; S. Krishnan, A. Pattekar, M. Lin and D. Manocha. Appeared in Proceedings of WAFR'98.
• V-COLLIDE: Accelerated Collision Detection for VRML; T. Hudson, M. Lin, J. Cohen, S. Gottschalk and D. Manocha. Appeared in Proc. of VRML'97.
• Interactive and Exact Collision Detection for Large-Scale Environments; J. Cohen, M. Lin, D. Manocha and K. Ponamgi, Technical report TR94-005, Department of Computer Science, University of N. Carolina, Chapel Hill.
• Incremental algorithms for collision detection between solid models; M. Ponamgi, D. Manocha and M. Lin, IEEE Transactions on Visualization and Computer Graphics , 1997.
• Fast Contact Determination in Dynamic Environments; M. Lin and D. Manocha, appeared in International Journal of Computational Geometry and Applications.
• Collision detection and response for computer animation; M. Moore and J. Wilhelms; Proceedings of the 15th annual conference on Computer graphics , 1988, Pages 289 - 298.
• Collision detection framework using model simplification; Tiow-Seng Tan, Ket-Fah Chong and Kok-Lim Low; Proceedings of the conference on SIGGRAPH 98: conference abstracts and applications , 1998, Page 246.
• Collision detection for volumetric objects; Taosong He and Arie Kaufman; Proceedings of the conference on Visualization '97, 1997, Page 27.
• An efficient collision detection algorithm using range data for walk-through systems; SonOu Lee, JunHyeok Heo and KwangYun Wohn; Proceedings of the ACM symposium on Virtual reality software and technology, 1997, Pages 119 - 123.
• Real-time collision detection for motion simulation within complex environments; Martin Held, James T. Klosowski and Joseph S. B. Mitchell; The art and interdisciplinary programs of SIGGRAPH '96 on SIGGRAPH '96 visual proceedings , 1996, Page 151.
• Collision detection for fly-throughs in virtual environments; Martin Held, James T. Klosowski and Joseph S. B. Mitchell; Proceedings of the twelfth annual symposium on Computational geometry,1996, Pages 513 - 514.
• Approximating polyhedra with spheres for time-critical collision detection; Philip M. Hubbard; ACM Trans. Graph. 15, 3 (Jul. 1996), Pages 179 - 210.
• Exact collision detection for interactive environments (extended abstract); Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha and Madhav K. Ponamgi; Proceedings of the tenth annual symposium on Computational geometry , 1994, Pages 391 - 392.
• Active Motion Planning and Collision Avoidance for Redundant Manipulators; Stephen Cameron, Yonghong Bu, ISATP 97, August 1997.
• Motion Planning and Collision Avoidance with Complex Geometry; Stephen Cameron, Caigong Qin, Int Conf Manufacturing Automation, April 1997.
• Path Planning and Collision Avoidance for Redundant Manipulators in Three Dimensions; Stephen Cameron, Alistair McLean, Int. Conf. Intelligent Autonomous Systems, Karlsruhe, March 1995.
• Effective Path Planning and Collision Avoidance for Redundant Manipulators; Stephen Cameron, Alistair McLean, Int. Conf. Advanced Robotics and Comp. Vision, Singapore, November 1994.
• Collision Detection by Four-Dimensional Intersection Testing; Stephen Cameron, IEEE Trans. Robotics and Automation 6(3), June 1990.
• Real-Time Collision Detection and Time-Critical Computing; P. M. Hubbard, Proceedings of the First ACM Workshop on Simulation and

Interaction in Virtual Environments, July 1995, pp. 92-96.
• Collision Detection for Interactive Graphics Applications; P. M. Hubbard, IEEE Transactions on Visualization and Computer Graphics ,

1(3), September 1995, pp. 218-230.
• Improving Accuracy in a Robust Algorithm for Three-Dimensional Voronoi Diagrams; P. M. Hubbard, The Journal of Graphics Tools , 1(1), 1996,

pp. 33-47.

Software

• Lin-Canny Closest Features Algorithm
• SOLID library
• I_COLLIDE: an interactive and exact collision detection library for large environments composed of convex polyhedra.
• Q_COLLIDE: Quick Collision Detection Library
• RAPID: Robust and Accurate Polygon Interference Detection based on OBB-Tree
• V-Collide: Collision Detection for Arbitrary Polygonal Objects
• V-COLLIDE- The Collision detection library
• Ian Palmer uses sphere trees in REALISM and ACE.
• Dynamic Collision Detection: using OBBs.
• Quick CD: A general-purpose collision detection library, capable of performing fast and exact collision detection on highly complex models. No assumption is made about the structure of the input. QuickCD robustly handles unstructured inputs consisting of a ``soup'' of polygons. No adjacency information is needed; the models are only specified as a collection of triangles.
• PQP-the Proximity Query Package
• Really simple collision detection code, it includes a couple of Java Applets.

Other Links

• A collision detection page in UNC
• A page for I-Collide
• Collision Detection for Virtual Reality
• Collision Detection Resources
• SODA'98
• A collision detection page in Brown
• A page for collision detection seminar
• A page in Ohio State University
• Some simple intersection tests for games
• A Faster Overlap Test for a Plane and a Bounding Box
• Real-Time Collision Detection Mpegs Based on Hierarchical Incremental Computation
• Collision Detection for Animation
• Collision Detection Video
• Discussion about collision detection
• Computer Graphics and Simulation Hot-list

People Interested in Collision Detection

• Stephen Cameron
• Kelvin Chung
• Leonidas Guibas
• Stefan Gottschalk
• Taosong He
• Martin Held
• Philip Hubbard
• Jim Klosowski
• Petr Konecny
• Ming Lin
• Dinesh Manocha
• Brian Mirtich
• Joe Mitchell
• Ian Palmer
• Gino van den Bergen
• Gabriel Zachmann

jgao@cs.stanford.edu
aaltman@cs.stanford.edu
Last modified: May 25th, 2001