Adaptive cell division for ray tracing

In ray tracing the two most commonly used data structures are the octree and uniform cell division. The octree structure allows efficient adaptive subdivision of space, while taking care of the spatial coherence of the objects in it; however, the tree structure locating the next node in the path of a ray is complex and time consuming. The cell structure, on the other hand, can be stored in a three-dimensional array, and each cell can be efficiently accessed by specifying three indices. However, such a uniform cell division does not take care of object coherence. The proposed data structure combines the positive features of the above data structures while minimising their disadvantages. The entire object space is implicitly assumed to be a three-dimensional grid of cells. Initially, the entire object space is a single voxel which later undergoes “adaptive cell division.” But, unlike in the octree structure, where each voxel is divided exactly at the middle of each dimension, in adaptive cell division, each voxel is divided at the nearest cell boundary. The result is that each voxel contains an integral number of cells along each axis. Corresponding to the implicit cell division we maintain a three-dimensional array, with each array element containing the voxel number which is used to index into the voxel array. The voxel array is used to store information about the structure of each voxel, in particular, the objects in each voxel. While a ray moves from one voxel to another we always keep track of the cell through which the ray is currently passing. Since only arrays are involved in accessing the next voxel in the path of the ray, the operation is very efficient.