Traversal fields for ray tracing dynamic scenes

ABSTRACT

This paper presents a novel scheme for accelerating ray traversal computation in ray tracing. By the scheme, a pre-computed stage is applied to constructing what is called a traversal field for each rigid object that records the destinations for all possible incoming rays. The field data, which could be efficiently compressed offline, is stored in a small number of big rectangles called ray-relays that enclose each approximate convex segment of an object. In the ray-tracing stage, the records on relays are retrieved in a constant time, so that a ray traversal is implemented as a simple texture lookup on GPU. Thus, the performance of our approach is only related to the number of relays rather than scene size, while the number of relays is quite small. In addition, because the traversal fields only depend on the internal construction of each convex segment, they can be used to ray trace objects undergoing rigid motions at a negligible extra cost. Experimental results show that interactive rates could be achieved for dynamic scenes with the effects of specular reflections and refractions on an ordinary desk PC with GPU.

REFERENCES

• 1: James Arvo , David Kirk, Fast ray tracing by ray classification, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.55-64, July 1987
• 2: Buss, S. R. Ray Trace software package, release 2.0.2. Available at http://math.ucsd.edu/~sbuss/MathCG.
• 3: Nathan A. Carr , Jesse D. Hall , John C. Hart, The ray engine, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 4: Nathan A. Carr , Jared Hoberock , Keenan Crane , John C. Hart, Fast GPU ray tracing of dynamic meshes using geometry images, Proceedings of the 2006 conference on Graphics interface, June 07-09, 2006, Quebec, Canada
• 5: Wei-Chao Chen , Jean-Yves Bouguet , Michael H. Chu , Radek Grzeszczuk, Light field mapping: efficient representation and hardware rendering of surface light fields, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 6: Christen, M. Ray Tracing on GPU. Diploma thesis, University of Applied Sciences Basel, Switzerland, 2005.Available at http://www.clockworkcoders.com/oglsl/rt.
• 7: Tim Foley , Jeremy Sugerman, KD-tree acceleration structures for a GPU raytracer, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 30-31, 2005, Los Angeles, California [doi>10.1145/1071866.1071869]
• 8: GLassner, A.S. Space Subdivision for fast ray tracing. IEEE Computer Graphics and Applications, 4, 10 (Oct. 1984), 15--22.
• 9: Andrew S. Glassner, An introduction to ray tracing, Academic Press Ltd., London, UK, 1989
• 10: Gosselin. ATI Octree open sources, ATI Research, Inc. 2003
• 11: Havran, V. 2001. Heuristic Ray Shooting Algorithm. PhD thesis, Faculty of Electrical Engineering, Czech Technical University in Prague.
• 12: Kalos, L.S., Aszódi, B, Lazányi, I., and Mátyás, P. Approximate ray-tracing on the GPU with distance impostors. Computer Graphics Forum, Proc. EUROGRAPHICS 2005, Vol. 24, No.3
• 13: Kirk, D., and Arvo, J. 1991. Improved ray tagging for voxel-based ray tracing. In Graphics Gems II, J. Arvo, Ed. Academic Press, 264--266.
• 14: Eric Lengyel, Mathematics for 3D game programming and computer graphics, Charles River Media, Inc., Rockland, MA, 2001
• 15: Tomas Möller , Ben Trumbore, Fast, minimum storage ray-triangle intersection, Journal of Graphics Tools, v.2 n.1, p.21-28, 1997
• 16: Page, D. L., Koschan, A. F., and Abidi, M. A., Perception-based 3D Triangle Mesh Segmentation Using Fast Marching Watersheds. Proc. IEEE International Conference on Computer Vision and Pattern Recognition, Madison, WI, USA, II (June.2003), 27--32.
• 17: Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 18: Alexander Reshetov , Alexei Soupikov , Jim Hurley, Multi-level ray tracing algorithm, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 19: Roshal, E. WinRAR, Compression Tool, available at http://www.winrar.de/eindex.html.
• 20: Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.61-70, July 1991
• 21: Wald, I., Slusallek. P., Benthin.C, and Wagner. M., Interactive Rendering with Coherent Ray Tracing, In Proc. EUROGRAPHICS 2001, Vol. 20, No. 3
• 22: Wald, I., and Slusallek, P. State of Art in Interactive RayTracing, EUROGRAPHICS 2001, (Feb.2001), 21--42
• 23: Wald, I., Purcell, T.J., Schmittler, J., Benthin, C., and Slusallek, P. Realtime Ray Tracing and its use for Interactive Global Illumination. State of the Art Reports EUROGRAPHICS 2003.
• 24: Wald, I. Realtime Ray Tracing and Interactive Global Illumination. PhD thesis, Computer Graphics Group, Saarland University, 2004. Available at http://www.mpisb.mpg.de/_wald/PhD/.
• 25: Ingo Wald , Thiago Ize , Andrew Kensler , Aaron Knoll , Steven G. Parker, Ray tracing animated scenes using coherent grid traversal, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 26: Wald, I., Boulos, S., and Shirley, P. Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies. Technical Report, SCI Institute, University of Utah, No UUSCI-2005-014. (conditionally accepted at ACM Transactions on Graphics), 2006

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
dynamic scene, graphics processing units (GPU), pre-computation, ray tracing