對OCTREE的描述
OCTREE 是對3D空間進行劃分，也可以叫空間分割。他允許你只對你的3D世界中攝象機照射的區(qū)域進行作畫。他也能用于沖突檢測。下面講一下為什么要進行空間分割。假設(shè)你建立了一個游戲世界，這個世界有超過100，000個多邊形要畫。如果你建立一個循環(huán)并傳遞這些多邊形，那速度是很慢的。即使你有一塊很好的顯示卡，他也會有很大的麻煩。但是玩你游戲的玩家的顯示卡不會超過300$。有沒有一種方法只渲染攝象機看見的多邊形？那就是美麗的OCTREE。他允許你快速的找到你要渲染的多邊形。
OCTREE是怎樣工作的 OCTREE工作在立方體中。最初，OCTREE從根接點開始，這個根接點對齊于立方體中整個世界，水平或場景的axis中心線。因此，把我們的整個世界想象成一個不可見的立方體。
現(xiàn)在根接點存儲了世界中的全部頂點。這是，他還是不能給我們?nèi)魏魏锰帲驗樗€會畫所有的東西。我們想把這個接點分成8個部分。一次，我們劃分時，有8個立方體包含那最初的根接點的立方體。那意味著有4個立方體在上面，4個立方體在下面。請看下圖：
記住圖中黃色輪廓線沒有。
我們剛剛把這個世界分成8個部分。想象一下如果我們有2，3，4個部分，我們的世界將是怎樣？我們的攝象機在世界的中間，向著后面靠右的角落。如果你看這些線，你將注意到在OCTREE中8個結(jié)點中的第4個。這些結(jié)點包含2個后面的頂和底結(jié)點。這意味著我們只用畫存儲在這些結(jié)點中的頂點。
我們?nèi)绾螜z測出我們要畫的結(jié)點？如果你學(xué)過破片揀選（frustum culling),這將是很簡單的。你能得到這些破片的大小并檢測每個結(jié)點，看他是否被截斷或在你的視覺破片中。有一個關(guān)于破片揀選的教程在http://www.gametutorials.com. 如果一個立方體截斷破片，我們就將畫這些結(jié)點。在這個例子中，我們切的數(shù)量是我們需要畫的50%。記住，這只是我們世界中的一個部分。部分越多，我們就將越精確。當(dāng)然，我們不會需要太多的點。下面，我們來看一下下面的圖：
在上面這幅圖中，你將發(fā)現(xiàn)許多的不同。這個例子中，不是在原始的8個立方體的每一個結(jié)點中建立8個新的立方體。原始的8個結(jié)點的頂和底面沒有細分。你總是把一個結(jié)點分成8個或更多的結(jié)點，但是，如果在這個面沒有三角形可以存儲，我們將忽視這個結(jié)點并不給他分配內(nèi)存。如果我們進一步的細分，更多的結(jié)點將形成原始的世界。如果我們變換到另一個部分，那立方體將相似的變換。為了說明這一點，請看圖：
?
在圖中，有兩個球，但是方向相反。注意左邊的部分，他將那世界分成2個結(jié)點，不是8個。這是因為球只要2個結(jié)點。請看右邊的球是不是和左邊的很相似。這幅圖告訴我們：只顯示需要的部分結(jié)點。如果沒有三角形占用空間，結(jié)點將不會建立。
何時停止細分
現(xiàn)在，我們明白了如何細分，但是我們也需要知道怎樣停止細分。有許多的方法：
1。如果當(dāng)時的三角形數(shù)量少于我們定義的最大的三角形數(shù)量，我們可以停止細分當(dāng)前的結(jié)點。舉個例子，我們定義三角形的最大數(shù)量為100。這意味著我們在細分結(jié)點之前，要檢測一下當(dāng)前三角形的總數(shù)量是否小于或等于我們定義的最大數(shù)量，然后再做決定。如果數(shù)量少于或等于，我們將停止細分并指定這些三角形到那個結(jié)點。請注意我們從不指定任何三角形到任何結(jié)點，除非他是末結(jié)點。如果我們劃分一個結(jié)點，我們不能存儲三角形到那個結(jié)點，但是可以存儲在他的子結(jié)點或他們的子結(jié)點中，甚至到他們的子中，等等。當(dāng)我們復(fù)習(xí)了怎樣畫0C樹后，將會有更多的了解。
2。另一個方法是在停止細分時，看我們是否細分的數(shù)目是否超過了細分的標(biāo)準(zhǔn)。例如，我們可以先建立細分的標(biāo)準(zhǔn)為10，如果細分的數(shù)量大于這個標(biāo)準(zhǔn)，我們將停止并指定這些在立方體中這個面的頂點到那個結(jié)點。當(dāng)我們說“大于這個標(biāo)準(zhǔn)”就意味著細分的數(shù)量有11個。
3。最后的方法是看結(jié)點數(shù)是否超過結(jié)點變量定義時的值。例如，我們設(shè)置結(jié)點變量的值為500。每次，我們建立一個結(jié)點，相應(yīng)的結(jié)點數(shù)增加1。然后在我們每次建立另一個結(jié)點時，檢測一下我們當(dāng)前的結(jié)點數(shù)是否超過結(jié)點變量。如果結(jié)點數(shù)為501，我們將不會細分這個結(jié)點，但是指定他的當(dāng)前頂點給他。我自己用1和3的方法，但是1和2也很好，因為你可以測試不同的細分的標(biāo)準(zhǔn)。
怎樣畫OCTREE
OCTREE建立后，我們就可以畫我們需要的結(jié)點。那些立方體不是全部包含在我們的視覺中的，只有一部分。這就是我們?yōu)槭裁匆嬎忝總€結(jié)點的三角形的數(shù)量，如果我們只需要一個結(jié)點中的一部分，這樣我們就不需要畫成千上萬個三角形。我們從根目錄開始畫OCTREE。對于每個結(jié)點都存儲著一個中心點。這是非常好的，比如在下面這個函數(shù)中：
//這個函數(shù)取走立方體（X，Y，Z）的中心點和他的大小（width/2)
bool CubeInFrustum(float x,float y,float z,float size);
這個函數(shù)返回true or false,是由立方體是否在破片中決定的。如果立方體在破片中，我們將檢測所有他的結(jié)點，看他們是否在破片中，否則我們將忽約樹中的整個分枝。當(dāng)我們得到了破片中的結(jié)點，但是沒有任何結(jié)點在他下面。我們想畫的頂點存儲在末結(jié)點中。記住，只有末結(jié)點有頂點存儲。看下面的圖：
有陰影的立方體是在破片中。白色的立方體不是在破片中。這里顯示了細分的2層。
OCTREE 中的沖突
OCTREE 不是用于渲染，但是用于沖突檢測很好。隨著游戲的發(fā)展，沖突檢測也在改變，你將不得不在游戲世界中運用自己的算式檢測你的角色或目標(biāo)是否沖突。下面是一些沖突檢測的例子：
1。 你將建立一個函數(shù)允許你轉(zhuǎn)遞3D空間中的點到你的OCTREE并返回在這個點周圍的頂點。你將轉(zhuǎn)遞的那個點是你的角色和目標(biāo)的中心點。這雖然可以工作一端時間，但如果這個點靠近一個立方體的邊時呢？你的角色或目標(biāo)可能和另一個立方體的頂點相沖突。為了解決這個問題，你將做一些事情。你可以轉(zhuǎn)遞角色/目標(biāo)的半徑或一定的空間，然后檢測半徑或一定的空間是否和周圍的結(jié)點相沖突。這由你的角色/目標(biāo)的形狀決定。下面是一些典型的函數(shù)：
//這個函數(shù)取走角色/目標(biāo)（X，Y，Z）的中心點并返回靠近他的頂點
CVector3 *GetVerticesFromPoint(float x,float y,float z);
//這個函數(shù)取走角色/目標(biāo)（X，Y，Z）的中心點和半徑，然后返回和他沖突的結(jié)點中的頂點
CVector3 *GetVerticesFromPointAndRadius(float x,float y,float z,float radius);
//這個函數(shù)取走角色/目標(biāo)（X，Y，Z）的中心點和立方體的大小，然后返回和他沖突的結(jié)點中的頂點
CVector3 *GetVerticesFromPointAndCube(float x,float y,float z,float size);
我相信你有更好的方法快速的檢測，在這里只是給你一點基礎(chǔ)。
總結(jié)
這篇教程只是給你講截如何建立自己的OCTREE。關(guān)于這篇文章中的代碼在www.gametutorials.com，我希望這篇文章對你有用。