research-article

Real-time KD-tree construction on graphics hardware

Authors:

Baining GuoAuthors Info & Claims

SIGGRAPH Asia '08: ACM SIGGRAPH Asia 2008 papers

Article No.: 126, Pages 1 - 11

https://doi.org/10.1145/1457515.1409079

Published: 01 December 2008 Publication History

Abstract

We present an algorithm for constructing kd-trees on GPUs. This algorithm achieves real-time performance by exploiting the GPU's streaming architecture at all stages of kd-tree construction. Unlike previous parallel kd-tree algorithms, our method builds tree nodes completely in BFS (breadth-first search) order. We also develop a special strategy for large nodes at upper tree levels so as to further exploit the fine-grained parallelism of GPUs. For these nodes, we parallelize the computation over all geometric primitives instead of nodes at each level. Finally, in order to maintain kd-tree quality, we introduce novel schemes for fast evaluation of node split costs.

As far as we know, ours is the first real-time kd-tree algorithm on the GPU. The kd-trees built by our algorithm are of comparable quality as those constructed by off-line CPU algorithms. In terms of speed, our algorithm is significantly faster than well-optimized single-core CPU algorithms and competitive with multi-core CPU algorithms. Our algorithm provides a general way for handling dynamic scenes on the GPU. We demonstrate the potential of our algorithm in applications involving dynamic scenes, including GPU ray tracing, interactive photon mapping, and point cloud modeling.

Supplementary Material

MOV File (a126-zhou-mp4_hi.mov)

Download
450.87 MB

References

[1]

Carr, N. A., Hall, J. D., and Hart, J. C. 2002. The ray engine. In Proceedings of Graphics Hardware, 37--46.

Digital Library

[2]

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, 203--209.

Digital Library

[3]

Foley, T., and Sugerman, J. 2005. Kd-tree acceleration structures for a GPU raytracer. In Graphics Hardware'05.

Digital Library

[4]

Goldsmith, J., and Salmon, J. 1987. Automatic creation of object hierarchies for ray tracing. IEEE CG & A 7, 5, 14--20.

Digital Library

[5]

Gropp, W., Lusk, E., and Skjellum, A. 1994. Using MPI: Portable Parallel Programming with the Message Passing Interface. MIT Press.

Digital Library

[6]

Günther, J., Wald, I., and Slusallek, P. 2004. Realtime caustics using distributed photon mapping. In Eurographics Symposium on Rendering, 111--121.

Digital Library

[7]

Harris, M., Owens, J., Sengupta, S., Zhang, Y., and Davidson, A., 2007. CUDPP homepage. http://www.gpgpu.org/developer/cudpp/.

[8]

Havran, V. 2001. Heuristic Ray Shooting Algorithms. PhD thesis, Czech Technical University in Prague.

[9]

Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Proceedings of SIGGRAPH'92, 71--78.

Digital Library

[10]

Horn, D. R., Sugerman, J., Houston, M., and Hanrahan, P. 2007. Interactive k-d tree GPU raytracing. In Proceedings of Symposium on Interactive 3D graphics and Games, 167--174.

Digital Library

[11]

Hunt, W., Mark, W. R., and Stoll, G. 2006. Fast kd-tree construction with an adaptive error-bounded heuristic. In IEEE Symposium on Interactive Ray Tracing, 81--88.

[12]

Jensen, H. W. 2001. Realistic Image Synthesis Using Photon Mapping. AK Peters.

Digital Library

[13]

MacDonald, J. D., and Booth, K. S. 1990. Heuristics for ray tracing using space subdivision. Vis. Comput. 6, 3, 153--166.

Digital Library

[14]

Manku, G. S., 2002. Fast bit counting routines. http://infolab.stanford.edu/ manku/bitcount/bitcount.html.

[15]

Mount, D. M., and Arya, S., 2006. ANN: A library for approximate nearest neighbor searching. http://www.cs.umd.edu/~mount/ANN/.

[16]

Nicolaychuk, A., 2008. RivaTuner. http://www.guru3d.com/index.php?page=rivatuner.

[17]

NVIDIA, 2007. CUDA programming guide 1.0. http://developer.nvidia.com/object/cuda.html.

[18]

Pauly, M., Keiser, R., Kobbelt, L. P., and Gross, M. 2003. Shape modeling with point-sampled geometry. In Proceedings of SIGGRAPH'03, 641--650.

Digital Library

[19]

Pharr, M., and Humpreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann.

Digital Library

[20]

Popov, S., Günther, J., Seidel, H.-P., and Slusallek, P. 2006. Experiences with streaming construction of SAH KD-trees. In IEEE Symposium on Interactive Ray Tracing, 89--94.

[21]

Popov, S., Günther, J., Seidel, H.-P., and Slusallek, P. 2007. Stackless kd-tree traversal for high performance GPU ray tracing. In Eurographics'07, 415--424.

[22]

Preparata, F. P., and Shamos, M. I. 1985. Computational Geometry: An Introduction. Springer-Verlag New York, Inc.

Digital Library

[23]

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

Digital Library

[24]

Purcell, T. J., Donner, C., Cammarano, M., Jensen, H. W., and Hanrahan, P. 2003. Photon mapping on programmable graphics hardware. In Graphics Hardware'03, 41--50.

Digital Library

[25]

Reshetov, A., Soupikov, A., and Hurley, J. 2005. Multilevel ray tracing algorithm. In SIGGRAPH '05, 1176--1185.

Digital Library

[26]

Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Graphics Hard-ware'07, 97--106.

Digital Library

[27]

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

[28]

Shiue, L.-J., Jones, I., and Peters, J. 2005. A realtime GPU subdivision kernel. ACM Trans. Gr. 24, 3, 1010--1015.

Digital Library

[29]

Stoll, G. 2005. Part II: Achieving real time - optimization techniques. In SIGGRAPH 2005 Course on Interactive Ray Tracing.

[30]

Wald, I., and Havran, V. 2006. On building fast kd-trees for ray tracing, and on doing that in O(Nlog N). In Proceedings of IEEE Symposium on Interactive Ray Tracing, 61--69.

[31]

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

[32]

Wald, I., Günther, J., and Slusallek, P. 2004. Balancing considered harmful --faster photon mapping using the voxel volume heuristic. In Proceedings of Eurographics'04, 595--603.

[33]

Wald, I., Ize, T., Kensler, A., Knoll, A., and Parker, S. G. 2006. Ray tracing animated scenes using coherent grid traversal. ACM Trans. Gr. 25, 3, 485--493.

Digital Library

[34]

Wald, I., Boulos, S., and Shirley, P. 2007. Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Trans. Gr. 26, 1, 6.

Digital Library

[35]

Wald, I. 2007. On fast construction of SAH based bounding volume hierarchies. In IEEE Symposium on Interactive Ray Tracing, 33--40.

Digital Library

[36]

Wang, R. Y., Pulli, K., and Popović, J. 2007. Real-time enveloping with rotational regression. ACM Trans. Gr. 26, 3, 73.

Digital Library

[37]

Yoon, S.-E., Curtis, S., and Manocha, D. 2007. Ray tracing dynamic scenes using selective restructuring. In Eurographics Symposium on Rendering.

Digital Library

[38]

Zhou, K., Huang, X., Xu, W., Guo, B., and Shum, H.-Y. 2007. Direct manipulation of subdivision surfaces on GPUs. ACM Trans. Gr. 26, 3, 91, 9.

Digital Library

[39]

Zwicker, M., Pfister, H., van Baar, J., and Gross, M. 2001. Surface splatting. In SIGGRAPH'01, 371--378.

Digital Library

[40]

Zwicker, M., Pauly, M., Knoll, O., and Gross, M. 2002. Pointshop 3d: an interactive system for point-based surface editing. In SIGGRAPH'02, 322--329.

Digital Library

Cited By

Huang Y(2024)Improvement of Parallel K-means Algorithm Based on Map Reduce and KD TreeProceedings of the 5th International Conference on Computer Information and Big Data Applications10.1145/3671151.3671335(1055-1059)Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1145/3671151.3671335
Mu YYu CSun CLi KZhang YWei JXiao JWang J(2023)3DT-CM: A Low-complexity Cross-matching Algorithm for Large Astronomical Catalogues Using 3d-tree ApproachResearch in Astronomy and Astrophysics10.1088/1674-4527/acee5023:10(105011)Online publication date: 20-Sep-2023
https://doi.org/10.1088/1674-4527/acee50
Ni YDeng YLi Z(2022)Agglomerative Memory and Thread Scheduling for High-Performance Ray-Tracing on GPUsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.305891041:2(334-345)Online publication date: Feb-2022
https://doi.org/10.1109/TCAD.2021.3058910
Show More Cited By

Index Terms

Real-time KD-tree construction on graphics hardware

Recommendations

Real-time KD-tree construction on graphics hardware

We present an algorithm for constructing kd-trees on GPUs. This algorithm achieves real-time performance by exploiting the GPU's streaming architecture at all stages of kd-tree construction. Unlike previous parallel kd-tree algorithms, our method builds ...
SAH KD-tree construction on GPU
HPG '11: Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics

KD-tree is one of the most efficient acceleration data structures for ray tracing. In this paper, we present a kd-tree construction algorithm that is precisely SAH-optimized and runs entirely on GPU. We construct the tree nodes in breadth-first order. ...
Simplified photon mapping for real-time caustics rendering

The objective of this paper is to adapt photon mapping for real-time simulation of caustics. High-performance algorithm adapted for the GPU and implemented on the basis of cross-platform OpenGL and OpenCL APIs is proposed. For effective rendering of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH Asia '08: ACM SIGGRAPH Asia 2008 papers

December 2008

581 pages

ISBN:9781450318310

DOI:10.1145/1457515

Editor:
John C. Hart
University of Illinois at Urbana-Champaign, Urbana, IL

Copyright © 2008 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: 01 December 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGGRAPH '08

Sponsor:

SIGGRAPH

SIGGRAPH '08: Special Interest Group on Computer Graphics and Interactive Techniques Conference

December 10 - 13, 2008

Singapore

Acceptance Rates

SIGGRAPH Asia '08 Paper Acceptance Rate 59 of 320 submissions, 18%;

Overall Acceptance Rate 178 of 869 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
4,003
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang Y(2024)Improvement of Parallel K-means Algorithm Based on Map Reduce and KD TreeProceedings of the 5th International Conference on Computer Information and Big Data Applications10.1145/3671151.3671335(1055-1059)Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1145/3671151.3671335
Mu YYu CSun CLi KZhang YWei JXiao JWang J(2023)3DT-CM: A Low-complexity Cross-matching Algorithm for Large Astronomical Catalogues Using 3d-tree ApproachResearch in Astronomy and Astrophysics10.1088/1674-4527/acee5023:10(105011)Online publication date: 20-Sep-2023
https://doi.org/10.1088/1674-4527/acee50
Ni YDeng YLi Z(2022)Agglomerative Memory and Thread Scheduling for High-Performance Ray-Tracing on GPUsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.305891041:2(334-345)Online publication date: Feb-2022
https://doi.org/10.1109/TCAD.2021.3058910
Gundabolu SVijaykumar TThottethodi Mde Supinski BHall MGamblin T(2021)FastZProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3458817.3476202(1-13)Online publication date: 14-Nov-2021
https://dl.acm.org/doi/10.1145/3458817.3476202
Yan DWang YWang JWang HLi Z(2021)K-Nearest Neighbor Search by Random Projection ForestsIEEE Transactions on Big Data10.1109/TBDATA.2019.29081787:1(147-157)Online publication date: 1-Mar-2021
https://doi.org/10.1109/TBDATA.2019.2908178
Suresha MKuppa SRaghukumar D(2021)PointRend Segmentation for a Densely Occluded Moving Object in a Video2021 Fourth International Conference on Computational Intelligence and Communication Technologies (CCICT)10.1109/CCICT53244.2021.00059(282-287)Online publication date: Jul-2021
https://doi.org/10.1109/CCICT53244.2021.00059
Su SYang JZhang CMa XLuan S(2021)Intelligent power equipment identification model based on grid topology analysisE3S Web of Conferences10.1051/e3sconf/202126002001260(02001)Online publication date: 19-May-2021
https://doi.org/10.1051/e3sconf/202126002001
Kougianos GMoustakas K(2021)Large-scale ray traced water caustics in real-time using cascaded caustic mapsComputers and Graphics10.1016/j.cag.2021.06.00898:C(255-267)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1016/j.cag.2021.06.008
De Boi IRibbens BJorissen PPenne R(2020)Feasibility of Kd-Trees in Gaussian Process Regression to Partition Test Points in High Resolution Input SpaceAlgorithms10.3390/a1312032713:12(327)Online publication date: 5-Dec-2020
https://doi.org/10.3390/a13120327
Jakob JGuthe M(2020) Optimizing LBVH‐Construction and Hierarchy‐Traversal to accelerate k NN Queries on Point Clouds using the GPU Computer Graphics Forum10.1111/cgf.1417740:1(124-137)Online publication date: 28-Oct-2020
https://doi.org/10.1111/cgf.14177
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