Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (28): 202-204.DOI: 10.3778/j.issn.1002-8331.2010.28.057

• 图形、图像、模式识别 • Previous Articles     Next Articles

Ray-tracing acceleration algorithm based on median-cut kd-tree

HUANG Zhong1,JIANG Ju-lang1,ZHANG You-sheng2,CAI Qing-hua3   

  1. 1.School of Physics and Electric Engineering,Anqing Teachers College,Anqing,Anhui 246011,China
    2.School of Computer and Information,Hefei University of Technology,Hefei 230009,China
    3.School of Computer and Information,Anqing Teachers College,Anqing,Anhui 246011,China
  • Received:2009-03-03 Revised:2009-05-15 Online:2010-10-01 Published:2010-10-01
  • Contact: HUANG Zhong

基于中剖面kd-树的光线跟踪加速算法

黄 忠1,江巨浪1,张佑生2,蔡庆华3   

  1. 1.安庆师范学院 物理与电气工程学院,安徽 安庆 246011
    2.合肥工业大学 计算机与信息学院,合肥 230009
    3.安庆师范学院 计算机与信息学院,安庆 246011
  • 通讯作者: 黄 忠

Abstract: Kd-tree algorithm is one of the most prominent and the most widely used algorithms of ray-tracing acceleration.On the base of carrying out in-depth research and analysis,median-cut kd-tree algorithm is proposed.Build an index table of the scene lay information in pretreatment stage,and use the auxiliary stack to store the information that will be used when visiting the next node,then the middle section kd-tree algorithm saving storage space about 50%.In addition,use a more flexible manner to treat the subdivision axial,and divide the scene in accordance with the largest extension axial to reduce the possibility the light across two nodes at the same time,therefore this algorithm can reduce the cost time of visiting node and improve its computation efficiency.

Key words: ray-tracing, acceleration technique, kd-tree, median-cut kd-tree

摘要: kd-树算法是光线跟踪加速技术中效果最突出、应用最广泛的算法之一。在深入讨论该算法的基础上,提出了中剖面kd-树算法。该算法通过在预处理阶段加入一个场景层次信息索引表,将剖分平面固定为中剖面,并利用栈存储下一结点所需信息,节约了一半的存储空间;此外,将剖分轴按照最大轴向进行剖分,从而减少了光线同时穿过两个子结点的可能性,减少了访问时间,提高了算法效率。

关键词: 光线跟踪, 加速技术, kd-树, 中剖面kd-树

CLC Number: