Graphics Reference
In-Depth Information
values: one specifying the axis the split was along and the other the coordinate value
of the splitting point along that axis. If instead the node is a leaf node, it must contain
a pointer or an index into an array of the data contained in the leaf. For ease of use,
the splitting value is assumed to be given as a single-precision float.
At this point, a key insight is that changing the low-order bit(s) of the 23-bit
floating-point mantissa will only ever so slightly change the value of the number. For
the splitting plane of a
k
-d tree, this slight movement would be completely insignif-
icant. Thus, without any ill effects the two low-order bits of the mantissa can be
appropriated to store some other data. Specifically, the two low bits can be used to
indicate the type of the node, with binary values 00, 01, and 10 specifying the
x
,
y
,or
z
axis, respectively, as the splitting axis for an internal
k
-d tree node. The binary value 11
is used to indicate that the
k
-d tree node is a leaf node. When the node is a leaf node,
the remaining 30 bits contain an index referring to the actual leaf contents stored
elsewhere. Taking these ideas into account, a
k
-d tree node can be expressed as:
union KDNode {
float splitVal_type;
// nonleaf, type 00 = x, 01 = y, 10 = z-split
int32 leafIndex_type;
// leaf, type 11
};
By having the type bits be the low two bits of the float, it is possible to directly use
splitVal_type
as a float without stripping off the type bits. As argued, leaving them
intact simply moves the splitting plane by a minuscule and insignificant amount.
Overall, a
k
-d tree node can therefore be efficiently represented as a 32-bit value.
Assuming a cache line width of 64 bytes, a single cache line can hold a complete
four-level
k
-d tree of 15 nodes output in breadth-first order (thus the children for a
node at a 0-based index
n
can directly be located at positions 2
n
+
1 and 2
n
+
2). See
Figure 13.4 for an illustration of the overall format.
A complete tree could now be stored by cutting the tree every four levels deep and
outputting the resulting subtrees of 15 nodes in breadth-first order. Given a pointer,
pNode
,toa
KDNode
, pointers to the children can quickly be determined without further
memory accesses.
// 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
