14. Collision Detection and Proximity Queries
Monday, Half Day, 8:30 am - 12:15 pm
Room 515A
Level: Intermediate

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.

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.

Co-Organizers
Dave Eberle
Sunil Hadap
PDI/DreamWorks

Lecturers
Dave Eberle
PDI/DreamWorks

Christer Ericson
Sony Computer Entertainment America

Sunil Hadap
PDI/DreamWorks

Ming C. Lin
University of North Carolina at Chapel Hill

Stephane Redon
University of North Carolina at Chapel Hill

Pascal Volino
MIRALab, Université de Genève

Schedule

	Session I - Introduction
8:30	Overview Hadap
8:55	Primitive Tests Eberle
9:20	Session II - Broadphase and Midphase Optimizations Volino
10	Collision Algorithms for Rigid Bodies Lin
10:15	Break
	Session III - Algorithms for Rigid Convex Objects
10:40	Feature Tracking Lin
10:55	Gilbert-Johnson-Keerthi (GJK) Algorithm Ericson
	Session IV - Advance Topics
11:20	Continuous Collision Detection for Deforming Geometry Eberle
11:30	Continuous Collision Detection for Rigid Geometry Redo
11:55	Adaptively Sampled Distance Fields Hadap
12:05	Collision Detection Using GPU Lin