A fast ray tracing algorithm based on adaptive space subdivision  

作　　者：鲍虎军 彭群生 

机构地区：[1]State Key Laboratory of CAD and CG, Zhejiang University, Hangzhou 310027, China

出　　处：《Science China Mathematics》1995年第4期490-498,共9页中国科学：数学（英文版）

基　　金：Project supported by the National Natural Science Foundation of China.

摘　　要：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.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.

关 键 词：RAY TRACING SPACE SUBDIVISION BINARY tree. 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]