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

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


Your raytracer should, by now, be able to raytrace a complicated scene hierarchy. Unfortunately the most interesting primitives we have are spheres. In this assignment we extend our raytracer to handle triangles. To support rendering more complicated meshes, 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 use Hierarchical Axis-Aligned Bounding Boxes [Shirley, 10.9.2].

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:

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, and an OBJ file of the Utah Teapot here.

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


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.

Framework and Reference Implementation

You can download a patch for your raytracer here. It consists of a new UCB directory that replaces the old scene loader with a new scene loader. It supports a superset of the interface exposed by the previous loader, so it should cleanly replace your current loader. See the "Example Scene" section for files you need to render. See the Framework page here for the full framework.

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;


	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_ */