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

Article

Interactive k-d tree GPU raytracing

Authors:

Daniel Reiter Horn,

Jeremy Sugerman,

Pat HanrahanAuthors Info & Claims

I3D '07: Proceedings of the 2007 symposium on Interactive 3D graphics and games

Pages 167 - 174

https://doi.org/10.1145/1230100.1230129

Published: 30 April 2007 Publication History

Abstract

Over the past few years, the powerful computation rates and high memory bandwidth of GPUs have attracted efforts to run raytracing on GPUs. Our work extends Foley et al.'s GPU k-d tree research. We port their kd-restart algorithm from multi-pass, using CPU load balancing, to single pass, using current GPUs' branching and looping abilities. We introduce three optimizations: a packetized formulation, a technique for restarting partially down the tree instead of at the root, and a small, fixed-size stack that is checked before resorting to restart. Our optimized implementation achieves 15 - 18 million primary rays per second and 16 - 27 million shadow rays per second on our test scenes.

Our system also takes advantage of GPUs' strengths at rasterization and shading to offer a mode where rasterization replaces eye ray scene intersection, and primary hits and local shading are produced with standard Direct3D code. For 1024x1024 renderings of our scenes with shadows and Phong shading, we achieve 12-18 frames per second. Finally, we investigate the efficiency of our implementation relative to the computational resources of our GPUs and also compare it against conventional CPUs and the Cell processor, which both have been shown to raytrace well.

References

[1]

ATI, 2006. Radeon X1900 product site. http://ati.amd.com/products/radeonx1900/index.html.

[2]

ATI, 2006. Researcher CTM documentation. http://ati.amd.com/companyinfo/researcher/documents.html.

[3]

Benthin, C., Wald, I., Scherbaum, M., and Friedrich, H. 2006. Ray Tracing on the CELL Processor. In Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing.

[4]

Blythe, D. 2006. The Direct3D 10 system. ACM Trans. Graph. 25, 3, 724--734.

Digital Library

[5]

Buck, I., Foley, T., Horn, D., Sugerman, J., Fatahalian, K., Houston, M., and Hanrahan, P. 2004. Brook for GPUs: Stream computing on graphics hardware. In Proceedings of ACM SIGGRAPH 2004.

Digital Library

[6]

Buck, I. 2005. GPU computation strategies. In GPGPU Course Notes - SIGGRAPH 2005.

Digital Library

[7]

Carr, N. A., Hoberock, J., Crane, K., and Hart, J. C. 2006. Fast gpu ray tracing of dynamic meshes using geometry images. In Proceedings of Graphics Interface 2006, Canadian Information Processing Society.

Digital Library

[8]

Foley, T., and Sugerman, J. 2005. Kd-tree acceleration structures for a gpu raytracer. In HWWS '05: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, ACM Press, New York, NY, USA, 15--22.

Digital Library

[9]

Havran, V., and Bittner, J. 2002. On improving kd-trees for ray shooting. In Proceedings of WSCG'2002 conference, 209--217.

[10]

Intel, 2006. Intel Core2 Duo Processor. http://www.intel.com/products/processor/core2duo.

[11]

Microsoft, 2003. Directx home page. http://www.microsoft.com/windows/directx/default.asp.

[12]

Purcell, T. J., Buck, I., Mark, W. R., and Hanrahan, P. 2002. Ray tracing on programmable graphics hardware. ACM Trans. Graph., 703--712.

Digital Library

[13]

Reshetov, A., Soupikov, A., and Hurley, J. 2005. Multi-level ray tracing algorithm. ACM Trans. Graph. 24, 3, 1176--1185.

Digital Library

[14]

Schmittler, J., Wald, I., and Slusallek, P. 2002. Saarcor: a hardware architecture for ray tracing. In HWWS '02: Proceedings of the ACM

Digital Library

[15]

SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 27--36.

[16]

Stanford University, 2006. GPUBench. http://graphics.stanford.edu/projects/gpubench.

[17]

Sugerman, J., Foley, T., Yoshioka, S., and Hanrahan, P., 2006. Ray tracing on a cell processor with software caching. Poster at The 2006 IEEE Symposium on Interactive Ray Tracing. http://www.sci.utah.edu/RT06/full_compendium.pdf.

[18]

Thrane, N., and Simonsen, L. O. 2005. A comparison of acceleration structures for GPU assisted ray tracing. M. S. thesis, University of Aarhus, Aarhus, Denmark.

[19]

Wald, I., Slusallek, P., Benthin, C., and Wagner, M. 2001. Interactive rendering with coherent ray tracing. Computer Graphics Forum 20, 3, 153--164.

Digital Library

[20]

Wald, I. 2004. Realtime Ray Tracing and Interactive Global Illumination. PhD thesis, Saarland University.

[21]

Woop, S., Schmittler, J., and Slusallek, P. 2005. Rpu: a programmable ray processing unit for realtime ray tracing. ACM Trans. Graph. 24, 3, 434--444.

Digital Library

Cited By

Li MWang HDai HLi MChai CGu RChen FChen ZLi SLiu QChen G(2024)A Survey of Multi-Dimensional Indexes: Past and Future TrendsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336418336:8(3635-3655)Online publication date: Aug-2024
https://doi.org/10.1109/TKDE.2024.3364183
Ma JLiu MAhmedt-Aristizabal DNguyen C(2024)HashPoint: Accelerated Point Searching and Sampling for Neural Rendering2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00427(4462-4472)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.00427
Han MWang LXiao LZhang HZhang CXu XZhu J(2023)QuickFPS: Architecture and Algorithm Co-Design for Farthest Point Sampling in Large-Scale Point CloudsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.327492242:11(4011-4024)Online publication date: Nov-2023
https://doi.org/10.1109/TCAD.2023.3274922
Show More Cited By

Index Terms

Interactive k-d tree GPU raytracing
1. Computing methodologies
  1. Computer graphics
    1. Graphics systems and interfaces
      1. Graphics processors

Recommendations

Brook for GPUs: stream computing on graphics hardware
SIGGRAPH '04: ACM SIGGRAPH 2004 Papers

In this paper, we present Brook for GPUs, a system for general-purpose computation on programmable graphics hardware. Brook extends C to include simple data-parallel constructs, enabling the use of the GPU as a streaming co-processor. We present a ...
Brook for GPUs: stream computing on graphics hardware

In this paper, we present Brook for GPUs, a system for general-purpose computation on programmable graphics hardware. Brook extends C to include simple data-parallel constructs, enabling the use of the GPU as a streaming co-processor. We present a ...
Brook for GPUs: Stream Computing on Graphics Hardware
Seminal Graphics Papers: Pushing the Boundaries, Volume 2

In this paper, we present Brook for GPUs, a system for general-purpose computation on programmable graphics hardware. Brook extends C to include simple data-parallel constructs, enabling the use of the GPU as a streaming co-processor. We present a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

I3D '07: Proceedings of the 2007 symposium on Interactive 3D graphics and games

April 2007

196 pages

ISBN:9781595936288

DOI:10.1145/1230100

General Chairs:
Bruce Gooch
Northwestern University
,
Peter-Pike Sloan
Microsoft
,
Program Chairs:
Jonathan Cohen
Lawrence Livermore National Laboratory
,
Greg Turk
Georgia Institute of Technology
,
Ben Watson
North Carolina State University

Copyright © 2007 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]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

I3D07

Sponsor:

SIGGRAPH

I3D07: Symposium on Interactive 3D Graphics and Games 2007

April 30 - May 2, 2007

Washington, Seattle

Acceptance Rates

Overall Acceptance Rate 148 of 485 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

136
Total Citations
View Citations
2,110
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)7

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li MWang HDai HLi MChai CGu RChen FChen ZLi SLiu QChen G(2024)A Survey of Multi-Dimensional Indexes: Past and Future TrendsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336418336:8(3635-3655)Online publication date: Aug-2024
https://doi.org/10.1109/TKDE.2024.3364183
Ma JLiu MAhmedt-Aristizabal DNguyen C(2024)HashPoint: Accelerated Point Searching and Sampling for Neural Rendering2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00427(4462-4472)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.00427
Han MWang LXiao LZhang HZhang CXu XZhu J(2023)QuickFPS: Architecture and Algorithm Co-Design for Farthest Point Sampling in Large-Scale Point CloudsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.327492242:11(4011-4024)Online publication date: Nov-2023
https://doi.org/10.1109/TCAD.2023.3274922
Gutiérrez A. MVexo FThalmann DGutiérrez A. MVexo FThalmann D(2023)Computer GraphicsStepping into Virtual Reality10.1007/978-3-031-36487-7_2(15-54)Online publication date: 12-Aug-2023
https://doi.org/10.1007/978-3-031-36487-7_2
Lewis ZTu Y(2022)G-PICS: A Framework for GPU-Based Spatial Indexing and Query ProcessingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.299244034:3(1243-1257)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TKDE.2020.2992440
Saed MChou YLiu LNowicki TAamodt T(2022)Vulkan-Sim: A GPU Architecture Simulator for Ray Tracing2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO56248.2022.00027(263-281)Online publication date: Oct-2022
https://doi.org/10.1109/MICRO56248.2022.00027
Hong LChamorro L(2022)A fast, non-iterative ray-intersection approach for three-dimensional microscale particle trackingLab on a Chip10.1039/D1LC01042E22:5(964-971)Online publication date: 2022
https://doi.org/10.1039/D1LC01042E
Będkowski JBędkowski J(2022)LiDAR MetricsLarge-Scale Simultaneous Localization and Mapping10.1007/978-981-19-1972-5_8(171-229)Online publication date: 14-Jun-2022
https://doi.org/10.1007/978-981-19-1972-5_8
Liu LChang WDemoullin FChou YSaed MPankratz DNowicki TAamodt T(2021)Intersection Prediction for Accelerated GPU Ray TracingMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3466752.3480097(709-723)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3466752.3480097
Yildirim GGunduzalp ETatar Y(2021)Fuzzy Logic-Based SBR Acceleration Approach for Radio Propagation Prediction in Indoor EnvironmentsArabian Journal for Science and Engineering10.1007/s13369-021-06044-1Online publication date: 2-Sep-2021
https://doi.org/10.1007/s13369-021-06044-1
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents