Ray tracing of irregular scene based on spatial grid subdivision
SUN Jingguang1,LIU Jiatong2
1. School of Electronic and Information Engineering, Liaoning Technical University, Huludao Liaoning 125105, China;
2. School of Graduate, Liaoning Technical University, Huludao Liaoning 125105, China
To solve the slow rendering problem of ray tracing algorithm in irregular scene, an improved grid subdivision ray tracing algorithm was proposed based on the in-depth study and comparison of the recent acceleration algorithms of ray tracing. First, the rectangular bounding box of the scene was set to remove the influence of external light, and the intersect operations was simplified; second, spatial grids were created with a new way to limit the spatial unit number and complexity of storage space within a certain range; finally, the traditional spatial grid algorithm was greatly improved by subdividing grids to eliminate the bad influence on acceleration effects due to ignoring some blank space. The experimental results show that this method can effectively improve the light speed in blank space, it not only increases the time efficiency but also reduces the space lost.
孙劲光 刘佳桐. 基于空间网格细分的不规则场景的光线跟踪[J]. 计算机应用, 2014, 34(5): 1431-1434.
SUN Jingguang LIU Jiatong. Ray tracing of irregular scene based on spatial grid subdivision. Journal of Computer Applications, 2014, 34(5): 1431-1434.
APPEL A. Some techniques for shading machine renderings of solids [C]// Proceedings of Spring Joint Computer Conference. New York: ACM, 1968:37-45.
[2]
PENG Q, BAO H, JIN X. Based of computer realistic graphics algorithms [M]. Beijing: Science Press, 1999.(彭群生,鲍虎军,金小刚.计算机真实感图形算法基础[M].北京:科学出版社,1999.)
[3]
WHITTED T. An improved illumination model for shaded display [J]. Communications of the ACM, 1980,23(6):343-349.
[4]
WANG W, XIAO S, MENG W, et al. Ray tracing algorithm based on octree space partition method [J]. Journal of Computer Applications, 2008,28(3):656-658.(王文玺,肖世德,孟文,等.一种基于八叉树空间剖分技术的光线跟踪算法[J].计算机应用,2008,28(3):656-658.
[5]
WANG H, ZHU L, GU Y. Quick ray tracing algorithm based on surfaces of revolution [J]. Computer Engineering, 2008,34(10):274-276.(王华,朱丽华,顾耀林.基于旋转曲面场景的快速光线跟踪算法[J].计算机工程,2008,34(10):274-276.)
[6]
LIU Y, ZHANG M. Acceleration techniques in ray tracing algorithm [J]. Computer and Digital Engineering, 2013,41(6):863-866.(柳有权,张曼.光线跟踪算法的加速技术研究[J].计算机与数字工程,2013,41(6):863-866.)
[7]
POPOV S, GNTHER J, SEIDEL H P, et al. Stackless KD-tree traversal for high performance GPU ray tracing [J]. Computer Graphics Forum, 2007,26(3):415-424.
[8]
GARANZHA K, LOOP C. Fast ray sorting and breadth-first packet traversal for GPU ray tracing [J]. Computer Graphics Forum, 2010,29(2):289-298.
[9]
LU H, BAO P, FENG J. OpenCL-based real-time KD-tree and ray tracing for dynamic scene [J]. Journal of Computer-Aided Design and Computer Graphics, 2013,25(7):964-973.(卢贺齐,鲍鹏,冯洁青.基于OpenCL的实时KD-Tree与动态场景光线跟踪[J].计算机辅助设计与图形学学报,2013,25(7):964-973.)
[10]
CHOI B, KOMURAVELLI R, LU V, et al. Parallel SAH k-D tree construction for fast dynamic scene ray tracing [R/OL]. [2013-03-08].https://www.ideals.illinois.edu/bitstream/handle/2142/13798/parkd.pdf?sequence=2.
[11]
BUDGE B C, ANDERSON J C, GARTH C, et al. A straightforward CUDA implementation for interactive ray-tracing [C]// Proceedings of IEEE Symposium on Interactive Ray Tracing. Piscataway: IEEE Press, 2008:178.
[12]
WALD I, SLUSALLEK P, BENTHIN C, et al. Interactive rendering with coherent ray tracing [J]. Computer Graphics Forum, 2001,20(3):153-164
[13]
THRANE N, SIMONSEN L O. A comparison of acceleration structures for GPU assisted ray tracing [D]. Aarhus: University of Aarhus, 2005.
[14]
LI J, WANG W, WU E. Optimizing grid resolutions for ray tracing [J]. Journal of Computer-Aided Design and Computer Graphics, 2008,20(8):968-977.(李静,王文成,吴恩华.加快光线跟踪计算的网格优化划分[J].计算机辅助设计与图形学学报,2008,20(8):968-977.)
[15]
LI J, WANG W, WU E. Ray tracing of dynamic scenes by managing empty regions in adaptive boxes [J]. Chinese Journal of Computers, 2009,32(6):1172-1182.(李静,王文成,吴恩华.基于空盒自适应生成的动态场景光线跟踪算法[J].计算机学报,2009,32(6):1172-1182.)