CS184 AS6: Triangle Meshes and Speed-up Structures for your Raytracer

DUE DATE: Tuesday 17th March, 11:00pm

Aim

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

Minimum Specifications

We will provide you with an OBJ importer that supports 3D triangle meshes. This importer will take a complicated OBJ file and provide you with a vector of Triangle objects and a vector of Vertex objects. You can merge these lists of Triangles with your world's list of Primitives to create a flat scene hierarchy, just like in AS5. For this assignment, modify your raytracer in the following ways:

1. Shadows, Reflections: You should already have working shadows and reflections from AS5. Be sure to complete it if you don't.
2. Triangle Meshes and Bounding Box intersection:
   
   • We will supply you with an OBJ loader that exports a list of triangles and vertices. You need to use this data to populate the world with Triangle objects. Create a Triangle class that extends Primitive. Write the intersection method for this class, allowing you to render OBJ files in the same way as you currently render spheres.
   • We will now have bounding boxes on all our objects. Write a bounding box class, and add methods to both the sphere and the triangle to return a bounding box for it. Then write an intersection test method for this bounding box. Note that you don't need to know the actual t-value for bounding box intersection, you only need to know whether it occurred or not. As for implementation details, see the Framework section for a suggested layout of your bounding box class.
3. Hierarchical Axis-Aligned Bounding Boxes (AABB trees) -- Construction:
   
   • During your scene creation, create your flat scene hierarchy by populating the World's primitives vector now with both spheres and triangles (See Implementation Tips on grabbing triangles from our OBJ parser). Now that you have a hierarchically flat, fully instantiated "sea of spheres and triangles", construct an acceleration structure that allows for sublinear time intersection tests. This acceleration structure is in world space. We recommend you construct an Axis Aligned Bounding Box Tree
   • Recursive Construction: You will now write a recursive function that takes in a current list of primitives and a AABB node, and construct the given node's children or make it a leaf node. Call this function with a root node and the whole list of primitives.
     1. If the number of primitives is less than the maximum number of primitives you want to store of 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. 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.
4. 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 "open up" each bounding box that the ray intersects and then do recursively intersection tests on all children inside.
   • When the ray finally intersects a bounding box of a leaf, it will then do an intersection calculation with the leaf-primitive (sphere or triangle). If the instance has a transformation associated with it, do the inverse transformation on the ray as you did in Assignment #5.
5. Evaluation of Performance Gain:
• Compare the rendering times in your ray-tracer with and without using this data structure.

Extra Credit ideas:

• Better acceleration structure organization: Implement two levels of speedup structures - one in model space for each imported mesh, one in world space for the scene. The scene's acceleration structure will have instances as leaves, where all instances of an object shares the same geometry and acceleration structure. If you are doing animation, only the scene tree needs to be rebuilt after each frame, while the acceleration structure for each mesh stays constant.
• Animation: Our scene parser still fully supports animation as it did for AS3. Implement animation for your raytracer to take advantage of this.
• Smooth Shading: Rather than considering each triangle as a separate entity and shading it with a flat shading model, implement smooth shading (either Gouraud or Phong Interpolation) to smooth colors across triangle borders.
• Different acceleration structures: If you are rally ambitious you can implement other acceleration structures, such as KD Trees or Bounding Interval Hierarchies.

Example Scene (for submission)

Here is some OBJ files for you to have fun with:

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

Submission

• Submit using the submit as6 command on the INST machines:
  1. A copy of your code, including the whole framework, the 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.
  3. TWO images generated by your raytracer. One of whatever complicated scene you want (preferably the thousand spheres one), one of the Utah Teapot. For each scene note the total render time with and without the use of the Hierarchical Bounding Boxes.
     
• 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.

Framework and Reference Implementation

Accessing Mesh Data

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.

Bounding Box prototype

This is our suggested bounding box class. Be sure to look at the largest number that can be represented as a double, std::numeric_limits::max(), to set useful initial values for your bounding box.

#ifndef BBOX_H_
#define BBOX_H_

#include "global.h"
#include <algorithm>

struct BBox {

	vec4 min;
	vec4 max;

	BBox();

	void expand(const BBox & bbox);
	void expandToFit(const vec4 & v);

	vec4 getMidpoint() const;
	BBox transform(mat4 T) const;

	bool intersect(Ray & ray) const;
};

#endif /* BBOX_H_ */