next up previous
Next: Monte Carlo Integration Up: A Review of Monte Previous: Derivation of the Rendering

Quasi-Random Walk Methods

In equation 15 the unknown function I appears on both sides. Substituting the right side's I by tex2html_wrap_inline791 , which is obviously I according to the equation, we get:


Repeating this step n times, the original equation can be expanded into a Neumann series:


If integral operator tex2html_wrap_inline784 is contractive, that is if


then tex2html_wrap_inline799 , thus


The contractive property of tex2html_wrap_inline784 comes from the fact that a reflection or refraction always decreases the energy.

The terms of this infinite Neumann series have intuitive meaning as well: tex2html_wrap_inline803 comes from the emission, tex2html_wrap_inline805 comes from a single reflection, tex2html_wrap_inline807 from two reflections, etc.

In order to study the structure of tex2html_wrap_inline809 , let us consider the case of i=2:



To evaluate the integrand at point tex2html_wrap_inline815 , the following algorithm must be executed:

  1. Surface point tex2html_wrap_inline817 -- that is the point which is visible from tex2html_wrap_inline732 at direction tex2html_wrap_inline821 -- must be determined. This can be done by sending a ray from tex2html_wrap_inline732 into direction tex2html_wrap_inline821 and indentifying the surface that is first intersected.
  2. Surface point tex2html_wrap_inline827 -- that is the point visible from tex2html_wrap_inline829 at direction tex2html_wrap_inline831 is identified. This means the continuation of the ray tracing at direction tex2html_wrap_inline831 .
  3. The emission intensity of the surface at tex2html_wrap_inline835 in the direction of tex2html_wrap_inline837 is acquired and is multiplied with the cosine terms and the BRDFs of the two reflections.

Figure: The integrand of the second bound is a two-step walk

This algorithm can easily be generalised for arbitrary number of reflections. In order to compute the contribution of the nth reflection of the light to tex2html_wrap_inline776 , the following function should be integrated: A ray is emanated recursively from tex2html_wrap_inline732 at direction tex2html_wrap_inline821 then from the found surface at tex2html_wrap_inline831 , etc. until tex2html_wrap_inline849 . The emission intensity at the end of the walk is read and multiplied by the BRDFs and the cosine terms of the stages of the walk.

These walks provide the value of the integrand at ``point'' tex2html_wrap_inline851 . The integral is estimated as the average of these values. Directions tex2html_wrap_inline851 should be selected to minimise the error of the approximation.

Thus we can conclude that the solution of the rendering equation requires the evaluation of high-dimensional ingegrals.

next up previous
Next: Monte Carlo Integration Up: A Review of Monte Previous: Derivation of the Rendering

Csébfalvi Balázs
Tue Apr 15 18:39:13 METDST 1997