## 4.2 Aggregates

Acceleration structures are one of the components at the heart of any ray
tracer. Without algorithms to reduce the number of unnecessary ray
intersection tests, tracing a single ray through a scene would take
time linear in the number of primitives in the scene, since the ray would
need to be tested against each primitive in turn to find the closest
intersection. However, doing so is extremely wasteful in most scenes, since
the ray passes nowhere near the vast majority of primitives. The goals of
acceleration structures are to allow the quick, simultaneous rejection of
*groups* of primitives and to order the search process so that
nearby intersections are likely to be found first so that farther away ones can
potentially be ignored.

Because ray–object intersections can account for the bulk of execution
time in ray tracers, there has been a substantial amount of research into
algorithms for ray intersection acceleration. We will not try to explore all
of this work here but refer the interested reader to references in the
“Further Reading”
section at the end of this chapter and in particular Arvo and Kirk’s chapter in *An Introduction
to Ray Tracing* (Glassner 1989a), which has a useful taxonomy for classifying different
approaches to ray-tracing
acceleration.

Broadly speaking, there are two main approaches to this problem: spatial subdivision and object subdivision. Spatial subdivision algorithms decompose 3D space into regions (e.g., by superimposing a grid of axis-aligned boxes on the scene) and record which primitives overlap which regions. In some algorithms, the regions may also be adaptively subdivided based on the number of primitives that overlap them. When a ray intersection needs to be found, the sequence of these regions that the ray passes through is computed and only the primitives in the overlapping regions are tested for intersection.

In contrast, object subdivision is based on progressively breaking the objects in the scene down into smaller sets of constituent objects. For example, a model of a room might be broken down into four walls, a ceiling, and a chair. If a ray doesn’t intersect the room’s bounding volume, then all of its primitives can be culled. Otherwise, the ray is tested against each of them. If it hits the chair’s bounding volume, for example, then it might be tested against each of its legs, the seat, and the back. Otherwise, the chair is culled.

Both of these approaches have been quite successful at solving the general
problem of ray intersection computational requirements; there’s no
fundamental reason to prefer one over the other. The `KdTreeAccel` in
this chapter is based on the spatial subdivision approach, and the
`BVHAccel` is based on object subdivision.

The `Aggregate` class provides an interface for grouping multiple
`Primitive` objects together. Because `Aggregate`s themselves
implement the `Primitive` interface, no special support is required
elsewhere in `pbrt` for intersection acceleration. `Integrator`s can
be written as if there was just a single `Primitive` in the scene,
checking for intersections without needing to be concerned about how
they’re actually found. Furthermore, by implementing acceleration in this
way, it is easy to experiment with new acceleration techniques by simply
adding a new `Aggregate` primitive to `pbrt`.

Like `TransformedPrimitive`s do, the implementation
of the `Aggregate` intersection methods
leave the `SurfaceInteraction::primitive` pointer set to the primitive
that the ray actually hit, not the aggregate that holds the primitive.
Because `pbrt` uses this pointer to obtain information about the primitive
being hit (its reflection and emission properties), the
`GetAreaLight()`, `GetMaterial()`, and
`ComputeScatteringFunctions()` methods of `Aggregate`s should
never be called, so the implementations of those methods (not shown here)
issue a run-time error.