Please wait a minute...
浙江大学学报(工学版)
J4  2012, Vol. 46 Issue (1): 84-89    DOI: 10.3785/j.issn.1008-973X.2012.01.14
    
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
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      

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.

Published: 22 February 2012
CLC:  TP 312  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

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

URL:

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


基于GPU的层次包围盒快速构造方法

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

［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] ZHU Wen-qiao, DIAO Chang-yu, XU Duan-qing, LU Dong-ming. Multi-view three-dimensional reconstruction using continuous symmetric disparity[J]. J4, 2014, 48(1): 85-91.
[2] YANG Xin, XU Duan-qing, ZHAO Lei, YANG Bing. Secondary ray tracing in parallel[J]. J4, 2012, 46(10): 1796-1802.