# A Shader-Based Ray Tracing Engine
## 3 Design
### BVH Tree Construction  
Bounding Volume Hierarchy is one of the well-known hierarchical approaches to the ray tracing acceleration structures, which handles the operation at a significantly lower cost than without it [23]. It stores the scene data into a binary tree where primitives are recursively wrapped in the bounding volumes, ultimately composing one unified volume on the root of the tree. After its construction, the ray can then traverse down the tree checking intersections with the bounding volume at each node, excluding the primitives which are not in the active ones.  
Fast and efficient Boundary Volume Hierarchy tree construction is another interesting aspect of its design. Analysis of its approach is still ongoing despite its aged foundation and is recently aimed at building an inexpensive and dynamic structure for its practical usage [23]. Nonetheless, we implemented a simple bottom-up breadth-first tree generation valuing simpleness over completeness.  
We pair the primitives close to each other's _centroid_, leaving a list of single-depth tree nodes, which has the primitives as the child. We then recursively pair the nodes again with the closest centroid, building the tree bottom to top, until it reaches the root node where there are no more nodes to be paired. Figure 6 visualizes this bottom-up breath-first approach.  
Figure 5: Overview of our ray tracing engine.  
Although this algorithm provides an efficient enough BVH tree to be traversed, its unstable construction time is a drawback. It has the worst time complexity of \(O(2^{n}n^{3})\), dramatically lowering the performance as the number of primitives \(n\) increases.  
To speed up this process, we exploited [PERSON]'s _Morton code method_[31]. The space-awareness characteristics of the Morton code, which is also known as the _z-order curve_, allows us to organize the primitives in the octree hierarchy [28; 32]. Primitives are first binned into the _z_-ordered array indexed by their centroid. Figure 7 explains this _z_-ordering sequence with a sample 2D quad-tree representation.  
Once all the primitives are grouped, we generate BVH trees for each bin and merge them to create one complete tree for the model. This greatly reduces the overhead of closest centroid searching with neglectable precision loss. Our experimental results will be presented in Section 4.  
The constructed tree is now transferred to the video memory (VRAM) and hundred millions of rays are evaluated with the _compute shader_. We found the _roped BVH structure_ to be optimal when sending the tree data to GPU [28; 32]; it ensures stackless traversal by storing a skip pointer instead of the parent-sibling tree structure. Figure 8 demonstrates the  
Figure 6: A simple 2D example of the bottom-up breath-first tree construction: closer objects are paired until the whole space is processed into the tree.  
Figure 7: A _z_-order sequence marked on the 2D quad-tree representation, and its corresponding Morton-ordered binning sequence.  
creation of an example roped BVH, in a step by step manner [33; 34]. Blue lines represent the tree traversal in the left-to-right order, while red arrows represent skip pointers where iteration will skip to when the current volume is not hit. After linking the nodes by the traversal order, we convert the tree into an array and send it to the GPU as a _texture_. The tree will be traversed with the code in Pseudocode 1.  
Pseudo code for the Roped BVH tree traversal.