Two-Level Hierarchies for Instanced Scenes

A forest of identical trees is one mesh and many placements. A crowd is a handful of body meshes, each posed and positioned thousands of times. The naive hierarchy over such a scene stores every copy’s triangles, so a mesh with a million primitives instanced ten thousand times would need ten billion primitive entries, and no build or traversal would survive it. The two-level hierarchy exists to avoid that multiplication: one structure over the placements, and one shared structure over each distinct mesh.

The structure and what it stores

The top-level structure, usually called the TLAS, holds one leaf per instance. Each leaf carries a transform — a 4×3 affine matrix is the common storage, twelve floats with the implicit last row — a reference to a bottom-level structure, and a material or object identifier. The bottom-level structure, the BLAS, is built once per distinct mesh in the mesh’s own object space and shared by every instance that references it.

The memory consequence is decisive. A BLAS over $m$ primitives costs $O(m)$ nodes and is stored once. The TLAS costs $O(k \log k)$ nodes for $k$ instances and is independent of $m$. Total memory is therefore $O(m + k \log k)$ rather than $O(mk)$. For a mesh of 100,000 triangles instanced 10,000 times, the difference is between roughly a hundred million triangle records if duplicated and one mesh plus a ten-thousand-leaf tree if shared. The build time follows the same scaling: the expensive SAH build over the mesh happens once, and the TLAS build over instance bounds is cheap by comparison because the SAH’s primitive count is $k$, not $mk$.

The trade is that a shared BLAS cannot be specialised. A hierarchy built per instance could use the instance’s world-space bounds and the actual viewing distribution to choose splits; the shared one is built for a generic distribution. Instances far from the camera and instances filling the screen share the same tree, which is the correct default because a hierarchy is built once and traversed many times, and building per instance would multiply the build cost by the instance count for a benefit that only appears when instances differ greatly in their ray distribution.

Transformed traversal and where the interval goes

A ray in world space must reach the BLAS in object space. The standard approach is to transform the ray once per instance, at the moment the traversal enters that instance’s BLAS, and to traverse the BLAS entirely in object space. The alternative — transforming every BLAS node’s box into world space — costs a matrix multiply per node and inflates the boxes, since a transformed axis-aligned box generally becomes an oriented box and its world-space axis-aligned bound is larger than the object-space one. Transforming the ray costs one multiply per instance entry and leaves the boxes tight, which is why it is the standard.

The transform is not free of consequences. Ray direction transformed by a non-uniformly-scaled matrix changes length, so a parameter computed in object space is not the world-space parameter: if the ray is transformed by the inverse of the instance matrix, then $t_{\text{world}} = t_{\text{object}} \cdot |M^{-1} d| / |d|$, a ratio that is constant along the ray because both directions are constant vectors. The traversal can therefore carry one scalar per instance entry that converts object-space parameters to world space, computed once, or it can carry the interval in object space and convert only the final hit. The former is more correct in the presence of pruning against a world-space bound; the latter is cheaper and is what most kernels do, converting the accepted hit’s parameters at the leaf.

The interval must be transformed in the right direction, which is easy to get backwards. The ray enters the instance with an object-space direction of $M^{-1} d$ and a world-space upper bound $t_{\max}$. The object-space bound is $t_{\max}$ multiplied by the ratio above, so a shrinking world-space bound shrinks the object-space one proportionally. If instead the code re-derives the object-space interval from scratch at each instance entry — starting from the instance’s own extents — it loses the pruning obtained so far and re-tests geometry already excluded. The bookkeeping is one float per stack entry, and getting it wrong produces images that are correct but take several times longer.

/* Transform the ray into instance space. The direction is NOT normalised:
   keeping its length preserves the parameter along the original ray. */
typedef struct { float x, y, z; } vec3;

typedef struct {
    float m[3][3];      /* linear part of the inverse instance transform */
    float trans[3];     /* translation of that inverse transform */
    float tinv;         /* conservative |M^-1 d| / |d| bound, per instance */
} inst;

int enter_instance(const inst *in, vec3 o, vec3 d, float tmax,
                   vec3 *o_out, vec3 *d_out, float *tmax_out)
{
    float ox[3] = {o.x, o.y, o.z}, dx[3] = {d.x, d.y, d.z};
    float oo[3], dd[3];
    for (int i = 0; i < 3; i++) {
        oo[i] = in->m[i][0]*ox[0] + in->m[i][1]*ox[1] + in->m[i][2]*ox[2] + in->trans[i];
        dd[i] = in->m[i][0]*dx[0] + in->m[i][1]*dx[1] + in->m[i][2]*dx[2];
    }
    *o_out = (vec3){oo[0], oo[1], oo[2]};
    *d_out = (vec3){dd[0], dd[1], dd[2]};
    /* tmax scales by |M*d| / |d|; compute once per instance, store with it. */
    *tmax_out = tmax * in->tinv;
    return 1;
}

The scalar tinv shown there is the direction-length ratio for the instance, but it is only exact for a uniform scale. Under a non-uniform transform the ratio depends on the direction, so a single scalar is wrong for rays of different orientations and correct only in the sense that it bounds the interval conservatively if computed for the worst case. Kernels that need exactness compute the ratio per ray at instance entry: one length computation in object space and one known length in world space, a square root and a divide, which is why many renderers normalise the world-space direction once and then compute the object-space length as the square root of a quadratic form.

A further consequence of non-uniform scaling is that distances are not preserved, so a lower bound on $t$ derived from the world-space origin’s precision — as in the interval discussion — must be scaled too. A scale of 1000 in one axis makes the object-space bound 1000 times smaller, and the accumulated error in the transformed origin is also amplified by the inverse transform’s norm. The practical rule is that the lower bound after entering an instance should be computed from the transformed origin’s own coordinates, not carried across.

Where the top level fails

The TLAS is a hierarchy over instance bounds, and its quality depends on how much those bounds overlap. Instances that overlap in space cannot be separated by a hierarchy built over their bounding boxes, so every ray crossing the overlap region must descend into both instances’ BLASes. That is not a correctness problem — each will reject its own primitives — but it multiplies the work by the depth of overlap. A crowd where characters stand shoulder to shoulder has instance bounds that touch and often interpenetrate; a pile of rocks has bounds that heavily overlap. In the worst case — a thousand instances all overlapping one region, which happens with particle systems, foliage cards, or a volumetric cloud of sprites — the TLAS degenerates into a linear list and the hierarchy provides nothing.

The usual mitigations are structural rather than algorithmic. The first is to shrink each instance’s stored bound from its object-space box transformed to world space (which is loose for rotated objects) down to the tightest axis-aligned world-space box of the transformed geometry, accepting a one-time cost per instance per transform change. The second is to keep instance vertex data in a form whose bounds are computed after the transform, which is only possible if the instance is baked; dynamic instances must inflate. The third is to use a different top-level structure entirely for such scenes — a grid over the space containing the instances has no bounding-box overlap problem, only a cell-count problem, and the cell size can be tuned to the instance density.

An orthogonal failure is instance count in the thousands with an unbalanced TLAS built by insertion. Building by SAH over instance bounds is possible with the same sweep as the mesh build, but the transform of each instance’s bounds is a per-instance cost that dwarfs the build arithmetic for small instances. A common compromise is to build the TLAS with a coarse binned SAH and rely on the instance count being small relative to the primitive count.

Motion and refitting

A BLAS is expensive to build and cheap to refit if the mesh’s topology is fixed. Skinned characters change vertex positions every frame; their topology does not. Refitting recomputes each node’s bounds bottom-up from the new vertex positions without changing the tree’s shape, which costs one pass over the nodes and is far cheaper than a rebuild.

The quality cost is real. A refit propagates each vertex’s new position up the existing tree, and if the deformation moves geometry into regions the tree did not anticipate, the bounds become loose and the hierarchy degrades a little each frame. Repeated refits over a long animation can leave a tree substantially worse than a fresh build, so the standard practice is to alternate: refit for a bounded number of frames, rebuild when the measured quality falls below a threshold, and choose the threshold from the ratio of box tests to primitive tests. The measurement is cheap and unambiguous, unlike the estimation of how much a given deformation will degrade the tree.

For rigid instances — moving a whole object without deforming it — the BLAS needs no change at all. Only the TLAS’s instance bounds move, and if the TLAS is rebuilt each frame it is a build over a few thousand boxes, which is affordable. For instances that also rotate, the BLAS is unchanged but the world-space bound must be recomputed from the rotated object-space bound, which is the loosest useful bound: the world axis-aligned box of the rotated object-space box has a volume up to the object’s diagonal cubed larger than the object itself, and for elongated objects the looseness is substantial.

Instancing and the material indirection

The BLAS’s leaves must report which instance they belong to, because the intersection point’s object-space coordinates must be transformed to world space for shading and because the material differs per instance. A traversal that enters an instance carries the instance index implicitly, so the leaf’s hit record needs only the instance slot from the stack, not from the leaf, and the BLAS is fully shared. The alternative — baking a per-instance copy of the leaf with the instance identifier stored inline — duplicates the BLAS and defeats the purpose.

Attributes interpolated in object space and then transformed are not equivalent to attributes interpolated in world space, because interpolation is linear and the transform is affine, so the two agree — an affine transform commutes with barycentric interpolation. Normals do not, since they transform by the inverse transpose, so a normal computed from object-space vertex normals and then transformed is correct only if the transform’s inverse transpose is applied to the result, not to the inputs. Computing the world-space normal from the three transformed vertices is the safer route, at the cost of three vertex transforms per hit rather than one normal transform.

The last structural point is that two-level hierarchies compose. An instance can reference a BLAS that itself contains instances, giving a multi-level structure for scenes assembled from assemblies. The bookkeeping is a stack of transforms and a matching stack of intervals, and the depth is the nesting depth, which is bounded by the scene’s authoring and not by the geometry. Each level costs one ray transform and one interval conversion on entry, and each exit restores the previous frame — which means the traversal must be strictly nested, so deferred siblings at one level cannot be visited while inside another level’s BLAS. That constraint makes the stack entry richer: a deferred entry must remember which level it belongs to and what transform applies there, which is why deep instancing is usually flattened to two levels by the exporter rather than handled at traversal time. The flattening duplicates BLAS references but keeps the traversal’s state small, and the trade between state size and tree depth is the same one that governs stack depth in a flat hierarchy.