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 sub-linear, 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 axis-aligned 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.
NOTE: Perform a
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: Ray-Triangle Intersection (20%)
In this task, you will implement a ray-triangle intersection routine. Triangles are generally the default modeling primitives and hence essential for rendering a variety of scenes. You will implement the ray-triangle 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 per-vertex normal data is available. The barycentric coordinates can be computed as a part of the triangle intersection routine. By interpolating the per-vertex normals using the barycentric coordinates the shading normal can be computed. If per-vertex 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.
NOTE: Dirt uses a right-handed coordinate system where the 'z' axis points out from the screen. Hence triangles in our framework are assumed to have a counter-clockwise orientation of their vertices. Make sure to take this into account while computing the face normal for triangles. It can be convenient to assume a canonical triangle with one vertex at origin, one vertex along the x-axis and one vertex along the y-axis and using this triangle to determine where the normal should actually point towards to. An incorrect normal direction might result in lighting computations to return always zero since the normal direction determines what is the 'inside' and 'outside' of a surface.
Task 2: Ray-Mesh 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 (
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).
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 per-vertex 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.
NOTE: The triangles in the meshes are assumed to have already been transformed into world space. Hence ray-triangle intersections can be carried out directly without transforming the ray into object-space.
Once you've completed adding the intersection code to
Mesh::intersect() routine, run the
01_raytrace application with the provided scene file '
NOTE: The provided scene file employs a 'bbh' acceleration structure. If you have not implemented one yet, you should remove the accelerator field from the json file to employ the linear accelerator. Not doing so will result in a blank image since you have not implemented an acceleration structure yet. Also employing the linear accelerator will be slow since it employs a brute-force exhaustive intersection search for every ray.
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 per-vertex normals results in a smoother appearance.
Figure 1: Teapot without barycentric normal interpolation
Figure 2: Teapot with barycentric normal interpolation
NOTE: Certain meshes might not have per vertex normal data associated with a mesh. In such cases, make sure to explicitly check for normal data and perform shading normal interpolation only when the data is present. If per vertex normal data is not available then the shading normal is the same as the face normal.
Task 3: Ray-AABB Intersection (25%)
The BBH employs an axis aligned aligned bounding box (AABB) as its enclosing primitive for the internal nodes. A ray-AABB test is much cheaper than a ray-mesh 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 ray-box 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 in-turn 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 top-down 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 4-10, 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 higher-quality 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 pseudo-code for the first two split strategies.
NOTE: The middle split strategy might result in a degenerate case where all primitives are partitioned inside only one of the child nodes while the other gets none. You must detect this condition and write code that handles this appropriately (e.g. by cycling to a different split axis or using equal-counts for just that level).
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).
NOTE: We encourage you to start the acceleration structure construction coding process by trying to implement the simpler methods before starting the SAH since it can be notoriously hard to track down bugs with regards to acceleration structure construction. Also try to test your code with simple scenes having limited geometry before using large scenes since construction times can be significant.
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.cppsource file contains pseudo-code 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 ray-acceleration structure traversal pseudo-code for more information.
NOTE: We cannot stop traversal of a ray within a BBH as soon as an intersection is encountered. This is because a BBH does not guarantee spatial ordering between primitives and hence all the nodes have to be processed before the nearest intersected primitive is returned.
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.
NOTE: The provided json scene files use a relative path scheme for loading OBJ file format meshes. It assumes that the scene directory is one level above the working directory of the executable. If you encounter an error indicating that the program was unable to load the mesh file, please change the paths to the meshes within the json files. This edit operation is very minor and can be easily accomplished.
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
- bunny-dragons.json: 3.0037
- sponza-buddha.json: 2.8254
Figure 3: Reference image for 'simple.json'.
Figure 4: Reference image for 'bunny-dragons.json'.
Figure 5: Reference image for 'sponza-buddha.json'.
What to hand in
You should submit a zip file containing
- The source code with your changes (the entire
- Images of all provided scenes as produced by your raytracer. After you finish the assignment, run
01_raytracer on all scenes in
scenes/02_raytrace_faster, and add the images to the zip.
- A 'README' file containing the output of the
- Also add the ray traversal stats (average ray-primitive 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.