fast high quality k-d tree construction algorithm

ISCAS OpenIR

	fast high quality k-d tree construction algorithm
	Qian Yin-Ling; Liang Xiao; Zhang Yan-Ci
	2012
发表期刊	Ruan Jian Xue Bao/Journal of Software
ISSN	1000-9825
卷号	23 期号:UPPL.2 页码:158-167
摘要	This paper proposes a high quality k-D tree constructing algorithm for interactive dynamic scene ray tracing. Combined with the fact that scene primitives were usually well distributed, a reasonable formula is derived from the basic k-D tree traversal cost function to represent the traversal cost for sequential positions in node. After dividing the bounding box of splitting node to uniform bin series, the best splitting position is directly computed by resolving the analytic solution of the cost formula. To guarantee superior rendering performance for different ray tracing applications, the study raised several sensible functions for sub-space number computing in different situations. Experimental results proved that this algorithm was suitable for scenes with various kinds of primitive distribution, and it can be used for full k-D tree construction. Great construction efficiency was obtained with the best splitting quality maintained. © Copyright 2012, Editorial Department of Journal of Software.; This paper proposes a high quality k-D tree constructing algorithm for interactive dynamic scene ray tracing. Combined with the fact that scene primitives were usually well distributed, a reasonable formula is derived from the basic k-D tree traversal cost function to represent the traversal cost for sequential positions in node. After dividing the bounding box of splitting node to uniform bin series, the best splitting position is directly computed by resolving the analytic solution of the cost formula. To guarantee superior rendering performance for different ray tracing applications, the study raised several sensible functions for sub-space number computing in different situations. Experimental results proved that this algorithm was suitable for scenes with various kinds of primitive distribution, and it can be used for full k-D tree construction. Great construction efficiency was obtained with the best splitting quality maintained. © Copyright 2012, Editorial Department of Journal of Software.
收录类别	EI
关键词	Algorithms Forestry Ray Tracing
部门归属	(1) State Key Laboratory of Computer Science Institute of Software The Chinese Academy of Sciences Beijing 100190 China; (2) College of Computer Science Sichuan University Chengdu 610065 China; (3) College of Computer Science Southwest Petroleum University Chengdu 610500 China; (4) State Key Laboratory of Fundamental Science on Synthetic Vision Sichuan University Chengdu 610065 China
语种	中文
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15125
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Qian Yin-Ling,Liang Xiao,Zhang Yan-Ci. fast high quality k-d tree construction algorithm[J]. Ruan Jian Xue Bao/Journal of Software,2012,23(UPPL.2):158-167.
APA	Qian Yin-Ling,Liang Xiao,&Zhang Yan-Ci.(2012).fast high quality k-d tree construction algorithm.Ruan Jian Xue Bao/Journal of Software,23(UPPL.2),158-167.
MLA	Qian Yin-Ling,et al."fast high quality k-d tree construction algorithm".Ruan Jian Xue Bao/Journal of Software 23.UPPL.2(2012):158-167.