Graphics Reference
In-Depth Information
// Computes the KDOP d of KDOPs d0 and d1
void KDOPEnclosingKDOPs(KDOP &d, KDOP d0, KDOP d1, int k)
{
for(inti=0;i<k/2;i++) {
d.min[i] = Min(d0.min[i], d1.min[i]);
d.max[i] = Max(d0.max[i], d1.max[i]);
}
}
6.6 Efficient Tree Representation and Traversal
So far, hierarchy construction and traversal has been described in a fairly abstract
manner. However, for an industrial-strength implementation it is important to opti-
mize both the traversal code and the tree representation itself. As memory accesses
and branch prediction misses tend to cause large penalties in modern architectures,
two obvious optimizations are to minimize the size of the data structures involved
and to arrange the data in a more cache-friendly way so that relevant information is
encountered as soon as possible.
This section describes a few data representations and traversal optimizations that
help speed up collision queries. However, always remember that due to difficult-to-
predict cache behaviors some of these more advanced techniques might not always
provide the expected speedups. If this is the case, consider that keeping the traversal
code as short and straightforward as possible might in fact be a simple way of making
it faster. Efficient tree representation is revisited in Chapter 13, in the context of
memory optimization.
6.6.1 Array Representation
Assume a complete binary tree of n nodes is given as a collision hierarchy. This tree
can be stored into an array of n elements by mapping its nodes in a breadth-first
level-by-level manner.
// First level
array[0] = *(root);
// Second level
array[1] = *(root->left);
array[2] = *(root->right);
// Third level
array[3] = *(root- > left- > left);
...
 
Search WWH ::




Custom Search