Graphics Reference
In-Depth Information
Some applications, such as path planning and animation rendering, do not
require real-time performance of their collision systems. Others applications, com-
puter 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 topic is not just on collision detection in general, but specifically on the effi-
cient implementation of data structures and algorithms to solve collision detection
problems in real-time applications. While the games domain is often used for exam-
ples, 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 topic.
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 topic.
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.
