Ingo Wald
Skip Abstract Section
Abstract
The most significant deficiency of most of today's interactive ray tracers is that they are restricted to static walkthroughs. This restriction is due to the static nature of the acceleration structures used. While the best reported frame rates for static geometric models have been achieved using carefully constructed kd-trees, this article shows that bounding volume hierarchies (BVHs) can be used to efficiently ray trace large static models.More importantly, the BVH can be used to ray trace deformable models (sets of triangles whose positions change over time) with little loss of performance. A variety of efficiency techniques are used to achieve this performance, but three algorithmic changes to the typical BVH algorithm are mainly responsible. First, the BVH is built using a variant of the surface area heuristic conventionally used to build kd-trees. Second, the topology of the BVH is not changed over time so that only the bounding volumes need to be refit from frame-to-frame. Third, and most importantly, packets of rays are traced together through the BVH using a novel integrated packet-frustum traversal scheme. This traversal scheme elegantly combines the advantages of both packet traversal and frustum traversal and allows for rapid hierarchy descent for packets that hit bounding volumes as well as rapid exits for packets that miss. A BVH-based ray tracing system using these techniques is shown to achieve performance for deformable models comparable to that previously available only for static models.
- Adams, B., Keiser, R., Pauly, M., Guibas, L. J., Gross, M., and Dutré, P. 2005.Efficient raytracing of deforming point-sampled surfaces. Comput. Graph. For. 24, 3 (Sept.), 677--684.Google Scholar
- Adelson, S. J. and Hodges, L. F. 1995. Generating exact ray-traced animation frames by reprojection. IEEE Comput. Graph. Appl. 15, 3, 43--52. Google ScholarDigital Library
- Appel, A. 1968. Some techniques for shading machine renderings of solids. In Proceedings of the Spring Joint Computer Conference (SJCC). 27--45.Google ScholarDigital Library
- Arvo, J. and Kirk, D. 1989. A survey of ray tracing acceleration techniques. In An Introduction to Ray Tracing, A. S. Glassner, Ed. Academic Press, San Diego, CA. Google ScholarDigital Library
- Benthin, C., Wald, I., Scherbaum, M., and Friedrich, H. 2006. Ray tracing on the CELL processor. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 15--23.Google Scholar
- Bentley, J. L. 1975. Multidimensional binary search trees used for associative searching. Comm. ACM 18, 9, 509--517. Google ScholarDigital Library
- Boulos, S., Edwards, D., Lacewell, J. D., Kniss, J., Kautz, J., Shirley, P., and Wald, I. 2006. Interactive distribution ray tracing. Tech. rep. UUSCI-2006-022, SCI Institute, University of Utah.Google Scholar
- Carr, N., Hoberock, J., Craneh, K., and Hart, J. 2006. Fast GPU ray tracing of dynamic meshes using geometry images. In Proceedings of Graphics Interface. Submitted for publication. Google ScholarDigital Library
- Clark, J. H. 1976. Hierarchical geometric models for visible surface algorithms. Commun. ACM 19, 10, 547--554. Google ScholarDigital Library
- Cleary, J., Wyvill, B., Birtwistle, G., and Vatti, R. 1983. A parallel ray tracing computer. In Proceedings of the Association of Simula Users Conference. 77--80.Google Scholar
- Dmitriev, K., Havran, V., and Seidel, H.-P. 2004. Faster ray tracing with SIMD shaft culling. Research rep. MPI-I-2004-4-006, Max-Planck-Institut für Informatik, Saarbrücken, Germany.Google Scholar
- Foley, T. and Sugerman, J. 2005. KD-tree acceleration structures for a GPU raytracer. In Proceedings of the ACM SIGGRAPH/Eurographics Workshop on Graphics Hardware (HWWS). 15--22. Google ScholarDigital Library
- Genetti, J., Gordon, D., and Williams, G. 1998. Adaptive supersampling in object space using pyramidal rays. Comput. Graph. For. 17, 29--54.Google Scholar
- Glassner, A. 1988. Spacetime ray tracing for animation. IEEE Comput. Graph. Appl. 8, 2, 60--70. Google ScholarDigital Library
- Glassner, A. S. 1984. Space subdivision for fast ray tracing. IEEE Comput. Graph. Appl. 4, 10, 15--22.Google ScholarCross Ref
- Goldsmith, J. and Salmon, J. 1987. Automatic creation of object hierarchies for ray tracing. IEEE Comput. Graph. Appl. 7, 5, 14--20. Google ScholarDigital Library
- Gröller, E. and Purgathofer, W. 1991. Using temporal and spatial coherence for accelerating the calculation of animation sequences. In Proceedings of Eurographics. 103--113.Google Scholar
- Günther, J., Friedrich, H., Wald, I., Seidel, H.-P., and Slusallek, P. 2006. Ray tracing animated scenes using motion decomposition. In Proceedings of Eurographics. 517--525. To appear.Google Scholar
- Guttman, A. 1984. R-trees: A dynamic index structure for spatial searching. In Proceedings of SIGMOD. 47--57. Google ScholarDigital Library
- Haines, E. 1987. A proposal for standard graphics environments. IEEE Transactions on Comput. Graph. Appl. 7, 11, 3--5.Google ScholarDigital Library
- Haines, E. 1991. Efficiency improvements for hierarchy traversal in ray tracing. In Graphics Gems II, J. Arvo, Ed., Academic Press, 267--272.Google Scholar
- Havran, V. 2001. Heuristic ray shooting algorithms. Ph.D. thesis, Faculty of Electrical Engineering, Czech Technical University in Prague.Google Scholar
- Hurley, J. T., Kapustin, A., Reshetov, A., and Soupikov, A. 2002. Fast ray tracing for modern general purpose CPU. In Proceedings of GraphiCon.Google Scholar
- Jansen, F. 1986. Data structures for ray tracing,. In Proceedings of the Workshop in Data Structures for Raster Graphics. 57--73. Google ScholarDigital Library
- Kaplan, M. 1985. The uses of spatial coherence in ray tracing. In ACM SIGGRAPH Course Notes 11.Google Scholar
- Kay, T. and Kajiya, J. 1986. Ray tracing complex scenes. In Proceedings of SIGGRAPH. 269--278. Google ScholarDigital Library
- Kirk, D. and Arvo, J. 1988. The ray tracing kernel. In Proceedings of AUSGRAPH. 75--82.Google Scholar
- Larsson, T. and Akenine-Möller, T. 2003. Strategies for bounding volume hierarchy updates for ray tracing of deformable models. Tech. rep. MDH-MRTC-92/2003-1-SE, Feb., MRTC.Google Scholar
- Larsson, T. and Akenine-Möller, T. 2005. A dynamic bounding volume hierarchy for generalized collision detection. Workshop on Virtual Reality Interaction and Physical Simulation. 91--100.Google Scholar
- Lauterbach, C., Yoon, S.-E., Tuft, D., and Manocha, D. 2006. RT-DEFORM: Interactive ray tracing of dynamic scenes using BVHs. In Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing. 39--45.Google Scholar
- Lext, J. and Akenine-Möller, T. 2001. Towards rapid reconstruction for animated ray tracing. In Proceedings of Eurographics Short Presentations. 311--318.Google Scholar
- Lext, J., Assarsson, U., and Möller, T. 2000. BART: A benchmark for animated ray tracing. Tech. rep., Department of Computer Engineering, Chalmers University of Technology, Göteborg, Sweden. May.Google Scholar
- MacDonald, J. D. and Booth, K. S. 1989. Heuristics for ray tracing using space subdivision. In Proceedings of Graphics Interface. 152--163.Google Scholar
- Mahovsky, J. 2005. Ray Tracing with reduced-precision bounding volume hierarchies. Ph.D. thesis, University of Calgary. Google ScholarDigital Library
- Mahovsky, J. and Wyvill, B. 2004. Fast ray-axis aligned bounding box overlap tests with Plücker coordinates. J. Graph. Tools 9, 1, 35--46.Google ScholarCross Ref
- Mark, W. and Fussell, D. 2005. Real-time rendering systems in 2010. Tech. rep. 05-18, (May.) Computer Science, University of Texas.Google Scholar
- Minor, B., Fossum, G., and To, V. 2005. TRE : Cell broadband optimized real-time ray-caster. In Proceedings of GPSx.Google Scholar
- Möller, T. and Trumbore, B. 1997. Fast, minimum storage ray triangle intersection. J. Graph. Tools 2, 1, 21--28. Google ScholarDigital Library
- Müller, G. and Fellner, D. 1999. Hybrid scene structuring with application to ray tracing. In Proceedings of International Conference on Visual Computing. 19--26.Google Scholar
- Muuss, M. 1995. Towards real-time ray-tracing of combinatorial solid geometric models. In Proceedings of BRL-CAD Symposium.Google Scholar
- Ng, K. and Trifonov, B. 2003. Automatic bounding volume hierarchy generation using stochastic search methods. in Mini-Workshop on Stochastic Search Algorithms.Google Scholar
- Parker, S. 2002. Interactive ray tracing on a supercomputer. In A. Chalmers and E. Reinhard, Eds. In Practical Parallel Rendering. Google ScholarDigital Library
- Parker, S. G., Martin, W., Sloan, P.-P. J., Shirley, P., Smits, B. E., and Hansen, C. D. 1999. Interactive ray tracing. In Proceedings of Interactive 3D Graphics. 119--126. Google ScholarDigital Library
- Purcell, T., Buck, I., Mark, W., and Hanrahan, P. 2002. Ray tracing on programmable graphics hardware. ACM Transactions on Graphics 21, 3, 703--712. (Proceedings of ACM SIGGRAPH). Google ScholarDigital Library
- Reinhard, E., Smits, B., and Hansen, C. 2000. Dynamic acceleration structures for interactive ray tracing. In Proceedings of the Eurographics Workshop on Rendering. Brno, Czech Republic, 299--306. Google ScholarDigital Library
- Reshetov, A., Soupikov, A., and Hurley, J. 2005. Multi-level ray tracing algorithm. ACM Transaction on Graphics 24, 3, 1176--1185. (Proceedings of ACM SIGGRAPH 2005). Google ScholarDigital Library
- Rubin, S. and Whitted, T. 1980. A 3D representation for fast rendering of complex scenes. In Proceedings of SIGGRAPH. 110--116. Google ScholarDigital Library
- Santalo, L. 2002. Integral Geometry and Geometric Probability. Cambridge University Press. Cambridge, UK.Google Scholar
- Schmidl, H., Walker, N., and Lin, M. 2004. CAB: Fast update of OBB trees for collision detection between articulated bodies. J. Graph. Tools 9, 2, 1--9.Google ScholarCross Ref
- Schmittler, J., Wald, I., and Slusallek, P. 2002. SaarCOR---A hardware architecture for ray tracing. In Proceedings of the ACM SIGGRAPH/Eurographics Conference on Graphics Hardware. 27--36. Google ScholarDigital Library
- Smits, B. 1998. Efficiency issues for ray tracing. J. Graph. Tools 3, 2, 1--14. Google ScholarDigital Library
- Stoll, G., Mark, W. R., Djeu, P., Wang, R., and Elhassan, I. 2006. Razor: An architecture for dynamic multiresolution ray tracing. Tech. rep. 06-21, Department of Computer Science, University of Texas at Austin.Google Scholar
- van den Bergen, G. 1997. Efficient collision detection of complex deformable models using AABB trees. J. Graph. Tools 2, 4, 1--14. Google ScholarDigital Library
- van der Zwaan, M., Reinhard, E., and Jansen, F. 1995. Pyramid clipping for efficient ray traversal. In Rendering Techniques, Proceedings of the Eurographics Workshop on Rendering. 1--10.Google Scholar
- Wald, I. 2004. Realtime ray tracing and interactive global illumination. Ph.D. thesis, Saarland University.Google Scholar
- Wald, I., Benthin, C., and Slusallek, P. 2003. Distributed interactive ray tracing of dynamic scenes. In Proceedings of the IEEE Symposium on Parallel and Large-Data Visualization and Graphics. 11--20. Google ScholarDigital Library
- Wald, I. and Havran, V. 2006. On building fast kd-trees for ray tracing, and on doing that in O(N log N). In Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing. 61--70.Google Scholar
- Wald, I., Ize, T., Kensler, A., Knoll, A., and Parker, S. G. 2006. Ray tracing animated scenes using coherent grid traversal. ACM Trans. Graph. 25, 3, 485--493. Google ScholarDigital Library
- Wald, I., Slusallek, P., Benthin, C., and Wagner, M. 2001. Interactive rendering with coherent ray tracing. Compu. Graph. For. 20, 3, 153--164.Google Scholar
- Weghorst, H., Hooper, G., and Greenberg, D. 1984. Improved computational methods for ray tracing. ACM Trans. Graph. 3, 1, 52--69. Google ScholarDigital Library
- Whitted, T. 1980. An improved illumination model for shaded display. Comm. ACM Trans. 23, 6, 343--349. Google ScholarDigital Library
- Williams, A., Barrus, S., Morley, R. K., and Shirley, P. 2005. An efficient and robust ray-box intersection algorithm. J. Graph. Tools 10, 1, 49--54.Google ScholarCross Ref
- Woop, S., Schmittler, J., and Slusallek, P. 2005. RPU: A programmable ray processing unit for realtime ray tracing. ACM Transactions on Graphics 24, 3, 434--444. (Proceedings of SIGGRAPH). Google ScholarDigital Library
Index Terms
- Ray tracing deformable scenes using dynamic bounding volume hierarchies
Recommendations
Whitted ray-tracing for dynamic scenes using a ray-space hierarchy on the GPU
EGSR'07: Proceedings of the 18th Eurographics conference on Rendering TechniquesIn this paper, we present a new algorithm for interactive rendering of animated scenes with Whitted Ray-Tracing, running on the GPU. We focus our attention on the secondary rays (the rays generated by one or more bounces on specular objects), and use ...
Ray tracing dynamic scenes with shadows on GPU
EG PGV'10: Proceedings of the 10th Eurographics conference on Parallel Graphics and VisualizationWe present fast ray tracing of dynamic scenes in this paper with primary and shadow rays. We present a GPUfriendly strategy to bring coherency to shadow rays, based on previous work on grids as acceleration structures. We introduce indirect mapping of ...
Traversal fields for ray tracing dynamic scenes
VRST '06: Proceedings of the ACM symposium on Virtual reality software and technologyThis 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 ...
Comments