Abstract:
This paper examines the efficiency of different ray-shooting acceleration schemes, including the uniform space subdivision, octree and kd-tree. We use simple computational models, which assume that the objects are uniformly distributed in space. The efficiency is characterized by two measures, including the expected number of ray-object intersections needed to identify the firstly intersected object, and the expected number of steps on the space partitioning data structure. We can come to the interesting conclusion that these numbers are constant and are independent of the number of objects in the scene. The number of intersections is determined by how well the cells of the partitioning data structure enclose the objects. Such analysis helps to understand why kd-tree is better than octree and uniform space subdivision and provides hints to improve their implementation.
Keywords:
Efficiency, uniform subdivision, octree, kd-tree.