遊戲場景管理的八叉樹演算法是怎樣的？

11-25

看到許多如Unreal4、klayge等諸多3D引擎裡面都使用了八叉樹來管理渲染物體，一直沒明白它是如何完成八叉樹的構建和實時的更新，求大神釋疑。

八叉樹（octree）是三維空間劃分的數據結構之一，它用於加速空間查詢，例如在遊戲中：

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

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

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

圖片來源Wikipedia Octree

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

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

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

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

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

在分割時，我們只需檢查點是在每個軸的哪一方，就能知道該點應放置在哪個新的節點裡。

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

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

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

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

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

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

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

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

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

圖片來源：Akenine-Moller, Tomas, Eric Haines, and Naty Hoffman. Real-time rendering 3rd edition. p.655, AK, 2008. 在上圖中，七角星最後處於兩個葉節點。這時候至少有兩個解決方法：

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

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

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

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

以上所說的都是一些基本原理，在實現時要考慮具體的數據結構、內存布局等問題。現在一般認為，完全使用八叉樹可能不利於緩存，用一些扁平的結構並利用SIMD可能更可提高性能，或是需要混合的方案，如八叉樹只有兩、三層，葉節點內使用扁平的方式儲存各種包圍體。

因此，除了傳統的四／八叉樹實現，也可以參考一些更新的技術，例如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

前面狠多人都介紹了八叉樹的原理，我就補充一點。
實際應用中，八叉樹在存儲三角面片時可能會遇到這樣的問題：
不管怎麼切，總發現有些面片同時位於兩個（或者多個）節點
對於沒有大小的元素（點），是不會存在這個問題的。

蟹妖。我對此了解並不多，也沒有太多工程實踐。
不管是什麼樹，都屬於需要適應場景內容的空間劃分，劃分的結果需要盡量平均地分割場景里的對象，不然就失去了空間劃分的意義。
具體實現上，走一次空間劃分需要遍歷場景里的對象（至少也要遍歷它們的bbox），甚至可能不止一次，所以必然有相當的計算代價。對於軸平行的劃分方法，起始一次劃分的時候不妨從bbox在那個軸上的中值開始。優化上，由於物體的移動是漸進的，可以考慮從上一次劃分的結果起始下一次劃分。
我自己喜歡用固定尺寸的網格。

揮刀自宮。我好像把什麼東西弄混了。

好像貼圖裡面涉及到少量的八叉樹構建吧，實時更新好像沒有涉及，不知道是否有幫助，沒幫助請摺疊.

內容出自Ogre3d
beginner Guide。

可以從四叉樹和GeoHash看起。原理類似。

差不多就是三維空間的二分法??