游戲場景管理的八叉樹算法是怎樣的_數(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個應(yīng)用都是加速一些形狀（frustum、ray、proximity shape如球體）的相交測試（intersection test）。

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

圖片來源Wikipedia Octree

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因此，除了傳統(tǒng)的四／八叉樹實現(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