# RT Engine: An Efficient Hardware Architecture for Ray Tracing
## 2 Overall System Architecture
### Ray Tracing Algorithm  
The BVH ray traversing algorithm can be described as the while-while loop [10] in Algorithm 1. This algorithm's initial value sets the node's address to the root node of BVH, and the initial value of the bottom of the stack is a mask. When a ray enters this loop, it traverses from the root node. The outer while loop determines whether the current ray has finished. When the node's address is the mask of stacks, this indicates the current ray has completed the traversal. The first inner while loop is a depth-first traversal of BVH. The ray must intersect against the child nodes when the node is an internal node. If two child nodes intersect against the ray, push the farther children into the stack, and the other transfer to the next unit; if only one child node is intersected, traversal this child node; if no child node is intersected, then pop the stack. The second inner while loop is the intersection of leaf nodes. The primary purpose of this loop is to determine the intersection of rays and primitives of the scene and calculate the intersection. The calculation results of this loop can be used by the shader to render an image. After completing this part, the current leaf node is complete. Then, it pops the stack. We adopt a multiple-stacks approach to solve the parallelism of ray tracing. In addition, we also design two improved methods to accelerate the speed of the triangle intersection test. We will introduce each of these methods in detail next.  
Algorithm 1 is a standard ray tracing algorithm for BVH. The current ray tracing algorithm introduced stackless-based BVH Traversal, such as [PERSON] et al. [28]. This method uses simple logic to sort each node's parent pointer and minimize the stack's use. However, it requires re-visiting internal nodes, which will cause some redundant operations. [PERSON] et al. [29] present a BVH backtracking algorithm in constant time with two tables. The primary method is to prepare the bit trail and the current key for each level, which causes BVH's storage space to increase. In addition, two tables are needed to occupy ample storage. The full-stack method will be easier and more efficient in dedicated hardware than those implementation methods. In addition, many later works have also studied how to use multi-branching wide BVH [23; 30]. Compared with wide BVH, using binary-based BVH can reduce the expenses of the operation and reduce redundant processes. So, we finally chose this standard algorithm.  
```
Input: ray, rootNode of the BVH Output: intersection results
1 hit\(\leftarrow\) false \(curNode\leftarrow\) rootNode
2 Stack\(\leftarrow\)\(\phi\) whilecurNode\(\
eq\phi\)do
3 whilecurNode is a internal nodedo
4 foreach child in curNodedo
5 ifcurRay hits curNode.left and does not hit curNode.rightthen
6 Traverse(curRay, curNode.left)
7 ifcurRay hits curNode.right and does not hit curNode.leftthen
8 Traverse(curRay, curNode.right)
9 ifit_distance_right \(>\) hit_distance_left then
10 Traverse(curRay, curNode.left)
11 ifcurRay hits curNode.right and curNode.leftthen
12 ifhit_distance_right \(\leq\) hit_distance_left then
13 Tavverse(curRay, curNode.left)
14 ifit_curRay does not hit curNode.right or curNode.leftthen
15 curNode = Stack.pop
16
17 whilecurNode is a leaf nodedo
18 fortriangles in the nodedo
19\(\leftarrow\) Intersection(ray,traiangle)
20 ifhitthen
21 return closest hit
22 break
23 curNode \(\leftarrow\) Stack.pop()
```  
**Algorithm 1**BVH Ray Tracing Algorithm