Graphics Reference
In-Depth Information
To remove the indirection inherent in this leaf structure, leaves can be cached into
a leaf node structure that contains all information as a consecutive block of data.
// Explicitly declared triangle, no indirection
struct Triangle {
Point p0, p1, p2;
};
// 2
∧
N-1 for fast hash key masking w/ '&'
#define NUM_LEAFCACHE_ENTRIES (128-1)
// Cached leaf node, no indirection
struct CachedLeaf {
Leaf *pLeaf;
// hash key corresponding to leaf id
int16 numTris;
// number of triangles in leaf node
Triangle triangle[MAX_TRIANGLES_PER_LEAF];
// the cached triangles
} leafCache[NUM_LEAFCACHE_ENTRIES];
Figure 13.7 illustrates how the leaves of the previous tree structure are associated
with a cache entry containing the linearized data, allowing triangles to be processed
without any indirection at all.
The code that processes a leaf node can now be written to see if the node is already
in cache, cache it if it is not, and then operate on the cached leaf node data.
// Compute direct-mapped hash table index from pLeaf pointer (given as input)
int32 hashIndex = ((int32)pLeaf >> 2) & NUM_LEAFCACHE_ENTRIES;
Cached linearized leaf:
(x
0
,
y
0
,
z
0
)(x
2
,
y
2
,
z
2
)(x
3
,
y
3
,
z
3
)(x
0
,
y
0
,
z
0
)(x
4
,
y
4
,
z
4
)
...
Figure 13.7
The same structure as in Figure 13.6, now linearized through a caching scheme
so that vertices can be directly accessed with no indirection.
