Optimization - Real-Time Collision Detection - page 535

// If leaf not in cache at this address, cache it
CachedLeaf *pCachedLeaf = &leafCache[hashIndex];
if (pCachedLeaf- > pLeaf != pLeaf) {
// Set cache key to be pLeaf pointer
pCachedLeaf- > pLeaf = pLeaf;
// Fetch all triangles and store in cached leaf (linearized)
int numTris = pLeaf- > numTris;
pCachedLeaf- > numTris = numTris;
for(inti=0;i<numTris; i++) {
Triangle *pCachedTri = &pCachedLeaf->triangle[i];
IndexedTriangle *pTri = &triangle[pLeaf->tri[i]];
pCachedTri->p0 = vertex[pTri->i0];
pCachedTri->p1 = vertex[pTri->i1];
pCachedTri->p2 = vertex[pTri->i2];
}
}
// Leaf now in cache so use cached leaf node data for processing leaf node
int numTris = pCachedLeaf- > numTris;
for(inti=0;i<numTris; i++) {
Triangle *pCachedTri = &pCachedLeaf- > triangle[i];
DoSomethingWithTriangle(pCachedTri- > p0, pCachedTri- > p1, pCachedTri- > p2);
}
...
For a 64-byte cache line, the original uncached code might in the worst case touch
10 cache lines for a single triangle: two cache lines for the leaf structure, two for the
indexed triangle structure, and two for each of the vertices. Even if each individual
piece of data has been padded to align to a cache line, the worst case is still upward
of five cache line accesses. With the leaf in cache, the cached code would touch at
most two cache lines per triangle and often just one cache line.
13.5.2 Amortized Predictive Linearization Caching
The linearization concept can also be used in more advanced caching schemes. As
an example, consider a static tree hierarchy representing the world geometry. Let
a collision query be issued for, say, a spherical volume surrounding the immediate
neighborhood of a player character. By caching all polygon data within this volume
into a linearized format, as long as the player remains within the sphere only the
cached data has to be tested and the main hierarchy does not have to be traversed or
tested against.