More Web Proxy on the site http://driver.im/

research-article

Naive ray-tracing: A divide-and-conquer approach

Author:

Benjamin MoraAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 30, Issue 5

Article No.: 117, Pages 1 - 12

https://doi.org/10.1145/2019627.2019636

Published: 22 October 2011 Publication History

Abstract

We present an efficient ray-tracing algorithm which, for the first time, does not store any data structures when performing spatial subdivisions, and directly computes intersections inside the scene. This new algorithm is often faster than comparable ray-tracing methods at rendering dynamic scenes, and has a similar level of performance when compared to static ray-tracers. Memory management is made minimal and deterministic, which simplifies ray-tracing engineering, as spatial subdivision data structures are no longer considered in the graphics pipeline. This is possible with a modification of Whitted's naive ray-tracing algorithm by using a divide-and-conquer approach, and by having a sufficient collection of rays in order to reduce the complexity of naive ray-tracing. In particular, the algorithm excels at spontaneously solving large Ray/Primitive intersection problems.

Supplementary Material

JPG File (tp147_12.jpg)

Download
22.14 KB

mora (mora.zip)

Supplemental movie and image files for, Naive ray-tracing: A divide-and-conquer approach

Download
16.13 MB

MP4 File (tp147_12.mp4)

Download
15.83 MB

References

[1]

Akenine-Möller, T. 2001. Fast 3D triangle-box overlap testing. J. graph. Tools 6, 1, 29--33.

Digital Library

[2]

Amanatides, J. 1984. Ray tracing with cones. In Proceedings of ACM SIGGRAPH, 129--135.

Digital Library

[3]

Bentley, J. L. Multidimensional binary search trees used for associative searching. 1975. Comm. ACM 18, 9, 509--517.

Digital Library

[4]

Cleary, J. G. and Wyvill, G. 1988. Analysis of an algorithm for fast ray tracing using uniform space subdivision. Vis. Comput. 4, 2, 65--83.

[5]

Eberly, D. 2000. Intersection of a line and a cone. http://www. geometrictools.com/Documentation/IntersectionLineCone.pdf

[6]

Fuchs, H., Kedem, Z. M., and Naylor B. F. 1980. On visible surface generation by a priori tree structures. In Proceedings of SIGGRAPH. 124--133.

Digital Library

[7]

Fujimoto, A., Tanaka, T. and Iwata, K. 1986. Arts: Accelerated ray-tracing system. IEEE Comput. Graph. Appl. 6, 4, 16--26.

Digital Library

[8]

Garanzha, K. and Loop, C. 2010. Fast ray sorting and breadth-first packet traversal for GPU ray tracing. In Proceedings of Eurographics. 289--298.

[9]

Glassner A., S. 1984. Space subdivision for fast ray tracing. IEEE Comput. Graph. Appl. 4, 10, 15--22.

[10]

Gribble, C. P. and Ramani, K. 2008. Coherent ray tracing via stream filtering. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 59--66.

[11]

Havran., V., Herzog, R., and Seidel H.-P. 2006. On the fast construction of spatial hierarchies for ray tracing. In Proceedings of the IEEE Symposium on Raytracing. 71--80.

[12]

Hunt, W., Mark, W. R. and Stoll, G. 2006. Fast kd-tree construction with an adaptive error-bounded heuristic. In Proceedings of the IEEE Symposium on Raytracing. 81--88.

[13]

Hunt, W., and Mark, W. R. 2008a. Ray-Specialized acceleration structures for ray tracing. In Proceedings of the IEEE/EG Symposium on Raytracing. 3--10.

[14]

Hunt, W., and Mark, W. R. 2008b. Adaptive acceleration structures in perspective space. In Proceedings of the IEEE/EG Symposium on Raytracing. 11--17.

[15]

Ize, T., Shirley, P. and Parker, S. G. 2007. Grid creation strategies for efficient ray tracing. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 27--32.

Digital Library

[16]

Jensen, H. W., Marschner, S. R., Levoy, M., and Hanrahan, P. 2001. A practical model for subsurface light transport. In Proceedings of ACM SIGGRAPH. 501--518.

Digital Library

[17]

Kajiya, J. 1986. The rendering equation. In Proceedings of SIGGRAPH'86. 143--150.

Digital Library

[18]

Kay, T. and Kajiya, J. 1986. Ray Tracing complex scenes. In Proceedings of SIGGRAPH'86. 269--278.

Digital Library

[19]

Keller, A. 1997. Instant radiosity. In Proceedings of SIGGRAPH. 49--56.

Digital Library

[20]

Lagae, A. and Dutré, P. 2008. Compact, fast and robust grids for ray tracing. In Proceedings of the Eurographics Symposium on Rendering. 1235--1244.

Digital Library

[21]

Lauterbach, C., Yoon, S. and Manocha, D. 2006. RT-DEFORM: Interactive ray tracing of dynamic scenes using BVHs. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 39--45.

[22]

McGuire, M. and Luebke, D. 2009. Hardware-Accelerated global illumination by image space photon mapping. In Proceedings of the Conference on High Performance Graphics. 77--89.

Digital Library

[23]

Möller, T. and Trumbore, B. 1997. Fast, minimum storage ray-triangle intersection. J. Graph. Tools 2, 1, 21--28.

Digital Library

[24]

Nakamaru, K. and Ohno, Y. 1997. Breadth-First ray tracing utilizing uniform spatial subdivision. IEEE Trans. Vis. Comput. Graph. 3, 4, 316--328.

Digital Library

[25]

Overbeck, R., Ramamoorthi, R. and Mark, W. R. 2007. A real-time beam tracer with application to exact soft shadows. In Proceedings of the Eurographics Symposium on Rendering. 85--98.

Digital Library

[26]

Roger, D., Assarson, U., Holzschuch, N. 2007. Whitted ray-tracing using a ray-space hierarchy on the GPU. Multi-level ray tracing algorithm. In Proceedings of the Eurographics Symposium on Rendering.

Digital Library

[27]

Reshetov, A., Soupikov, A. and Hurley, J. 2005. Multi-Level ray tracing algorithm. In Proceedings of ACM SIGGRAPH. 1176--1185.

Digital Library

[28]

Reshetov, A. 2006. Omnidirectional ray tracing traversal algorithm for kd-trees. In Proceedings of the IEEE/EG Symposium on Raytracing. 57--60.

[29]

Rubin S., Whitted, J. 1980. A 3-dimensional representation for fast rendering of complex scenes. In Proceedings of SIGGRAPH. 110--116.

Digital Library

[30]

Schmittler, J., Woop, S., Wagner, D., Paul, W. J., and Slusallek, P. 2004. Realtime ray tracing of dynamic scenes on an FPGA chip. In Proceedings of the Graphics Hardware. 95--106.

Digital Library

[31]

Shevtsov, M., Soupikov, A. and Kapustin, A. 2007. Highly parallel fast KD-tree construction for interactive ray tracing of dynamic scenes. In Proceedings of Eurographics. 395--404.

[32]

Tsakok, J. A. 2008. Faster fast ray tracing techniques. Master thesis, Electrical and Computer Engineering. University of Waterloo.

[33]

Tsakok, J. A. 2009. Faster incoherent rays: Multi-BVH ray stream tracing. In Proceedings of the Conference on High Performance Graphics. 151--158.

Digital Library

[34]

Wächter, C. and Keller, A. 2006. Instant ray tracing: The bounding interval hierarchy. In Proceedings of the Eurographics Symposium on Rendering. 139--149.

Digital Library

[35]

Wächter, C. and Keller, A. 2007. Terminating spatial hierarchies by a priori bounding memory. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 41--46.

Digital Library

[36]

Wächter, C. and Keller, A. 2009. Efficient ray tracing without acceleration data structure. U.S. Patent Applications Publication No. US 2009/0225081 A1.

[37]

Wald, I., Slusallek, P., Benthin, C. and Wagner, M. 2001. Interactive rendering with coherent ray tracing. In Proceedings of EUROGRAPHICS. 153--164.

[38]

Wald, I., Ize, T., Kensler, A., Knoll, A., and Parker, S. G. 2006a. Ray tracing animated scenes using coherent grid traversal. In Proceedings of ACM SIGGRAPH. 485--493.

Digital Library

[39]

Wald, I., Boulos, S., and Shirley, P. 2006b. Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Trans. Graph. 26, 1, Article 6.

Digital Library

[40]

Wald, I. 2007. On fast construction of SAH based bounding volume hierarchies. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 485--493.

Digital Library

[41]

Whitted, T. 1980. An improved illumination model for shaded display. Comm. ACM 23, 6, 343--349.

Digital Library

[42]

Zhou, K., Hou, Q., Wang, R., Guo., B. 2008. Real-Time kd-tree construction on graphics hardware. ACM Trans. Graph. 27, 5, Article 126.

Digital Library

Cited By

Meister DOgaki SBenthin CDoyle MGuthe MBittner J(2021)A Survey on Bounding Volume Hierarchies for Ray TracingComputer Graphics Forum10.1111/cgf.14266240:2(683-712)Online publication date: 4-Jun-2021
https://doi.org/10.1111/cgf.142662
Mohanto BIslam AGobbetti EStaadt O(2021)An integrative view of foveated renderingComputers & Graphics10.1016/j.cag.2021.10.010Online publication date: Oct-2021
https://doi.org/10.1016/j.cag.2021.10.010
Otsu HHanika JHachisuka TDachsbacher C(2018)Geometry-aware metropolis light transportACM Transactions on Graphics10.1145/3272127.327510637:6(1-11)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3272127.3275106
Show More Cited By

Index Terms

Naive ray-tracing: A divide-and-conquer approach
1. Computing methodologies
  1. Computer graphics
    1. Animation

Recommendations

Ray tracing-based interactive diffuse indirect illumination

Despite great efforts in recent years to accelerate global illumination computation, the real-time ray tracing of fully dynamic scenes to support photorealistic indirect illumination effects has yet to be achieved in computer graphics. In this paper, we ...
Complex Luminaires: Illumination and Appearance Rendering

Simulating a complex luminaire such as a chandelier is expensive and slow, even using state-of-the-art algorithms. A more practical alternative is to use precomputation to accelerate rendering. Prior approaches cached information on an aperture surface ...
A ray tracing solution for diffuse interreflection

An efficient ray tracing method is presented for calculating interreflections between surfaces with both diffuse and specular components. A Monte Carlo technique computes the indirect contributions to illuminance at locations chosen by the rendering ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 30, Issue 5

October 2011

198 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2019627

Issue’s Table of Contents

Copyright © 2011 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2011

Revised: 01 February 2011

Received: 01 May 2010

Published in TOG Volume 30, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Engineering and Physical Sciences Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
3,979
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)3

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Meister DOgaki SBenthin CDoyle MGuthe MBittner J(2021)A Survey on Bounding Volume Hierarchies for Ray TracingComputer Graphics Forum10.1111/cgf.14266240:2(683-712)Online publication date: 4-Jun-2021
https://doi.org/10.1111/cgf.142662
Mohanto BIslam AGobbetti EStaadt O(2021)An integrative view of foveated renderingComputers & Graphics10.1016/j.cag.2021.10.010Online publication date: Oct-2021
https://doi.org/10.1016/j.cag.2021.10.010
Otsu HHanika JHachisuka TDachsbacher C(2018)Geometry-aware metropolis light transportACM Transactions on Graphics10.1145/3272127.327510637:6(1-11)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3272127.3275106
Serpa YRodrigues M(2018)Flexible Use of Temporal and Spatial Reasoning for Fast and Scalable CPU Broad‐Phase Collision Detection Using KD‐TreesComputer Graphics Forum10.1111/cgf.1352938:1(260-273)Online publication date: 29-Jul-2018
https://doi.org/10.1111/cgf.13529
Pahins CStephens SScheidegger CComba J(2017)HashedcubesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2016.259862423:1(671-680)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TVCG.2016.2598624
(2017)ReferencesPhysically Based Rendering10.1016/B978-0-12-800645-0.50027-0(1165-1211)Online publication date: 2017
https://doi.org/10.1016/B978-0-12-800645-0.50027-0
Gu YHe YBlelloch G(2015)Ray Specialized Contraction on Bounding Volume HierarchiesComputer Graphics Forum10.1111/cgf.1276934:7(309-318)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1111/cgf.12769
Mattausch OBittner JJaspe AGobbetti EWimmer MPajarola R(2015)CHC+RTComputer Graphics Forum10.1111/cgf.1258234:2(537-548)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1111/cgf.12582
Bittner JMeister D(2015)T-SAHComputer Graphics Forum10.1111/cgf.1258134:2(527-536)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1111/cgf.12581
Barringer RAkenine-Möller T(2014)Dynamic ray stream traversalACM Transactions on Graphics10.1145/2601097.260122233:4(1-9)Online publication date: 27-Jul-2014
https://dl.acm.org/doi/10.1145/2601097.2601222
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents