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.
Supplemental Material
Available for Download
Supplemental movie and image files for, Naive ray-tracing: A divide-and-conquer approach
- Akenine-Möller, T. 2001. Fast 3D triangle-box overlap testing. J. graph. Tools 6, 1, 29--33. Google ScholarDigital Library
- Amanatides, J. 1984. Ray tracing with cones. In Proceedings of ACM SIGGRAPH, 129--135. Google ScholarDigital Library
- Bentley, J. L. Multidimensional binary search trees used for associative searching. 1975. Comm. ACM 18, 9, 509--517. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Eberly, D. 2000. Intersection of a line and a cone. http://www. geometrictools.com/Documentation/IntersectionLineCone.pdfGoogle Scholar
- 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. Google ScholarDigital Library
- Fujimoto, A., Tanaka, T. and Iwata, K. 1986. Arts: Accelerated ray-tracing system. IEEE Comput. Graph. Appl. 6, 4, 16--26. Google ScholarDigital Library
- Garanzha, K. and Loop, C. 2010. Fast ray sorting and breadth-first packet traversal for GPU ray tracing. In Proceedings of Eurographics. 289--298.Google Scholar
- Glassner A., S. 1984. Space subdivision for fast ray tracing. IEEE Comput. Graph. Appl. 4, 10, 15--22.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Hunt, W., and Mark, W. R. 2008b. Adaptive acceleration structures in perspective space. In Proceedings of the IEEE/EG Symposium on Raytracing. 11--17.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Kajiya, J. 1986. The rendering equation. In Proceedings of SIGGRAPH'86. 143--150. Google ScholarDigital Library
- Kay, T. and Kajiya, J. 1986. Ray Tracing complex scenes. In Proceedings of SIGGRAPH'86. 269--278. Google ScholarDigital Library
- Keller, A. 1997. Instant radiosity. In Proceedings of SIGGRAPH. 49--56. Google ScholarDigital Library
- Lagae, A. and Dutré, P. 2008. Compact, fast and robust grids for ray tracing. In Proceedings of the Eurographics Symposium on Rendering. 1235--1244. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Möller, T. and Trumbore, B. 1997. Fast, minimum storage ray-triangle intersection. J. Graph. Tools 2, 1, 21--28. Google ScholarDigital Library
- Nakamaru, K. and Ohno, Y. 1997. Breadth-First ray tracing utilizing uniform spatial subdivision. IEEE Trans. Vis. Comput. Graph. 3, 4, 316--328. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Reshetov, A., Soupikov, A. and Hurley, J. 2005. Multi-Level ray tracing algorithm. In Proceedings of ACM SIGGRAPH. 1176--1185. Google ScholarDigital Library
- Reshetov, A. 2006. Omnidirectional ray tracing traversal algorithm for kd-trees. In Proceedings of the IEEE/EG Symposium on Raytracing. 57--60.Google ScholarCross Ref
- Rubin S., Whitted, J. 1980. A 3-dimensional representation for fast rendering of complex scenes. In Proceedings of SIGGRAPH. 110--116. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Tsakok, J. A. 2008. Faster fast ray tracing techniques. Master thesis, Electrical and Computer Engineering. University of Waterloo.Google Scholar
- Tsakok, J. A. 2009. Faster incoherent rays: Multi-BVH ray stream tracing. In Proceedings of the Conference on High Performance Graphics. 151--158. Google ScholarDigital Library
- Wächter, C. and Keller, A. 2006. Instant ray tracing: The bounding interval hierarchy. In Proceedings of the Eurographics Symposium on Rendering. 139--149. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Wächter, C. and Keller, A. 2009. Efficient ray tracing without acceleration data structure. U.S. Patent Applications Publication No. US 2009/0225081 A1.Google Scholar
- Wald, I., Slusallek, P., Benthin, C. and Wagner, M. 2001. Interactive rendering with coherent ray tracing. In Proceedings of EUROGRAPHICS. 153--164.Google Scholar
- 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. Google ScholarDigital Library
- Wald, I., Boulos, S., and Shirley, P. 2006b. Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Trans. Graph. 26, 1, Article 6. Google ScholarDigital Library
- Wald, I. 2007. On fast construction of SAH based bounding volume hierarchies. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 485--493. Google ScholarDigital Library
- Whitted, T. 1980. An improved illumination model for shaded display. Comm. ACM 23, 6, 343--349. Google ScholarDigital Library
- Zhou, K., Hou, Q., Wang, R., Guo., B. 2008. Real-Time kd-tree construction on graphics hardware. ACM Trans. Graph. 27, 5, Article 126. Google ScholarDigital Library
Index Terms
- Naive ray-tracing: A divide-and-conquer approach
Recommendations
Ray tracing-based interactive diffuse indirect illumination
Despite great efforts in recent years to accelerate global illumination computation, the real-time ray tracing of fully dynamic scenes to support photorealistic indirect illumination effects has yet to be achieved in computer graphics. In this paper, we ...
Complex Luminaires: Illumination and Appearance Rendering
Simulating a complex luminaire such as a chandelier is expensive and slow, even using state-of-the-art algorithms. A more practical alternative is to use precomputation to accelerate rendering. Prior approaches cached information on an aperture surface ...
A ray tracing solution for diffuse interreflection
An efficient ray tracing method is presented for calculating interreflections between surfaces with both diffuse and specular components. A Monte Carlo technique computes the indirect contributions to illuminance at locations chosen by the rendering ...
Comments