“Naïve Ray Tracing: A Divide-And-Conquer Approach” by Mora

  • ©Benjamin Mora

Conference:


Type:


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


ACM Digital Library Publication: