Graphics Reference
In-Depth Information
also important to make sure the worst case for the selected algorithms is not taking
a magnitude longer than the average case.
A number of things can be done to speed up collision processing, which in large
part is what this topic is about. Some general ideas of what optimizations are relevant
for collision detection are discussed in the next section.
2.5.1
Optimization Overview
The first tenet of optimization is that nothing is faster than not having to perform a
task in the first place. Thus, some of the more successful speed optimizations revolve
around pruning the work as quickly as possible down to the minimum possible. As
such, one of the most important optimizations for a collision detection system is
the broad-phase processing mentioned in Section 2.4.1: the exploitation of objects'
spatial locality. Because objects can only hit things that are close to them, tests against
distant objects can be avoided by breaking things up spatially. Tests are then only made
against the regions immediately nearby the object, ignoring those that are too far away
to intersect the object. There are strong similarities between this spatial partitioning
and what is done for view frustum culling to limit the number of graphical objects
drawn.
Spatial partitioning can be performed using a flat structure, such as by dividing
space into a grid of cells of a uniform size. It also can be implemented in terms of a
hierarchy, where space is recursively divided in half until some termination goal is
met. Objects are then inserted into the grid or the hierarchy. Grids and hierarchical
partitioning are also useful for the pair tests of the narrow phase, especially when
the objects have high complexity. Rather than having to test an entire object against
another, they allow collision tests to be limited to the parts of two objects nearest
each other. Object and spatial partitioning are discussed in Chapters 6 and 7.
Doing inexpensive bounding volume tests before performing more expensive geo-
metric tests is also a good way of reducing the amount of work needed to determine
a collision. Say encompassing bounding spheres have been added to all objects, then
a simple sphere-sphere intersection test will now show — when the spheres do not
overlap — that no further testing of the complex contained geometry is necessary.
Bounding volumes are covered in Chapter 4.
The insight that objects tend to take small local steps from frame to frame — if
moving at all — leads to a third valuable optimization: to exploit this
temporal
(or
frame-to-frame
)
coherency
. For example, only objects that have moved since the last
frame need to be tested; the collision status remains the same for the other objects.
Temporal coherency may also allow data and calculations to be cached and reused over
one or more future frames, thus speeding up tests. Assumptions based on movement
coherency are obviously invalidated if objects are allowed to “teleport” to arbitrary
locations. Coherence is further discussed in Chapter 9.
Last, architecture-specific optimizations are also very important. Many platforms
support some type of code or data parallelism that when fully exploited can provide
