fast high quality k-d tree construction algorithm

CORC > 软件研究所 > 软件所图书馆 > 期刊论文

	fast high quality k-d tree construction algorithm
	Qian Yin-Ling ; Liang Xiao ; Zhang Yan-Ci
刊名	Ruan Jian Xue Bao/Journal of Software
	2012
卷号	23 期号:UPPL.2 页码:158-167
关键词	Algorithms Forestry Ray tracing
ISSN号	1000-9825
中文摘要	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
语种	中文
公开日期	2013-09-17
内容类型	期刊论文
源URL	[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.