Modify your C++ ray tracing program to include a bounding volume data structure, either a Binary Space Partition (BSP) or a grid, to speed up the rendering of triangle meshes. A BSP is a data structure that is similar to a binary tree where triangles are arranged in hierarchical axis aligned bounding boxes. Render speed can be increased with a BSP by only testing for intersection with triangles in leaves of the tree that intersect with a ray. A grid is a data structure that is similar to a hash table where triangles are binned into a three-dimensional grid. Render speed can be increased with a grid by only testing for intersection with triangles in grid cells that a ray intersects with. Both of these data structures can also speed up render time even further by checking for intersections with bounding volumes from nearest to farthest.
For this assignment you can choose which bounding volume data structure to implement. For either data structure the mesh class should have a bounding volume data structure member value. The bounding volume data structure class should store pointers to the triangles in the mesh class. The mesh intersect function should be modified to use the intersect method of the bounding volume data structure class.
If you choose to implement a grid, the dimensions of the grid should be determined by the number of triangles in the mesh and the size of the mesh bounding box. The cells of the grid should be lists of pointers to triangles in the mesh. The triangles can be efficiently added to the grid by computing the minimum and maximum cell by first computing the minimum and maximum point of the triangle and then adding the triangle to all cells between the minimum and maximum cell. The grid intersection function should test for intersection with the cells in the grid in the order that the ray intersects with the cells of the grid. If an intersection is found, and the intersection point is inside the cell, then the remaining cells do not need to be tested.
If you choose to implement a BSP, the maximum number of triangles per node should be set with a constant. All nodes should should have a bounding box that bounds the bounding box of the node's children. Leaf nodes should also contain a list of pointers to triangles in the mesh that are at least partially inside the leaf's bounding box. Non-leaf nodes should have two children that partition the node's bounding box along the x, y, or z axis, depending on the height of the node. For example, all nodes at height h, where h % 3 is 0 should partition using x values. The location of the partition should be computed as the average of the partition type, x, y, or z, of all vertices inside the node's bounding box. The BSP intersection function should descend from the root returning the closest intersection of each of its children. Note, it should test the child that intersects the ray first. If the node does not have children, then it should return the closest intersection of all the triangles in the node.
Tar your code in a file that contains your name and submit it on the course Inquire site.