利用鄰域特性擴展的kd-tree及其查找算法.pdf

1、計算場景中數(shù)量龐大的各種對象間的距離以判斷交互與否是游戲系統(tǒng)中興趣管理功能的一類主要計算工作。Kd-tree作為一種最近鄰查找工具已被應用于游戲空間的分割，在一定程度上保證了興趣管理的效率。但目前對kd-tree的應用僅利用了各個子空間被一分為二的特點，查找時需從起始葉節(jié)點先向上遍歷找到一個包含興趣域的非葉節(jié)點，然后再向下遍歷樹結(jié)構(gòu)以找到與興趣域相交的所有葉節(jié)點，在處理興趣域跨越多棵子樹深層葉節(jié)點的情況時，由于查找路徑很長，性能下降明顯

2、。
　　 注意到相交于興趣域的葉節(jié)點均與起始葉節(jié)點在空間上相鄰，存在建立更短連接路徑的可能，以及游戲中分割得到的最小子空間大于興趣域的特點，提出了鄰域特性概念。
　　 鄰域特性體現(xiàn)了節(jié)點在空間上的各種鄰接特征，利用這些特征可使查找過程根據(jù)興趣域與起始葉節(jié)點的位置以更短的路徑抵達周邊子空間，減緩由于單純靠層次遍歷造成的查找路徑過長的問題。利用鄰域特性擴展了傳統(tǒng)的kd-tree結(jié)構(gòu)，利用分割維度體現(xiàn)鄰域特性，在節(jié)點間層次關(guān)系