CS 488/688: Introduction to Computer Graphics

Fall 2016 Assignment 4: Trace


The goal of this assignment is to write a simple, mostly non-recursive ray tracer that can do (at least) the following:

  1. Cast primary rays from the eye position through every pixel in an image plane;
  2. Intersect primary rays with scene geometry;
  3. Cast shadow rays from intersection points to each light source; and
  4. Use the gathered information to perform illumination calculations and choose a colour for the pixels associated with the primary rays.

For geometric primitives you must support spheres, cubes and triangle meshes. Those primitives can be assembled into a modelling hierarchy, meaning that your ray-object intersection code must be able to traverse that hierarchy recursively. You must support a standard Phong illumination model (remember that this is different from Phong shading of mesh surfaces), lit by point light sources and a global ambient light. You must support ray tracing acceleration via hierarchical bounding volumes (which can be spheres, boxes, or some other, fancier data structure), and be capable of demonstrating the resulting improvement in performance. Finally, you must implement one additional feature of your own choosing, and create a novel scene and rendered image that demonstrate that feature.

A few additional notes on these features:


As with Assignment 3, input scenes are described using a simple modelling language built on top of a Lua interpreter. The following function behaves similarly to Assignment 3, but isn't quite identical:

Assignment 4 also includes the following new functions:

The functions gr.nh_box and gr.nh_sphere allow you to implement a non-hierarchical version of the ray tracer, since you can place spheres and boxes in arbitrary locations in world coordinates. Thus you will be able to test aspects of your code such as shading and shadows without necessarily having hierarchical transformations working. We provide a few non-hierarchical test scenes to facilitate this process. Later you may find it easier to build scenes using gr.sphere, gr.cube, and hierarchical transformations.

Tips and cautions

You are free to develop your code as you like. However, you will probably find it easiest if you first write a non-hierarchical ray tracer (Objectives 1–6). Once you have that part of the code debugged, add the hierarchical part (Objectives 8 and 9, affine transformations, a general hierarchy, and bounding volumes for meshes). Depending on what you implement for your extra feature, you may or may not want to complete Objective 10 before starting on hierarchical transformations. Finally, you need to create a unique scene (Objective 7). While you can write the unique scene earlier in the development cycle, you may want to wait until you know if you will finish hierarchical models, since the power of hierarchical modelling will let you build a more interesting scene.

For this assignment, you are allowed to produce some console output. For instance, you may want to output your render parameters and have some indication of how much progress your ray tracer is making (i.e., 10%, 20% done etc). Printing out your entire hierarchy tree is probably too much output, though.

For debugging purposes, it can be useful to have a way to trace a single primary ray. That way, if you know that a particular part of your scene is producing incorrect output you can follow your program's execution at a single pixel and examine its behaviour in detail. Another approach is to render a scene in false colours that provide some insight into the behaviour of the program at every pixel. You might even consider embedding the ray tracer in an interactive UI like that of A3, where you can compare an OpenGL rendering of your scene with the corresponding raytraced image (but this could require a lot of extra effort).

Be aware of numerical issues that arise in any ray tracing algorithm. In particular, consider the following tips from past students:

In hierarchical ray tracing, on "the way down" you should transform the point and vector forming the ray with a node's inverse transform. On "the way back up" you should transform the intersection point by the original transformation, and (assuming you represent the normal as a column vector) you should transform the normal with the transpose of the upper-3×3 part of the inverse transform.


You are required to implement an additional non-trivial feature. There are many possibilities, such as an efficiency improvement or an addition of functionality. Several ideas are given below. They are purely a list of suggestions for your consideration, and not intended to be exhaustive; a list of papers on ray tracing is given in the course bibliography. These papers contain a lot more possibilities (some of them might even include code.) A good overall reference for possible extensions is the book Physically Based Rendering by Pharr and Humphreys.

New features

Improved efficiency

The key to improving efficiency is the avoidance of unnecessary work, or rather, only applying work were it will make a difference. Some ideas for improving efficiency are:

If you choose to implement some kind of optimization for your extra feature, you must offer an effective demonstration that it actually works. If the improvement can not be demonstrated visually, you might note differences in timing in your README, for example.

There's no harm in implementing multiple extensions in the scope of this assignment. We'll give you the credit for whichever one you want to associate "officially" with this assignment. If you plan to extend your ray tracer for the project, you'll still be able to count all those additional extensions as objectives later.

Provided files

As usual, you should be able to use premake4 gmake; make in the A4/ subdirectory to build the skeleton code. When run, the skeleton program ignores the scene graph read in from the Lua script and produces a fixed background as a demonstration of writing colours to pixels.

A number of sample scripts are provided in the Assets directory. The .lua files are the scene files themselves, which you pass as command-line arguments to the A4 executable; the .obj files are meshes that are loaded by the scene files. Most of these scripts will work only when invoked from within the Assets directory, since they load OBJ files in the same directory. For some of the test scenes, we provide sample renderings in the course gallery.

Note the files polyroots.hpp and polyroots.cpp, which provide stable and robust solvers for quadratic, cubic and quartic polynomials. We recommend you use these solvers to handle intersections with most algebraic surfaces.


Prepare and upload a ZIP file of the A4/ directory, omitting unnecessary files (executables, build files, etc.). Make sure to include at least the following files:

There will be a bit of subjective grading of your raytraced images. If the image is extremely good, we may award extra credit. If the image is extremely simple, but tests all features, the TA may subtract up to one half a mark. If the image does not test all features, more marks may be deducted, since the TAs will not be able to verify all the features.

If you can not get hierarchical transformations working, submit an image made without them, and mention that you are missing hierarchical transformations in your README. You will be severely penalized if we discover that you misrepresented yourself, of course.

Objective list

Every assignment includes a list of objectives. Your mark in the assignment will be based primarily on the achievement of these objectives, with possible deductions outside the list if necessary.

Assignment 4 objectives