Please wait a minute...
浙江大学学报(工学版)
J4  2012, Vol. 46 Issue (1): 84-89    DOI: 10.3785/j.issn.1008-973X.2012.01.14
自动化技术、计算机技术     
基于GPU的层次包围盒快速构造方法
杨鑫1 , 王天明2, 许端清1
1.浙江大学 计算机科学与技术学院,浙江 杭州 310027；2.海军装备研究院舰船所,北京 100073
Fast BVH construction on GPU
YANG Xin1, WANG Tian-ming2, XU Duan-qing1
1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China;
2.Naval Academy of Armament, Beijing 100073, China
 全文: PDF  HTML
摘要：

为了能够在基于光线跟踪技术的真实感图形绘制过程中迅速而高效地排除无效的光线相交计算,快速地构造高质量的加速结构,提出基于图形处理器（GPU）体系架构研究基于图形处理器的层次包围盒快速构造方法.在构造初期、构造中期、构造末期3个阶段分别针对二叉树结构特点和多核架构特点来设计不同的策略，从而实现层次包围盒结构(BVH)的并行快速构造.实验表明,采用该方法可以最大限度地发挥图形处理器强大的并行计算能力,有效使用硬件计算资源和存储资源,在保证加速结构构造质量的前提下大大缩短加速结构的构造时间.
Abstract:

The acceleration structure construction is a key step to accelerate rendering for ray tracing. An approach was proposed for fast bounding volume hierarchy (BVH) construction on the graphics processing unit (GPU) based on tree structure feature and multicore architecture, which adapted different construction strategies for the early, midterm and late phases. Experimental results show that the approach can effectively exploit the inherent parallelism of the GPU to accelerate computation. The processing power and memory resources provided by the GPU are effectively utilized, and construction time is significantly reduced for the same acceleration structure quality.
出版日期: 2012-02-22
:  TP 312  
基金资助:

国家“十一五”科技支撑计划资助项目（2010BAK67B17）；浙江省科技计划资助项目（2008C13079） .
通讯作者: 许端清，男，教授，博导.     E-mail: xdq@zju.edu.cn
作者简介: 杨鑫（1984-），男，博士生，从事计算机图形学和并行计算的研究. E-mail: xinyang@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

杨鑫 , 王天明, 许端清. 基于GPU的层次包围盒快速构造方法[J]. J4, 2012, 46(1): 84-89.

YANG Xin, WANG Tian-ming, XU Duan-qing. Fast BVH construction on GPU. J4, 2012, 46(1): 84-89.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2012.01.14    或    http://www.zjujournals.com/eng/CN/Y2012/V46/I1/84

［1］ INGO W, THIAGO I, ANDREW K, et al. Ray tracing animated scenes using coherent grid traversal ［J］. ACM Transactions on Graphics, 2006, 25(3): 485-493.
［2］ HAVRAN V. Heuristic ray shooting algorithms ［D］. Prague: Czech Technical University, 2001．
［3］ JEFFREY J. Automatic creation of object hierarchies for ray tracing ［J］. IEEE Computer Graphics and Applications, 1987, 7(5): 14-20．
［4］ DAN G, SHUHONG C. Fronttoback display of bsp trees ［J］. IEEE Computer Graphics and Applications, 1991, 11(5): 79-85.
［5］ CARSTEN W, ALEXANDER K. Instant ray tracing: the bounding interval hierarchy ［C］∥Proceeding of the 17th Eurographics Symposium on Rendering. Nicosia, Cyprus: EG Press, 2006: 39-149．
［6］ ANDREW S. An introduction to ray tracing ［M］. Maryland: Academic Press, 1989．
［7］ INGO W, VLASTIMIL H. On building fast kdtrees for ray tracing, and on doing that in o(nlogn) ［R］. Utah:  University of Utah, 2006．
［8］ GEIMER M, MLLER S. A crossplatform framework for raytracing［EB/OL］.2003-10-15.http:∥citeseerx.ist.psu.edu/viewdoc/summary．
［9］ WALD I, BOULOS S, SHIRLEY P. Ray tracing deformable scenes using dynamic bounding volume hierarchies ［J］. ACM Transactions on Graphics, 2007, 26(1): 67-76．
［10］ LAUTERBACH C, YOON S, TUFT D, et al. RTDEFORM: interactive ray tracing of dynamic scenes using BVHs ［C］∥IEEE Symposium on Interactive Ray Tracing. Salt Lake City: IEEE, 2006: 39-46．
［11］MACDONALD D, BOOTH S. Heuristics for ray tracing using space subdivision ［J］. The Visual Computer, 1990, 6(3): 153-166．
［12］GNTHER J, POPOV S, HANS S, et al. Realtime ray tracing on GPU with BVHbased packet traversal ［C］∥Proceedings of the IEEE/Eurographics Symposium on Interactive Ray Tracing. Ulm: IEEE, 2007: 113-118．
［13］ POPOV S, GNTHER J, SEIDEL P, et al. Experiences with streaming construction of SAH KDtrees ［C］∥ Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing. Salt Lake City: IEEE, 2006: 89-94．
［14］ SHEVTSOV M, SOUPIKOV A, KAPUSTIN A. Highly parallel fast KDtree construction for interactive ray tracing of dynamic scenes ［J］. Computer Graphics Forum, 2007, 26(3): 395-404．
［15］ 李静,王文成,吴恩华. 基于空盒自适应生成的动态场景光线跟踪计算［J］. 计算机学报, 2009, 32(6): 1172-1182．
LI Jing, WANG Wencheng, WU Enhua. Ray tracing of dynamic scenes by managing empty regions in adaptive boxes ［J］. Chinese Journal of Computers, 2009, 32(6): 1172-1182．
［16］ APPEL A. Some techniques for shading machine renderings of solids ［C］∥Proceedings of Spring Joint Computer Conference. Atlantic: Thomson, 1968: 37-45．
［17］ STEFAN P, JOHANNES G, HANS S, et al. Stackless KDtree traversal for high performance GPU ray tracing ［R］. Saarland: Saarland University, 2007．
［18］ HORN R, SUGERMAN J, HOUSTON M, et al. Interactive kd tree GPU raytracing ［C］∥Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games. New York: ACM, 2007: 167-174．
［19］ INGO W, THIAGO I, STEVEN P. Fast, parallel, and asynchronous of BVHs for ray tracing animated scenes ［J］. Computer and Graphics, 2008, 32(1): 3-13．
［20］ 张舒,褚艳利. GPU高性能运算之CUDA［M］. 北京：中国水利水电出版社,2009．
［21］ JOHN N, IAN B, MICHAEL G, et al. Scalable parallel programming with CUDA ［J］. Queue, 2008, 6(2): 40-53.
［22］ ERIK L, JOHN N, STUART O, et al. Nvidia Tesla: a unified graphics and computing architecture ［J］. IEEE Micro, 2008, 28(2): 39-55．
［23］ KHRONOS. The OpenCL 10 specification ［EB/OL］. 20081007. http:∥www.khronos.org．
［24］ AMD company. ATI stream computing website ［EB/OL］. 20080911. http:∥ati.amd.com/technology/streamcomputing/．
［25］ BUCK I, FOLEY T, HORN D, et al. Brook for GPUs: stream computing on graphics hardware ［J］. ACM Transactions on Graphics, 2004, 23(3): 777-786．
［26］ MCCOOL M, TOIT D, POPA T, et al. ACM SIGGRAPH 2004 class ［R］. New York: SIGGRAPH, 2004．
［27］ TARDITI D, PURI S, OGLESBY J. Accelerator: using data parallelism to program GPUs for generalpurpose uses ［J］. SIGOPS Operation System, 2006, 40(5): 325-335．
［28］ CHRISTIAN L, MICHAEL G, SHUBHABRATA S, et al. Fast BVH construction on GPUs ［J］. Computer Graphics Forum, 2009, 28(2): 375-384．
［29］ NHTV University. Project arauna ［CP/DK］. Breda, The Netherlands: the NHTV University of Appied Sciences, 2006．
［30］ Nvidia Company. The new fermi architecture ［EB/OL］. 2009-03-08. http:∥www.hardocp.com/article/2009/09/30/nvidias_fermi_architecture_white_paper/．
[1] 朱文峤,刁常宇,许端清,鲁东明. 基于连续对称视差计算的多视图立体匹配[J]. J4, 2014, 48(1): 85-91.
[2] 杨鑫, 许端清, 赵磊, 杨冰. 二级光线跟踪的并行计算[J]. J4, 2012, 46(10): 1796-1802.