CS 348B - Computer Graphics: Image Synthesis Techniques
Spring Quarter, 1998
Marc Levoy
Handout #19
Due Monday, May 11, 11:59pm
The goal of this 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 triangles. There are two basic approaches to doing this:
Most of your effort should be spent on approach 2, i.e. reducing the number of ray-triangle intersections. You are free to experiment with any of the acceleration schemes described in Chapter 6, ``A Survey of Ray Tracing Acceleration Techniques,'' of Glassner. 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 and spheres. The resulting program should still be able to handle all the test scenes from programming assignment #1.
In addition, the directory /usr/class/cs348b/proj2/tests contains
several new test scenes. You will notice that among these test1 has per-vertex
normals and materials, and test2 has per-vertex materials but not normals. To
make grading fair, you should implement per-vertex normals and materials where
indicated by the test scene. Per-vertex normals and materials imply
interpolation of these quantities at the current ray-polygon intersection
point. The method I described in class for intersecting rays with triangles
gives you the barycentric coordinates you need for performing this
interpolation. Implementing all this is a bit more work, but you'll be glad in
project #3 that you did it, because it will give you the ability to display
triangle meshes as smooth objects.
The new test scenes each contain up to thousands of triangles. 50% 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. The other 50% will be based on the cleverness of your acceleration scheme and on how cleanly you implemented it.
All images should be 400 x 400 pixels, with one ray traced per pixel, and rays should be traced with 5 levels of intersections, i.e. each ray should bounce 5 times. If during these bounces you strike surfaces with a zero specular reflectance Ks, stop there. At each bounce, rays should be traced to all light sources, including shadow testing, as in programming assignment #1. None of the test scenes will include transparent surfaces, so refraction can be ignored.
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 may 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. Reading binary instead of ascii files is also fair, but not likely to yield much savings on these scenes relative to the time required to render them. In general, don't go overboard tuning aspects of your system that aren't related to tracing rays.
You should add to (or modify) the command line interface of your ray tracer so
that instead of running interactively it will read in a specified scene (and
any acceleration data structures you have computed), ray trace it once, save
the resulting image, and exit. During these timing runs, do not update the
on-screen canvas; it will slow down your ray tracer. To time your code, type
"time myraytracer arguments...". This utility will report the
user, system, and elapsed time on a single text line. We are particularly
interested in elapsed time. Time your performance on each test scene, and
paste the reported timings into your README file. All timings should be made
on the Sweet Hall firebirds (250 MHz R4400).
We would also like you to record the approximate amount of memory you use
rendering each scene. To record memory use, type "top" during a
run (not one of your timing runs). This program gives the size in Kbytes of
the busiest programs in the system. Your ray tracer should be among them, and
its memory use will probably be fairly constant during a run. Look for the
rough maximum, exit the program (by typing ^C), and paste the line describing
your ray tracer into the README file.
If you are precomputing data structures to accelerate your ray tracer, your timing runs do not need to include the time required to generate these data structures. You may precompute them for each test scene and store them in files. However, we do want you to time these precomputations and include the timings as a separate line in your README file.
When you have completed your assignment, make a copy of your code and the images you have generated in a directory called project2 in your home directory. Write a README file containing a brief description of the acceleration techniques you employed. If you made any special assumptions, state them. Also indicate where you got your ideas. Include a list of references. But keep it short -- one page is plenty. Then, include the following information for each test scene:
time utility.
top utility.