“Real-time KD-tree construction on graphics hardware”
Conference:
Type(s):
Title:
- Real-time KD-tree construction on graphics hardware
Session/Category Title: Lighting, shading & GPUs
Presenter(s)/Author(s):
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.
References:
1. Carr, N. A., Hall, J. D., and Hart, J. C. 2002. The ray engine. In Proceedings of Graphics Hardware, 37–46. Google ScholarDigital 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. Google ScholarDigital Library
3. Foley, T., and Sugerman, J. 2005. Kd-tree acceleration structures for a GPU raytracer. In Graphics Hardware’05. Google Scholar
4. Goldsmith, J., and Salmon, J. 1987. Automatic creation of object hierarchies for ray tracing. IEEE CG & A 7, 5, 14–20. Google Scholar
5. Gropp, W., Lusk, E., and Skjellum, A. 1994. Using MPI: Portable Parallel Programming with the Message Passing Interface. MIT Press. Google Scholar
6. Günther, J., Wald, I., and Slusallek, P. 2004. Realtime caustics using distributed photon mapping. In Eurographics Symposium on Rendering, 111–121. Google Scholar
7. Harris, M., Owens, J., Sengupta, S., Zhang, Y., and Davidson, A., 2007. CUDPP homepage. http://www.gpgpu.org/developer/cudpp/.Google Scholar
8. Havran, V. 2001. Heuristic Ray Shooting Algorithms. PhD thesis, Czech Technical University in Prague.Google Scholar
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. Google Scholar
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. Google Scholar
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.Google Scholar
12. Jensen, H. W. 2001. Realistic Image Synthesis Using Photon Mapping. AK Peters. Google Scholar
13. MacDonald, J. D., and Booth, K. S. 1990. Heuristics for ray tracing using space subdivision. Vis. Comput. 6, 3, 153–166. Google ScholarDigital Library
14. Manku, G. S., 2002. Fast bit counting routines. http://infolab.stanford.edu/ manku/bitcount/bitcount.html.Google Scholar
15. Mount, D. M., and Arya, S., 2006. ANN: A library for approximate nearest neighbor searching. http://www.cs.umd.edu/~mount/ANN/.Google Scholar
16. Nicolaychuk, A., 2008. RivaTuner. http://www.guru3d.com/index.php?page=rivatuner.Google Scholar
17. NVIDIA, 2007. CUDA programming guide 1.0. http://developer.nvidia.com/object/cuda.html.Google Scholar
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. Google Scholar
19. Pharr, M., and Humpreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann. Google Scholar
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.Google Scholar
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.Google Scholar
22. Preparata, F. P., and Shamos, M. I. 1985. Computational Geometry: An Introduction. Springer-Verlag New York, Inc. Google ScholarCross Ref
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. Google ScholarDigital 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. Google Scholar
25. Reshetov, A., Soupikov, A., and Hurley, J. 2005. Multilevel ray tracing algorithm. In SIGGRAPH ’05, 1176–1185. Google Scholar
26. Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Graphics Hard-ware’07, 97–106. Google Scholar
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.Google Scholar
28. Shiue, L.-J., Jones, I., and Peters, J. 2005. A realtime GPU subdivision kernel. ACM Trans. Gr. 24, 3, 1010–1015. Google ScholarDigital Library
29. Stoll, G. 2005. Part II: Achieving real time – optimization techniques. In SIGGRAPH 2005 Course on Interactive Ray Tracing.Google Scholar
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.Google Scholar
31. Wald, I., Slusallek, P., Benthin, C., and Wagner, M. 2001. Interactive rendering with coherent ray tracing. Computer Graphics Forum 20, 3, 153–164.Google ScholarDigital 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.Google Scholar
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. Google ScholarDigital 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. Google Scholar
35. Wald, I. 2007. On fast construction of SAH based bounding volume hierarchies. In IEEE Symposium on Interactive Ray Tracing, 33–40. Google ScholarDigital Library
36. Wang, R. Y., Pulli, K., and Popović, J. 2007. Real-time enveloping with rotational regression. ACM Trans. Gr. 26, 3, 73. Google ScholarDigital Library
37. Yoon, S.-E., Curtis, S., and Manocha, D. 2007. Ray tracing dynamic scenes using selective restructuring. In Eurographics Symposium on Rendering. Google Scholar
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. Google ScholarDigital Library
39. Zwicker, M., Pfister, H., van Baar, J., and Gross, M. 2001. Surface splatting. In SIGGRAPH’01, 371–378. Google Scholar
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. Google Scholar
