CSE 557 Computer Graphics Grail

Winter Quarter 2000

Project Handouts

[A

Project 2: Ray Tracing

Assigned: Tuesday, 25 January, 2000
Due: Thursday, 10 February, 2000 (code frozen by midnight)
Artifacts Due: Monday, 14 February, 2000 (by 5:00PM)

Project Description

You will build a program called Ray that will generate ray-traced images of complex scenes. The ray tracer should trace rays recursively using the Whitted's illumination model.

Getting Started

To install the starting point source code, unzip the file, here. The skeleton code can load scenes and save images. It generates extremely simple "ray-traced" images. The pixels are shaded only by the diffuse terms of the material at the ray intersections.

The skeleton code can run in both text mode and graphics mode. (the text mode NT version only displays windows for timing information and error messages.) Text mode is considerably faster. Running without no arguments will execute the program in the graphics mode. For usage see 'ray --help'.

Required Functionality

We'll describe these requirements in more detail afterwards:
  1. The skeleton code has no box-ray intersection implementation. Fill in the box-intersection code so that your ray tracer can handle boxes. (This routine should also be very useful for your acceleration algorithm.)
  2. Implement Whitted's illumination model (FvDFH, eq. 16.55), which includes ambient, diffuse, and specular terms for each light source as well as reflection and refraction terms. You only need to handle directional and point light sources, i.e. no area lights, but you should be able to handle multiple lights.
  3. Implement Phong interpolation of normals.
  4. Implement anti-aliasing. Regular super-sampling is acceptable, more advanced anti-aliasing will be considered as an extension.
  5. Implement data structures that speed up the intersection computations in large scenes.

Notes on Whitted's illumination model

The first three terms in Whitted's model will require you to trace rays towards each light, and the last two will require you to recursively trace reflected and refracted rays. When tracing rays toward lights, you should look for intersections with objects, thereby rendering shadows. If you intersect a semi-transparent object, you should attenuate the light, thereby rendering partial shadows, but you may ignore refraction of the light source.

The skeleton code doesn't implement Phong interpolation of normals. You need add code for this (only for meshes with per-vertex normals.)

Anti-aliasing

Once you've implemented the shading model and can generate images, you will notice that the images you generated are filled with "jaggies". You should implement an anti-aliasing technique to smooth these rough edges. In particular, you are required to perform super-sampling and averaging down. You should provide a slider and an option to control the number of samples per pixel (1, 4, 9 or 16 samples). You need only implement a box filter for the averaging down step. More sophisticated anti-aliasing methods are left as bells and whistles below.

Acclerated ray-surface intersection

The goal of this portion of the assignment is to speed up the ray-surface intersection module in your ray tracer. In particular, we want you to improve the running time of the program when ray tracing complex scenes containing large numbers of objects (they are usually triangles). There are two basic approaches to do this:
  1. Specialize and optimize the ray-object intersection test to run as fast as possible.
  2. Add data structures that speed the intersection query when there are many objects.

Most of your effort should be spent on approach 2, i.e. reducing the number of ray-object intersection tests. You are free to experiment with any of the acceleration schemes described in Chapter 6, ''A Survey of Ray Tracing Acceleration Techniques,'' of Glassner's book. Of course, you are also free to invent new acceleration methods.

Make sure that you design your acceleration module so that it is able to handle the current set of geometric primitives - that is, triangles spheres, squares, boxes, and cones.

The sample scenes include several simple scenes and three complex test scenes: test1, test2, and test3 (also include some sample ray-traced images). You will notice that, among them, test1 has per-vertex normals and materials, and test2 has per-vertex materials but not normals. Per-vertex normals and materials imply interpolation of these quantities at the current ray-triangle intersection point (using barycentric coordinates).

Acceleration grading criteria

The test scenes each contain up to thousands of triangles. A portion of your grade for this assignment will be based on the speed of your ray tracer running on these scenes. The faster you can render a picture, the higher your grade.

For grading on the rendering speed, the scenes will be traced at the specific size with one ray traced per pixel, and the rays should be traced with 5 levels of recursion, i.e. each ray should bounce 5 times. If during these bounces you strike surfaces with a zero specular reflectance and zero refraction, stop there. At each bounce, rays should be traced to all light sources, including shadow testing. The command for testing rendering speed looks like: 

ray -t -w 400 -d 5 in.ray out.bmp
[For fairness, don't include other stop criteria (except for the one mentioned above) for -t option.]

You are welcome to precompute scene-specific (but not viewpoint-specific) acceleration data structures and make other time-memory tradeoffs, but your precomputation time and memory use should be reasonable. Don't try to customize your ray tracer for the test scenes; we will also use other scenes during grading. If you have any questions about what constitutes a fair acceleration technique, ask us. Coding your inner loops in machine language is unfair. Using multiple processors is unfair. Compiling with optimization enabled is fair. In general, don't go overboard tuning aspects of your system that aren't related to tracing rays.

Bells and Whistles

This assignment is large, and, furthermore, the optimization element is completely open-ended, so you can profitably work on that until the project is due. Therefore we don't neccessarily expect a bunch of bells and whistles. We can't stop you, though. Here are some interesting extensions to this project.

Approved Bells and Whistles

[Whistle]
Specify a background image to replace the environment's ambient color during the rendering.

[Bell]
Implement adaptive supersampling as described in Glassner, Chapter 1, Section 4.5 and Figure 19.

[Bell] [Bell]
Implement stochastic (jittered) supersampling. See Glassner, Chapter 5, Section 4.1 - 4.2 and the first 4 pages of Section 7.

[Bell][Bell] for the first,[Bell] for each additional
Implement stochastic or distributed ray tracing to produce one or more or the following effects: depth of field, soft shadows, motion blur, glossy reflection (See Glassner, chapter 5, or Foley, et al., 16.12.4).

[Bell] [Bell]
Implement texture mapping.

[Bell] [Bell]
Implement bump mapping.

[Bell] [Bell] [Bell]
Implement "Adaptive Uniform Grid" for accleration. Fujimoto's uniform grid is a popular acceleration algorithm for ray tracing. However, the algorithm suffers from the "teapot in a stadium" problem. Adaptive grid algorithm addresses the problem and becomes one of the fastest algorithms up to date. See Faster Ray Tracing Using Adaptive Grids, K. Klimaszewski & T. Sederberg. CG&A Jan. 1997, pp 42-51. Also see the discussions in Ray Tracing News, Vol. 10, No. 3.

References