This repository represents a Computer Graphics Engine done from scratch entirely in C++.
Here you can see a couple of pictures generated using only our Engine:
The features implemented are as follows:
Here a ray is shot at the right wall of the box and it is colored green, as the color of the intersection point
The BVH is implemented fully inside the bounding_volume_hierarchy.cpp and the corresponding header file. The creation goes the following way:
- For each triangle and sphere in the scene create a Primitive struct. This structure stores the primitive’s centroid as well as the data of the primitive itself. For the triangle it collects the triangle’s mesh index and the indices of the vertices. For the sphere it saves the sphere’s index in the scene.
- Now we call the createBVH function. It is recursively defined to operate on a range of primitives inside the primitives vector.
- If the range contains only one primitive or we have achieved the maximum depth (defined to be 16 levels), we are creating the leaf node. The node struct stores an axis aligned bounding box that holds all the primitives inside. Additionally it has some more information - a boolean marker for leaf nodes, the range into the primitives vector (of the contained primitives) and for non-leaf nodes the indices of the left and right child nodes. Once we have all the information about the node, we save it in the nodes vector and return the index we stored it at.
- For the recursive case we call the function splitFunc that for the standard feature works the following way. We pass the primitives vector, the range into this vector we want to operate on and the depth we’re at. For the standard BVH the splitFunc is set to be splitStandard function. Based on the depth value we decide the axis to perform the split on. Then we find the median primitive in the range by doing a partial sort (std::nth_element). Now we have all the “smaller” primitives to the left of the median and all the “greater” to the right. Lastly we return the index on which we performed the split.
- Back in createBVH we call the function recursively on the left and right ranges. We get back the indices where the child nodes got stored at. Now we have all the required information to save our internal node, so we do it. Lastly we return the index the node was stored at.
- Now the bounding volume hierarchy is finished. We save the root node’s index to be used for traversal.
In the method intersect() in bounding_volume_hierarchy.cpp a stack is being used for the traversal of the hierarchy, as it will contain all the intersected aabb’s found in the ray’s path. We start with the root node that is first pushed as the first element in the stack. We have a while loop that iterates until the stack becomes empty(no more unvisited aabb’s). Every iteration we pop the top element from the stack, check whether that popped node is a leaf node, if it is a leaf node we iterate over all the primitives that leaf node contains and use the intersect method provided by the library to check whether an intersection has happened. If a node is not a leaf node, then we take its two children (we use indexes here into the std::vector nodes list to retrieve the corresponding children). After getting the children we check if the children are being intersected by the upcoming ray. If they are, we push them to the stack. Traversal checks all the nodes and updates the closest primitive so far hit. We have defined a Primitive to be a Triangle or a Sphere, and thus the traversal handles both cases very nicely. Optimization has been achieved through the use of indexes and const references, which has improved the speed of rendering images. In the getIntersecting() method we pass the iterators for the first primitive in the box and the last primitive in the box, and by using modern c++ we iterate over all of them and update the optional primitive in case of a hit.
