Programming Assignment A3:
Ray Tracing

For this assignment, extend the ray caster you wrote in 15-462 to simulate specular reflection and transmission with refraction, do antialiasing, and use BSP trees to accelerate ray-surface intersection testing. Use this program to make some attractive animation that shows off these features (details below). You are to work individually on this assignment.

Those of you who took 15-462 from Heckbert, Welling, or Seitz probably implemented a ray caster using the starter code in the following subdirectories of /afs/cs/academic/class/15462/src/ : libdl, raytrace, raymain following this assignment handout or something close to it.

Those of you who took 462 from Davis probably worked from the directory new_ray following this assignment handout.

If you didn't didn't get most of the bugs out of that code, or you'd prefer to start with a clean slate on this assignment, then send email to us ( amperez@andrew ) or talk to us after lecture and we can help you out. Don't wait until the last day to do this!

What you animate could be subdivision surfaces from A2, or almost anything else, as long as it meets the requirements below.

• Simulate specular reflection and specular transmission with refraction by tracing additional rays. Unless their coefficients are zero, compute the directions of these rays, trace them recursively, and add in their appropriately weighted radiances into the radiance (color) that will be returned for the current ray. A few of you implemented this in 15-462. If so, you've got a head start. There should be a maximum ray depth controllable on the command line or in some convenient way to prevent infinite recursion. Trace to a depth of at least 3 (meaning that photons bouncing three times or fewer should be accounted for).
• adaptive antialiasing. Do antialiasing by tracing up to n rays per pixel. To make this efficient, shoot just one ray per pixel initially and then, where the returned radiances of neighboring pixels differ above some threshold, trace n rays per pixel and average those. n=16 is recommended (see Tips below).
• BSP trees. Implement Binary Space Partitioning trees (if you haven't already) to accelerate ray-surface intersection testing. Put your triangles and spheres (if any) in the BSP tree. It should work reasonably efficiently on scenes of thousands of objects (triangles, spheres, or other primitives), so that you can create animation on scenes of high complexity in reasonable time. Rip any spatial data structure code (e.g. the provided octree or k-d tree code) out of your 462 code when you start this assignment.

  If you happened to implement BSP trees for 462, then implement a different spatial data structure (e.g. hierarchical bounding volumes) this time. Talk to us if you have questions about this.

• Source code. Leave your code in subdirectories of classdir/students/yourid/a3. We will look at your source during the demo.
• Demo on 3 Apr.: Demo your program during the class time on Tuesday, 3 Apr. Show us pictures that demonstrate specular reflection, refraction, antialiasing, and a scene of 10,000 or more primitives. Testing refraction is a bit tricky. If your code is libdl-based, compile raymain/glass.cc and link into your ray tracer code, generate a picture like pub/pix/a3/glass.tif, and show us this during your demo. If your code is new_ray-based, or uses some other approach, try to emulate this scene, and generate a similar picture that tests reflection and refraction rigorously.
• Generate animation by 11:59 pm Sun 8 Apr that demonstrates the following effects: specular reflection or transmission, antialiasing, and an object with 10,000 or more primitives.

  Frame files should be 640x480 pixel 24 bit TIFFs or JPEGs, with filenames of the form ###.tif or ###.jpg e.g. 000.tif, 001.tif, 002.tif, ... Short animations will be recorded at 15 frames per second, while long ones will be recorded at 30 frames per second. Tell us if you have a preference (we can accomodate 30/k fps for any integer k). Please use a 4/3 aspect ratio (width/height in pixels).

• Make sure your code for ray-sphere intersection testing is returning the right root in all cases. Return the smallest root with t>epsilon, where epsilon=1e-6 or so. For transparent spheres, if the ray is originating on or inside the surface of the sphere, you want to return the second root. This detail of your code was probably not exercised in 462's assignment.
• To help debug refraction, antialiasing, and other features, see the pictures in pub/pix/a3.
• If your ray tracer used libdl: DL has extra (not in OpenGL) mechanisms for setting the RGB coefficients of specular transmission, the index of refraction, and the fog color, if any. See the code (libdl/dlState.cc).
• To determine the relative index of refraction as you enter a material, you'll need to keep some concept of the current material. The easiest way to do this is set an "enter" flag in the Isect (raytrace) or Intersect (new_ray) data structure carefully in your Tri::intersect and Sphere::intersect routines, and then consult this bit to determine if you're entering the solid or exiting the solid. You can assume that transparent solids never intersect. If enter=1 then you're entering the solid (e.g. air into glass) and if enter=0 then you're exiting (e.g. glass into air), and you can set the ratio of indices of refraction accordingly.
• For antialiasing, we recommend two pass rendering. On the first pass, trace one ray per pixel and save the returned radiances in a 2-D array of RGB colors. On the second pass, revisit each pixel, and if it differs from its four neighbors by more than a threshold, supersample the pixel n times. A reasonable value for n is 16 (e.g. jittered in a 4x4 grid within the square pixel area). The threshold should be settable at runtime. This will allow you to turn the feature off for debugging, by setting the threshold very high. For pixels that are supersampled, average the returned radiances to compute the pixel's color to be written to the picture file.
• In real life, lights attenuate as 1/r^2 with distance, but we don't require you to implement this.
• A simple idea for an animation that would probably be technically and visually interesting is to take your subdivision surface creation, fairly finely subdivided, set the materials so that it will look glass-like, and photograph it from a slowly moving viewpoint, perhaps surrounded by a texture-mapped box (so that the background will have some texture that is refracted by the glass).
• Since the focus of this assignment is shading, not modeling, you can use 3D models from the web.
• Your BSP trees will need to be fairly balanced, or they will get quite inefficient. As with quicksort, you can usually do fairly well by testing a small number of randomly-chosen pivots (split planes), and choosing the one that balances best. BSP tree construction will be discussed in class.
• To see if your BSP trees are fairly balanced, compute their depth. If your trees are O(log n) depth, they're well balanced (good); if they're O(n) depth, they're extremely imbalanced (bad!). To determine the approximate asymptotic behavior of your algorithm, you'll need to test several values of n, i.e. at least two and preferably three or more. One good way to do this is to use the Sierpinski tetrahedral gasket object that Adrian described in the news group (subject: Something that might help).
• If you encounter numerical problems with your BSP trees (symptoms can include tumor-like growths protruding from a surface), make sure you're using doubles, not floats, for your geometric calculations (plane coefficients, ray parameters, etc).

Grading Criteria

• 8 points: functioning program during demo
• 4 points: nice animation (we expect more than glass balls and spinning planets!)

15-463, Computer Graphics 2
Paul Heckbert