Optimization - Real-Time Collision Detection - page 529

inline int32 PopCount8(int32 n)
{

n=n-((n&0xaa) >> 1); // Form partial sums of two bits each

n = (n & 0x33) + ((n >> 2) & 0x33); // Form partial sums of four bits each

return (n + (n >> 4)) & 0x0f; // Add four-bit sums together and mask result

}

Alternatively, PopCount8() can be implemented using a small (4- or 8-bit-wide)
lookup table. The cost for computing the address of the children increases somewhat
under this method compared to storing a full complete tree, but it still compares
favorably to the cost of the incurred cache misses of most other schemes.
With appropriate changes, the same overall design principle applies to other cache
line widths. For example, with a 32-byte cache line the nodes would have to be
reduced to contain a three-level tree instead of the four-level tree presented here.
The k -d tree structure presented here was first presented in [Ericson03]. A similar
approach to efficiently representing k -d trees is presented in [Szécsi03].

13.4.2 A Compact AABB Tree

AABB trees can be expressed in a compact format with the help of a simple observa-
tion: because the six sides of a parent AABB will all come from either or both children
AABBs, at most six additional faces are required to be able to reconstruct the two child
AABBs from the bounds of the parent AABB. That is, the minimum x value of the par-
ent AABB must be either the minimum x value of the left child AABB or the minimum
x value of the right child AABB. Additionally, 6 bits are needed to specify which child
inherits a given side from the parent and which child gets its side determined by one
of the six additional faces given.
Instead of expressing the new face values as floats, the memory requirements can
be reduced further by quantizing them to a byte each, defining them in terms of a ratio
of the parent sides [Gomez01]. The following code illustrates the node layout and
how the children AABBs are reconstructed from the parent AABB and a compressed
AABB node.

// Uncompressed AABB
struct AABB {
float & operator [](int n) { return ((float *)this)[n]; }
Point min; // The minimum point defining the AABB

Point max; // The maximum point defining the AABB

};