Fast Hardware Construction and Refitting of Quantized Bounding Volume Hierarchies
Abstract
There is recent interest in GPU architectures designed to accelerate ray tracing, especially on mobile systems with limited memory bandwidth. A promising recent approach is to store and traverse Bounding Volume Hierarchies BVHs, used to accelerate ray tracing, in low arithmetic precision. However, so far there is no research on refitting or construction of such compressed BVHs, which is necessary for any scenes with dynamic content. We find that in a hardware-accelerated tree update, significant memory traffic and runtime savings are available from streaming, bottom-up compression. Novel algorithmic techniques of modulo encoding and treelet-based compression are proposed to reduce backtracking inherent in bottom-up compression. Together, these techniques reduce backtracking to a small fraction. Compared to a separate top-down compression pass, streaming bottom-up compression with the proposed optimizations saves on average 42% of memory accesses for LBVH construction and 56% for refitting of compressed BVHs, over 16 test scenes. In architectural simulation, the proposed streaming compression reduces LBVH runtime by 20% compared to a single-precision build, and 41% compared to a single-precision build followed by top-down compression. Since memory traffic dominates the energy cost of refitting and LBVH construction, energy consumption is expected to fall by a similar fraction.
References
[1]
<label>{Ape14}</label> Apetrei C.: Fast and Simple Agglomerative LBVH Construction. In Computer Graphics and Visual Computing CGVC2014. 2
[2]
<label>{DFM13}</label> Doyle M., Fowler C., Manzke M.: A hardware unit for fast SAH-optimized BVH construction. ACM Transactions on Graphics Volume 32, Issue 4 2013, pp.139:1-10. 1, 3, 6
[3]
<label>{DP15}</label> Domingues L.R., Pedrini H.: Bounding volume hierarchy optimization through agglomerative treelet restructuring. In Proc. High-Performance Graphics2015, pp. pp.13-20. 2
[4]
<label>{FD09}</label> Fabianowski B., Dingliana J.: Compact bvh storage for ray tracing and photon mapping. In Proc. Eurographics Ireland Workshop2009, pp. pp.1-8. 2, 7, 8
[5]
<label>{GPM11}</label> Garanzha K., Pantaleoni J., McAllister D.: Simpler and faster HLBVH with work queues. In Proc. High-Performance Graphics2011, pp. pp.59-64. 2
[6]
<label>{GS87}</label> Goldsmith J., Salmon J.: Automatic creation of object hierarchies for ray tracing. Computer Graphics and Applications Volume 7, Issue 5 1987, pp.14-20. 2
[7]
<label>{IWP07}</label> Ize T., Wald I., Parker S.G.: Asynchronous BVH construction for ray tracing dynamic scenes on parallel multi-core architectures. In Proc. Eurographics Conf. Parallel Graphics and Visualization2007, pp. pp.101-108. 3
[8]
<label>{Kar12}</label> Karras T.: Maximizing parallelism in the construction of BVHs, octrees, and k-d trees. In Proc. High-Performance Graphics2012, pp. pp.33-37. 2, 9
[9]
<label>{Kee14}</label> Keely S.: Reduced precision hardware for ray tracing. In Proc. High-Performance Graphics2014, pp. pp.29-40. 1, 2, 3, 8, 10
[10]
<label>{KIS*12}</label> Kopta D., Ize T., Spjut J., Brunvand E., Davis A., Kensler A.: Fast, effective BVH updates for animated scenes. In Proc. Symp. Interactive 3D Graphics and Games2012, pp. pp.197-204. 1, 3
[11]
<label>{KK86}</label> Kay T.L., Kajiya J.T.: Ray tracing complex scenes. In ACM SIGGRAPH Computer Graphics 1986, vol. Volume 20, ACM, pp. pp.269-278. 3
[12]
<label>{KYM15}</label> Kim Y., Yang W., Mutlu O.: Ramulator: A fast and extensible DRAM simulator. IEEE Computer Architecture Letters PP, Volume 99 2015, pp.1-1. 10
[13]
<label>{LGS*09}</label> Lauterbach C., Garland M., Sengupta S., Luebke D., Manocha D.: Fast BVH construction on GPUs. Computer Graphics Forum Volume 28, Issue 2 2009, pp.375-384. 1, 2
[14]
<label>{LSL*13}</label> Lee W., Shin Y., Lee J., Kim J., Nah J., Jung S., Lee S., Park H., Han T.: SGRT: A mobile GPU architecture for real-time ray tracing. In Proc. High-Performance Graphics2013, pp. pp.109-119. 1
[15]
<label>{LV16}</label> Liktor G., Vaidyanathan K.: Bandwidth-efficient BVH layout for incremental hardware traversal. In Proc. High Performance Graphics2016, pp. pp.51-61. 1, 8, 10
[16]
<label>{LYM07}</label> Lauterbach C., Yoon S.-E., Manocha D.: Ray-strips: A compact mesh representation for interactive ray tracing. In Proc. IEEE Int. Symp. Interactive Ray Tracing 2007, IEEE, pp. pp.19-26. 10
[17]
<label>{McG11}</label> McGuire M.: Computer graphics archive, 2011. "http://graphics.cs.williams.edu/data/meshes.xml". 10
[18]
<label>{MW06}</label> Mahovsky J., Wyvill B.: Memory-conserving bounding volume hierarchies with coherent raytracing. In Computer Graphics Forum 2006, vol. Volume 25, pp. pp.173-182. 2
[19]
<label>{NKK*14}</label> Nah J., Kwon H., Kim D., Jeong C., Park J., Han T., Manocha D., Park W.: RayCore: A ray-tracing hardware architecture for mobile devices. ACM Transactions on Graphics Volume 33, Issue 5 2014, pp.162:1-15. 1
[20]
<label>{NKP*15}</label> Nah J., Kim J., Park J., Lee W., Park J., Jung S., Park W., Manocha D., Han T.: HART: A hybrid architecture for ray tracing animated scenes. IEEE Transactions on Visualization and Computer Graphics Volume 21, Issue 3 2015, pp.389-401. 1, 3, 8
[21]
<label>{PL10}</label> Pantaleoni J., Luebke D.: HLBVH: Hierarchical LBVH construction for real-time ray tracing of dynamic geometry. In Proc. High-Performance Graphics2010, pp. pp.87-95. 2
[22]
<label>{Pow15}</label> Power VR: PowerVR ray tracing. Accessed Feb 20, 2017, 2015. "http://imgtec.com/powervr/ray-tracing/". 1
[23]
<label>{SE10}</label> Segovia B., Ernst M.: Memory efficient ray tracing with hierarchical mesh quantization. In Proc. Graphics Interface2010, pp. pp.153-160. 2, 8, 10
[24]
<label>{SKBD12}</label> Spjut J., Kopta D., Brunvand E., Davis A.: A mobile accelerator architecture for ray tracing. In Proc. Workshop on SoCs, Heterogeneous Architectures and Workloads2012. 1
[25]
<label>{SKKB09}</label> Spjut J., Kensler A., Kopta D., Brunvand E.: TRaX: a multicore hardware architecture for real-time ray tracing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Volume 28, Issue 12 2009, pp.1802-1815. 1
[26]
<label>{VAMS16}</label> Vaidyanathan K., Akenine-Möller T., Salvi M.: Watertight ray traversal with reduced precision. Proc. High-Performance Graph2016. 2, 3, 4, 5, 6, 8, 10
[27]
<label>{VKJ*15}</label> Viitanen T., Koskela M., Jääskeläinen P., Kultala H., Takala J.: MergeTree: a HLBVH constructor for mobile systems. In SIGGRAPH Asia Technical Briefs2015, p. pp.12. 1, 2, 3, 8
[28]
<label>{VKJT16}</label> Viitanen T., Koskela M., Jääskeläinen P., Takala J.: Multi bounding volume hierarchies for ray tracing pipelines. In SIGGRAPH Asia Technical Briefs2016, p. pp.8. 10
[29]
<label>{Wal07}</label> Wald I.: On fast construction of SAH-based bounding volume hierarchies. In Proc. IEEE Int. Symp. Interactive Ray Tracing2007, pp. pp.33-40. 2, 8
[30]
<label>{WBB08}</label> Wald I., Benthin C., Boulos S.: Getting rid of packets - efficient SIMD single-ray traversal using multi-branching BVHs. In Proc. IEEE Int. Symp. Interactive Ray Tracing 2008, IEEE, pp. pp.49-57. 1
[31]
<label>{WBS07}</label> Wald I., Boulos S., Shirley P.: Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Transactions on Graphics Volume 26, Issue 1 2007, pp.6. 2, 3, 8
[32]
<label>{WSS05}</label> Woop S., Schmittler J., Slusallek P.: RPU: a programmable ray processing unit for realtime ray tracing. ACM Transactions on Graphics Volume 24, Issue 3 2005, pp.434-444. 1
Recommendations
Stochastic Light Culling for VPLs on GGX Microsurfaces
This paper introduces a real-time rendering method for single-bounce glossy caustics created by GGX microsurfaces. Our method is based on stochastic light culling of virtual point lights VPLs, which is an unbiased culling method that randomly determines ...
Hardware-Assisted Visibility Sorting for Unstructured Volume Rendering
Harvesting the power of modern graphics hardware to solve the complex problem of real-time rendering of large unstructured meshes is a major research goal in the volume visualization community. While, for regular grids, texture-based techniques are well-...
Rasterized Bounding Volume Hierarchies
We present the rasterized bounding volume hierarchy (RBVH), a compact data structure that accelerates approximate ray casting of complex meshes and provides adjustable level of detail. During construction, we identify subtrees of BVHs containing ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
The Eurographs Association & John Wiley & Sons, Ltd.
Chichester, United Kingdom
Publication History
Published: 01 July 2017
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025