游戲場景管理的八叉樹算法是怎樣的_數(shù)據(jù)分析師

八叉樹（octree）是三維空間劃分的數(shù)據(jù)結(jié)構(gòu)之一，它用于加速空間查詢，例如在游戲中：

1. 加速用于可見性判斷的視錐裁剪（view frustum culling）。
2. 加速射線投射（ray casting） ，如用作視線判斷或槍擊判定。
3. 鄰近查詢（proximity query），如查詢玩家角色某半徑范圍內(nèi)的敵方NPC。
4. 碰撞檢測的粗略階段（broad phase），找出潛在可能碰撞的物體對。

總括而言，前3個(gè)應(yīng)用都是加速一些形狀（frustum、ray、proximity shape如球體）的相交測試（intersection test）。

簡單來說，八叉樹的空間劃分方式是，把一個(gè)立方體分割為八個(gè)小立法體，然后遞歸地分割小立方體。

圖片來源Wikipedia Octree

相似地，四叉樹把一個(gè)正方形空間分割成四個(gè)小正方形。由于三維空間較難理解，之后本答案主要以四叉樹作圖示解釋。

四／八叉樹有多種變種，先談一個(gè)簡化的情況，就是假設(shè)所有物體是一個(gè)點(diǎn)，這樣比較容易理解。

把每點(diǎn)放到正方形空間里，若該正方形含有超過一個(gè)點(diǎn)，就把該正方式分割，直至每個(gè)小正方形（葉節(jié)點(diǎn)）僅含有一個(gè)點(diǎn)，就可以得出以下的分割結(jié)果：

圖片來源：CS267: Notes for Lecture 24, Apr 11 1996

這種做法是adaptive的，就是說按照一定的條件（葉節(jié)點(diǎn)只能有一個(gè)點(diǎn)）來進(jìn)行分割。實(shí)際上，我們可以設(shè)置其他條件去決定是否分割一個(gè)葉節(jié)點(diǎn)，例如節(jié)點(diǎn)內(nèi)的點(diǎn)超過10個(gè)，或是最多分割4層就不再分割等等。

在分割時(shí)，我們只需檢查點(diǎn)是在每個(gè)軸的哪一方，就能知道該點(diǎn)應(yīng)放置在哪個(gè)新的節(jié)點(diǎn)里。

建立了一個(gè)四／八叉樹之后，我們可以得出一個(gè)重要特性：

如果一個(gè)形狀S與節(jié)點(diǎn)A的空間（正方形／立方體）不相交，那么S與A子樹下的所有點(diǎn)都不相交。

那么，在相交測試中，我們可以從根節(jié)點(diǎn)開始，遍歷四／八叉樹的節(jié)點(diǎn)，如節(jié)點(diǎn)相交就繼續(xù)遍歷，如不相交就放棄遍歷該子樹，最后在葉節(jié)點(diǎn)進(jìn)行形狀與點(diǎn)的相交測試。這樣做，一般能剔除許多點(diǎn)，但注意最壞的情況是所有點(diǎn)集中在一起，那么就不起加速作用。

———————-
9月4日晚更新

當(dāng)創(chuàng)建了一個(gè)四／八叉樹之后，如問題所提及，有時(shí)候需要新增、刪除物體（目前我們談及的是點(diǎn)），以及更新物體（點(diǎn)）的位置。

更新位置的最簡單實(shí)現(xiàn)，就是刪去物體再重新安插。然而，顯然的優(yōu)化方法就是，檢查舊位置和新位置是否位于同一個(gè)葉節(jié)點(diǎn)的正方／立方范圍里，如果沒超出范圍，就不需要做刪除再安插的工作。

但如果超出范圍呢？除了簡單地從根開始找合適的節(jié)點(diǎn)，也可以使用一些搜尋方法找到相鄰的節(jié)點(diǎn)，如[1]。這里就不談這些細(xì)節(jié)了。

了解最基本的四／八叉樹后，可以把問題擴(kuò)充至管理占面積／體積的物體。雖然我們可以每次比較場景物體和正方形／立方體是否相交，但為了性能，一般是使用物體的包圍體（bounding volume）而不是物體本身。例如是使用包圍球（bounding sphere）、軸對齊包圍盒（axis-aligned bounding box, AABB）或定向包圍體（oriented bounding box, OBB）。這個(gè)做法是保守的。

但無論是用物體的精確形狀，還是使用包圍體積，把它們放置在四／八叉樹中會有一個(gè)問題：它們可能會與節(jié)點(diǎn)的邊界相交。例如

圖片來源：Akenine-Moller, Tomas, Eric Haines, and Naty Hoffman. Real-time rendering 3rd edition. p.655, AK, 2008.

在上圖中，七角星最后處于兩個(gè)葉節(jié)點(diǎn)。這時(shí)候至少有兩個(gè)解決方法：

1. 所有與物體相交的子節(jié)點(diǎn)都引用至該物物體。在此例子中，有兩個(gè)葉節(jié)點(diǎn)都引用七角星物體。
2. 令中間節(jié)點(diǎn)（非葉節(jié)點(diǎn)）也能放置物體。在此例子中，上一層的中間節(jié)點(diǎn)（就是右上的正方形）放置七角星物體。

第一種方法的范圍比較精確，但如果物體的大小相差很大，大體積的物體便需要被大量小范圍的葉節(jié)點(diǎn)引用，而且管理上也會很麻煩。第二種做法是較常用的方法。然而，第二種方法的范圍可能非常大，例如物體剛好在場景的中心，即使是一個(gè)體積很小的物體，都只能放于根節(jié)點(diǎn)里。

要解決這個(gè)問題，可以考慮到在相交測試中，擴(kuò)大包圍盒總是保守的（這里的保守是指近似化不會做成錯(cuò)誤結(jié)果）。如果把四叉／八叉樹的正方／立方空間當(dāng)作包圍盒，那么擴(kuò)大這些包圍盒以容納剛好在邊界上相交的物體也是保守的。這就是松散四／八叉樹（loose quadtree/octree）[2] 的思路。

圖片來源：Akenine-Moller, Tomas, Eric Haines, and Naty Hoffman. Real-time rendering 3rd edition. p.656, AK, 2008.

以上所說的都是一些基本原理，在實(shí)現(xiàn)時(shí)要考慮具體的數(shù)據(jù)結(jié)構(gòu)、內(nèi)存布局等問題。現(xiàn)在一般認(rèn)為，完全使用八叉樹可能不利于緩存，用一些扁平的結(jié)構(gòu)并利用SIMD可能更可提高性能，或是需要混合的方案，如八叉樹只有兩、三層，葉節(jié)點(diǎn)內(nèi)使用扁平的方式儲存各種包圍體。

因此，除了傳統(tǒng)的四／八叉樹實(shí)現(xiàn)，也可以參考一些更新的技術(shù)，例如OpenVDB [3]中的一些思路。

[1] Frisken, Sarah F., and Ronald N. Perry. “Simple and efficient traversal methods for quadtrees and octrees.” Journal of Graphics Tools 7.3 (2002): 1-11.
[2] Ulrich, Thatcher. “Loose octrees.” Game Programming Gems 1 (2000): 434-442.
[3] K. Museth, “VDB: High-Resolution Sparse Volumes With Dynamic Topology”. ACM Transactions on Graphics, Volume 32, Issue 3, Pages 27:1-27:22, June 2013. http://www.museth.org/Ken/Publications_files/Museth_TOG13.pdf