文档介绍：河北大学
硕士学位论文
利用邻域特性扩展的kd-tree及其查找算法
姓名:李欢
申请学位级别:硕士
专业:计算机应用技术
指导教师:徐建民
2011-05
摘要
摘要
计算场景中数量庞大的各种对象间的距离以判断交互与否是游戏系统中兴趣管理
功能的一类主要计算工作。kd-tree 作为一种最近邻查找工具已被应用于游戏空间的分
割,在一定程度上保证了兴趣管理的效率。但目前对 kd-tree 的应用仅利用了各个子空间
被一分为二的特点,查找时需从起始叶节点先向上遍历找到一个包含兴趣域的非叶节
点,然后再向下遍历树结构以找到与兴趣域相交的所有叶节点,在处理兴趣域跨越多棵
子树深层叶节点的情况时,由于查找路径很长,性能下降明显。
注意到相交于兴趣域的叶节点均与起始叶节点在空间上相邻,存在建立更短连接路
径的可能,以及游戏中分割得到的最小子空间大于兴趣域的特点,提出了邻域特性概念。
邻域特性体现了节点在空间上的各种邻接特征,利用这些特征可使查找过程根据兴趣域
与起始叶节点的位置以更短的路径抵达周边子空间,减缓由于单纯靠层次遍历造成的查
找路径过长的问题。利用邻域特性扩展了传统的 kd-tree 结构,利用分割维度体现邻域特
性,在节点间层次关系基础上补充空间邻接关系,设计了新的从起始叶节点向四周扩展
的查找算法。经过对传统算法和新算法在原理和关键计算步骤上的分析,并通过仿真实
验证明,新的算法比传统算法有约 40%的性能提升且更稳定。
关键词邻域特性 kd-tree 空间查找空间分割
I
Abstract
Abstract
Calculating distance between a huge amount of objects in scene to determine interactions
is a puting task of the interest management in game system. The kd-tree being a type
of nearest neighbor finding tools has been applied to game scene partitioning, and keeps the
efficiency of interest management in a certain extent. But the current applications of kd-tree
just use the feature that the sub-space is divided into two, the searching needs to begin from
the standing node and goes upward recursively to a non-leaf node which passes the
AOI, then goes downward recursively to find all leaf nodes which intersect the AOI. When
the searching is among multiple deep tree nodes, the efficiency decreases evidently due to the
long searching path.
Noticing that the AOI intersecting leaf nodes are adjacent to standing node in space, it’s
possible to find a shorter linking path, and the size of smallest sub-divided space is larger than
AOI, the concept of neighbor feature is proposed. The neighbor feature represents many
space-adjacent features between nodes, these features can make the searching path to
surrounding spaces shorter based on the position-relation between AOI and standing node, it
alleviates the problem that searching hierarchical recurs