“Naïve Ray Tracing: A Divide-And-Conquer Approach” by Mora
Conference:
Type(s):
Title:
- Naïve Ray Tracing: A Divide-And-Conquer Approach
Presenter(s)/Author(s):
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:
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