Ray tracing requires many ray-object intersection tests. A way of reducing the number of ray-object intersection tests is to subdivide the space occupied by objects into many nonoverlapping subregions, called voxels, and construct an octree for the subdivided space.
In this thesis, we propose a new octree-variant data structure, called Octree-$\mathbf{R}$, for efficient ray tracing. The algorithm for constructing Octree-$\mathbf{R}$ first estimates the number of ray-object intersection tests. Then, it partitions the space along the plane that minimizes the estimated number of ray-object intersection tests.
We also propose a fast octree traversal method. In this method, traversal is done from the nearest common ancestor node of all neighbor nodes of the current node. This method avoids traversing the octree from the root to find a leaf node.
We present the results of extensive experiments for verifying the effectiveness of Octree-$\mathbf{R}$ and the new octree traversal method. In the experiment, Octree-$\mathbf{R}$ provides 10%-40%, 20% on the average, gain over the conventional octree. Our new octree traversal method gets more than 20% gain over the conventional traversal method.