OCTREE-R - AN ADAPTIVE OCTREE FOR EFFICIENT RAY-TRACING

Ray tracing requires many ray-obect intersection tests, A way of reduc ing the number of ray-object intersection tests is to subdivide the sp ace occupied by objects into many non overlapping subregions, called v oxels, and to construct an octree for the subdivided space. In this pa per, we propose the Octree-R, an octree-variant data structure for eff icient ray tracing. The algorithm for constructing the Octree-R first estimates the number of ray-object intersection tests. Then, it partit ions the space along the plane that minimizes the estimated number of ray-object intersection tests. We present the results of experiments f or verifying the effectiveness of the Octree-R. In the experiment, the Octree-R provides a 4% to 47% performance gain over the conventional octree. The result shows the more skewed the object distribution (as i s typical for real data), the more performance gain the Octree-R achie ves.