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:
Specialize and optimize the ray-triangle intersection test to run as fast
Add data structures that speed the intersection query when there are many
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
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.
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.
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:
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.
The scene name
The timings reported by the time utility.
The memory use reported by the top utility.
The time required to generate any precomputed data structures.
The name of the image file you saved for this scene.
Copyright © 1998 Marc Levoy
Updated by Frank Crow 27-Apr-1999