對OCTREE的描述

　　OCTREE 是對3D空間進(jìn)行劃分，也可以叫空間分割。他允許你只對你的3D世界中攝象機(jī)照射的區(qū)域進(jìn)行作畫。他也能用于沖突檢測。下面講一下為什么要進(jìn)行空間分割。假設(shè)你建立了一個游戲世界，這個世界有超過100，000個多邊形要畫。如果你建立一個循環(huán)并傳遞這些多邊形，那速度是很慢的。即使你有一塊很好的顯示卡，他也會有很大的麻煩。但是玩你游戲的玩家的顯示卡不會超過300$。有沒有一種方法只渲染攝象機(jī)看見的多邊形？那就是美麗的OCTREE。他允許你快速的找到你要渲染的多邊形。


OCTREE是怎樣工作的

　　OCTREE工作在立方體中。最初，OCTREE從根接點(diǎn)開始，這個根接點(diǎn)對齊于立方體中整個世界，水平或場景的axis中心線。因此，把我們的整個世界想象成一個不可見的立方體。
　

　　現(xiàn)在根接點(diǎn)存儲了世界中的全部頂點(diǎn)。這是，他還是不能給我們?nèi)魏魏锰帲驗(yàn)樗€會畫所有的東西。我們想把這個接點(diǎn)分成8個部分。一次，我們劃分時，有8個立方體包含那最初的根接點(diǎn)的立方體。那意味著有4個立方體在上面，4個立方體在下面。請看下圖：

　　記住圖中黃色輪廓線沒有。
　　我們剛剛把這個世界分成8個部分。想象一下如果我們有2，3，4個部分，我們的世界將是怎樣？我們的攝象機(jī)在世界的中間，向著后面靠右的角落。如果你看這些線，你將注意到在OCTREE中8個結(jié)點(diǎn)中的第4個。這些結(jié)點(diǎn)包含2個后面的頂和底結(jié)點(diǎn)。這意味著我們只用畫存儲在這些結(jié)點(diǎn)中的頂點(diǎn)。

　　我們?nèi)绾螜z測出我們要畫的結(jié)點(diǎn)？如果你學(xué)過破片揀選（frustum culling),這將是很簡單的。你能得到這些破片的大小并檢測每個結(jié)點(diǎn)，看他是否被截斷或在你的視覺破片中。有一個關(guān)于破片揀選的教程在http://www.gametutorials.com. 如果一個立方體截斷破片，我們就將畫這些結(jié)點(diǎn)。在這個例子中，我們切的數(shù)量是我們需要畫的50%。記住，這只是我們世界中的一個部分。部分越多，我們就將越精確。當(dāng)然，我們不會需要太多的點(diǎn)。下面，我們來看一下下面的圖：

　　在上面這幅圖中，你將發(fā)現(xiàn)許多的不同。這個例子中，不是在原始的8個立方體的每一個結(jié)點(diǎn)中建立8個新的立方體。原始的8個結(jié)點(diǎn)的頂和底面沒有細(xì)分。你總是把一個結(jié)點(diǎn)分成8個或更多的結(jié)點(diǎn)，但是，如果在這個面沒有三角形可以存儲，我們將忽視這個結(jié)點(diǎn)并不給他分配內(nèi)存。如果我們進(jìn)一步的細(xì)分，更多的結(jié)點(diǎn)將形成原始的世界。如果我們變換到另一個部分，那立方體將相似的變換。為了說明這一點(diǎn)，請看圖：

　　在圖中，有兩個球，但是方向相反。注意左邊的部分，他將那世界分成2個結(jié)點(diǎn)，不是8個。這是因?yàn)榍蛑灰?個結(jié)點(diǎn)。請看右邊的球是不是和左邊的很相似。這幅圖告訴我們：只顯示需要的部分結(jié)點(diǎn)。如果沒有三角形占用空間，結(jié)點(diǎn)將不會建立。


何時停止細(xì)分

　　現(xiàn)在，我們明白了如何細(xì)分，但是我們也需要知道怎樣停止細(xì)分。有許多的方法：
　　1。如果當(dāng)時的三角形數(shù)量少于我們定義的最大的三角形數(shù)量，我們可以停止細(xì)分當(dāng)前的結(jié)點(diǎn)。舉個例子，我們定義三角形的最大數(shù)量為100。這意味著我們在細(xì)分結(jié)點(diǎn)之前，要檢測一下當(dāng)前三角形的總數(shù)量是否小于或等于我們定義的最大數(shù)量，然后再做決定。如果數(shù)量少于或等于，我們將停止細(xì)分并指定這些三角形到那個結(jié)點(diǎn)。請注意我們從不指定任何三角形到任何結(jié)點(diǎn)，除非他是末結(jié)點(diǎn)。如果我們劃分一個結(jié)點(diǎn)，我們不能存儲三角形到那個結(jié)點(diǎn)，但是可以存儲在他的子結(jié)點(diǎn)或他們的子結(jié)點(diǎn)中，甚至到他們的子中，等等。當(dāng)我們復(fù)習(xí)了怎樣畫0C樹后，將會有更多的了解。

　　2。另一個方法是在停止細(xì)分時，看我們是否細(xì)分的數(shù)目是否超過了細(xì)分的標(biāo)準(zhǔn)。例如，我們可以先建立細(xì)分的標(biāo)準(zhǔn)為10，如果細(xì)分的數(shù)量大于這個標(biāo)準(zhǔn)，我們將停止并指定這些在立方體中這個面的頂點(diǎn)到那個結(jié)點(diǎn)。當(dāng)我們說“大于這個標(biāo)準(zhǔn)”就意味著細(xì)分的數(shù)量有11個。

　　3。最后的方法是看結(jié)點(diǎn)數(shù)是否超過結(jié)點(diǎn)變量定義時的值。例如，我們設(shè)置結(jié)點(diǎn)變量的值為500。每次，我們建立一個結(jié)點(diǎn)，相應(yīng)的結(jié)點(diǎn)數(shù)增加1。然后在我們每次建立另一個結(jié)點(diǎn)時，檢測一下我們當(dāng)前的結(jié)點(diǎn)數(shù)是否超過結(jié)點(diǎn)變量。如果結(jié)點(diǎn)數(shù)為501，我們將不會細(xì)分這個結(jié)點(diǎn)，但是指定他的當(dāng)前頂點(diǎn)給他。我自己用1和3的方法，但是1和2也很好，因?yàn)槟憧梢詼y試不同的細(xì)分的標(biāo)準(zhǔn)。

　
怎樣畫OCTREE

　　OCTREE建立后，我們就可以畫我們需要的結(jié)點(diǎn)。那些立方體不是全部包含在我們的視覺中的，只有一部分。這就是我們?yōu)槭裁匆嬎忝總€結(jié)點(diǎn)的三角形的數(shù)量，如果我們只需要一個結(jié)點(diǎn)中的一部分，這樣我們就不需要畫成千上萬個三角形。我們從根目錄開始畫OCTREE。對于每個結(jié)點(diǎn)都存儲著一個中心點(diǎn)。這是非常好的，比如在下面這個函數(shù)中：

　　//這個函數(shù)取走立方體（X，Y，Z）的中心點(diǎn)和他的大?。╳idth/2)
　　bool CubeInFrustum(float x,float y,float z,float size);

　　這個函數(shù)返回true or false,是由立方體是否在破片中決定的。如果立方體在破片中，我們將檢測所有他的結(jié)點(diǎn)，看他們是否在破片中，否則我們將忽約樹中的整個分枝。當(dāng)我們得到了破片中的結(jié)點(diǎn)，但是沒有任何結(jié)點(diǎn)在他下面。我們想畫的頂點(diǎn)存儲在末結(jié)點(diǎn)中。記住，只有末結(jié)點(diǎn)有頂點(diǎn)存儲。看下面的圖：

　　有陰影的立方體是在破片中。白色的立方體不是在破片中。這里顯示了細(xì)分的2層。


OCTREE 中的沖突

　　OCTREE 不是用于渲染，但是用于沖突檢測很好。隨著游戲的發(fā)展，沖突檢測也在改變，你將不得不在游戲世界中運(yùn)用自己的算式檢測你的角色或目標(biāo)是否沖突。下面是一些沖突檢測的例子：
　　1。 你將建立一個函數(shù)允許你轉(zhuǎn)遞3D空間中的點(diǎn)到你的OCTREE并返回在這個點(diǎn)周圍的頂點(diǎn)。你將轉(zhuǎn)遞的那個點(diǎn)是你的角色和目標(biāo)的中心點(diǎn)。這雖然可以工作一端時間，但如果這個點(diǎn)靠近一個立方體的邊時呢？你的角色或目標(biāo)可能和另一個立方體的頂點(diǎn)相沖突。為了解決這個問題，你將做一些事情。你可以轉(zhuǎn)遞角色/目標(biāo)的半徑或一定的空間，然后檢測半徑或一定的空間是否和周圍的結(jié)點(diǎn)相沖突。這由你的角色/目標(biāo)的形狀決定。下面是一些典型的函數(shù)：

　　//這個函數(shù)取走角色/目標(biāo)（X，Y，Z）的中心點(diǎn)并返回靠近他的頂點(diǎn)
　　CVector3 *GetVerticesFromPoint(float x,float y,float z);

　　//這個函數(shù)取走角色/目標(biāo)（X，Y，Z）的中心點(diǎn)和半徑，然后返回和他沖突的結(jié)點(diǎn)中的頂點(diǎn)
　　CVector3 *GetVerticesFromPointAndRadius(float x,float y,float z,float radius);

　　//這個函數(shù)取走角色/目標(biāo)（X，Y，Z）的中心點(diǎn)和立方體的大小，然后返回和他沖突的結(jié)點(diǎn)中的頂點(diǎn)
　　CVector3 *GetVerticesFromPointAndCube(float x,float y,float z,float size);

　　我相信你有更好的方法快速的檢測，在這里只是給你一點(diǎn)基礎(chǔ)。


總結(jié)

　　這篇教程只是給你講截如何建立自己的OCTREE。關(guān)于這篇文章中的代碼在www.gametutorials.com，我希望這篇文章對你有用。