CS184 AS6: Reflections and Acceleration Structures

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

Aim

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:
• Compare the rendering times in your ray-tracer with and without using this data structure. Specifically, set max objects in a leaf to 1, and then note timings for max depths of 1, 2, 8 and 16 for the two provided scenes. Write a few sentences explaining the performance differences you observe.

Extra Credit ideas:

• Refraction: Create rays that can travel through your scene primitives depending on coefficients of refraction (kt the transparency of the material and ktn the refractive index of the material). These rays should bend according to Snell's Law. Assume that the air has a refractive index of 1 (thus, the "n" value for air in snell's law is 1).
• Different acceleration structures: Implement other acceleration structures, such as KD Trees or Bounding Interval Hierarchies. Compare the performance you get.
• Other performance experiments: Experiment with interesting other ways to improve performance of your raytracer. For example, you could try progressively rendering the scene so that some low resolution rendering is returned in real time, and the result is iteratively refined over time. Or experiment with threading your program, or even implementing it on a GPU.

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

Submission

To submit this project, all of the following needs to be done by the deadline:
• Submit using the submit as6 command on the INST machines:
1. A copy of your code, including the whole framework, that compiles on the platform you developed on.
2. A README.txt containing: Your name, SID, Login and a description of the platform your code compiles on, and any extra credit you did. Also include your performance analysis (timings for depths 1,2,8,16, and a few sentences of analysis) for the thousand spheres and helical spheres scenes.
3. TWO images generated by your raytracer. One of the thousand spheres scene, and one of helical spheres scene.
• Put on your class instructional website:
1. A separate page for this assignment.
2. On this page, the images you are turning in, as well as the scene and OBJ files for them.
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.