接上文.
參考: http://bit.kuas.edu.tw/~cscheng/research/paper/kdtree.htm

根據(jù)我現(xiàn)在的理解. 比起blockmap, kd樹很靈活,它可以公平地劃分塊. 保證每塊的星星一樣多. 但是要分配出一個二叉樹(3D仍應(yīng)是二叉)的結(jié)構(gòu),當(dāng)深度比較大時,比如log(starn),就會費(fèi)內(nèi)存了. 還是用前面的例子實現(xiàn)...:

首先要計算層數(shù),就是kd tree里面的k. 設(shè)星球總數(shù)為m,層數(shù)為k,用后面說的方法就得出大致的時間方程: T=(m/2^k)^2+k*m,(b<=log2(m)),求T最小值時的k. 這個指數(shù)方程不會解~ hehe,暫定為k=log2(m)好了. 接著開始劃分并建立樹, 首先第一刀豎著切,x=所有星的x平均數(shù),這樣就分別把兩邊的星星標(biāo)記為2和3,表示當(dāng)前屬于2號和3號結(jié)點,這是第1層;再分別給2和3的區(qū)域橫著切兩刀,y仍取平均數(shù),這是第2層.... 這樣橫豎交替地切,因此在建立每一層就要遍歷starpool[]一次,一共是k*m次的位置檢索. 而最后被歸到同一個葉結(jié)點的星星組串成循環(huán)鏈表,以便對每組內(nèi)部做n=(m/2^k)^2/2次碰撞檢測. 現(xiàn)在就明白T的計算方法了.

午飯和晚飯都沒吃,無法再思考下去了. 至于kd tree的效果是不是非常好,是否用在網(wǎng)游里更合適. 以后再想.

轉(zhuǎn)載于:https://www.cnblogs.com/euclid/archive/2006/12/19/597157.html

總結(jié)

以上是生活随笔為你收集整理的碰撞检测技术:kd tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。