Graphics Reference
In-Depth Information
Software caching also works well with keeping collision data compressed. For
example, the leaves of a tree can be stored in a compressed format in the main
data structure. A software cache can now be established for the leaf nodes such that
whenever a leaf is visited it is checked whether a cached node exists for the leaf. If
it does not, the compressed data is uncompressed and cached with the leaf
id
as the
key. This particular application is outlined in more detail in the following section.
Memory can also be saved in a different sense using software caching. Normally, to
avoid runtime computations a lot of data is stored that could be computed at runtime
from other data already present. Redundant data might include the AABB bounds of
the content of a tree leaf node or face normals stored alongside the collision faces.
Using software caching, these items could be omitted from the stored data and, for
example, face normals could instead be computed on the fly from the vertex data and
stored during the caching step. This type of caching could also be used to remem-
ber certain expensive calculations, such as freezing any required transformations of
collision primitives.
Thanks to the spatial and temporal coherence exhibited by most collision queries,
the cost of decompressing or rederiving data and then caching it becomes amortized
over a number of queries, making the per-query overhead of caching largely negli-
gible. Because only those leaves at which queries are taking place are being cached,
spatial coherence implies that only a small number of cache entries is needed.
Another benefit of using software caching is that it allows the data format used in
the cache to serve as a unified format all code can work against. New data structures
can now be added to the system by providing a means to cache its data into the
unified format. A unified format allows the low-level primitive tests to be written
just once, better facilitating heavy optimization without risking having data format
changes invalidating the code.
Depending on how high-level cache systems are implemented, it might be useful
to provide the user with the option to enable or disable the software cache on a call-
by-call basis, so that time is not spent on caching for a query the user knows would
not benefit from it. Another potentially useful design option is to consider having
the cache exist in “soft” memory. That is, the cache exists in the unused part of the
memory manager heap and parts of the cache are invalidated when that memory is
reclaimed through an allocation from the memory manager. Usually software caches
are implemented through hashing into an array of fixed-size elements. For more detail
on hashing see [Knuth98]. The usefulness of software caching in a game context is
discussed in [Sauer01].
13.5.1
Cached Linearization Example
Software caching can help linearize data structures by following any indices and
removing all indirection by retrieving and caching all referenced data into a consec-
utive area of memory. The increased level of data locality improves the CPU data
