Naive ray-tracing: A divide-and-conquer approach

Abstract

We present an efficient ray-tracing algorithm which, for the first time, does not store any data structures when performing spatial subdivisions, and directly computes intersections inside the scene. This new algorithm is often faster than comparable ray-tracing methods at rendering dynamic scenes, and has a similar level of performance when compared to static ray-tracers. Memory management is made minimal and deterministic, which simplifies ray-tracing engineering, as spatial subdivision data structures are no longer considered in the graphics pipeline. This is possible with a modification of Whitted's naive ray-tracing algorithm by using a divide-and-conquer approach, and by having a sufficient collection of rays in order to reduce the complexity of naive ray-tracing. In particular, the algorithm excels at spontaneously solving large Ray/Primitive intersection problems.

References

1. Akenine-Möller, T. 2001. Fast 3D triangle-box overlap testing. J. graph. Tools 6, 1, 29--33.
2. Amanatides, J. 1984. Ray tracing with cones. In Proceedings of ACM SIGGRAPH, 129--135.
3. Bentley, J. L. Multidimensional binary search trees used for associative searching. 1975. Comm. ACM 18, 9, 509--517.
4. Cleary, J. G. and Wyvill, G. 1988. Analysis of an algorithm for fast ray tracing using uniform space subdivision. Vis. Comput. 4, 2, 65--83.
5. Eberly, D. 2000. Intersection of a line and a cone. http://www. geometrictools.com/Documentation/IntersectionLineCone.pdf
6. Fuchs, H., Kedem, Z. M., and Naylor B. F. 1980. On visible surface generation by a priori tree structures. In Proceedings of SIGGRAPH. 124--133.
7. Fujimoto, A., Tanaka, T. and Iwata, K. 1986. Arts: Accelerated ray-tracing system. IEEE Comput. Graph. Appl. 6, 4, 16--26.
8. Garanzha, K. and Loop, C. 2010. Fast ray sorting and breadth-first packet traversal for GPU ray tracing. In Proceedings of Eurographics. 289--298.
9. Glassner A., S. 1984. Space subdivision for fast ray tracing. IEEE Comput. Graph. Appl. 4, 10, 15--22.
10. Gribble, C. P. and Ramani, K. 2008. Coherent ray tracing via stream filtering. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 59--66.
11. Havran., V., Herzog, R., and Seidel H.-P. 2006. On the fast construction of spatial hierarchies for ray tracing. In Proceedings of the IEEE Symposium on Raytracing. 71--80.
12. Hunt, W., Mark, W. R. and Stoll, G. 2006. Fast kd-tree construction with an adaptive error-bounded heuristic. In Proceedings of the IEEE Symposium on Raytracing. 81--88.
13. Hunt, W., and Mark, W. R. 2008a. Ray-Specialized acceleration structures for ray tracing. In Proceedings of the IEEE/EG Symposium on Raytracing. 3--10.
14. Hunt, W., and Mark, W. R. 2008b. Adaptive acceleration structures in perspective space. In Proceedings of the IEEE/EG Symposium on Raytracing. 11--17.
15. Ize, T., Shirley, P. and Parker, S. G. 2007. Grid creation strategies for efficient ray tracing. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 27--32.
16. Jensen, H. W., Marschner, S. R., Levoy, M., and Hanrahan, P. 2001. A practical model for subsurface light transport. In Proceedings of ACM SIGGRAPH. 501--518.
17. Kajiya, J. 1986. The rendering equation. In Proceedings of SIGGRAPH'86. 143--150.
18. Kay, T. and Kajiya, J. 1986. Ray Tracing complex scenes. In Proceedings of SIGGRAPH'86. 269--278.
19. Keller, A. 1997. Instant radiosity. In Proceedings of SIGGRAPH. 49--56.
20. Lagae, A. and Dutré, P. 2008. Compact, fast and robust grids for ray tracing. In Proceedings of the Eurographics Symposium on Rendering. 1235--1244.
21. Lauterbach, C., Yoon, S. and Manocha, D. 2006. RT-DEFORM: Interactive ray tracing of dynamic scenes using BVHs. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 39--45.
22. McGuire, M. and Luebke, D. 2009. Hardware-Accelerated global illumination by image space photon mapping. In Proceedings of the Conference on High Performance Graphics. 77--89.
23. Möller, T. and Trumbore, B. 1997. Fast, minimum storage ray-triangle intersection. J. Graph. Tools 2, 1, 21--28.
24. Nakamaru, K. and Ohno, Y. 1997. Breadth-First ray tracing utilizing uniform spatial subdivision. IEEE Trans. Vis. Comput. Graph. 3, 4, 316--328.
25. Overbeck, R., Ramamoorthi, R. and Mark, W. R. 2007. A real-time beam tracer with application to exact soft shadows. In Proceedings of the Eurographics Symposium on Rendering. 85--98.
26. Roger, D., Assarson, U., Holzschuch, N. 2007. Whitted ray-tracing using a ray-space hierarchy on the GPU. Multi-level ray tracing algorithm. In Proceedings of the Eurographics Symposium on Rendering.
27. Reshetov, A., Soupikov, A. and Hurley, J. 2005. Multi-Level ray tracing algorithm. In Proceedings of ACM SIGGRAPH. 1176--1185.
28. Reshetov, A. 2006. Omnidirectional ray tracing traversal algorithm for kd-trees. In Proceedings of the IEEE/EG Symposium on Raytracing. 57--60.
29. Rubin S., Whitted, J. 1980. A 3-dimensional representation for fast rendering of complex scenes. In Proceedings of SIGGRAPH. 110--116.
30. Schmittler, J., Woop, S., Wagner, D., Paul, W. J., and Slusallek, P. 2004. Realtime ray tracing of dynamic scenes on an FPGA chip. In Proceedings of the Graphics Hardware. 95--106.
31. Shevtsov, M., Soupikov, A. and Kapustin, A. 2007. Highly parallel fast KD-tree construction for interactive ray tracing of dynamic scenes. In Proceedings of Eurographics. 395--404.
32. Tsakok, J. A. 2008. Faster fast ray tracing techniques. Master thesis, Electrical and Computer Engineering. University of Waterloo.
33. Tsakok, J. A. 2009. Faster incoherent rays: Multi-BVH ray stream tracing. In Proceedings of the Conference on High Performance Graphics. 151--158.
34. Wächter, C. and Keller, A. 2006. Instant ray tracing: The bounding interval hierarchy. In Proceedings of the Eurographics Symposium on Rendering. 139--149.
35. Wächter, C. and Keller, A. 2007. Terminating spatial hierarchies by a priori bounding memory. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 41--46.
36. Wächter, C. and Keller, A. 2009. Efficient ray tracing without acceleration data structure. U.S. Patent Applications Publication No. US 2009/0225081 A1.
37. Wald, I., Slusallek, P., Benthin, C. and Wagner, M. 2001. Interactive rendering with coherent ray tracing. In Proceedings of EUROGRAPHICS. 153--164.
38. Wald, I., Ize, T., Kensler, A., Knoll, A., and Parker, S. G. 2006a. Ray tracing animated scenes using coherent grid traversal. In Proceedings of ACM SIGGRAPH. 485--493.
39. Wald, I., Boulos, S., and Shirley, P. 2006b. Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Trans. Graph. 26, 1, Article 6.
40. Wald, I. 2007. On fast construction of SAH based bounding volume hierarchies. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 485--493.
41. Whitted, T. 1980. An improved illumination model for shaded display. Comm. ACM 23, 6, 343--349.
42. Zhou, K., Hou, Q., Wang, R., Guo., B. 2008. Real-Time kd-tree construction on graphics hardware. ACM Trans. Graph. 27, 5, Article 126.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation