“Ray tracing animated scenes using coherent grid traversal” by Wald, Ize, Kensler, Knoll and Parker

We present a new approach to interactive ray tracing of moderate-sized animated scenes based on traversing frustum-bounded packets of coherent rays through uniform grids. By incrementally computing the overlap of the frustum with a slice of grid cells, we accelerate grid traversal by more than a factor of 10, and achieve ray tracing performance competitive with the fastest known packet-based kd-tree ray tracers. The ability to efficiently rebuild the grid on every frame enables this performance even for fully dynamic scenes that typically challenge interactive ray tracing systems.

1. Akenine-Möller, T. 2001. Fast 3D triangle-box overlap testing. J. Graph. Tools 6(1), 29–33.]] Google ScholarDigital Library
2. Amanatides, J., and Woo, A. 1987. A Fast Voxel Traversal Algorithm for Ray Tracing. In Eurographics ’87. Eurographics Association, 3–10.]]Google Scholar
3. Benthin, C., Wald, I., and Slusallek, P. 2003. A Scalable Approach to Interactive Global Illumination. Computer Graphics Forum 22 (3), 621–630. (Proceedings of Eurographics).]]Google ScholarCross Ref
4. Cazals, F., Drettakis, G., and Puech, C. 1995. Filtering, Clustering and Hierarchy Construction: a new solution for Ray Tracing very Complex Environments. In Proceedings of Eurographics ’95.]]Google Scholar
5. Cleary, J., Wyvill, B., Birtwistle, G., and Vatti, R. 1983. A Parallel Ray Tracing Computer. In Proceedings of the Association of Simula Users Conference, 77–80.]]Google Scholar
6. Dmitriev, K., Havran, V., and Seidel, H.-P. 2004. Faster Ray Tracing with SIMD Shaft Culling. Research Report MPI-I-2004-4-006, Max-Planck-Institut für Informatik, Saarbrücken, Germany.]]Google Scholar
7. Foley, T., and Sugerman, J. 2005. KD-tree acceleration structures for a GPU raytracer. In Proceedings of HWWS, 15–22.]] Google ScholarDigital Library
8. Fujimoto, A., Tanaka, T., and Iwata, K. 1986. ARTS: Accelerated ray tracing system. IEEE CG&A 6 (4), 16–26.]] Google ScholarDigital Library
9. Glassner, A. S. 1984. Space subdivision for fast ray tracing. IEEE CG&A 4 (10), 15–22.]]Google Scholar
10. Glassner, A. 1989. An Introduction to Ray Tracing. Morgan Kaufmann.]] Google ScholarDigital Library
11. Günther, J., Friedrich, H., Wald, I., Seidel, H.-P., and Slusallek, P. 2006. Ray tracing animated scenes using motion decomposition. In Proceedings of Eurographics 2006. (to appear).]]Google Scholar
12. Havran, V. 2001. Heuristic Ray Shooting Algorithms. PhD thesis, Faculty of Electrical Engineering, Czech Technical University in Prague.]]Google Scholar
13. Havran, V. 2002. Mailboxing, Yea or Nay? Ray Tracing News 15 (1).]]Google Scholar
14. Heckbert, P. S., and Hanrahan, P. 1984. Beam tracing polygonal objects. In Proceedings of SIGGRAPH, 119–127.]] Google ScholarDigital Library
15. Jevans, D., and Wyvill, B. 1989. Adaptive voxel subdivision for ray tracing. Proceedings of Graphics Interface ’89 (June), 164–172.]]Google Scholar
16. Kajiya, J. T. 1986. The Rendering Equation. In Computer Graphics (Proceedings of ACM SIGGRAPH), D. C. Evans and R. J. Athay, Eds., vol. 20, 143–150.]] Google ScholarDigital Library
17. Kirk, D., and Arvo, J. 1991. Improved ray tagging for voxel-based ray tracing. In Graphics Gems II, J. Arvo, Ed. Academic Press, 264–266.]]Google Scholar
18. Klimaszewski, K. S., and Sederberg, T. W. 1997. Faster ray tracing using adaptive grids. IEEE CG&A 17 (1) (Jan./Feb.), 42–51.]] Google ScholarDigital Library
19. Lauterbach, C., Yoon, S.-E., Tuft, D., and Manocha, D. 2006. RT-DEFORM: Interactive Ray Tracing of Dynamic Scenes using BVHs. Tech. Rep. 06-010, Department of Computer Science, University of North Carolina at Chapel Hill.]]Google Scholar
20. Lext, J., and Akenine-Möller, T. 2001. Towards rapid reconstruction for animated ray tracing. In Eurographics Short Presentations, 311–318.]]Google Scholar
21. Mahovsky, J. 2005. Ray Tracing with Reduced-Precision Bounding Volume Hierarchies. PhD thesis, University of Calgary.]] Google ScholarDigital Library
22. Minor, B., Fossum, G., and To, V. 2005. TRE: Cell broadband optimized real-time ray-caster. In Proceedings of GPSx.]]Google Scholar
23. Möller, T., and Trumbore, B. 1997. Fast, minimum storage ray triangle intersection. JGT2 (1), 21–28.]] Google ScholarDigital Library
24. Parker, S., Parker, M., Livnat, Y., Sloan, P.-P., Hansen, C., and Shirley, P. 1999. Interactive ray tracing for volume visualization. IEEE Trans. on Computer Graphics and Visualization 5 (3), 238–250.]] Google ScholarDigital Library
25. Parker, S. G., Martin, W., Sloan, P.-P. J., Shirley, P., Smits, B. E., and Hansen, C. D. 1999. Interactive ray tracing. In Proceedings of Interactive 3D Graphics, 119–126.]] Google ScholarDigital Library
26. Purcell, T., Buck, I., Mark, W., and Hanrahan, P. 2002. Ray tracing on programmable graphics hardware. In Proceedings of SIGGRAPH, 703–712.]] Google ScholarDigital Library
27. Reinhard, E., Smits, B., and Hansen, C. 2000. Dynamic acceleration structures for interactive ray tracing. In Proceedings of the Eurographics Workshop on Rendering, 299–306.]] Google ScholarDigital Library
28. Reshetov, A., Soupikov, A., and Hurley, J. 2005. Multi-level ray tracing algorithm. In Proceedings of SIGGRAPH, 1176–1185.]] Google ScholarDigital Library
29. Spackman, J., and Willis, P. 1991. The SMART navigation of a ray through an oct-tree. Computers and Graphics 15 (2), 185–194.]]Google ScholarCross Ref
30. Spackman, J. 1990. Scene Decompositions for Accelerated Ray Tracing. PhD thesis, The University of Bath, UK. Available as Bath Computer Science Technical Report 90/33.]] Google ScholarDigital Library
31. Stoll, G., Mark, W. R., Djeu, P., Wang, R., and Elhassan, I. 2006. Razor: An Architecture for Dynamic Multiresolution Ray Tracing. Tech. Rep. 06-21, University of Texas at Austin Dep. of Comp. Science.]]Google Scholar
32. Stoll, G. 2005. Part II: Achieving Real Time – Optimization Techniques. In SIGGRAPH 2005 Course on Interactive Ray Tracing, P. Slusallek, P. Shirley, I. Wald, G. Stoll, and B. Mark, Eds.]]Google Scholar
33. Wald, I., and Havran, V. 2006. On building good kd-trees for ray tracing, and on doing this in O(N log N). Tech. Rep. UUSCI-2006-009, SCI Institute, University of Utah.]]Google Scholar
34. Wald, I., Slusallek, P., Benthin, C., and Wagner, M. 2001. Interactive Rendering with Coherent Ray Tracing. Computer Graphics Forum 20(3), 153–164. (Proceedings of Eurographics).]]Google ScholarDigital Library
35. Wald, I., Benthin, C., and Slusallek, P. 2003. Distributed Interactive Ray Tracing of Dynamic Scenes. In Proceedings of the IEEE Symposium on Parallel and Large-Data Visualization and Graphics (PVG).]] Google ScholarDigital Library
36. Wald, I., Boulos, S., and Shirley, P. 2006. Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies. ACM Transactions on Graphics (conditionally accepted, to appear).]] Google ScholarDigital Library
37. Wald, I. 2004. Realtime Ray Tracing and Interactive Global Illumination. PhD thesis, Saarland University.]]Google Scholar
38. Woop, S., Schmittler, J., and Slusallek, P. 2005. RPU: A programmable ray processing unit for realtime ray tracing. In Proceedings of SIGGRAPH, 434–444.]] Google ScholarDigital Library