A fast ray tracing algorithm based on adaptive space subdivision

A new fast ray tracing algorithm based on adaptive space subdivision is presented. Unlike the conventional octree and 3DDDA algorithms, the new algorithm subdivides the object space nonuniformly with the division planes coplanar with the boundary planes of bounding volumes of objects. At each recursive step, the concerned rectangular space is divided into two subcells. The partitioning direction and division plane is dynamically selected so that it has the least possibility to intersect the objects within and the difference of the number of objects enclosed in each subcell is small. An efficient traversal algorithm to search for the next node that the ray will enter is also designed. Theoretical analysis and experimental results show that the new algorithm is potential.