skip to main content
10.1145/1180495.1180510acmconferencesArticle/Chapter ViewAbstractPublication PagesvrstConference Proceedingsconference-collections
Article

Traversal fields for ray tracing dynamic scenes

Published: 01 November 2006 Publication History

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]
Arvo, J., and Kirk, D. Fast ray tracing by ray classification. Computer Graphics, 21, 4(July.1987), 55--64.
[2]
Buss, S. R. Ray Trace software package, release 2.0.2. Available at http://math.ucsd.edu/~sbuss/MathCG.
[3]
Carr, N. A., Hall, J. D., and Hart, J. C. The Ray Engine. In Proc. Graphics Hardware 2002, ACM Press, (Sep. 2002), 37--46.
[4]
Carr, N.A, Hoberock, J., Crane, K., and Hart, J. C. Fast GPU Ray Tracing of Dynamic Meshes using Geometry Images. In the Proceedings of Graphics Interface 2006.
[5]
Chen, W. C., Bouguet, J. Y., Chu, M. H., and Grzeszczuk, R. Light Field Mapping: Efficient Representation and Hardware Rendering of Surface Light Fields. ACM Transactions on Graphics, 21, 3 (July. 2002), 447--456.
[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]
Foley, T., and Sugerman, J. KD-Tree Acceleration Structures for a GPU Ray tracer. In Proc. Graphics Hardware 2005, 15--22.
[8]
GLassner, A.S. Space Subdivision for fast ray tracing. IEEE Computer Graphics and Applications, 4, 10 (Oct. 1984), 15--22.
[9]
Glassner, A.S. An Introduction to Ray Tracing. Morgan Kaufmann. ISBN 0-12286-60-4.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]
Lengyel, E. Mathematics for 3D Game Programming& Computer Graphics, Charles River Media, publisher of the Game Programming; Gems series. ISBN: 1584500379, 2002.
[15]
Möller. T. and Trumbore. B. Fast, Minimum Storage Ray-Triangle Intersection, Journal of Graphics Tools, 2(1):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]
Purcell, T.J., Buck, I., Mark, W.R., and Hanrahan, P. Ray tracing on programmable graphics hardware. ACM Transactions on Graphics, 21, 3(July.2002), 703--712.
[18]
Reshetov, A., Soupikov, A., and Hurley, J. Multi-level ray tracing algorithm. ACM Transactions on Graphics, 24, 3(July. 2005), 1176--1185.
[19]
Roshal, E. WinRAR, Compression Tool, available at http://www.winrar.de/eindex.html.
[20]
Teller, S. J., and Séquin, C.H. Visibility preprocessing for interactive walkthroughs. Proceedings of ACM SIGGRAPH'91, Computer Graphics, 25, 4(July. 1991), 61--69.
[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]
Wald, I., Lze, T., Kensler, A., Knoll, A., and Parker, S.G. Ray Tracing Animated Scenes using Coherent Grid Traversal. ACM Transactions on Graphics, Volume 25, Issue 3 (July 2006), Pages: 485--493.
[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

Cited By

View all
  • (2008)Real-Time Global Illumination for VR ApplicationsIEEE Computer Graphics and Applications10.1109/MCG.2008.12128:6(56-64)Online publication date: 1-Nov-2008
  • (2007)Real-time global illumination in the CAVEProceedings of the 2007 ACM symposium on Virtual reality software and technology10.1145/1315184.1315210(145-148)Online publication date: 5-Nov-2007

Index Terms

  1. Traversal fields for ray tracing dynamic scenes

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    VRST '06: Proceedings of the ACM symposium on Virtual reality software and technology
    November 2006
    400 pages
    ISBN:1595933212
    DOI:10.1145/1180495
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 November 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. dynamic scene
    2. graphics processing units (GPU)
    3. pre-computation
    4. ray tracing

    Qualifiers

    • Article

    Conference

    VRST06

    Acceptance Rates

    Overall Acceptance Rate 66 of 254 submissions, 26%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)3
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2008)Real-Time Global Illumination for VR ApplicationsIEEE Computer Graphics and Applications10.1109/MCG.2008.12128:6(56-64)Online publication date: 1-Nov-2008
    • (2007)Real-time global illumination in the CAVEProceedings of the 2007 ACM symposium on Virtual reality software and technology10.1145/1315184.1315210(145-148)Online publication date: 5-Nov-2007

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media