Graphics Reference
In-Depth Information
0
1
2
3
4
5
6
7
8
9 011
12
13
14
31
0
1
leaf index
1 1
31
0
S
E
M
n n
index to first child node
0
1
2
3
4
5
7
64 byte cache line
6
8
9
10
11
12
13
14
Figure 13.4 An efficient representation of a k -d tree. A 64-byte cache line holds a four-level
k -d tree, with 15 nodes in the first 60 bytes. The last 4 bytes of the cache line indicate which
eight child subtree pairs exist and where they can be located.
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 cacheLineFromStart = (nodeAddress - rootAddress) >> 6;
int32 leftCacheLine = 16 * cacheLineFromStart + 1;
int32 bitIndex = nodeIndex - 7; // (0-7)
leftAddress = rootAddress + leftCacheLine * 64 + bitIndex*2*64;
rightAddress = leftAddress + 64; // at next consecutive cache line
}
*pLeft = (KDNode *)leftAddress;
*pRight = (KDNode *)rightAddress;
}
A single root-leaf traversal of a tree of depth d would now only read d /4 cache lines
compared to the worst-case d cache lines of, for example, a preorder traversal order
output.
Even with just 4 bytes per node, storing a complete tree is still very expensive.
Instead of requiring each subtree to have 16 children for the full depth of the tree,
ideally only those subtrees actually present should be stored.
 
Search WWH ::




Custom Search