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

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

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