Cited By
View all- Zhang YTsai PTseng HSalapura VZahran MChong FTang L(2022)SIMD2Proceedings of the 49th Annual International Symposium on Computer Architecture10.1145/3470496.3527411(552-566)Online publication date: 18-Jun-2022
Accelerating Probabilistic Volumetric Mapping using Ray-Tracing Graphics Hardware
Pages 5440 - 5445
Abstract
Probabilistic volumetric mapping (PVM) represents a 3D environmental map for an autonomous robotic navigational task. A popular implementation such as Octomap is widely used in the robotics community for such a purpose. The Octomap relies on an octree to represent a PVM and its main bottleneck lies in massive ray-shooting to determine the occupancy of the underlying volumetric voxel grids.In this paper, we propose GPU-based ray shooting to drastically improve the ray shooting performance in Octomap. Our main idea is based on the use of recent ray-tracing RTX GPU, mainly designed for real-time photo-realistic computer graphics and the accompanying graphics API, known as DXR. Our ray-shooting first maps leaf-level voxels in the given octree to a set of axis-aligned bounding boxes (AABBs) and employ massively parallel ray shooting on them using GPUs to find free and occupied voxels. These are fed back into the CPU to update the voxel occupancy and restructure the octree. In our experiments, we have observed more than three-orders-of-magnitude performance improvement in terms of ray shooting using ray-tracing RTX GPU over a state-of-the-art Octomap CPU implementation, where the benchmarking environments consist of more than 77K points and 25K~34K voxel grids.
References
[1]
S. Thrun, W. Burgard, and D. Fox, Probabilistic robotics. Cambridge, Mass.: MIT Press, 2005.
[2]
A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss, and W. Burgard, “OctoMap: An efficient probabilistic 3D mapping framework based on octrees,” Autonomous Robots, 2013, software available at http://octomap.github.com. [Online]. Available: http://octomap.github.com
[3]
H. Moravec and A. Elfes, “High resolution maps from wide angle sonar,” in Proceedings. 1985 IEEE international conference on robotics and automation, vol. 2. IEEE, 1985, pp. 116-121.
[4]
Y. Roth-Tabak and R. Jain, “Building an environment model using depth information,” Computer, vol. 22, no. 6, pp. 85-90, 1989.
[5]
H. Moravec, “Robot spatial perception by stereoscopic vision and 3d evidence grids,” robotics institute," Tech. Rep., 1996.
[6]
K. Schauwecker and A. Zell, “Robust and efficient volumetric occupancy mapping with an application to stereo vision,” in 2014 IEEE International Conference on Robotics and Automation (ICRA), 2014, pp. 6102-6107.
[7]
E. Vespa, N. Nikolov, M. Grimm, L. Nardi, P. H. J. Kelly, and S. Leutenegger, “Efficient octree-based volumetric slam supporting signed-distance and occupancy mapping,” IEEE Robotics and Automation Letters, vol. 3, no. 2, pp. 1144-1151, 2018.
[8]
S. T. O’Callaghan and F. T. Ramos, “Gaussian process occupancy maps,” The International Journal of Robotics Research, vol. 31, no. 1, pp. 42-62, 2012.
[9]
S. Vasudevan, F. Ramos, E. Nettleton, H. Durrant-Whyte, and A. Blair, “Gaussian process modeling of large scale terrain,” in 2009 IEEE International Conference on Robotics and Automation, 2009, pp. 1047-1053.
[10]
J. Wang and B. Englot, “Fast, accurate gaussian process occupancy maps via test-data octrees and nested bayesian fusion,” in 2016 IEEE International Conference on Robotics and Automation (ICRA), 2016, pp. 1003-1010.
[11]
P. Fankhauser, M. Bloesch, and M. Hutter, “Probabilistic terrain mapping for mobile robots with uncertain localization,” IEEE Robotics and Automation Letters (RA-L), vol. 3, no. 4, pp. 3019-3026, 2018.
[12]
D. Belter, P. Łabcki, and P. Skrzypczyński, “Estimating terrain elevation maps from sparse and uncertain multi-sensor data,” in 2012 IEEE International Conference on Robotics and Biomimetics (ROBIO), 2012, pp. 715-722.
[13]
P. Biber and W. Strasser, “The normal distributions transform: a new approach to laser scan matching,” in Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) (Cat. No.03CH37453), vol. 3, 2003, pp. 2743–2748 vol.3.
[14]
T. Stoyanov, M. Magnusson, H. Andreasson, and A. Lilienthal, “Fast and accurate scan registration through minimization of the distance between compact 3d ndt representations,” The International Journal of Robotics Research, vol. 31, pp. 1377-1393, 09 2012.
[15]
J. Saarinen, H. Andreasson, T. Stoyanov, J. Ala-Luhtala, and A. J. Lilienthal, “Normal distributions transform occupancy maps: Application to large-scale online 3d mapping,” in 2013 IEEE International Conference on Robotics and Automation, 2013, pp. 2233-2238.
[16]
C. Schulz, R. Hanten, and A. Zell, “Efficient map representations for multi-dimensional normal distributions transforms,” in 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2018, pp. 2679-2686.
[17]
R. K. Hoetzlein, “Gvdb: Raytracing sparse voxel database structures on the gpu,” in Proceedings of High Performance Graphics, 2016, pp. 109-117.
[18]
F. Liu and Y. J. Kim, “Exact and adaptive signed distance fields computation for rigid and deformable models on gpus,” IEEE transactions on visualization and computer graphics, vol. 20, no. 5, pp. 714-725, 2014.
[19]
K. Zhou, M. Gong, X. Huang, and B. Guo, “Data-parallel octrees for surface reconstruction,” IEEE transactions on visualization and computer graphics, vol. 17, no. 5, pp. 669-681, 2010.
[20]
K. Museth, “Vdb: High-resolution sparse volumes with dynamic topology,” ACM transactions on graphics (TOG), vol. 32, no. 3, pp. 1-22, 2013.
[21]
M. Hadwiger, J. Beyer, W.-K. Jeong, and H. Pfister, “Interactive volume exploration of petascale microscopy data streams using a visualization-driven virtual memory approach,” IEEE Transactions on Visualization and Computer Graphics, vol. 18, no. 12, pp. 2285-2294, 2012.
[22]
C. Crassin, F. Neyret, M. Sainz, S. Green, and E. Eisemann, “Interactive indirect illumination using voxel cone tracing,” in Computer Graphics Forum, vol. 30, no. 7. Wiley Online Library, 2011, pp. 1921-1930.
[23]
C. Crassin, F. Neyret, S. Lefebvre, and E. Eisemann, “Gigavoxels: Ray-guided streaming for efficient and detailed voxel rendering,” in Proceedings of the 2009 symposium on Interactive 3D graphics and games, 2009, pp. 15-22.
[24]
E. Gobbetti, F. Marton, and J. A. I. Guitián, “A single-pass gpu ray casting framework for interactive out-of-core rendering of massive volumetric datasets,” The Visual Computer, vol. 24, no. 7-9, pp. 797-806, 2008.
[25]
Y. Kim, B. Kim, and Y. J. Kim, “Dynamic deep octree for highresolution volumetric painting in virtual reality,” in Computer Graphics Forum, vol. 37, no. 7. Wiley Online Library, 2018, pp. 179-190.
[26]
S. Laine and T. Karras, “Efficient sparse voxel octrees,” IEEE Transactions on Visualization and Computer Graphics, vol. 17, no. 8, pp. 1048-1059, 2010.
[27]
P. Shirley and R. K. Morley, Realistic ray tracing. AK Peters/CRC Press, 2003.
[28]
R. Woop, “A programmable ray processing unit for realtime ray tracing,” ACM Transactions on Graphics, SIGGRAPH, vol. 5, pp. 1-11, 2005.
[29]
M. J. Doyle, C. Fowler, and M. Manzke, “A hardware unit for fast sah-optimised bvh construction,” ACM Transactions on Graphics (TOG), vol. 32, no. 4, pp. 1-10, 2013.
[30]
J.-H. Nah, H.-J. Kwon, D.-S. Kim, C.-H. Jeong, J. Park, T.-D. Han, D. Manocha, and W.-C. Park, “Raycore: A ray-tracing hardware architecture for mobile devices,” ACM Transactions on Graphics (TOG), vol. 33, no. 5, pp. 1-15, 2014.
[31]
S. Woop, “A programmable hardware architecture for realtime ray tracing of coherent dynamic scenes,” Diss. Ph. D. Thesis, Sarrland University, 2007.
[32]
W.-J. Lee, Y. Shin, J. Lee, J.-W. Kim, J.-H. Nah, S. Jung, S. Lee, H.-S. Park, and T.-D. Han, “Sgrt: A mobile gpu architecture for realtime ray tracing,” in Proceedings of the 5th high-performance graphics conference, 2013, pp. 109-119.
[33]
M. Stich, “Introduction to NVIDIA RTX and DirectX Ray Tracing,” 2018. [Online]. Available: https://devblogs.nvidia.com/introduction-nvidia-rtx-directx-ray-tracing/
[34]
M.-K. Lefrancois and P. Gautron, “DX12 Raytracing tutorial,” 2018. [Online]. Available: https://developer.nvidia.com/rtx/raytracing/dxr/DX12-Raytracing-tutorial-Part-2
[35]
C. Gribble, “Multi-hit ray tracing in dxr,” in Ray Tracing Gems. Springer, 2019, pp. 111-125.
[36]
I. Wald, W. Usher, N. Morrical, L. Lediaev, and V. Pascucci, “Rtx beyond ray tracing: Exploring the use of hardware ray tracing cores for tet-mesh point location.” in High Performance Graphics (Short Papers), 2019, pp. 7-13.
[37]
J. Salmon and S. McIntosh-Smith, “Exploiting hardware-accelerated ray tracing for monte carlo particle transport with openmc,” in 2019 IEEE/ACM Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS). IEEE, 2019, pp. 19-29.
[38]
Nvidia, “Nvidia turing gpu architecture,” 2018. [Online]. Available: https://www.nvidia.com/content/dam/en-zz/Solutions/design-visualization/technologies/turing-architecture/NVIDIA-Turing-Architecture-Whitepaper.pdf
[39]
J. Amanatides, A. Wooet al., “A fast voxel traversal algorithm for ray tracing.”
[40]
D. Yadav, R. Jain, H. Agrawal, P. Chattopadhyay, T. Singh, A. Jain, S. B. Singh, S. Lee, and D. Batra, “Evalai: Towards better evaluation systems for ai agents,” 2019.
Recommendations
A Hardware Acceleration Method for Volumetric Ray Tracing
VIS '95: Proceedings of the 6th conference on Visualization '95In this paper we present an acceleration method for volumetric ray tracing which utilizes standard graphics hardware without compromising image accuracy. The graphics hardware is employed to identify those segments of each ray that could possibly ...
Use of hardware Z-buffered rasterization to accelerate ray tracing
SAC '07: Proceedings of the 2007 ACM symposium on Applied computingRay tracing is a rendering technique for producing realistic 3D computer graphics. Compared to traditional scan-line rendering which is generally adopted by graphics pipeline, ray tracing can simulate more realistic global illumination, however, with ...
Photon mapping on programmable graphics hardware
HWWS '03: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardwareWe present a modified photon mapping algorithm capable of running entirely on GPUs. Our implementation uses breadth-first photon tracing to distribute photons using the GPU. The photons are stored in a grid-based photon map that is constructed directly ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2021
9777 pages
Copyright © 2021.
Publisher
IEEE Press
Publication History
Published: 30 May 2021
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Nov 2024
Other Metrics
Citations
Cited By
View all- Zhang YTsai PTseng HSalapura VZahran MChong FTang L(2022)SIMD2Proceedings of the 49th Annual International Symposium on Computer Architecture10.1145/3470496.3527411(552-566)Online publication date: 18-Jun-2022
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in