Distribution Ray Tracing

Introduction

Traditional ray tracing uses exact calculations to define a ray tree (consists of the eye ray and all generated child reflection and refraction rays). A pixel's color is approximated through the use of a single eye ray. In reality, a pixel's color should represent the integration of color across the space it represents. The integral can be more accurately approximated by sampling with more rays. This concept was introducted in Cook's paper, "Distributed Ray Tracing," in Computer Graphics in 1984. [Presently it is referred to as distribution ray tracing due to the confusion the term distributed can produce]. Distribution ray tracing distributes the direction of rays according to the function they sample; it can also be considered supersampling. This concept allows for the generation of fuzzy effects, such as motion blur, translucency, soft shadows and depth of field.

Implementation changes

Supersampling - Multiple rays are sent out per pixel. Each pixel is supersampled with n X n rays created by jittering rays that are uniformly distributed on a grid. Supersampling antialiases the image.
Distribution of reflected rays - Random rays are generated by jittering the true reflection ray. The rays are all weighted equally. [Note: originally a poisson disk distribution was implemented, however I had significant difficult and abandoned it in exchange for something that worked. I still included info on how to generate a Poisson disk distribution for future changes in the appendix.]
Extended Light Sources - Light sources are modeled as a sphere. Random points on the surface of the sphere are generated using polar and azimuth angles. These points are used as additional light rays (all generated light rays for a single luminary are averaged with equal weight).

                    <start mental note>
                    Be careful in the placement of parentheses in the following expression:
                        (float)rand()/RAND_MAX
                    A simple error like this can take days to track down, especially if you assume your
                    "theory" is wrong as opposed to the implementation!!!
                    </end mental note>

Triangles as a primitive
Texture mapping on triangles - It took me two days to figure out that ALL that was wrong with my texture mapping code was probably a big-endian/little-endian error. If you notice, the image used is an image that I generated myself. When I tried moving back and forth between unix and the pc, the images were readable, but incorrect. I tried ftp and just copying through windows afs client, but neither worked. I can only generate ppm's on unix (xv) or through my raytracer which leaves my options limited.

Sample Images

In general, sample images are created with 9 rays per pixel supersampling, with 20 rays being used for reflection and area lights. The distribution of reflection rays may be too "spread out;" if you look closely at this image, the ball's reflection on the plane has some of the color of the texture mapped triangle. I wish I could have made better sample images to show off - the texture file problem of ppm's on unix vs. pc is a current problem for that!

Another lil' one with reflective spheres... (and a lot fewer rays - notice how much that affects the soft shadows and reflections. This one used 10 rays versus 20 for the one above)

Appendix A: Generating a Poisson disk distribution

Problem: Given true reflection (or transmission) ray, generate additional rays in the hemisphere that satisfy the Poisson disk property (no two samples are closer together than some distance rp).
Solution:
(Note: rp should be selected on the number of samples desired)
The first thing to note is that there are many ways to do this. The simplest algorithm is to just randomly generate candidates and throw them out if they do not satisfy the two requirements (being in the same hemisphere as the true ray and satisfying the poisson disk property). This algorithm is only feasible if a small number of samples are desired.

A fancier and less computationally expensive idea is to precompute a small pattern and save it in a table. Then the pattern can be replicated across the needed domain by reflection and rotation. Note that this means the edges of the generated pattern must be treated carefully to insure the property is not violated when the pattern is tiled. This method requires a precomputation step as well as additional storage requirements. It also provides access to a large number of samples.

Given that I will generally need a small number of samples, a method described in Andrew Glassner's Principles of Digital Image Synthesis is usually sufficient. The method is dynamic, in that it does not store a table, and is based on the idea of jittering. A random point is selected by first randomly choosing an angle in the range [pi/3, pi/2] and then a distance d. The distance must be less than (1-2p)/2 cos theta to insure the poisson disk property (see note). The point is then rotated into one of the six regions (accomplished by first putting it into one of three positive regions and then randomly flipping to put some into the opposite regions).

Trigonometry determines the (1-2p)/2 cos theta max distance value. Deriving that on paper took some serious effort - I'll throw in a diagram when I have the time.