Global Illumination - The Magic of Computer Graphics - page 48

(a) (b) (c) (d)

(e) (f) (g) (h)

Figure 2.19 GPU photon lookup. (After [Purcell et al. 03].)

radius is expanded to include it. (There are two photons in this cell, which
is shaded in Figure 2.19(b) and (c) ; the search radius is increased with each
photon found.)

3. The search moves outward to the pixels corresponding to the current search
radius, then Step 2 is applied at each pixel. Once k photons have been
added, the search radius stops expanding, but photons continue to be added.
This assures that the nearest photons are always included, although there
may be more than k of them. (This is shown in Figure 2.19(d)-(f) . In
Figure 2.19(d) , one photon is added, but the photon outside the maximum
search radius is excluded. In Figure 2.19(e) , the two photons inside the
search radius are added, which brings the total to five—one more than
needed. The one photon outside the search radius but inside the maximum
radius is excluded because enough have been added. In Figure 2.19(f) a
sixth photon is added.)

4. Step 3 is repeated until at least k photons are found, or only pixels outside
the maximum search radius remain. (As shown in Figure 2.19(g) , the search
circle hits three more pixels, but none contain contributing photons.)

The shaded circle in Figure 2.19(h) shows the effective search radius and the col-
lected photons. The algorithm differs from the original photon lookup algorithm
in that it computes the radius estimate of at least knear neighbors rather than
exactly the k nearest neighbors.
The photon lookup, the calculation of the radiance, and the storage of the
result in the final image framebuffer pixel are all done in one pass. The image
framebuffer is updated at each bounce, so it is possible to watch the simulation