Princeton University Computer Science Department

Computer Science 526  Advanced Computer Graphics Fall 2002 Thomas Funkhouser

Assignment 1: Monte Carlo Path Tracing

Due: Monday, October 14 at 12:01AM

Overview

In this assignment you will implement a Monte Carlo path tracer for realistic image synthesis. 

What You Have to Do

The assignment is worth 10 points. The following is a list of features that you may implement. The number in parentheses corresponds to how many points it is worth.  Options in bold are mandatory.

• (1) Generate, evaluate, and average over multiple primary rays per pixel.
• (1) For each ray intersection, estimate direct illumination by tracing random ray(s) towards each light source
• (1) For each ray intersection, generate secondary rays sampling higher order reflections
• (1) Add stratified sampling of pixels
• (1) Add a Russian roulette scheme for terminating traced rays (see Arvo90)
• (1) Add importance sampling of reflection directions according to the BRDF (see Lafortune94).
• (1) Combine stratified and importance sampling of reflection directions (see Veach95).
• (1) Add refractions due to transparent surfaces according to Snell's Law.
• (1) Accelerate ray intersection tests with hierarchical bounding volumes.
• (1) Accelerate ray intersections with a grid (see pseudocode in chapter 10 of "Realistic Ray Tracing" by Shirley)
• (1) Accelerate ray intersections with an octree
• (1) Accelerate ray intersections with a BSP (see pseudocode in CS426 lecture 5)
• (1) Open a window that displays a progressive view of the path tracing result in realtime.
• (1) Add depth of field camera effects (see Cook84)
• (2) Simulate real camera lens behavior (see Kolb95)
• (2) Implement "backwards path tracing" -- tracing rays from lights rather than the camera
• (3) Implement bidirectional path tracing -- tracing rays from both lights and cameras
• (3) Implement Metropolis Light Transport with at least one mutation scheme (see Veach97)
• (5) Implement "photon mapping" -- caching and resampling irradiance values stored in a KD-tree (see Jensen96)
• (?) Impress us with something we hadn't considered...

By implementing all the required features (in bold), you get 7 points. There are many ways to get more points:

• implementing optional features (as listed above),
• submitting images for the art contest (1), and
• winning the art contest (3).

It is possible to get more than 10 points. However, after 10 points, each point is divided by 2, and after 12 points, each point is divided by 4.

Getting Started

You can use the code available from the instructor as a starting point for your assignment. To allow you to focus on the nuts and bolts of the actual Monte Carlo path tracing, you are provided with a libaries (in the "pkgs" subdirectory) that provide a host of data structures for basic math and data manipulation operations (pkgs/RNBasics), 2D geometry (pkgs/R2Shapes), 3D geometry (pkgs/R3Shapes), and computer graphics rendering (pkgs/R3Graphics).   "Documentation" for each C++ class is provided in the "docs" subdirectory, and example programs appear in the "apps" subdirectory.  In particular, you should start by editing the code in apps/rdraw.C and/or apps/monte/rmonte.C, which implements simple ray casters and provide a good initial structure for your program.

After you copy the provided files to your directory (e.g., /u/sue/assn1), the first thing to do is compile all the existing code. If you are developing on a Windows NT machine, running Microsoft Visual C++, from the MS-DOS prompt, type:

% cd /u/sue/assn1
% "c:\Program Files\Microsoft Visual Studio\VC98\Bin\vcvars32"
% nmake

Then, you can begin editing the code in /u/sue/assn1/apps/monte/monte.C.  I recommend that you develop incrementally (implement in small steps, and test each step separately) and that you do most of your testing on simple, well-designed examples (simple scenes, small images, few paths per pixel, stresses feature of interest, etc.) because execution/debugging times will be quite long otherwise.

The code provides a function (R3ReadRayFile in R3Graphics/R3Io.C) to read simple scene files.  The syntax of the .ray file format is described here.  Those of you who took CS426 will recognize it as a subset of the .ray file format used for the ray tracing assignment (with a few minor changes).  Most significantly, groups with arbitrary transformations are not included, which makes intersection and sampling of rays much simpler. A repository of sample .ray files will be provided here.  Please email me useful/interesting .ray files that you create so that I can include them in the repository and other students can test their programs on them.

What to Submit

You should email to me the location of an archive (.tar or .zip file) containing:

• the complete source code with a Makefile,
• any *.ray files you created
• the images for the art contest, and
• a writeup.

The writeup should be a HTML document called index.html. It should describe in detail what you have completed and include images demonstrating the features you have implemented (at least for the test scenes in models/box).  For instance, you could provide side-by-side comparison of images and execution times achieved by your program both with and without a particular feature.  Or, you could provide a sequence of images with different numbers of paths per pixels to evaluate how quickly your program converges.  Finally, your writeup should conclude with a discussion of what you have learned -- e.g., which features are most significant, under what circumstances does your Monte Carlo path tracer work well/poorly, what improvements would you suggest, etc.