COS 426 - Computer Graphics

Spring 2011

Assignment 3: Ray Tracing

In this assignment you will create a simple ray tracing program. The program will read in a scene and output an image.

Getting Started

You should use the following skeleton code (cos426_assignment3.zip) as a starting point for your assignment. We provide you with several files, but you should mainly change raytrace.cpp.

• raypro.cpp: Parses the command line arguments, and calls the ray tracer function.
• rayview.cpp: Interactive program for viewing scenes
• raytrace.cpp: Implements the ray tracer -- this is the main file you should edit.
• R3Scene.cpp: code to support reading and representing scenes.
• R2: code to support operations on 2D points, vectors, lines, segments, and images
• R3: code to support operations on 3D points, vectors, lines, segments, planes, and meshes.
• jpeg: code to read/write JPEG files
• raypro.[vcproj/sln]: Project file for Visual Studio.
• rayview.[vcproj/sln]: Project file for Visual Studio.
• Makefile.[mac/cygwin/linux]: Make file for Mac OS X, cygwin, and linux.
• Makefile: Copy of make file for Mac OS X.

The first thing to do is compile the program. Two executables will be created: raypro and rayview (or raypro.exe and rayview.exe). raypro is the program that does the ray tracing (just like imgpro from assignment #1), while rayview provides a way for you to visualize and process rayes interactively. Of course, you are welcome to extend rayview.cpp any way you wish to provide new visualizations, but please keep the semantics of the existing user interface.

The skeleton code is able to read scenes in a simple scene file format, This format was created to provide the features required by this assignment -- a simple scene graph along with materials, lights, and cameras. We provide several scenes in the input subdirectory of the zip file that you can use to test your program along with an example writeup.html that shows output images for most of those scenes for comparison purposes. We also provide some sample scenes created by students in past years, which may be fun to try. However, of course, you are not limited to these files -- you are encouraged to create your own files, either by hand, or with your programs from assignment #2. Note that it is very easy to combine multiple meshes and scenes in a single scene file using the "mesh" and "include" commands in the .scn file format, and it is convenient to size and position scene elements with the transformations provided by the "begin" and "end" commands.

How the Program Works

The user interface for this assignment was kept as simple as possible, so you can concentrate on the ray tracing issues. The raypro program runs on the command line. It reads a scene from a .scn file (the first program argument) and writes an image to a new file (the second program argument). The program allows a few program arguments that control features of the raytracer. For example, ...

% raypro in.scn out.jpg -width 128 -height 128

How to view a mesh and try commands interactively

To view a scene file named input.scn interactively (e.g., to see approximately what the raytraced image should look like), type:

rayview input.scn.

What You Have to Do

The assignment is worth 20 points. The following is a list of features that you may implement (listed roughly from easiest to hardest within each group). The number in front of the feature corresponds to how many points the feature is worth. The features marked with a green asterisk are required for the first deadline (April 5th). The ones marked in bold are required for the second deadline (April 14th). The others are optional. Refer to the example writeup.html to see images of inputs and outputs for several of these filters.

• Basic Ray Generation:
  • * (1) Generate a ray for each pixel: Create a R3Ray through points on a regular grid of pixels on the view plane, as defined by the camera parameters (eye point, towards direction, up direction, xfov, and yfov) and viewport (image width and height). Images of this feature do not need to be included in the writeup.

• Ray-Primitive Intersection:
  • * (1) Intersect a ray with a sphere: Implement a function that takes in an R3Ray and an R3Sphere as arguments and returns whether or not the ray intersects the surface of the sphere, and if so what is the position, normal, and parametric value (t) on the ray at the first intersection point.
  • * (1) Intersect a ray with an axis-aligned box: Implement a function that takes in an R3Ray and an R3Box as arguments and returns whether or not the ray intersects the box, and if so what is the position, normal, and parametric value (t) on the ray at the first intersection point.
  • * (2) Intersect a ray with a triangle mesh: Implement a function that takes in an R3Ray and an R3Mesh as arguments and returns whether or not the ray intersects the mesh surface, and if so what is the position, normal, and parametric value (t) on the ray at the first intersection point.
  • (2) Intersect a ray with an axis-aligned cylinder: Implement a function that takes in an R3Ray and an R3Cylinder as arguments and returns whether or not the ray intersects the cylinder, and if so what is the position, normal, and parametric value (t) on the ray at the first intersection point.
  • (3) Intersect a ray with an axis-aligned cone: Implement a function that takes in an R3Ray and an R3Cone as arguments and returns whether or not the ray intersects the cone, and if so what is the position, normal, and parametric value (t) on the ray at the first intersection point.

• Ray-Scene Intersection:
  • * (1) Intersect a ray with a scene: Implement a function that takes in an R3Ray and an R3Scene as arguments and returns whether or not the ray intersects the scene, and if so what is the scene graph node, position, normal, and parametric value (t) on the ray at the first intersection point. This function should traverse the scene graph hierarchy recursively, intersecting the ray with all nodes, and returning the intersection with minimal parametric value (t) on the ray.
  • (1) Handle scene traversals with modeling transformations: Augment your recursive scene graph traversal to handle modeling transformations as it traverses the scene graph hierarchy. This feature requires transforming a ray by the inverse of the transformation prior to decending into a node's children and then transforming the intersection point and normal by the transformation and recomputing the parametric value t on the ray before returning them to the parent.
  • (1) Accelerate ray-scene intersection with node bounding box checks: Augment your code for ray-scene intersection to check whether a ray intersects the bounding box for each child of a scene graph node before checking for interesections recursively for that child. If the ray hits the bounding box, check the parametric value along the ray against the least parametric value seen so far for a ray-primitive intersection previously found during the same recursive traversal and avoid decending into the child if the parametric value of the ray-bbox intersection is greater. Note that the bounding box for each node is stored in the coordinate system of the parent node to facilitate these checks. To get credit for this feature, you must show timing differences for executions with and without the feature enabled.
  • (1) Accelerate ray-scene intersection by caching the last intersection: Augment your code for ray-scene intersection to: 1) remember the node in the scene graph that yielded the closest intersection last time a ray-scene intersection was performed, 2) check that node first to establish an upper bound on the parametric value (t) of the closest ray intersection (if the new ray intersects the primitives of that node again), and then avoid recursion into scene graph nodes whose ray-bbox intersections have parametric values greater than the established upper bound. To get credit for this feature, you must show timing differences for executions with and without the feature enabled.
  • (2) Accelerate ray-scene intersection by visiting children nodes in front-to-back order: Augment your code for ray-scene intersection with bounding box checks for each node to: 1) intersect the ray with the bounding boxes of all children nodes, 2) sort the intersected children nodes front-to-back with respect to the parameteric value along the ray for their ray-bbox intersections, 3) recurse into the children nodes in that sorted order, and 4) terminate the search if a ray-primitive intersection is found at a parametric value less than all remaining ray-bbox interesections. To get credit for this feature, you must show timing differences for executions with and without the feature enabled.
  • (3) Accelerate ray-mesh intersection using a grid: Augment your code for ray-mesh intersection (and/or R3Mesh.[h,cpp]) to index all faces in the mesh spatially with a grid, trace rays through grid cells in front-to-back order, and perform ray-face intersections only for faces residing in grid cells as they are traversed, keeping track of the first hit and terminating when no closer hits are possible. To get credit for this feature, you must show timing differences for executions with and without the feature enabled.
  • (4) Accelerate ray-mesh intersection using an octree: Augment your code for ray-mesh intersection (and/or R3Mesh.[h,cpp]) to index all faces in the mesh spatially with an octree, trace rays through cells in front-to-back order, and perform ray-face intersections only for faces residing in cells as they are traversed, keeping track of the first hit and terminating when no closer hits are possible. To get credit for this feature, you must show timing differences for executions with and without the feature enabled.
  • (4) Accelerate ray-mesh intersection using a BSP tree: Augment your code for ray-mesh intersection to (and/or R3Mesh.[h,cpp]) index all faces in the mesh spatially with a BSP tree, trace rays through BSP cells in front-to-back order, and perform ray-face intersections only for faces residing in BSP nodes as they are traversed, keeping track of the first hit and terminating when no closer hits are possible. To get credit for this feature, you must show timing differences for executions with and without the feature enabled.

• Illumination:
  • * (2) Phong Illumination: Compute the reflected radiance at every ray-primitive intersection by evaluating the Phong reflectance model for every directional, point, and spot light in the scene. The ambient term (k_a) should be added only once (not per light), while the diffuse and specular terms should be added for every light with ( k_d * (N dot L) + k_s * (V dot R)ⁿ) ) * I_L, where I_L is the irradiance due to a directional, point, or spot light source according to the equations provided in the .scn file format description. Note that point and spot light sources should include attenuation of the light power with distance, and spot light sources should include divergence from the central angle.
  • (2) Texture mapping: Implement texture mapping for the sphere geometry primitive. The texture is to modulate the diffuse reflectance component across a surface, i.e. for every ray intersection at a surface point with texture coordintes (u,v), you will use Texture(u,v) * k_d, rather than k_d in the diffuse reflection calculations.

• Shadows:
  • (1) Shadow rays: For every direct illumination calculation, cast a "shadow ray" from the reflection point to the light source position and include the contribution of that light source only if the shadow ray is not blocked by another surface in the scene.
  • (2) Area lights and soft shadows: Define lights with circular area (area_light) and cast a small number n (say n = 16) of rays towards random points on the circle, and compute the illumination from the light based on the proportion of rays which are not blocked by other surfaces in the scene. For large area lights, this should give a penumbra, or region where the light source is only partially concealed. To generate random points within a circle, one can iteratively sample on a quadrilateral, and discard points outside the circle, until the required number of samples within the circle has been found.

• Global Illumination:
  • (2) Specular reflection: Trace a secondary ray from every ray-surface intersection in the direction of perfect specular reflection, compute the irradiance I_R for that ray recursively, and include it into your illumination calculation using k_s * I_R. Rays should be traced up to the specified maximum number of ray intersections (max_depth).
  • (1) Transmission: Trace a secondary ray from every ray-surface intersection in the direction of perfect transmission (without refraction), compute the irradiance I_T for that ray recursively, and include it into your illumination calculation using k_t * I_T. Of course, this should be done for non-opaque surfaces -- i.e., ones where k_t is non-zero. Rays should be traced up to the specified maximum number of ray intersections (max_depth).
  • (2) Refraction: Trace a secondary ray from every ray-surface intersection in the direction of perfect refraction according to Snell's Law (instead of in the direction of perfect transmission), compute the irradiance I_T for that ray recursively, and include it into your illumination calculation using k_t * I_T. Of course, this should be done for non-opaque surfaces -- i.e., ones where k_t is non-zero. Rays should be traced up to the specified maximum number of ray intersections (max_depth).
  • (4) Distributed ray tracing: Trace multiple secondary rays (num_distributed_rays_per_intersection) from every ray-surface intersection by randomly sampling outgoing directions, compute the irradiance I_R,i for each of these rays recursively, perform a full Phong lighting calculation for each ray, and sum the results to produce the outgoing radiance for the intersection. Rays should be traced up to the specified maximum number of ray intersections (max_depth).

• Camera Effects:
  • (1) Camera antialiasing: Rather than tracing only one ray per pixel (which leads to aliasing), implement a random sampling of multiple rays for each pixel (num_primary_rays_per_pixel). Splat the radiance sampled on the rays to neighboring pixels using a Gaussian kernel for sigma=0.5.

• Debugging:
  • (2) Primary ray visualization: Provide code that will produce an image showing line segments indicating the paths of primary rays starting at the camera eye point and stopping at the first surface intersections. This option could be implemented by writing a .scn file with a representation for each ray (e.g., add "line" commands to the scene). Or, it could be implemented by extending rayview.cpp to show rays eminating from the camera provided in the .scn file as the scene is viewed interactively. You should restrict the number of rays displayed so that they are clearly visible. Commands for this feature do not need to be included in the runme file, but a description of your process should be included in the writeup.
  • (2) Secondary ray visualization: Provide code that will produce an image showing line segments indicating the paths of secondary rays starting at their reflection/transmission points and stopping at their next surface intersections. Commands for this feature do not need to be included in the runme file, but a description of your process should be included in the writeup.

• Input:
  • (1) Make an interesting scene: Submit the .scn file, and include a screenshot of your scene.

By implementing all the required features, you get 13 points. There are many ways to get more points:

• implementing the optional features listed above;
• (1) submitting one or more images for the art contest,
• (1) submitting a .mpeg or .avi movie showing images generated with a moving camera, a dynamic scene, and/or smoothly varying parameter settings,
• (2) winning the art contest.

It is possible to get more than 20 points. However, after 20 points, additional points will incur diminishing returns, as on past assignments.

Submitting

* This assignment has a split deadline. On the first due date (April 5th), please submit writeup1.html with the features marked with a green asterisk completed (8 points). On the second due date, please submit both an unchanged writeup1.html and new writeup2.html with 20 points completed. While only the first eight points marked with a green asterisk must be completed by the first due date, we strongly encourage you to start your implementation on more advanced features before then.

Please submit a single .zip file named [your NetID]_cos426_assignment3.zip containing:

• [your NetID]_cos426_assignment3/
  • writeup1.html (your writeup for the first eight points)
  • writeup2.html (your writeup for the remaining points)
  • Makefile or NMakefile
  • input/ (All the input data for your examples)
  • output/ (All the output images - images should be JPEG format)
  • art/ (All images submitted for the art contest (optional), and .mpeg or .avi movies submitted for the movie feature (optional).\ )
  • src/ (the complete, but cleaned modified source code)

We remind you that you are expected to use good programming style at all times, including meaningful variable names, a comment or three describing what the code is doing, etc. We will test your code by running make in your src/ subdirectory, followed by make in the main assignment directory to create the output images. Please ensure that your code builds/runs in this way.

Please see the general notes on submitting your assignments, or the same notes explained in slides, as well as the late policy and the collaboration policy.

The Dropbox link to submit part 1 of your assignment is here and part 2 here.