Graphics Reference
In-Depth Information
// Compressed AABB node
struct PackedAABBNode {
uint8 flags;
// Bits determining if new extent belong to left or right child
uint8 newExtent[6];
// New extents, quantized within the parent volume
...
// Potential links to children nodes
};
void ComputeChildAABBs(AABB &parent, PackedAABBNode &node, AABB *left, AABB *right)
{
for(inti=0;i<6;i++) {
intxyz=i&3;
// Compute the actual side value from the quantized newExtent[] value
float min = parent.min[xyz], max = parent.max[xyz];
float val = min + (max - min) * (float)node.newExtent[i] / 255.0f;
// Test bits to see which child gets parent side value and which gets new value
if (node.flags & (1 << i)) {
(*left)[i] = parent[i];
// Left child gets parent's bound
(*right)[i] = val;
// ...right child gets computed bound
} else {
(*left)[i] = val;
// Left child gets computed bound
(*right)[i] = parent[i];
// ...right child gets parent's bound
}
}
}
The two remaining bits of the flag field can, for example, be used to indicate
whether the node is a leaf or an internal node. In the presentation in [Gomez01],
pointers to children nodes are given as two 16-bit indices, bringing the total node size
to 11 bytes. For a static tree, one or both pointers could be omitted, making the node
size even smaller. It is very important that extent values be rounded correctly upon
packing, so that the quantized child AABB volumes are conservative and encompass
the original child volumes.
13.4.3
Cache Obliviousness
An alternative to cache-aware algorithms and data structures is the class of
cache-
oblivious
algorithms and data structures [Frigo99]. Rather than optimized for a given
architecture, these are designed so as to perform well on arbitrary targets with different
cache setups. They are conjectured to be no worse than a factor
O
(log
n
) slower than
cache-aware methods [Prokop99].
