“Collision Detection and Proximity Queries” by Eberle, Hadap, Ericson, Lin, Redon, et al. …
Conference:
Type:
Entry Number: 14
Title:
- Collision Detection and Proximity Queries
Course Organizer(s):
Presenter(s)/Author(s):
Abstract:
Prerequisites
Elementary geometry, introduction to data structures, linear algebra, and a penchant for collision detection.
Intended Audience
Practitioners of simulation, VR, haptics and robotics. Effects developers, technical directors, and aspiring researchers of spatial data structures.
Description
An authoritative overview of widely accepted and proved methodologies in collision detection. The course also introduces more advanced or recent topics such as continuous collision detection, ADFs, and using graphics hardware. When appropriate, methods will be tied to familiar applications such as rigid body and cloth simulation.
An essential task of most collision-detection schemes involves determining whether two geometric primitives are intersecting. The course reviews higher-level concepts such as the separating axis theorem and ray intersection. General strategies for efficient implementation of these tests are discussed and concise references to specific tests are provided.
Other topics include: algorithms devised to reduce the number of expensive primitive tests, bounding volume hierarchies for deformable and rigid geometry, the sweep and prune algorithm will be described and compared, the GJK algorithm as an efficient method of finding the proximity of convex geometry, and more general feature tracking methods.
A common problem in many applications that include collision detection is that of temporal aliasing. If objects are moving too fast between collision detection calls, many techniques fail to report a collision. Continuous methods offer a solution to this problem. In addition to being more robust, they have the ability to provide very accurate contact information, which is essential to many simulation applications. The course discusses continuous techniques for deforming and rigid geometry, along with strategies for their efficient implementation.
Adaptively sampled distance fields provide a means to determine penetration depth and direction of collision. The course presents techniques for building ADFs along with their applications and recent advances in GPU-based collision computation.
