SIGGRAPH 2004 - The 31st international conference on computer graphics and interactive techniques
Conferenece Exhibition Call For Participation Presenters Media Registration spacer

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.

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.

Dave Eberle
Sunil Hadap

Dave Eberle

Christer Ericson
Sony Computer Entertainment America

Sunil Hadap

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

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

1       2       3      
4       5       6      
7       8       9      
10     11     12
13     14     15
16     17     18
19     20     21
22     23     24
25     26     27
28     29     30
31     32     33
Course Evaluation
All course attendees are encouraged to evaluate SIGGRAPH 2004 Courses content and presenters.

Online Evaluation Forms

Your ratings and comments are very important. They will be used to ensure that the annual SIGGRAPH conference consistently offers excellent courses on topics that are important to the SIGGRAPH community.
 > courses committee
 > share the SIGGRAPH 2004 web site
Conference 8-12 August, Exhibition 10-12 August.  In Los Angeles, CA