Recent Advances in Real-Time Collision and Proximity Computations for Games and Simulations

This course is intended for instructing students and practitioners on recent developments related to collision and proximity computations for interactive games and simulations. There have been significant advances in various physics-based simulation techniques for movies, interactive games, and virtual environments. Most recent work has been on achieving realistic simulations of rigid, articulated, deforming, and fracturing models. However, many complex and challenging simulations (e.g., fracturing simulation) are not widely used in interactive games because of their computational requirements, although the hardware capability of current CPUs and GPUs has considerably improving. It is well known that one of the main performance bottlenecks in most simulations lies in proximity queries including collision detection, minimum separation distance, and penetration depth computations. As a result, there has been significant recent research on developing real-time proximity computation algorithms for interactive games and high-quality simulations. Some of recent advanced techniques are able to achieve interactive performance even for most challenging simulations such as fracturing or large-scale cloth simulations. However, these techniques are quite complicated. Moreover, they require in-depth geometric background and sophisticated optimizations on multi-core architectures. These techniques, therefore, have not been easily accessible to students and practitioners who work on real-time simulation methods. Our objective is to introduce and teach students and practitioners about efficient proximity computation methods and their practical implementations. By doing so, we can expose the attendees to the latest developments, to bridge the gap between the two different fields: proximity computation and simulation. At a broad level, this course will cover the following topics: Basic algorithms for various proximity queries including collision detection, minimum separation distances, penetration depth, etc.; Discrete and continuous algorithms for rigid, articulated, deforming, and fracturing models. Parallel algorithms that utilize many cores of CPUs, GPUs, or CPUs/GPUs. Applications of various proximity queries in Havoc, a widely used Physics simulation package. Optimized proximity data structures for many-core architectures including GPU. Integrating proximity computation algorithms into physically-based simulation systems. We have four instructors from academia and industry, each of who has significant experiences in designing and implementing different aspects of the aforementioned teaching materials. Since each instructor is a world-class expert in his field, students will receive the best instruction. Moreover, students and practitioners can learn how the industry-leading physics systems benefits from efficient proximity queries.

, booktitle = {
Eurographics 2012 - Tutorials
}, editor = {
Renato Pajarola and Michela Spagnuolo
}, title = {{
Recent Advances in Real-Time Collision and Proximity Computations for Games and Simulations
}}, author = {
Frye, Stephen
Harada, Takahiro
Kim, Young J.
Yoon, Sung-eui
}, year = {
}, publisher = {
The Eurographics Association
}, ISSN = {
}, ISBN = {}, DOI = {
} }