**DUE DATE: Saturday March 5, 11:00pm**

**Groups of two are allowed!**

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

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

**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).

**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.- 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.
- 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.
- 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.
- 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.

**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.

**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.

**Mesh intersection:**The provided scene loading framework also supports loading triangle meshes from OBJ files. Use this to add triangle mesh intersection to your raytracer, and trace some scenes with meshes.**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.

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 |

- Submit using the
*submit as6*command on the INST machines:- A copy of your code, including the whole framework, that compiles on the platform you developed on.
- 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. **TWO**images generated by your raytracer. One of the thousand spheres scene, and one of helical spheres scene.

- Put on your class instructional website:
- A separate page for this assignment.
- On this page, the images you are turning in, as well as the scene and OBJ files for them.

`make`

and for solaris `gmake`

.
`submit as6`

to easily submit the whole project to us.

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.

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.