“Multi-level ray tracing algorithm” by Reshetov, Soupikov and Hurley

  • ©Alexander Reshetov, Alexei Soupikov, and Jim Hurley




    Multi-level ray tracing algorithm



    We propose new approaches to ray tracing that greatly reduce the required number of operations while strictly preserving the geometrical correctness of the solution. A hierarchical “beam” structure serves as a proxy for a collection of rays. It is tested against a kd-tree representing the overall scene in order to discard from consideration the sub-set of the kd-tree (and hence the scene) that is guaranteed not to intersect with any possible ray inside the beam. This allows for all the rays inside the beam to start traversing the tree from some node deep inside thus eliminating unnecessary operations. The original beam can be further sub-divided, and we can either continue looking for new optimal entry points for the sub-beams, or we can decompose the beam into individual rays. This is a hierarchical process that can be adapted to the geometrical complexity of a particular view direction allowing for efficient geometric anti-aliasing. By amortizing the cost of partially traversing the tree for all the rays in a beam, up to an order of magnitude performance improvement can be achieved enabling interactivity for complex scenes on ordinary desktop machines.


    1. Amanatides, J. 1984. Ray Tracing with Cones, In Computer Graphics (Proceedings of ACM SIGGRAPH 84), 18, 4, ACM, 129–135. Google ScholarDigital Library
    2. Amanatides, J. and Woo, A. 1987. A fast voxel traversal algorithm for ray tracing. Eurographics Conference Proceedings 1987, 3–10.Google Scholar
    3. Arvo, J. and Kirk, D. 1987. Fast Ray Tracing by Ray Classification, In Computer Graphics (Proceedings of ACM SIGGRAPH 87), 21, 4, ACM, 55–64. Google ScholarDigital Library
    4. Assarsson, U. and Möller, T. 2000. Optimized View Frustum Culling Algorithms for Bounding Boxes. Journal of Graphics Tools, 5, 9–22. Google ScholarDigital Library
    5. Benthin, C., Wald, I., and Slusallek, P. 2003. A Scalable Approach to Interactive Global Illumination, Computer Graphics Forum (Proceedings of Eurographics 2003), 22(3), 621–630. Google ScholarDigital Library
    6. Cho, F. S. and Forsyth, D. 1999. Interactive ray tracing with the visibility complex. Computers and Graphics (Special Issue on Visibility – Techniques and Applications), 23(5), 703–717.Google Scholar
    7. Davis, T. and Davis, E. 1999. Exploiting frame coherence with the temporal depth buffer in a distributed computing environment, Proceedings of the 1999 IEEE symposium on Parallel visualization and graphics, 29–38. Google ScholarDigital Library
    8. Dmitriev, K., Havran, V., and Seidel, H.-P. 2004. Faster Ray Tracing with SIMD Shaft Culling, Research Report, Max-Planck Institut Für Informatik, MPI-1-2004-4-006.Google Scholar
    9. Genetti, J., Gordon, D., and Williams, G. 1998. Adaptive Supersampling in Object Space Using Pyramidal Rays. Computer Graphics Forum, 16(1), 29–54.Google ScholarCross Ref
    10. Ghazanfarpour, D. and Hasenfratz, J-M. 1998. A Beam Tracing with Precise Antialiasing for Polyhedral Scenes. Computer & Graphics, 22(1), 103–115.Google ScholarCross Ref
    11. Glassner, A. 1984. Space Subdivision for Fast Ray Tracing. IEEE Computer Graphics & Applications, 4(10), 15–22.Google ScholarCross Ref
    12. Gritz, L., Apodaca, T., Quaroni, G., Bredow, R., Goldman, D., Landis, H., and Pharr, M. 2002. RenderMan in Production. ACM SIGGRAPH 2002 Course Notes, Course 16.Google Scholar
    13. Havran, V. and Bittner, J. 2000. LCTS: Ray Shooting using Longest Common Traversal Sequences, Computer Graphics Forum, 19(3), C59–C70.Google ScholarCross Ref
    14. Havran, V. 2000. Heuristic Ray Shooting Algorithms, Ph. D. Thesis, Czech Technical University.Google Scholar
    15. Havran, V., Bittner, J., and Seidel, H.-P. 2003. Rendering: Exploiting temporal coherence in ray casted walkthroughs, Proceedings of the 19th Spring Conference on Computer Graphics (SCCG 2003), 149–155. Google ScholarDigital Library
    16. Heckbert, P. and Hanrahan, P. 1984. Beam tracing polygonal objects. In Computer Graphics (Proceedings of ACM SIGGRAPH 84), 18, 4, ACM, 119–127. Google ScholarDigital Library
    17. Kay, T. L. and Kajiya, J. T. 1986. Ray Tracing Complex Scenes, In Computer Graphics (Proceedings of ACM SIGGRAPH 86), 20, 4, 269–278. Google ScholarDigital Library
    18. Macdonald, J. and Booth, K. 1990. Heuristics for ray tracing using space subdivision. Visual Computer, 6, 153–166. Google ScholarDigital Library
    19. Martin, W., Reinhard, E., Shirley, P., Parker, S., and Thompson, W. 2002. Temporally Coherent Interactive Ray Tracing. Journal of Graphics Tools, 7(2), 41–48.Google ScholarCross Ref
    20. Nakamaru, K. and Ohno, Y. 1997. Breadth-First Ray Tracing Utilizing Uniform Spatial Subdivision, IEEE Transactions On Visualization and Computer Graphics, 3(4), 316–328. Google ScholarDigital Library
    21. Ohta, M. and Maekawa, M. 1990. Ray-bound tracing for perfect and efficient anti-aliasing. The Visual Computer: International Journal of Computer Graphic, 6(3), 125–133. Google ScholarDigital Library
    22. Ramasubramanian, M., Pattanaik, S., and Greenberg, D. 1999. A perceptually based physical error metric for realistic image synthesis. In Proceedings of ACM SIGGRAPH 1999, ACM Press ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, ACM, 73–82. Google ScholarDigital Library
    23. Shinya, M., Takahashi, T., and Naito, S. 1987. Principles and applications of pencil tracing. In Computer Graphics (Proceedings of ACM SIGGRAPH 87), 21, 4, ACM, 45–54. Google ScholarDigital Library
    24. Szirmay-Kalos, L., Havran, V., Balazs, B., and Szécsi, L. 2002. On the Efficiency of Ray-shooting Acceleration Schemes. Proceedings of the 18th Spring Conference on Computer Graphics (SCCG 2002), 89–98. Google ScholarDigital Library
    25. Teller, S. and Alex, J. 1998. Frustum Casting for Progressive, Interactive Rendering. Technical Report, Laboratory for Computer Science, Massachusetts Institute of Technology, TR-740. Google ScholarDigital Library
    26. Wald, I., Schmittler, J., Benthin, C., Slusallek, P., and Purcell, T. J. 2003. Realtime Ray Tracing and its use for Interactive Global Illumination, STAR, Computer Graphics Forum (Proceedings of Eurographics 2002), 22(3). Google ScholarDigital Library
    27. Wald, I., 2004. Realtime Ray Tracing and Interactive Global Illumination, Ph. D. thesis, Saarland University.Google Scholar
    28. Wald, I., Slusallek, P., Benthin, C., and Wagner, M. 2001. Interactive Rendering with Coherent Ray Tracing. Computer Graphics Forum (Proceedings of Eurographics 2001), 20(3), 153–164.Google Scholar

ACM Digital Library Publication:

Overview Page: