Programming assignment #2 - Accelerated ray tracer

CS 348B - Computer Graphics: Image Synthesis Techniques
Spring Quarter, 1996
Marc Levoy
Handout #19

Due Monday, May 13, 11:59pm

Speeding up your ray tracer

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:

  1. Specialize and optimize the ray-triangle intersection test to run as fast as possible.
  2. Add data structures that speed the intersection query when there are many triangles.

    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.

    Grading criteria

    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.

    Measuring elapsed time

    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).

    Measuring memory use

    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.

    Measuring precomputation time

    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:

    1. The scene name
    2. The timings reported by the time utility.
    3. The memory use reported by the top utility.
    4. The time required to generate any precomputed data structures.
    5. The name of the image file you saved for this scene.
    Finally, include detailed instructions for running your program, including precomputing acceleration data structures. We may wish to verify your results or test your program on other scenes. Then submit your assignment as before.
    Copyright © 1996 Marc Levoy
    Last update: Friday, 20-Feb-1998 15:57:04 CST