This SIGGRAPH 1997 paper by Eric Veach and Leonidas J. SIGGRAPH (short for S pecial I nterest G roup on GRAPH ics and Interactive Techniques is the name of the annual conference on Computer graphics Guibas describes an application of a variant of the Monte Carlo method called the Metropolis-Hastings algorithm to the rendering equation for generating images from detailed physical descriptions of three dimensional scenes. Monte Carlo methods are a class of Computational Algorithms that rely on repeated Random sampling to compute their results In Mathematics and Physics, the Metropolis-Hastings algorithm is a method for creating a Markov chain that can be used to generate a sequence of In Computer graphics, the rendering equation is an Integral equation in which the equilibrium Radiance leaving a point is given as the sum of emitted
The procedure constructs paths from the eye to a light source using bidirectional path tracing, then constructs slight modifications to the path. Some careful statistical calculation (the Metropolis algorithm) is used to compute the appropriate distribution of brightness over the image. This procedure has the advantage, relative to bidirectional path tracing, that once a path has been found from light to eye, the algorithm can then explore nearby paths; thus difficult-to-find light paths can be explored more thoroughly with the same number of simulated photons.
In short, the algorithm generates a path and stores the paths 'nodes' in a list. It can then modify the path by adding extra nodes and creating a new light path. While creating this new path, the algorithm decides how many new 'nodes' to add and whether or not these new nodes will actually create a new path.