CS 348B - Computer Graphics: Image Synthesis Techniques
Spring Quarter, 1996
Marc Levoy
Handout #19
Due Monday, May 13, 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 mentioned in class or 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 the directory /usr/class/cs348b/proj2 are several test
scenes with 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.
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 (assuming it continues to strike surfaces with a non-zero specular reflectance). 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.
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. 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 4096-byte
pages 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.