利用领域特性扩展的kd-tree及其查找算法

被引:0
作者
李欢
机构
[1] 河北大学
关键词
邻域特性; kd-tree; 空间查找; 空间分割;
D O I
暂无
年度学位
2011
学位类型
硕士
导师
摘要
计算场景中数量庞大的各种对象间的距离以判断交互与否是游戏系统中兴趣管理功能的一类主要计算工作。kd-tree作为一种最近邻查找工具已被应用于游戏空间的分割,在一定程度上保证了兴趣管理的效率。但目前对kd-tree的应用仅利用了各个子空间被一分为二的特点,查找时需从起始叶节点先向上遍历找到一个包含兴趣域的非叶节点,然后再向下遍历树结构以找到与兴趣域相交的所有叶节点,在处理兴趣域跨越多棵子树深层叶节点的情况时,由于查找路径很长,性能下降明显。 注意到相交于兴趣域的叶节点均与起始叶节点在空间上相邻,存在建立更短连接路径的可能,以及游戏中分割得到的最小子空间大于兴趣域的特点,提出了邻域特性概念。邻域特性体现了节点在空间上的各种邻接特征,利用这些特征可使查找过程根据兴趣域与起始叶节点的位置以更短的路径抵达周边子空间,减缓由于单纯靠层次遍历造成的查找路径过长的问题。利用邻域特性扩展了传统的kd-tree结构,利用分割维度体现邻域特性,在节点间层次关系基础上补充空间邻接关系,设计了新的从起始叶节点向四周扩展的查找算法。经过对传统算法和新算法在原理和关键计算步骤上的分析,并通过仿真实验证明,新的算法比传统算法有约40%的性能提升且更稳定。
引用
收藏
页数:45
共 7 条
[1]
空间二叉树排序查找算法及其在网络游戏中的应用 [J].
张渊 ;
余小清 ;
万旺根 .
计算机应用, 2007, (S1) :356-359
[2]
A load balancing scheme for massively multiplayer online games [J].
Carlos Eduardo Benevides Bezerra ;
Cláudio Fernando Resin Geyer .
Multimedia Tools and Applications, 2009, 45 :263-289
[3]
Highly parallel fast KD-tree construction for interactive ray tracing of dynamic scenes [J].
Shevtsov, Maxim ;
Soupikov, Alexei ;
Kapustin, Alexander .
COMPUTER GRAPHICS FORUM, 2007, 26 (03) :395-404
[4]
Encoding natural movement as an agent-based system: an investigation into human pedestrian behaviour in the built environment [J].
Turner, A ;
Penn, A .
ENVIRONMENT AND PLANNING B-PLANNING & DESIGN, 2002, 29 (04) :473-490
[5]
Aspects of networking in multiplayer computer games [J].
Smed, J ;
Kaukoranta, T ;
Hakonen, H .
ELECTRONIC LIBRARY, 2002, 20 (02) :87-97
[6]
MULTIDIMENSIONAL BINARY SEARCH TREES USED FOR ASSOCIATIVE SEARCHING [J].
BENTLEY, JL .
COMMUNICATIONS OF THE ACM, 1975, 18 (09) :509-517
[7]
Quad trees a data structure for retrieval on composite keys.[J].R. A. Finkel;J. L. Bentley.Acta Informatica.1974, 1