Game Development Reference
The construction stage is divided in four steps:
1. Generate AABBs and 32-bit Morton codes for each primitive.
2. Sort primitives using their Morton codes as their keys.
3. Build the tree.
4. Generate AABBs for each node.
Generate AABBs and Morton codes for each primitive. The first step is straight-
forward. Each thread computes the Morton code of one primitive. This process
assumes that the bounding box for the whole model is known. Since we know
the boundaries of the bounding box of the root, it is possible to initialize node 0
(which is invalid) and node 1, which “contains” the whole model. The output of
this stage is the input of the sorting algorithm. Each primitive is represented by
a Morton code in order to take advantage of its space coherence. The code used
is shown in Listing 1.2.
// The centroid is not divided by 3
// so we have to adjust the points of the box.
float3 bbMin = (3*g_vfMin);
float3 bbMax = (3*g_vfMax);
// inverse of the boundaries (size of the grid)
float3 invBox = 1024.0f / (bbMin - bbMax);
// Set initial bits according to the position of the primitive.
int3 primComp = int3((vfCentroid - bbMin) * invBox);
uint zComp = (primComp.z & 1);
uint yComp = ((primComp.y & 1) << 1);
uint xComp = ((primComp.x & 1) << 2);
// Initialize Morton code's components.
uint mCode = zComp | yComp | xComp;
int shift3 = 2;
int shift = 2;
// 30 bits for the Morton code (xyz=3 shifts*10)
for ( int j = 1; j < 10; j++)
mCode |= (tmp.z & shift) << (shift3++);
mCode |= (tmp.y & shift) << (shift3++);
mCode |= (tmp.x & shift) << (shift3);
shift <<= 1;
// Copy to global memory.
g_uMortonCode[index].primitiveId = index;
g_uMortonCode[index].code = mCode;
Listing 1.2. Computation of the Morton code for each primitive.