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

doi:10.3778/j.issn.1002-8331.2010.28.057

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (28): 202-204.DOI: 10.3778/j.issn.1002-8331.2010.28.057

• 图形、图像、模式识别 • 上一篇下一篇

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

黄忠¹，江巨浪¹，张佑生²，蔡庆华³

1.安庆师范学院物理与电气工程学院，安徽安庆 246011
2.合肥工业大学计算机与信息学院，合肥 230009
3.安庆师范学院计算机与信息学院，安庆 246011

收稿日期:2009-03-03 修回日期:2009-05-15 出版日期:2010-10-01 发布日期:2010-10-01
通讯作者: 黄忠

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

HUANG Zhong¹，JIANG Ju-lang¹，ZHANG You-sheng²，CAI Qing-hua³

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

摘要/Abstract

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

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

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

中图分类号:

TP391.41

黄忠¹，江巨浪¹，张佑生²，蔡庆华³. 基于中剖面kd-树的光线跟踪加速算法[J]. 计算机工程与应用, 2010, 46(28): 202-204.

HUANG Zhong¹，JIANG Ju-lang¹，ZHANG You-sheng²，CAI Qing-hua³. Ray-tracing acceleration algorithm based on median-cut kd-tree[J]. Computer Engineering and Applications, 2010, 46(28): 202-204.

[1]	张健，焦良葆，陈瑞. CPU-GPU混合平台上动态场景光线跟踪的研究[J]. 计算机工程与应用, 2012, 48(21): 151-154.
[2]	宫文,樊养余,张胜超,李胜亮. 一种基于光线跟踪的软阴影算法[J]. 计算机工程与应用, 2008, 44(5): 46-47.
[3]	秦合森,顾耀林. 使用半球谐函数进行的快速全局照明计算[J]. 计算机工程与应用, 2007, 43(27): 116-118.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics