Programming assignment #2 - Accelerated ray tracer

CS 348B - Computer Graphics: Image Synthesis Techniques
Spring Quarter, 1999

Due Wednesday, May 12, 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.

  3. 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 or any others you can find in the literature. 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. A handout will describe how to compute barycentric coordinates needed 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.

    Grading criteria

    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.

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

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

    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.

    Submission

    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.


    levoy@cs.stanford.edu

    Copyright © 1998 Marc Levoy
    Updated by Frank Crow 27-Apr-1999