CS184 AS6: Reflections and Acceleration Structures

DUE DATE: Saturday March 5, 11:00pm
Groups of two are allowed!


In this assignment we add reflections to our raycaster to make it a proper raytracer. To support rendering more complicated scenes, we will also implement a data structure for sublinear intersection tests of our scene. Speedup structures come in many forms; for this assignment we will strongly suggest using Hierarchical Axis-Aligned Bounding Boxes [Shirley, 10.9.2] {or 12.3.2}.

IMPORTANT: To complete this project, we assume you've already read the textbook's chapter 6, 9 and 10.

Minimum Specifications

For this assignment, modify your raytracer in the following ways:

  1. Raytracing:
    • Reflection: Create rays which reflect off objects (the so-called "bounce ray"), and are again sent into the scene in the bounce direction. To accomplish this, write your raycast(Ray, depth) function in such a way that it can be used recursively. Use ks as the coefficient of reflection and multiply pairwise against S (as defined in as4) to account for metalness: ks * pairwiseMult(S, raycast(ray, depth-1)).
    • Limited Bounce Depth: In theory you could estimate when the maximum possible contribution from an additional recursive bounce-ray is less than say 1/256, then stop recursion at that point. But estimating a good bound on maximum possible contribution is tricky, and you would likely have excessive bounces in highly reflective, brightly lit scenes. Instead, just set a hard limit for the number of consecutive bounce rays, i.e., terminate the recursive raycasts after some specified depth. Set the default depth to 4 (so, discounting shadow rays, you will cast at most 4 rays per image sample).
  2. Hierarchical Axis-Aligned Bounding Boxes (AABB trees) -- Construction:
    • Construct an acceleration structure that allows for sublinear time intersection tests. This acceleration structure is in world space. Specifically, use an Axis Aligned Bounding Box Tree
    • Recursive Construction: You will now write a recursive function that takes in a current list of primitives and an AABB node, and constructs the given node's children or makes it a leaf node. Call this function with a root node and the whole list of primitives.
      1. If you've reached some maximum recursive depth or the number of primitives is less than the maximum number of primitives you want to store in a leaf node, then declare the current node a leaf and store all the primitives in this leaf.
      2. If not, we need to separate the current list of primitives into a left and a right list by partitioning the primitives according to some axis. You can either calculate the average centroid of the current list of primitives, or you can find the median of the current list of primitives. Once you've done this, you can partition the list into primitives on the left or on the right of this partitioning point. To separate it into left and right, you need to consider only one of the three axes. In Shirley, the suggestion is to cycle through axes as you move down the tree. If you don't use the median to partition, a better solution is to calculate which axis would give the best partitioning. Calculate the difference in number of primitives between the left and right branch for each axis. Choose to partition the list by the axis that makes this difference the smallest, thus constructing the most balanced tree.
      3. Now that you've partitioned this list into two sublists, create a left and a right child node for the current node, and recursively call this build function on the left and right child nodes with their respective left and right partitioned lists.
      4. When you reach the leaf nodes, your function should return a bounding box for that node. The recursive function was used to create the tree moving downwards, now we will generate the nested bounding box hierarchy as we return bounding boxes upwards. At each node, save its bounding box by constructing a bounding box out of both children's bounding boxes. After this is complete, you should have a nested bounding box structure.
  3. Hierarchical Axis-Aligned Bounding Boxes -- Traversal:
    • After having built this additional data-access structure you can now do the queries as to what each ray intersects much more efficiently.
    • Ray - Bbox intersection tests start at the root of the hierarchy and will recursively test each child bounding box that the ray intersects, starting with the closest.
    • When the ray finally intersects a bounding box of a leaf, it will then do an intersection calculation with each primitive in the leaf. The closest intersection found in the leaf can then be returned up the tree as a candidate for closest intersection point, and optionally used to skip recursing into bounding boxes which would be hit after that point.
  4. Evaluation of Performance Gain:

Extra Credit ideas:

Example Scene (for submission)

We want to see that your speedup structures actually work. To that end, we're supplying you with a 1000 sphere scene that you need to render. In addition, we supply a smaller scene with some interesting reflections.

A thousand spheres. thousandspheres.scd
A helical pattern of spheres. scene2.scd
Three spheres scene rendered with reflections. threespheres.scd

For those who want to implement triangle meshes (one of the extra credit suggestions), here are some scenes with OBJ files for you to have fun with:

A single triangle added to our threespheres world threespheresandtriangle.scd, triangle.obj
The famous Utah Teapot. teapot.scd and teapot.obj


To submit this project, all of the following needs to be done by the deadline: Windows Users: The grader should ONLY have to open your .sln file and press F5 to build and run your solution.
*Nix Users: The grader should ONLY have to run make with the appropriate makefile to build your project. Thus, for Mac and Linux make and for solaris gmake.

Note: The submit program retains the directory structure of what you send it. Thus, we recommend making a new directory for your assignment on the server, cd'ing into that directory, copying the whole framework with your code into this directory, and running submit as6 to easily submit the whole project to us.

Group submissions

For this project, groups of two are allowed. If you're working in a group, only one of you should submit the full project results; the other should only submit the README.txt file. Both of you should include your partner's name in the README.txt file.

Implementation Tips

When testing performance, you'll want to enable optimizations in your compiler. For mac and unix, the makefile should already do this for you. For visual studio you can set the project to compile in 'Release mode'.

To time your program performance, you can use the clock() function from time.h. Use CLOCKS_PER_SEC to convert the timing value to seconds.

Accessing Mesh Data (optional / extra credit)

Meshes are represented as an OBJTriangleMesh struct containing a list of OBJTriangle and a list of OBJVertex objects. An OBJTriangle consists of three indices, that indicate which OBJVertex objects define the three corners of the mesh. Check whether a SceneGroup contains a Mesh by using the SceneGroup.computeMesh() function. Each mesh has its own color, material and transform just as Spheres had their own color, material and transform.