Assignment 6: Ray tracing faster
 Due Nov 6, 2017 by 11:59pm
 Points 10
 Submitting a file upload
 File Types zip
 Available after Sep 9, 2017 at 12am
Overview
In this assignment, you will learn how to accelerate ray tracing by using acceleration data structures. In the previous assignment, each time you traced a ray the code would perform an intersection test against every single primitive in your scene. This is a reasonable solution for scenes with a few primitives, but quickly becomes impractical in typical scenes that contain meshes with thousands to billions of primitives/triangles. Naive ray tracing on these scenes is infeasible since the cost of tracing a ray grows linearly with the number of primitives. Acceleration structures allow us to keep this cost sublinear, providing tremendous speed improvements for typical scenes.
In this assignment you will implement an acceleration structure called a bounding volume hierarchy (BVH) that employs a hierarchy of axisaligned bounding boxes (AABB) as the bounding volume primitive, hence forming a bounding box hierarchy (BBH). You will start by implementing basic primitive intersection routines that will build upon one another culminating in a fully functional BBH implementation that will allow you to render scenes with thousands to millions of triangles in a matter of seconds to minutes.
This assignment comes with multiple tasks with the undergraduate and graduate students having slightly different requirements.
git pull
to get the latest code changes from the repo before working on the assignment. Ray tracing is a popular programming exercise, and there are countless implementations of ray tracing and acceleration structures available online. Needless to say, you are not allowed to look at those implementations or copy their source code when completing this assignment. You are required to design and implement your own solution and failing to adhere to this policy will be a direct violation of the academic honor code.Task 1: RayTriangle Intersection (20%)
In this task, you will implement a raytriangle intersection routine. Triangles are generally the default modeling primitives and hence essential for rendering a variety of scenes. You will implement the raytriangle intersection code for a single triangle within the static method Mesh::singleTriangleIntersect()
in the src/mesh.cpp
file. Once you've finished writing up the intersection code, you can go ahead and run the 02_test1_tri_intersection
application that tests your intersection code. This application is provided for you to make sure your intersection routine is working properly before proceeding ahead with mesh intersection. Making sure your triangle intersection works correctly saves you the trouble of debugging the code as you perform full ray tracing against a scene containing lots of geometry. You can implement any of the triangle intersection routines taught in the class lectures and book.
The intersection routines have a reference to a Intersect3f
struct as input argument. This structure conveniently encapsulates all data about the intersection of a ray with any surface within the scene. The structure has a geometric normal (Intersect3f::gn
) that represents the face normal of a triangle. The geometric normal can be computed from the edges of the triangles using a cross product. The shading normal (Intersect::sn
) can be computed when pervertex normal data is available. The barycentric coordinates can be computed as a part of the triangle intersection routine. By interpolating the pervertex normals using the barycentric coordinates the shading normal can be computed. If pervertex normals are not available, the shading normal is the same as the geometric normal.
Implement your code and run the 02_test1_tri_intersection
application. You should get the correct required solutions as indicated in the source code. The application tests for both the geometric and shading normals' correctness.
Task 2: RayMesh Intersection (5%)
Once you've made sure that your single triangle intersection routine works correctly, you can now proceed ahead to implement the Mesh::intersect()
routine. A mesh is a collection of triangles. The triangle data is stored in an indexed format within the mesh. The vertex positions are stored within the Mesh::m_V
vector and the triangle faces are represented as tuples of 3 indices (vector3i
) within Mesh::m_F
that index into the vertices vector. Using an indexed notation saves memory by not having duplicate vertex data. Mesh::m_N
stores per vertex normal data that can be provided along with a scene file. Mesh::m_UV
stores per vertex 'uv' texture coordinates that will be used to texture meshes in a scene (texturing will be covered in a later lecture).
The Mesh::intersect()
routine takes as input an additional 'index' argument that can be used to retrieve vertex location data as well as other associated data (normal and 'uv' coordinates) with respect to a triangle. The 'index' argument refers to a triangle within the Mesh::m_F
whose three components give the indices of the vertex data within Mesh::m_V
(the same indices can give the locations of pervertex normal and texture coordinates data if available). Once you fetch this data, compute the intersection with the specified triangle using the static function Mesh::singleTriangleIntersect()
that you've already written.
Once you've completed adding the intersection code to Mesh::intersect()
routine, run the 01_raytrace
application with the provided scene file 'teapot.json
'.
We have provided two reference images (Figure1 and Figure2) that show the shading normal not being computed and being computed. Notice how barycentric interpolation of pervertex normals results in a smoother appearance.
Figure 1: Teapot without barycentric normal interpolation
Figure 2: Teapot with barycentric normal interpolation
Task 3: RayAABB Intersection (25%)
The BBH employs an axis aligned aligned bounding box (AABB) as its enclosing primitive for the internal nodes. A rayAABB test is much cheaper than a raymesh intersection test. Hence a primitive is tested for intersection only if its bounding box passes an intersection test with the ray. You will have to implement the raybox intersection test within the src/bbh.cpp
file. Once you have implemented the intersection code, run the 02_test2_aabb_intersection
application to test your code. You should pass the all the tests run by the application.
Task 4: Acceleration Structure Construction and Traversal (50%)
For this task you will be implementing a bounding box hierarchy (BBH) in order to accelerate ray traversal speed. As indicated earlier, acceleration structures rapidly increase ray tracing speed when compared to naive object intersections. The quality of the acceleration structure built determines the average number of primitives tested per ray for intersection. This inturn directly affects the ray tracing speed as well. A BBH is essentially a binary tree where the leaf nodes contain the actual primitives whereas internal nodes partition the global list of primitives into different subsets. A BBH employs an object partitioning scheme and hence two sibling nodes have no two primitives in common between them. Each internal node has a bounding volume that encompasses all the set of objects it has. Hence the root node is the global bounding box of the entire scene.
A BBH can be constructed in either a top down or bottom up fashion using a variety of methods. However a recursive topdown approach of constructing the BBH is comparatively easy to other methods. We start from the root node and recursively create child nodes as well as leaf nodes depending upon the number of primitives we want the leaf nodes to have (BBH::maxPrimsInNode
). Setting too fine a number means that we have deep trees spending more time intersecting bounding boxes, while setting a large number means that we have shallower trees but spend more time intersecting all the primitives in the leaves. A good value is generally 410, however we encourage you to play with this number to see how it affects your ray tracing performance.
As indicated earlier, at each node we recursively divide the contained elements. This division is called a 'split' strategy and a variety of split strategies exist. A simpler strategy might might construct the BBH tree quickly, while a complicated one might take longer while yielding a higherquality BBH that results in faster overall ray tracing time. BBH performance is typically determined by the amount of bounding overlap between nodes and different split strategies result in different overlap characteristics. In this assignment we will deal with 3 split strategies typically encountered in literature.
 Middle split  Split the node at the spatial center of the encompassing bounding box and partition objects into a 'left' and 'right' node based on location with respect to the split location.
 Equal counts split  Split the node into 'left' and 'right' child nodes that have the same number of primitives
 Surface Area Heuristic (SAH)  A heuristic for choosing the split criterion which tries to minimize the expected cost of a random ray intersecting the BBH.
The first two split strategies are relatively easy compared to the SAH heuristic method. The text book provides pseudocode for the first two split strategies.
Undergraduate students are required to implement the first two split strategies (middle and equal counts). You can undertake the SAH split method for extra credit.
Graduate students are required to implement the SAH splitting method as well as one of the other two (you can also try to implement all three, but this will just be for personal satisfaction and bragging rights, and not for extra credit).
In this assignment, you are required to implement your acceleration structure building code in the BBH::build()
routine in the src/bbh.cpp
file. The split technique is determined by the BBH::splitMethod
in the source files which is initialized by the splitMethod
key when loading a json scene file. Once you are done implementing the build routine, you should add your acceleration structure traversal routine to the BBH::intersect()
routine in the same file as above. The provided bbh.cpp
source file contains pseudocode to help you with the traversal process. The traversal process starts at the root node where the ray is tested for intersection with the root bounding box. If no intersection happens, we exit immediately since a ray cannot hit any primitive when it doesn't hit the bounding box. We then perform a recursive traversal within both the children of each node. When we reach a leaf node, we check for intersection between all the primitives within the leaf and update ray parameters appropriately. We then continue with the traversal in a recursive manner until we check all other nodes in the tree. Please refer to the textbook for rayacceleration structure traversal pseudocode for more information.
You can test your acceleration structure code by running the 01_raytrace
application with scenes from the scenes/02_raytrace_faster
folder. The provided code computes the average number of primitives tested per traced ray (primitives_intersected / traced_rays
). This number is indicative of the quality of the BBH (a lower number indicates that only a few costly primitive intersection tests are performed overall). Report this number as a part of your submission, it will be used as one component of the grading. We encourage you to also post your statistics on Piazza to compare your performance with other classmates.
We provide the average number of primitives tested per ray for our implementation of the BBH on the scenes provided. Note that these numbers can vary with respect to different parameters such as view location. The numbers provided are respective to the given scene file configurations. These numbers are given to you so that you can estimate how well your implementation is performing compared to ours.
 simple.json: 2.2486
 teapots.json: 1.3499
 bunnydragons.json: 3.0037
 sponzabuddha.json: 2.8254
Figure 3: Reference image for 'simple.json'.
Figure 4: Reference image for 'bunnydragons.json'.
Figure 5: Reference image for 'sponzabuddha.json'.
What to hand in
You should submit a zip file containing
 The source code with your changes (the entire
src
folder)  Images of all provided scenes as produced by your raytracer. After you finish the assignment, run
01_raytracer
on all scenes inscenes/02_raytrace_faster
, and add the images to the zip.  A 'README' file containing the output of the
02_test2_xxxx_intersection
applications.  Also add the ray traversal stats (average rayprimitive intersection tests) performance of your BBH on the different scenes provided (don't change the view location or other scene parameters).
 Report any problems you've experienced or any further comments you want to add.
Do not submit binaries. Do not include your build folder.
Rubric
Criteria  Ratings  Pts  

Task 1
threshold:
pts


pts



Task 2
threshold:
pts


pts



Task 3
threshold:
pts


pts



Task 4
threshold:
pts


pts



Total Points:
10.0
out of 10.0
