QQ客服 官方微博 反馈留言

	Real-time kd-tree construction on graphics hardware
	Kun Zhou ; Qiming Hou ; Rui Wang ; Baining Guo
	2010-10-12 ; 2010-10-12
关键词	Practical Theoretical or Mathematical/ computer graphics ray tracing trees (mathematics)/ real-time kd-tree construction graphics hardware streaming architecture breadth-first search order GPU ray tracing interactive photon mapping point cloud modeling/ C6130B Graphics techniques C1160 Combinatorial mathematics
中文摘要	We present an algorithm for constructing kd-trees on GPUs. This algorithm achieves real-time performance by exploiting the CPU'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.
语种	英语
出版者	ACM ; USA
内容类型	期刊论文
源URL	[http://hdl.handle.net/123456789/78732]
专题	清华大学
推荐引用方式 GB/T 7714	Kun Zhou,Qiming Hou,Rui Wang,et al. Real-time kd-tree construction on graphics hardware[J],2010, 2010.
APA	Kun Zhou,Qiming Hou,Rui Wang,&Baining Guo.(2010).Real-time kd-tree construction on graphics hardware..
MLA	Kun Zhou,et al."Real-time kd-tree construction on graphics hardware".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。