對(duì)OCTREE的描述

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


OCTREE是怎樣工作的

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

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

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

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

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

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


何時(shí)停止細(xì)分

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

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

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

　
怎樣畫OCTREE

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

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

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

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


OCTREE 中的沖突

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

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

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

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

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


總結(jié)

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