计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2011年
3期
257-262
,共6页
邻域特性%kd-tree%查找%场景分割%游戏
鄰域特性%kd-tree%查找%場景分割%遊戲
린역특성%kd-tree%사조%장경분할%유희
处理场景中数量庞大的各种对象间的交互是游戏的一类主要计算工作.将κd-tree用于组织场景,提高了这类计算的效率.传统算法采用树的层次遍历方式进行查找,处理跨节点情况时性能下降明显.提出了邻域特性概念以扩展传统κd-tree结构,增添了树节点间的平面邻接关系,且考虑了游戏对κd-tree的一些限定,设计了从起始节点向四周扩展的查找算法.经分析与实验证明,新算法比传统算法有约40%的性能提升且更稳定.
處理場景中數量龐大的各種對象間的交互是遊戲的一類主要計算工作.將κd-tree用于組織場景,提高瞭這類計算的效率.傳統算法採用樹的層次遍歷方式進行查找,處理跨節點情況時性能下降明顯.提齣瞭鄰域特性概唸以擴展傳統κd-tree結構,增添瞭樹節點間的平麵鄰接關繫,且攷慮瞭遊戲對κd-tree的一些限定,設計瞭從起始節點嚮四週擴展的查找算法.經分析與實驗證明,新算法比傳統算法有約40%的性能提升且更穩定.
처리장경중수량방대적각충대상간적교호시유희적일류주요계산공작.장κd-tree용우조직장경,제고료저류계산적효솔.전통산법채용수적층차편력방식진행사조,처리과절점정황시성능하강명현.제출료린역특성개념이확전전통κd-tree결구,증첨료수절점간적평면린접관계,차고필료유희대κd-tree적일사한정,설계료종기시절점향사주확전적사조산법.경분석여실험증명,신산법비전통산법유약40%적성능제승차경은정.