COS 426: Computer Graphics Spring 2014

Overview

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

Running the Program

The ray tracing program, raypro, 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

creates a 128x128 image (out.jpg) of the scene in in.scn.

The raypro program reads scenes in a simple file format, which was created specifically for this course to provide the features required by this assignment -- a simple scene graph along with materials, lights, and cameras. We provide several example scenes in the input subdirectory of the zip file that you can use to test your program. 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.

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

% rayview input.scn.

A window will pop up showing the scene from the camera include in the scene file (or a default, if there is none), and with lights like the ones in the scene file (or defaults, if there are none). You can drag the cursor with the left mouse button down to rotate the scene, with SHIFT-left-button to scale it (or the middle mouse button), and CTRL-left-button to translate it. You can also type F in the window to toggle display of faces, E to toggle display of edges, B to toggle display of the node bounding boxes, C to toggle display of the input camera, L to toggle display of lights, SPACE to print the current camera parameters (in a format that can be included in another .scn file), Q to quit, and F1 to save a screenshot in an image (in "imageN.jpg", for N=1,2,etc. increasing each time an image is dumped in the same session). Some of these commands are also available via a menu that pops up when the right mouse button is pressed.

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 ones marked in bold are required. The others are optional. Refer to the example web page to see images of inputs and outputs for several of these features.

• 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) Answering a nontrivial question on Piazza (please copy the question and answer into your writeup),
• (1) Submitting a movie showing images generated with a moving camera, a dynamic scene, and/or smoothly varying parameter settings,
• (1) Submitting one or more images for the art contest,
• (2) Rendering the most complex scene of anybody in the class (using less than 10 minutes of compute time), or
• (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.

Getting Started

You should use the skeleton code in (cos426_assignment3.zip) as a starting point for your assignment. It contains a R3Scene class for reading and representing scenes (in R3Scene.h and R3Scene.cpp). It also contains useful classes for manipulating images and geometric primitives in the R2, R3, and jpeg subdirectories, just like in Assignment 2.

Compiling the code produces two executables: raypro and rayview (or raypro.exe and rayview.exe). raypro is the program that runs on the command line, and rayview provides a way for you to visualize scenes interactively.

To implement the ray tracing features listed above, you should add code to the appropriate functions within src/raytrace.cpp, add commands to the Makefile to test them, and edit sections of the writeup.html to present and discuss your results. You are welcome to create your own program arguments by editing raypro.cpp or rayview.cpp, but please do not change the program arguments already provided. You may also want to extend rayview.cpp to provide new visualizations to aid debugging, but please do not override or remove any of the commands in the existing user interface.

Submitting

You should submit your solution using one zip file named cos426_assignment3.zip via CS dropbox at this submission link. The submitted zip file should have the following internal directory structure:

cos426_assignment3/

• writeup.html - your writeup (see the description below),
• Makefile - a Linux script that generates all the images in the output directory from the data in the input directory)
• src/ - the complete source code, including all the code for libraries, compilation, etc.
• input/ - all the input data for the commands in your Makefile
• output/ - all the images referenced by your writeup
• art/ - all images submitted for the art contest (optional), and movie files submitted for the movie feature (optional).

The writeup.html file should be an HTML document demonstrating the effects of the features you have implemented and would like scored. You can start from the writeup.html provided with the distribution as a template -- simply add/delete sections to that HTML file for the features you implement.

The src directory should have all code required to compile and link your program (including the files provided with the assignment), along with a Visual Studio Solution file and a Makefile to rebuild the code. We will not attempt to grade assignments that neither build in Visual Studio nor with GNU Make under Mac OS X.

The Makefile should be a script containing the commands that generate all the meshes in the output directory that demonstrate features of your program you would like scored. It should run without crashing when started in the cos426_assignment3/ directory (i.e., it should be possible to delete all the mesh files in the output directory and then run make to regenerate them).

We will test your code on Linux 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 before submitting. Your Makefile should generate all the images in the output directory referenced by your writeup.

To save space, please submit images in .jpeg format (not .bmp or .ppm) and remove binaries and backup files from the src directory before submitting -- i.e., run make clean (under Linux or Mac OS) and execute "Clean Solution" on the "Build menu" in MS Visual Studio.

Note 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. Partial credit may not be assigned for code without comments.

FAQ

Answers to frequently asked questions: