在游戏中利用邻域特性扩展的kd-tree及其查找算法

摘要：

处理场景中数量庞大的各种对象间的交互是游戏的一类主要计算工作.将κd-tree用于组织场景,提高了这类计算的效率.传统算法采用树的层次遍历方式进行查找,处理跨节点情况时性能下降明显.提出了邻域特性概念以扩展传统κd-tree结构,增添了树节点间的平面邻接关系,且考虑了游戏对κd-tree的一些限定,设计了从起始节点向四周扩展的查找算法.经分析与实验证明,新算法比传统算法有约40%的性能提升且更稳定.

关键词：邻域特性、kd-tree、查找、场景分割、游戏

所属期刊栏目：38

分类号：TP391(计算技术、计算机技术)

资助基金：中国博士后科学基金20070420700

在线出版日期：2011-06-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：257-262