Dutre proposed an algorithm that does not require mesh generation and can handle all types of light-surface interactions [DLW93]. This algorithm is based on particle model and direct computation of pixel intensities. Particles perform random walk through the scene and whenever a surface is hit, a ray is traced from the intersection point to the eye and direct light source contribution is added to the relevant pixel.

The random walks are denoted by a sequence of pairs
,
where and
is the last point generated. For the *i*th particle
the pair is the pair
representing the starting point and starting direction
of the *i*th particle.

for each particle ( ): determine the starting position trace a ray towards the eye and add the direct light source contribution to the relevant pixel determine the new direction absorbed = False; repeat until absorbed: compute trace a ray from to the eye and add the reflection contribution to the relevant pixel use the subcritical PDF to generate or to absorb the particlej=j+1 determine for each pixel display image

The new direction is chosen according to the subcritical pdf (spdf) on the basis of importance sampling:

where is the bi-directional reflection distribution function (BRDF). The pdf is subcritical because it does not integrate to 1 over all possible angles, at least for physically valid BRDFs. The actual value of the integration gives the chance that random walk is continued, which ensures that the random walk terminates. This technique is commonly called Russian roulette.

Tue Apr 15 18:39:13 METDST 1997