Real-time KD-tree construction on graphics hardware

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Real-time KD-tree construction on graphics hardware

Full text

Mov (24:56), Pdf

Pdf (2.90 MB)

Source

International Conference on Computer Graphics and Interactive Techniques archive
ACM SIGGRAPH Asia 2008 papers table of contents

Singapore

SESSION: Lighting, shading & GPUs table of contents

Article No. 126

Year of Publication: 2008

ISSN:0730-0301

Also published in ...

Authors

Kun Zhou	Zhejiang University and Microsoft Research Asia
Qiming Hou	Tsinghua University
Rui Wang	Zhejiang University
Baining Guo	Tsinghua University and Microsoft Research Asia

Sponsor

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 132, Downloads (12 Months): 773, Citation Count: 9

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1457515.1409079 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Nathan A. Carr , Jesse D. Hall , John C. Hart, The ray engine, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
	2	Nathan A. Carr , Jared Hoberock , Keenan Crane , John C. Hart, Fast GPU ray tracing of dynamic meshes using geometry images, Proceedings of Graphics Interface 2006, June 07-09, 2006, Quebec, Canada
	3	Tim Foley , Jeremy Sugerman, KD-tree acceleration structures for a GPU raytracer, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 30-31, 2005, Los Angeles, California [doi>10.1145/1071866.1071869]
	4	Jeffrey Goldsmith , John Salmon, Automatic Creation of Object Hierarchies for Ray Tracing, IEEE Computer Graphics and Applications, v.7 n.5, p.14-20, May 1987 [doi>10.1109/MCG.1987.276983]
	5	William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI: portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1994
	6	Günther, J., Wald, I., and Slusallek, P. 2004. Realtime caustics using distributed photon mapping. In Eurographics Symposium on Rendering, 111--121.
	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	Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
	10	Daniel Reiter Horn , Jeremy Sugerman , Mike Houston , Pat Hanrahan, Interactive k-d tree GPU raytracing, Proceedings of the 2007 symposium on Interactive 3D graphics and games, April 30-May 02, 2007, Seattle, Washington [doi>10.1145/1230100.1230129]
	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	Henrik Wann Jensen, Realistic image synthesis using photon mapping, A. K. Peters, Ltd., Natick, MA, 2001
	13	David J. MacDonald , Kellogg S. Booth, Heuristics for ray tracing using space subdivision, The Visual Computer: International Journal of Computer Graphics, v.6 n.3, p.153-166, 1990 [doi>10.1007/BF01911006]
	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	Mark Pauly , Richard Keiser , Leif P. Kobbelt , Markus Gross, Shape modeling with point-sampled geometry, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
	19	Matt Pharr , Greg Humphreys, Physically Based Rendering: From Theory to Implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
	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	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	23	Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	24	Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
	25	Alexander Reshetov , Alexei Soupikov , Jim Hurley, Multi-level ray tracing algorithm, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
	26	Shubhabrata Sengupta , Mark Harris , Yao Zhang , John D. Owens, Scan primitives for GPU computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
	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	Le-Jeng Shiue , Ian Jones , Jörg Peters, A realtime GPU subdivision kernel, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
	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.
	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	Ingo Wald , Thiago Ize , Andrew Kensler , Aaron Knoll , Steven G. Parker, Ray tracing animated scenes using coherent grid traversal, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	34	Ingo Wald , Solomon Boulos , Peter Shirley, Ray tracing deformable scenes using dynamic bounding volume hierarchies, ACM Transactions on Graphics (TOG), v.26 n.1, p.6-es, January 2007 [doi>10.1145/1189762.1206075]
	35	Wald, I. 2007. On fast construction of SAH based bounding volume hierarchies. In IEEE Symposium on Interactive Ray Tracing, 33--40.
	36	Robert Y. Wang , Kari Pulli , Jovan Popović, Real-time enveloping with rotational regression, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
	37	Yoon, S.-E., Curtis, S., and Manocha, D. 2007. Ray tracing dynamic scenes using selective restructuring. In Eurographics Symposium on Rendering.
	38	Kun Zhou , Xin Huang , Weiwei Xu , Baining Guo , Heung-Yeung Shum, Direct manipulation of subdivision surfaces on GPUs, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
	39	Matthias Zwicker , Hanspeter Pfister , Jeroen van Baar , Markus Gross, Surface splatting, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.371-378, August 2001 [doi>10.1145/383259.383300]
	40	Matthias Zwicker , Mark Pauly , Oliver Knoll , Markus Gross, Pointshop 3D: an interactive system for point-based surface editing, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas

CITED BY 9

	Ke Yang , Bingsheng He , Qiong Luo , Pedro V. Sander , Jiaoying Shi, Stack-based parallel recursion on graphics processors, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Timo Aila , Samuli Laine, Understanding the efficiency of ray traversal on GPUs, Proceedings of the Conference on High Performance Graphics 2009, August 01-03, 2009, New Orleans, Louisiana
	Morgan McGuire , David Luebke, Hardware-accelerated global illumination by image space photon mapping, Proceedings of the Conference on High Performance Graphics 2009, August 01-03, 2009, New Orleans, Louisiana
	Andrew Adams , Natasha Gelfand , Jennifer Dolson , Marc Levoy, Gaussian KD-trees for fast high-dimensional filtering, ACM Transactions on Graphics (TOG), v.28 n.3, August 2009
	Bongjun Jin , Insung Ihm , Byungjoon Chang , Chanmin Park , Wonjong Lee , Seokyoon Jung, Selective and adaptive supersampling for real-time ray tracing, Proceedings of the Conference on High Performance Graphics 2009, August 01-03, 2009, New Orleans, Louisiana
	Javor Kalojanov , Philipp Slusallek, A parallel algorithm for construction of uniform grids, Proceedings of the Conference on High Performance Graphics 2009, August 01-03, 2009, New Orleans, Louisiana
	Martin Stich , Heiko Friedrich , Andreas Dietrich, Spatial splits in bounding volume hierarchies, Proceedings of the Conference on High Performance Graphics 2009, August 01-03, 2009, New Orleans, Louisiana
	Markus Billeter , Ola Olsson , Ulf Assarsson, Efficient stream compaction on wide SIMD many-core architectures, Proceedings of the Conference on High Performance Graphics 2009, August 01-03, 2009, New Orleans, Louisiana
	Rui Wang , Rui Wang , Kun Zhou , Minghao Pan , Hujun Bao, An efficient GPU-based approach for interactive global illumination, ACM Transactions on Graphics (TOG), v.28 n.3, August 2009