Graphics Reference
In-Depth Information
Note that the original query code remains the same. It has only been bracketed
by the grouped query code, making it easy to post-fit this type of optimization to
existing code.
The type of optimization done here can be seen as a form of caching, and it would
be possible to keep track of the alternative starting node from frame to frame, incre-
mentally updating it by moving up and down the tree as the group of objects moved.
The next section looks further at caching as a means of optimizing collision queries.
6.7
Improved Queries Through Caching
Caching serves as a very important means of optimizing collision queries. The basic
idea is very simple. By keeping track of various information about the last collision
query (or queries) an object was involved in, that information can often be used in
a subsequent query to speed it up by “jump-starting” the calculations, thanks to the
spatial and temporal coherence objects tend to exhibit.
The information cached can be classified in two types:
positive
(meaning it helps
in more quickly detecting that the two objects are colliding) and
negative
(meaning it
aids in determining the separation of the two objects). Specific pieces of information
that can help quickly answer decision problems are referred to as
witnesses
.
In addition to caching witnesses and start nodes in hierarchies, caching can also
be used for instance to keep track of both upper and lower distance bounds as an aid
to excluding or including objects from further query processing. The caching ideas
presented in the following sections are in no way intended as a full coverage but as
a means of conveying through a few examples how caching can be used.
To facilitate caching it is helpful to associate an identity number with each unique
query. This number can then serve as a key for a hash table in which the cached data
is kept.
Something to keep in mind is that game restarts, object teleportation, activation
or deactivation, and similar events can potentially wreak havoc on a caching system.
It is important that cache structures are reset or invalidated whenever required by
exception events such as the foregoing.
6.7.1
Surface Caching: Caching Intersecting Primitives
The most obvious caching scheme is to store one or more overlapping primitives from
each object when the objects are found colliding. These primitives serve as witnesses
of the collision. The next time the same two objects are tested for overlap these cached
primitives can be tested first to see if they are still in collision. If so, a test query can
immediately return without having to examine the full hierarchies, worst case. The
drawback is that this type of caching method only works for test queries. If for instance
all contacts are needed, no caching scheme of this type is able to provide a correct
answer.
