Multi-level ray tracing algorithm

ABSTRACT

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.

REFERENCES

• 1: John Amanatides, Ray tracing with cones, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.129-135, January 1984
• 2: Amanatides, J. and Woo, A. 1987. A fast voxel traversal algorithm for ray tracing. Eurographics Conference Proceedings 1987, 3--10.
• 3: James Arvo , David Kirk, Fast ray tracing by ray classification, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.55-64, July 1987
• 4: Ulf Assarsson , Tomas Möller, Optimized view frustum culling algorithms for bounding boxes, Journal of Graphics Tools, v.5 n.1, p.9-22, Sept. 2000
• 5: Ingo Wald , Carsten Benthin , Philipp Slusallek, Interactive global illumination in complex and highly occluded environments, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium
• 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.
• 7: Timothy A. Davis , Edward W. Davis, Exploiting frame coherence with the temporal depth buffer in a distributed computing environment, Proceedings of the 1999 IEEE symposium on Parallel visualization and graphics, p.29-38, October 25-26, 1999, San Francisco, California, United States [doi>10.1145/328712.319334]
• 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.
• 9: Genetti, J., Gordon, D., and Williams, G. 1998. Adaptive Supersampling in Object Space Using Pyramidal Rays. Computer Graphics Forum, 16(1), 29--54.
• 10: Ghazanfarpour, D. and Hasenfratz, J-M. 1998. A Beam Tracing with Precise Antialiasing for Polyhedral Scenes. Computer & Graphics, 22(1), 103--115.
• 11: Glassner, A. 1984. Space Subdivision for Fast Ray Tracing. IEEE Computer Graphics & Applications, 4(10), 15--22.
• 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.
• 13: Havran, V. and Bittner, J. 2000. LCTS: Ray Shooting using Longest Common Traversal Sequences, Computer Graphics Forum, 19(3), C59--C70.
• 14: Havran, V. 2000. Heuristic Ray Shooting Algorithms, Ph. D. Thesis, Czech Technical University.
• 15: Vlastimil Havran , Jiří Bittner , Hans-Peter Seidel, Exploiting temporal coherence in ray casted walkthroughs, Proceedings of the 19th spring conference on Computer graphics, April 24-26, 2003, Budmerice, Slovakia [doi>10.1145/984952.984977]
• 16: Paul S. Heckbert , Pat Hanrahan, Beam tracing polygonal objects, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.119-127, January 1984
• 17: Timothy L. Kay , James T. Kajiya, Ray tracing complex scenes, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.269-278, August 1986
• 18: David J. MacDonald , Kellogg S. Booth, Heuristics for ray tracing using space subdivision, The Visual Computer: International Journal of Computer Graphics, v.6 n.3, p.153-166, 1990 [doi>10.1007/BF01911006]
• 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.
• 20: Koji Nakamaru , Yoshio Ohno, Breadth-First Ray Tracing Utilizing Uniform Spatial Subdivision, IEEE Transactions on Visualization and Computer Graphics, v.3 n.4, p.316-328, October 1997 [doi>10.1109/2945.646235 ]
• 21: Masataka Ohta , Mamoru Maekawa, Ray-bound tracing for perfect and efficient anti-aliasing, The Visual Computer: International Journal of Computer Graphics, v.6 n.3, p.125-133, 1990 [doi>10.1007/BF01911004]
• 22: Mahesh Ramasubramanian , Sumanta N. Pattanaik , Donald P. Greenberg, A perceptually based physical error metric for realistic image synthesis, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.73-82, July 1999 [doi>10.1145/311535.311543]
• 23: Mikio Shinya , T. Takahashi , Seiichiro Naito, Principles and applications of pencil tracing, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.45-54, July 1987
• 24: László Szirmay-Kalos , Vlastimil Havran , Benedek Balázs , László Szécsi, On the efficiency of ray-shooting acceleration schemes, Proceedings of the 18th spring conference on Computer graphics, April 24-27, 2002, Budmerice, Slovakia [doi>10.1145/584458.584475]
• 25: S. Teller , J. Alex, Frustum Casting for Progressive, Interactive Rendering, Massachusetts Institute of Technology, Cambridge, MA, 1998
• 26: Ingo Wald , Thomas Kollig , Carsten Benthin , Alexander Keller , Philipp Slusallek, Interactive global illumination using fast ray tracing, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 27: Wald, I., 2004. Realtime Ray Tracing and Interactive Global Illumination, Ph. D. thesis, Saarland University.
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Keywords:
anti-aliasing, frustum occlusion culling, ray-tracing