Ray tracing STAR Aims Results Summary Acceleration Data Structures for Ray Tracing Marek Vinkler Department of Computer Graphics and Design October 18, 2011 Acceleration Data Structures for Ray Tracing 1 / 23 Ray tracing STAR Aims Results Summary Outline Ray tracing STAR Aims Results Acceleration Data Structures for Ray Tracing 2 / 23 Ray tracing STAR Aims Results Summary Motivation Figure: [PFHA10] Jacopo Pantaleoni, Luca Fascione, Martin Hall, and Timo Aila. Pantaray: Fast ray-traced occlusion caching of massive scenes. ACM Trans. Graph., 29(4):37:1-37:10, 2010. Acceleration Data Structures for Ray Tracing 3 / 23 Ray tracing STAR Aims Results Summary Complexity 15min per frame Over 6 years to render a movie 4,000 Hewlett-Packard servers (35,000 processor cores) Ever increasing demand for Complex scenes Higher resolution (stereo) Sophisticated effects Acceleration Data Structures for Ray Tracing 4 / 23 Ray tracing STAR Aims Results Summary Computing the image Naive tracing number of rays × number of triangles #ray × #triangles ⇒ Quintillions OPs (unbearable) With acceleration data structure number of rays × log(number of triangles) #ray × log(#triangles) ⇒ Billions OPs Acceleration Data Structures for Ray Tracing 5 / 23 Ray tracing STAR Aims Results Summary Acceleration Data structures Acceleration Data Structures for Ray Tracing 6 / 23 Light buffer Ray tracing STAR Aims Results Summary Acceleration Data structures Light buffer Ray classification H-tree Tetrahedrons BSPHierarchical grid BIH Octree Grid Kd-tree BVH Kd-tree 2 1 3 BVH Grid Acceleration Data Structures for Ray Tracing 6 / 23 Ray tracing STAR Aims Results Summary Surface Area Heuristic Goldsmith and Salmon [GS87] Standard method Probability of intersecting a box Guides the division of triangles Greedy heuristic Acceleration Data Structures for Ray Tracing 7 / 23 Ray tracing STAR Aims Results Summary Research Faster traversal Faster build STAR [Wal07] Acceleration Data Structures for Ray Tracing 8 / 23 Ray tracing STAR Aims Results Summary Traversal Improving SAH cost Soupikov et al. [SSK08] Popov et al. [PGDS09] Stich et al. [SFD09] Acceleration Data Structures for Ray Tracing 9 / 23 Ray tracing STAR Aims Results Summary Build Asymptotical complexity Wald and Havran [WH06] Hunt and Mark [HMS06] Parallelization CPU Wald [Wal07] Choi et al. [CKL+ 10] Parallelization GPU Lauterbach et al. [LGS+ 09] Pantaleoni and Luebke [PL10] Acceleration Data Structures for Ray Tracing 10 / 23 Ray tracing STAR Aims Results Summary Aims Better acceleration data structures Higher traversal performance Realtime on commodity hardware Acceleration Data Structures for Ray Tracing 11 / 23 Ray tracing STAR Aims Results Summary Plan Journal paper in 2011 Conference paper in 2012 Framework for students Acceleration Data Structures for Ray Tracing 12 / 23 Ray tracing STAR Aims Results Summary Occlusion SAH SAH Acceleration Data Structures for Ray Tracing 13 / 23 Ray tracing STAR Aims Results Summary Occlusion SAH SAH OSAH Acceleration Data Structures for Ray Tracing 13 / 23 Ray tracing STAR Aims Results Summary Results Acceleration Data Structures for Ray Tracing 14 / 23 Ray tracing STAR Aims Results Summary Acquiring visibility Acceleration Data Structures for Ray Tracing 15 / 23 Ray tracing STAR Aims Results Summary Summary High quality images Costly to compute Optimizations Visibility Acceleration Data Structures for Ray Tracing 16 / 23 Ray tracing STAR Aims Results Summary Any question? Acceleration Data Structures for Ray Tracing 17 / 23 Ray tracing STAR Aims Results Summary Thank you! Acceleration Data Structures for Ray Tracing 18 / 23 References Byn Choi, Rakesh Komuravelli, Victor Lu, Hyojin Sung, Robert L. Bocchino, Sarita V. Adve, and John C. Hart. Parallel SAH k-D Tree Construction. In Michael Doggett, Samuli Laine, and Warren Hunt, editors, High-Performance Graphics 2010, pages 77–86, Saarbrücken, Germany, 2010. Eurographics Association. Jeffrey Goldsmith and John Salmon. Automatic Creation of Object Hierarchies for Ray Tracing. IEEE Computer Graphics and Applications, 7(5):14–20, May 1987. Acceleration Data Structures for Ray Tracing 19 / 23 References (cont.) W. Hunt, W.R. Mark, and G. Stoll. Fast kd-tree construction with an adaptive error-bounded heuristic. In Proceedings of the 2006 IEEE/Eurographics Symposium on Interactive Ray Tracing, pages 81–88, sep. 2006. C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha. Fast BVH Construction on GPUs. Computer Graphics Forum, 28(2):375–384, 2009. Jacopo Pantaleoni, Luca Fascione, Martin Hall, and Timo Aila. Pantaray: Fast ray-traced occlusion caching of massive scenes. ACM Trans. Graph., 29(4):37:1–37:10, 2010. Acceleration Data Structures for Ray Tracing 20 / 23 References (cont.) Stefan Popov, Iliyan Georgiev, Rossen Dimov, and Philipp Slusallek. Object Partitioning Considered Harmful: Space Subdivision for BVHs. In HPG ’09: Proceedings of the Conference on High Performance Graphics 2009, pages 15–22, New York, NY, USA, 2009. ACM. Jacopo Pantaleoni and David Luebke. HLBVH: Hierarchical LBVH Construction for Real-Time Ray Tracing of Dynamic Geometry. In Michael Doggett, Samuli Laine, and Warren Hunt, editors, High-Performance Graphics 2010, pages 87–95, Saarbrücken, Germany, 2010. Eurographics Association. Acceleration Data Structures for Ray Tracing 21 / 23 References (cont.) Martin Stich, Heiko Friedrich, and Andreas Dietrich. Spatial Splits in Bounding Volume Hierarchies. In HPG ’09: Proceedings of the Conference on High Performance Graphics 2009, pages 7–13, New York, NY, USA, 2009. ACM. A. Soupikov, M. Shevtsov, and A. Kapustin. Improving kd-tree quality at a reasonable construction cost. In Proceedings of the 2008 IEEE/Eurographics Symposium on Interactive Ray Tracing, pages 67–72, aug. 2008. Acceleration Data Structures for Ray Tracing 22 / 23 References (cont.) Ingo Wald. On fast Construction of SAH-based Bounding Volume Hierarchies. In Proceedings of the 2007 IEEE Symposium on Interactive Ray Tracing, pages 33–40, Washington, DC, USA, 2007. IEEE Computer Society. I. Wald and V. Havran. On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N). In Proceedings of the 2006 IEEE/Eurographics Symposium on Interactive Ray Tracing, pages 61–69, sep. 2006. Acceleration Data Structures for Ray Tracing 23 / 23