Octree-R: an adaptive octree for efficient ray tracing

摘要

Ray tracing requires many ray-object intersection tests. A way ofnreducing the number of ray-object intersection tests is to subdivide thenspace occupied by objects into many nonoverlapping subregions, callednvoxels, and to construct an octree for the subdivided space. We proposenthe Octree-R, an octree-variant data structure for efficient rayntracing. The algorithm for constructing the Octree-R first estimates thennumber of ray-object intersection tests. Then, it partitions the spacenalong the plane that minimizes the estimated number of ray-objectnintersection tests. We present the results of experiments for verifyingnthe effectiveness of the Octree-R. In the experiment, the Octree-Rnprovides a 4% to 47% performance gain over the conventional octree. Thenresult shows the more skewed the object distribution (as is typical fornreal data), the more performance gain the Octree-R achieves