Real-Time Collision Detection

Christer Ericson

• Publisher: CRC Press
• Year: 2004
• ISBN:
  9781000750553
• Edition: 1
• Topic: Kunst
• Subtopic: Kunst Allgemein

Written by an expert in the game industry, Christer Ericson's new book is a comprehensive guide to the components of efficient real-time collision detection systems. The book provides the tools and know-how needed to implement industrial-strength collision detection for the highly detailed dynamic environments of applications such as 3D games, virt

Chapter 1

Introduction

This book is concerned with the subject of collision detection, a broad topic dealing with a seemingly simple problem: detecting if two (or more) objects are intersecting. More specifically, collision detection concerns the problems of determining if, when, and where two objects come into contact. “If” involves establishing a Boolean result, answering the question whether or not the objects intersect. “When” must additionally determine at what time during a movement collision occurred. “Where” establishes how the objects are coming into contact. Roughly, these three types of queries become increasingly more complex to answer in the order given.

Gathering information about when and where (in addition to the Boolean collision detection result) is sometimes labeled collision determination. The terms intersection detection and interference detection are sometimes used synonymously with collision detection.

Collision detection is fundamental to many varied applications, including computer games, physically based simulations (such as computer animation), robotics, virtual prototyping, and engineering simulations (to name a few).

In computer games, collision detection ensures that the illusion of a solid world is maintained. It keeps player characters from walking through walls or falling through floors; it provides for line-of-sight queries, telling enemies if they can see the player and therefore can attack; and it keeps a skateboarder attached to an invisible guide surface, ensuring that the player safely makes it back down into a halfpipe after having gone airborne up it.

In computer animation, collision detection is used, for example, to constrain the physical simulation of cloth, ensuring clothing behaves in a lifelike manner and does not slide off a character as the character moves. Collision detection is used for path planning in robotics applications, helping robots steer away from obstacles. In virtual prototyping, collision detection assists in computing clearances, and overall allows prototypes to be refined without the production of physical models. Collision detection is used in crash tests and other engineering simulations.

Some applications, such as path planning and animation rendering, do not require real-time performance of their collision systems. Others applications, computer games in particular, have extraordinary demands on the real-time efficiency of collision detection systems. Computer- and console-based action games involve simulations requiring that a large number of queries be performed at frame rates of about 30 to 60 frames per second (fps). With such tight time constraints and with collision detection an integral part of game and physics engines, collision detection can account for a large percentage of the time it takes to complete a game frame. In computer games, a poorly designed collision system can easily become a key bottleneck.

This book is not just on collision detection in general, but specifically on the efficient implementation of data structures and algorithms to solve collision detection problems in real-time applications. While the games domain is often used for examples, several nongame applications have performance requirements similar to (or even greater than) those of games, including haptic (force feedback) systems, particle simulations, surgical simulators, and other virtual reality simulations. The methods described here apply equally well to these applications.

Many of the methods discussed herein are applicable to areas other than collision detection. For instance, the methods discussed in Chapters 6 through 8 can be used to accelerate ray tracing and ray casting (for, say, computing scene lighting), and in regard to geographic information systems (GIS) to answer queries on large geographical databases. Some problems from the field of computer graphics can be solved as collision detection problems. For example, view frustum culling can be addressed using the methods described in Chapters 6 and 7.

1.1 Content Overview

The following sections provide a brief outline of the chapters of this book.

1.1.1 Chapter 2: Collision Detection Design Issues

This chapter talks about issues that must be considered when constructing a collision detection system and what factors affect the design. Such factors include how objects are represented, how many of them there are, how they move, and what types of collision queries the user wants to pose. Chapter 2 also introduces terminology used throughout the rest of the book.

1.1.2 Chapter 3: A Math and Geometry Primer

Any nontrivial collision detection system requires a large portion of geometry-oriented mathematics to work out the if, when, and where of collision queries. Chapter 3 introduces the mathematical and geometrical concepts necessary to understand the material explored in the remaining chapters.

1.1.3 Chapter 4: Bounding Volumes

To accelerate collision queries, simple geometrical objects such as spheres and boxes are initially used to represent objects of more complex nature. Only if the “simple” bounding volumes (which are large enough to encapsulate complex objects) collide are tests performed on the complex geometry. Chapter 4 describes several bounding volume types, how to perform intersection tests on them, and how to fit a bounding volume to a complex object.

1.1.4 Chapter 5: Basic Primitive Tests

Having introduced some intersection tests in the previous chapter, Chapter 5 describes, in detail, a large number of tests for determining intersection status and distance between pairs of objects of varying types, including lines, rays, segments, planes, triangles, polygons, spheres, boxes, cylinders, and polyhedra. Both static and moving objects are considered in these tests.

1.1.5 Chapter 6: Bounding Volume Hierarchies

For large objects and for collections of objects, performance benefits can be had by constructing hierarchies of bounding volumes over the object(s). Such hierarchies provide quick identification of objects or parts of an object that cannot possibly participate in a collision, allowing queries to restrict testing to a small number of objects or object parts. Chapter 6 talks about desired characteristics of bounding volume hierarchies and ways in which to construct and perform queries over them. The chapter also explores efficient ways of representing these hierarchies.

1.1.6 Chapter 7: Spatial Partitioning

When a large number of objects are considered for collision, the objects must be partitioned into small disjoint subgroups to facilitate fast tests (by avoiding the worst-case quadratic behavior of testing all objects against all other objects). The bounding volume hierarchies discussed in Chapter 6 represent one way of performing such partitioning. Chapter 7 examines other partitioning approaches, based on grids, trees, and object sorting.

1.1.7 Chapter 8: BSP Tree Hierarchies

One of the most versatile tree structures for representing collision detection data is the binary space partitioning (BSP) tree. BSP trees can be used to partition space independently from the objects in the space. They can also be used to partition the boundary of an object from the space it is in, thereby effectively forming a volume representation of the object. Chapter 8 talks about robustly constructing BSP trees and how to perform tests on the resulting trees.

1.1.8 Chapter 9: Convexity-based Methods

Chapter 9 looks at a number of more advanced methods for performing collision queries on convex objects, exploiting the special properties of convex objects. Presented are hierarchical representations, the V-Clip closest feature algorithm, the mathematical optimization methods of linear and quadratic programming, the efficient Gilbert–Johnson–Keerthi algorithm, and a separating vector algorithm due to Chung and Wang.

1.1.9 Chapter 10: GPU-assisted Collision Detection

PC commodity graphics cards have advanced to a point at which they incorporate more computational power than the main PC CPU. This change has triggered an interest in outsourcing computations to the graphics card. Chapter 10 takes a brief look at how to perform collision detection tests using graphics hardware.

1.1.10 Chapter 11: Numerical Robustness

Even the smallest errors in a collision detection system can lead to catastrophic failures, such as objects failing to collide with world geometry and thus falling out of the world. This chapter discusses the robustness problems associated with working with floating-point arithmetic and suggests approaches to dealing with these problems.

1.1.11 Chapter 12: Geometrical Robustness

Whereas Chapter 11 looked at how to perform calculations robustly, Chapter 12 considers the problem of taking an arbitrary set of polygons and turning it into well-formed geometry, suitable for input into a collision detection system. Presented are methods for welding of vertices, removal of gaps and cracks, merging of coplanar faces, and decomposition of objects into convex (or triangular) pieces.

1.1.12 Chapter 13: Optimization

The last chapter of the book talks about how to take the efficient data structures and algorithms presented throughout the book and make them even more efficient by targeti...