Quickly and accurately capturing the the process of light scattering in a volume filled with a participating medium remains a challenging problem, but often it is one that must be solved to achieve photo-realistic rendering. The scattering process can be adequately described by the standard volume radiative transfer equation where is a position in space, is a spherical direction, is the phase function, σ _s is the scattering coefficient, σ _a is the absorption coefficient, σ _t = σ _s + σ _a is the extinction coefficient, and is any emissive field within the volume [1] . This simply says that the change in radiance along any path includes the loss due to absorption and out-scattering (coefficient − σ _t ) and the gain due to in-scattering from other paths (coefficient σ _s ).

Radiative transfer in volumes is a well-studied topic, and many methods for solving Eq. 25.1 have been suggested. Most are a variation on one of a few central themes. Rushmeier and Torrance [25] used a radiosity (finite-element) technique to model energy exchange between environmental zones and hence capture isotropic scattering. Their method requires computing form factors between all pairs of volume elements. Bhate and Tokuta [2] extended this approach to anisotropic scattering, at the cost of additional form-factor computation.

The most popular approach is undoubtedly the discrete ordinates method [3] in which Eq. 25.1 is discretized to a spatial lattice with a fixed number of angular directions in which light may propagate. The need to compute only local lattice point interactions, rather than form factors between all volumes, substantially reduces the computational complexity. Max [21] and Languènou et al . [20] were able to capture anisotropic effects using early variations on this technique. It is well known, however, that this discretization leads to two types of potentially visible errors: (1) light smearing caused by repeated interpolations and (2) spurious beams, called the ray effect. Fattal [8] has recently suggested a method that significantly ameliorates both. Successive iteration across six collections of 2-D maps of rays, along which light is propagated, is employed. The 2-D maps are detached from the 3-D lattice, thus allowing a much finer granularity in the angular discretization. Execution time for grids of reasonable size (e.g., 128 ³ ) is several minutes. Kaplanyan and Dachsbacher [17] have recently provided a real-time variation on the discrete ordinates method that is principally aimed at single-bounce, indirect illumination. The method propagates virtual point lights along axial cells by projecting illumination to the walls of an adjacent cell and then constructing a new point light in the adjacent cell that would deliver exactly that effect. It is not immune to either light smearing or the ray effect, and thus the authors restrict its use to low-frequency lighting. The method is extremely fast, largely owing to relatively low-resolution nested grids that are fixed in camera space and give higher resolution close to the viewer.

A third central theme, and that to which our own method may be attached, is the diffusion approximation . Stam [27] , motivated by earlier work of Kajiya and Von Herzen [16] in lighting clouds, observed that a two-term Taylor expansion of diffuse intensity in the directional component only could be substituted into Eq. 25.1 to ultimately yield a diffusion process that is an accurate approximation for highly scattering (optically thick) media. Jensen et al . [15] showed that a simple two-term approximation of radiance naturally leads to a diffusion approximation that is appropriate for a highly scattering medium. This was later extended to include thin translucent slabs and multilayered materials [7] .

In [11] we introduced an approach to solving Eq. 25.1 based on a Lattice Boltzmann technique and showed how this might be applied to lighting participating media such as clouds, smoke, and haze. In [12] we extended this approach to capture diffuse transmission, interobject scattering, and ambient occlusion, such as needed in photo-realistic rendering of dense forest ecosystems. Most recently, we showed that the technique could be parameterized to allow real-time relighting of scenes in response to movement of light sources [28] .

As originally described in [11] , the technique was effective, but slow. The technique is grid based, and a steady-state solution for a grid of reasonable size (128 ³ nodes) originally required more than 30 minutes on a single CPU. Our goal here is to provide the details of a GPU-based implementation that, for this same size grid, will run on a single GPU in 2 seconds. Example lighting tasks will include clouds, plants, and plastics.

Lattice Boltzmann (LB) methods are a particular class of cellular automata (CA), a collection of computational structures that can trace their origin at least back to John Conway's famous Game of Life [10] , which models population changes in a hypothetical society that is geographically located on a rectangular grid. In Conway's game, each grid site follows only local rules, based on nearest-neighbor population, in synchronously updating itself as populated or not, and yet global behavior emerges in the form of both steady-state colonies and migrating bands of “beings” who can generate new colonies or destroy existing ones.

Arbitrary graphs and sets of rules for local updates can be postulated in a general CA, but those that are most interesting exhibit a global behavior that has some provable characteristic. Lattice Boltzmann methods also employ synchronous, neighbor-only update rules on a discrete grid, but the discrete populations have been replaced by continuous distributions of some quantity of interest. The result is that the provable characteristic is often quite powerful: the system is seen to converge, as lattice spacing and time step approach zero, to a solution of a targeted class of partial differential equations (PDEs).

Lattice Boltzmann methods are thus often regarded as computational alternatives to finite-element methods (FEMs) for solving coupled systems of PDEs. The methods have provided significant successes in modeling fluid flows and associated transport phenomena [4] [13] [26] [29] and [31] . They provide stability, accuracy, and computational efficiency comparable to finite-element methods, but they realize significant advantages in ease of implementation, parallelization, and an ability to handle interfacial dynamics and complex boundaries.

The principal drawback to the methods, compared with FEMs, is the counterintuitive direction of the derivation they require. Differential equations describing the macroscopic system behavior are derived (emerge) from a postulated computational update (the local rules), rather than the reverse. Thus, a relatively simple computational method must be justified by a derivation that is often fairly intricate.

In the section titled “Derivation of the Diffusion Equation,” we provide the derivation of the parameterized diffusion equation for our lighting model. On one hand, the derivation itself is totally irrelevant to the implementation of the LB lighting technique proposed here, and users of the technique may feel free to skip it entirely. On the other hand, if the processes of interest to the user vary, beyond simple parameter changes, from our basic diffusion process, a new derivation will be required, and it is extremely valuable to have such a sample derivation at hand.

Lattice Boltzmann methods are grid based, and so, we begin with a standard 3-D lattice, a rectangular collection of points with integer coordinates in 3-D space. A complication of LB methods in three dimensions is that isotropic flow, whether it is water or photon density, requires that all neighboring lattice points of any site (lattice point) be equidistant. A standard approach, owing to d'Humiéres, Lallemand, and Frisch [6] , is to use 24 points equidistant from the origin in 4-D space and project onto 3-D. The points are: and projection is truncation of the fourth component, which yields 18 directions, that is, the vectors from the origin in 3-D space to each of the projected points. Axial directions then receive double weights. Representation of several phenomena, including energy absorption and energy transmission, is facilitated by adding a direction from each lattice point back to itself, which thus yields 19 directions, the non-corner lattice points of a cube of unit radius.

The key quantity of interest is the per-site photon density. We store this value at each lattice point and then simulate transport by synchronously updating all the values in discrete time steps according to a single update rule. Let denote the density at lattice site at simulation time t that is moving in cube direction , m ∈ {0, 1, …, 18}. If the lattice spacing is λ and the simulation time step is τ , then the update (local rule) is: where Ω _m denotes row m of a 19 × 19 matrix, Ω, that describes scattering, absorption, and (potentially) wavelength shift at each site. If denotes total site density, then the derivation in the the section titled “Derivation of the Diffusion Equation” shows that the limiting case of Eq. 25.2 as λ , τ → 0 is the diffusion equation where the diffusion coefficient As noted, this is consistent with previous approaches to modeling multiple photon scattering events [15] and [27] , which have invariably led to diffusion processes.

For any Lattice Boltzmann method, the choice of the so-called collision matrix, Ω, is not unique. Standard constraints are conservation of mass, , and conservation of momentum, , where and represents any site external force. Here, as in [11] [12] [13] and [28] , for the case of isotropic scattering, we specify Ω as follows:

For row 0: For the axial rows, i = 1, …, 6: For the nonaxial rows, i = 7, …, 18: Entry i , j controls scattering from direction into direction , and thus the nondiagonal entries are scaled values of the scattering coefficient for the medium, σ _s . Diagonal entries must include out-scattering, − σ _t , and, as noted earlier, isotropic flow requires double weights (scale factors) on the axial directions. Directional density f ₀ holds the absorption/emission component. On update, that is, Ω ⋅ f , fraction σ _a from each directional density will be moved into f ₀ . The entries of Ω are then multiplied by the density of the medium at each lattice sight so that a zero density yields a pass-through in Eq. 25.2 and a density of 1 yields a full scattering.

Of course, in general, scattering is anisotropic and wavelength dependent. Anisotropic scattering is incorporated by multiplying σ _s that appears in entry Ω _{i , j} by a normalized phase function: where p _{i, j} (g ) is a discrete version of the Henyey-Greenstein phase function [14] , Here is the normalized direction, . Parameter g ∈ [−1, 1] controls scattering direction. Value g > 0 provides forward scattering, g < 0 provides backward scattering, and g = 0 yields isotropic. Mie scattering [9] is generally considered preferable, but the significant approximations induced here by a relatively coarse grid render the additional complexity unwarranted. Note that Eq. 25.8 , which first appeared in [12] , differs from the treatment in [11] , in that setting σ _a = 0 and g = 1 yields an effect that is identical to a pass-through.

If the media in the model are presumed to interact with all light wavelengths in an identical way, then can be considered to be the luminance density. In our cloud lighting example of Section 25.3.2 , this is the case.

Otherwise, as in our other examples, each discrete wavelength to be modeled is characterized by appropriate scattering parameters and phase function. The Lattice Boltzmann model is run once for each parameter set, and the results are combined in a post-processing (ray-tracing) step.

An alternative approach is to implement as a vector of per-wavelength densities and run the model one time. This approach can be used to incorporate wavelength shifts during the collision process.

The model is thus completely specified by a choice of g , σ _a , and σ _s , any of which can be wavelength-dependent.

Initial conditions include zero photon density in all directions at all interior nodes in the lattice. For each node in the lattice boundary, directions that have positive dot products with the external light source direction will receive initial photon densities that are proportional to these dot products. These directional photon densities on boundary nodes are fixed for the duration of the execution. Any flow (movement of photon density) into a boundary node is ignored, as is any flow out of a boundary node that goes off lattice.

In Table 25.3 we compare timings for solutions of our LB lighting model as applied to the 256 × 128 ² grid used in the cloud lighting example of Section 25.3.2 . Because each line includes a 1-second CPU overhead for loading, the available speedup (without resorting to SSE instructions or multithreading) is from 1169 s to 5 s, or 234x.

It is interesting to note that by resorting to SSE instructions and multithreading on the i7 X980, we can achieve an execution time that is better than that of the naive kernel running on the GTX 480.

Results scale linearly with available resources. It should be expected that doubling the longest edge dimension would increase execution time by a factor of four. There are twice as many nodes, but achieving steady-state requires twice as many iterations. In Table 25.4 we show execution times for a cloud model of size 128 ³ . Results are as expected. Of the 2 seconds required for the final kernel on the 128 ³ problem, approximately 0.7 seconds may be attributed to CPU loading, and thus the expected factor of ×4 holds for all entries.

Although the computational structure of our method is similar to that which would be used in a parallel implementation of the discrete ordinates method, it is important to remember that our simulation-like structure is actually a numerical solution of an approximating diffusion equation. Thus, like Stam's approach [27] , its value is probably restricted to highly scattering geometry. Nevertheless, on the other side of this same coin, one should not expect any ray effects, as seen in the discrete ordinates derivatives.

We believe that our LB lighting model is effective in quickly lighting scenes with highly scattering geometry, such as clouds or forests. It is best used to capture diffuse transmission, interobject scattering, and ambient occlusion, all of which are important to photo-realism.

There are limitations. Because the technique models photon transport as a diffusion process, it is inappropriate for most direct illumination effects. Thus, it must be augmented with other techniques to capture such effects. Another limitation is the memory requirement. Because the grid state is maintained as floats:

a grid of size 256 ³ would require 2.5 GB, and larger grids would exceed available GPU memory. To light a scene with more than a single cloud or a single tree and yet capture interobject, indirect illumination requires a grid hierarchy, such as the one suggested in [28] .

More effective use of grids of limited size is under investigation. The impressive real-time performance achieved by Kaplanyan and Dachsbacher [17] can be attributed to their use of nested grids of varying resolution positioned in camera space. Their grid hierarchy is more sophisticated than our own [28] and could offer significant performance benefits. Another approach is the use of dynamic grids. In [5] we proposed a spring-loaded vertex model for 2-D radiosity computations. The grids were represented as point masses interconnected by zero-rest-length springs. Spring forces were dynamically determined by the current best lighting solution until equilibrium, with an attendant deformed grid, was achieved. This approach allowed high-quality lighting solutions with relative small grid sizes. Application of this approach to 3-D lighting appears most promising.

The purpose of this section is to show that, as the lattice spacing, λ , and the time step, τ , both approach 0, the limiting behavior of the fundamental update in Eq. 25.2 is the diffusion Eq. 25.3 . A sketch of the derivation originally appeared in [11] . The present treatment includes significantly more detail. As noted earlier, the principal value of this derivation is as a prototype for related derivations.

We begin by expanding the left side of Eq. 25.2 in a Taylor series with respect to the differential operator which handles three spatial dimensions and one temporal. This gives us

For the diffusion behavior we seek, it will be important for the time step to approach 0 faster than the lattice spacing. Specifically, we write that is, t ₀ is a term that approaches 0 faster than ϵ ² , and It follows from the chain rule for differentiation that and As is standard practice in Lattice Boltzmann modeling, we also assume that we can write as a small perturbation on this same scale about some local equilibrium, f ⁽⁰⁾ , i.e., where the local equilibrium carries the total density, i.e., . Equation 25.12 is the Chapman-Enskog expansion from statistical mechanics [4] , wherein it is assumed that any flow that is near equilibrium can be expressed as a perturbation in the so-called Knudsen number, ϵ , which represents the mean free path (expected distance between successive density collisions) in lattice spacing units.

Equation 25.11 now becomes:

Equating coefficients of ϵ ⁰ in (25.13) , we obtain: i.e., f ⁽⁰⁾ is indeed a local equilibrium. In general, a local equilibrium need not be unique, and the choice can affect the speed of convergence [18] . Nevertheless, in this case it turns out that Ω has a one-dimensional null space. We observe that (where entries 1–6 are 1/12) satisfies , all m , and so we must have where the scaling coefficient, K , is determined by the requirement that . Thus, we have:

Similarly, equating coefficients of ϵ ¹ in (25.13 ), we obtain: that is, after substituting Eq. 25.15 , We would like to solve Eq. 25.17 for f ⁽¹⁾ , but we cannot simply invert Ω, since it is singular. Nevertheless, we can observe that any vector comprising lattice direction components, as well as any of is an eigenvector of Ω with eigenvalue − σ _t . Thus, if we write and substitute into (25.17 ), we can determine that K = − λ /((1 + σ _a ) σ _t ) and so

Finally, we need to equate ϵ ² terms in Eq. 25.13 , but here it will suffice to sum over all directions. We obtain: Substituting (25.15) and (25.18) into Eq. 25.19 and observing that we obtain which, if we multiply through by ϵ ² , yields the standard diffusion equation, with diffusion coefficient The critical step is clearly a choice of Ω that both represents plausible collision events and has readily determined eigenvectors that can be used to solve for the first few components in the Chapmann-Enskog expansion.

This work was supported in part by the National Science Foundation under Award 0722313 and by an equipment donation from NVIDIA Corporation.