Efficient stack-less BVH traversal for ray tracing

ABSTRACT

We propose a new, completely iterative traversal algorithm for ray tracing bounding volume hierarchies that is based on storing a parent pointer with each node, and on using simple state logic to infer which node to traverse next. Though our traversal algorithm does re-visit internal nodes, it intersects each visited node only once, and in general performs exactly the same ray-box tests and ray-primitive intersection tests---and in exactly the same order---as a traditional stack-based variant. The proposed algorithm can be used for computer architectures that need to minimize the use of local memory for processing rays or those that need to minimize the data transport such as distributed multi-CPU architectures.

References

1. Aila, T., and Laine, S. 2009. Understanding the Efficiency of Ray Traversal on GPUs. In Proc. High-Performance Graphics 2009, 145--149.
2. Boulos, S., and Haines, E. 2006. Notes on Efficient Ray Tracing. Ray Tracing News 19.
3. Caustic Graphics, Inc. 2009. CausticRT platform. http://www.caustic.com/.
4. Foley, T., and Sugerman, J. 2005. KD-tree acceleration structures for a GPU raytracer. In Proceedings of Graphics Hardware, 15--22.
5. Gribble, C., and Ramani, K. 2008. Coherent ray tracing via stream filtering. In Interactive Ray Tracing, 2008. RT 2008. IEEE Symposium on, 59--66.
6. Havran, V., Bittner, J., and Žára, J. 1998. Ray Tracing with Rope Trees. In Proceedings of SCCG'98 (Spring Conference on Computer Graphics), 130--139.
7. Horn, D. R., Sugerman, J., Houston, M., and Hanrahan, P. 2007. Interactive k-d tree GPU raytracing. In SI3D, 167--174.
8. Hughes, D. M., and Lim, I. S. 2009. Kd-jump: a path-preserving stackless traversal for faster isosurface raytracing on gpus. IEEE Transactions on Visualization and Computer Graphics 15 (November), 1555--1562.
9. Kajiya, J. T. 1986. The rendering equation. In Computer Graphics, 143--150.
10. Kaplan, M. 1985. Space-Tracing: A Constant Time Ray-Tracer. In SIGGRAPH '85 State of the Art in Image Synthesis seminar notes, 149--158.
11. Karras, T., Aila, T., and Laine, S., 2009. Understanding the Efficiency of Ray Traversal on GPUs; Google Code. {online} http://code.google.com/p/understanding-the-efficiency-of-ray-traversal-on-gpus/.
12. Kato, T., and Saito, J. 2002. "kilauea": parallel global illumination renderer. In Proceedings of the Fourth Eurographics Workshop on Parallel Graphics and Visualization, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, EGPGV '02, 7--16.
13. Laine, S. 2010. Restart trail for stackless bvh traversal. In Proceedings of the Conference on High Performance Graphics, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, HPG '10, 107--111.
14. MacDonald, J. D., and Booth, K. S. 1990. Heuristics for Ray Tracing Using Space Subdivision. Visual Computer 6, 153--65.
15. Moon, B., Byun, Y., Kim, T.-J., Claudio, P., Kim, H.-S., Ban, Y.-J., Nam, S. W., and Yoon, S.-E. 2010. Cache-oblivious ray reordering. ACM Trans. Graph. 29, 3, 1--10.
16. Navratil, P. A., Fussell, D. S., Lin, C., and Mark, W. R. 2007. Dynamic ray scheduling to improve ray coherence and bandwidth utilization. In Proceedings of the 2007 IEEE Symposium on Interactive Ray Tracing, IEEE Computer Society, Washington, DC, USA, 95--104.
17. NVIDIA, C., 2007. Tesla technical brief. {online} http://www.nvidia.com/docs/IO/43395/tesla_technical_brief.pdf.
18. NVIDIA, C., 2009. Whitepaper nvidia, next generation cuda compute architecture: Fermi. {online} http://www.nvidia.com/content/PDF/fermi_white_papers/NVIDIA_Fermi_Compute_Architecture_Whitepaper.pdf.
19. NVIDIA, C., 2011. NVIDIA CUDA Compute Unified Device Architecture - Programming Guide, Jan. Version 3.2, {online} http://developer.nvidia.com/object/cuda_3_ 2_downloads.html.
20. Popov, S., Günther, J., Seidel, H.-P., and Slusallek, P. 2007. Stackless kd-tree traversal for high performance GPU ray tracing. Computer Graphics Forum 26, 3 (Sept.), 415--424. (Proceedings of Eurographics).
21. Ramani, K., Gribble, C. P., and Davis, A. 2009. Streamray: a stream filtering architecture for coherent ray tracing. SIGPLAN Not. 44 (March), 325--336.
22. Smits, B. 1998. Efficiency issues for ray tracing. J. Graph. Tools 3 (February), 1--14.
23. Torres, R., Martin, P. J., and Gavilanes, A. 2009. Ray Casting using a Roped BVH with CUDA. In 25th Spring Conference on Computer Graphics (SCCG 2009), 107--114.
24. Woop, S., Schmittler, J., and Slusallek, P. 2005. Rpu: a programmable ray processing unit for realtime ray tracing. In ACM SIGGRAPH 2005 Papers, ACM, New York, NY, USA, SIGGRAPH '05, 434--444.

Index Terms

• Computing methodologies

  • Computer graphics

    • Rendering

      • Ray tracing