Graphics Reference
In-Depth Information
The remaining last 4 bytes on the cache line can be used to facilitate a com-
pact representation of linkage to other subtrees. Let the first 3 bytes form an index
into the array of existing subtrees, specifying where the first child subtree starts. Then
let the 8 bits of the last byte specify which of the eight pairs of children are present,
in that a subtree node at the fourth level will either have two or no children. To find
the actual offset from the 3-byte index, at which point a given pair of child subtrees
can be located, the bits corresponding to the preceding trees can then be added and
multiplied by 128, the size of two cache lines. The following code illustrates how to
compute pointers to the left and right subtrees of a
k
-d tree node using the described
representation.
// Align tree root to start of cache line (64-byte aligned)
void ComputeChildPointers(KDNode *pRoot, KDNode *pNode, KDNode **pLeft, KDNode **pRight)
{
int32 nodeAddress = (int32)pNode;
int32 nodeIndex = (nodeAddress & 0x3f) >> 2;
// node index within cache line (0-14)
int32 leftAddress, rightAddress;
if (nodeIndex < 7) {
// Three out of four children are at 2n+1 and 2n+2 within current cache line
leftAddress = nodeAddress + (nodeAddress & 0x3f) + 4;
rightAddress = leftAddress + 4;
} else {
// The children are roots of subtrees at some other cache lines
int32 rootAddress = (int32)pRoot;
int32 bitIndex = nodeIndex - 7;
// (0-7)
// Last word on cache line specifies linking of subtrees
int32 linkWord = *((int32 *)(nodeAddress | 0x3c));
assert(linkWord & (1 << bitIndex));
// must be set
int32 offset = PopCount8(linkWord & ((1 << bitIndex) - 1));
leftAddress = rootAddress + ((linkWord >> 8) + offset * 2) * 64;
rightAddress = leftAddress + 64;
// at next consecutive cache line
}
*pLeft = (KDNode *)leftAddress;
*pRight = (KDNode *)rightAddress;
}
The function
PopCount8()
computes the number of bits set in a byte. It can be
implemented as a repeated parallel process in which first all odd bits are masked out
and added to the even bits to form partial sums (of consecutive pairs of odd and even
bit values) in each pair of two bits. These partial sums can then be masked and added
in the same fashion until the final result is obtained.
