原理
由於
注意
設想你的地形是一個非常大的方格
for(int ctr=
DrawCell();
}
注意：一個小單元就是一個包含一些三角形的正方形，它是地形的一部分），看起來非常好，但是本 來我們只是占用了16個單元，可是畫了256個。Tw.wINGWIT.Com這是非常大的浪費，在我們的可視截面裡只有5個單元。 現在第一個優化：我們要測試所有的單元是否在可視截面裡，如果在就畫他，現在的代碼如下：
for(int ctr=0; ctr
if(cell is in frustum) DrawCell();
}
如果單元在我們的可視截面中，就畫他，非常正確。現在我們只畫了5個單元，而不是256個，我們只 是更改很少的代碼。在上面，我們保存了我們沒有繪出的251個單元，每次都是，這是非常的浪費，如下圖：
我將一些單元變成了蘭色，這樣我們可以建立一個包圍盒，如果蘭色的單元不在截面內，我們可以安全 的說這個單元在區域A中，如果我們知道蘭色的單元不在截面內，我們如何去測試區域A中的其他144個單元 呢，這由quadtrees 來工作
quadtrees 是從地形中獲得的，把它分割成四個較小的部分，每一個部分繼續分下去，直到一個分到 一個設定的大小，這看起來有點亂，讓我結合圖片解釋一下，首先，從我們的網格出發，現在將他分為四份。
如圖三，我們現在有四個子地形，繼續分下去，知道一個部分只有一個單元，，在下圖中，我們把第一個 小部分分成了四個更小的部分。
然後繼續：
然後繼續：
好了，現在第一個部件只有一個單元大小，我們告訴樹停止分割第一個部件，分割下一個，直到 全部分割完畢。當然你也可以將樹分割到合適的三角形數目停止，在我們的例子中為16個三角形，第 一，這個樹是父子關系，每個子節點有一個父節點，每個父節點有四個子節點，葉節點例外，他只有 一個父節點沒有子節點。葉節點是我們允許的最小的子節點，第二，每個樹都有一個根節點，它沒有 父節點，但有四個子節點。
再看一下圖，暗紅的邊界就是根節點，在圖3中，我們分割根節點，分配給他的子節點。藍線描繪 的正方形是根節點的四個子。稱為節點2，3，4，5。在圖4 ，我們把節點2分為四份，這些正方形是 節點的子，稱為節點6，7，8，9。繼續由節點6分割出10，11，12，13，由節點10分割為14，15， 16，17。這是他們的葉節點。停止分割。分割節點11，分完後是12和13，然後是7，8，和9。然後是 3，4，5。完成。
quadtrees 使用一個節點的包圍坐標工作，我們說我們的圖形0-16在X軸上，0-16在Z軸上。由於 這個原因，我們整個地圖的包圍坐標為左上為（0，0，0）右上（16，0，0）左下（0，0，16）右下 （16，0，16）當我們分割父節點時，我們就分割他的包圍坐標，於是節點2的包圍坐標為：左上 （0，0，0）右上（8，0，0）左下（0，0，8）右下（8，0，8）如圖7.
Test 1
方法如下：我們從根節點開始問“攝象機是否在根節點的包圍坐標內？”我們說是。我們知道攝 象機在根節點的一個子節點內，於是測試他們，“攝象機在節點2的包圍坐標內嗎？”這裡回答不， 於是我們離開節點2和它的子節點。這樣我們就可以不用測試節點2的64個單元了，不壞，不壞。
Test 2
你可以看圖8，我移出了節點2和它的子節點。繼續測試，“攝象機在節點3的包圍坐標內嗎？” ，回答不，於是我們可以安全的離開節點3和它的子節點。
Test 3
繼續“攝象機在節點4的包圍坐標內嗎？”回答不測試節點5。
Test 4
這時，攝象機在節點5的包圍坐標內，我們測試它的子節點，我們給他的子節點命名為A，B，C，D， 測試第一個子節點“攝象機在節點A的包圍坐標內嗎？”如圖10，不在，於是我們離開節點A和它的子節 點。
Test 5
現在測試節點5的第二個子節點，“攝象機在節點B的包圍坐標內嗎？”如圖11。不在
Test 6
現在測試節點5的第三個子節點，“攝象機在節點C的包圍坐標內嗎？”如圖12。不在
Test 7
OK，他一定在節點D中，“攝象機在節點D的包圍坐標內嗎？”，是的，太好了，我們將在這裡停止。 考慮一下上面的測試，共有16次測試（節點D內），結果是有5個單元被看見，測試總數是7+16為23。 我們從256減少為23次。
A quadtree is used to dismiss large chunks of terrain at a time. If an apple is on a tree's leaf, chopping off the branches the apple is nowhere near saves you looking on every leaf.
編碼
Before we go any further, I advise those who are unsure about Indexed Lists to read through my tutorial here.
我們需要:
一個保存我們QUADTREE數據的結構
一個建立樹的函數
一個保存三角形數據的結構
typedef struct node
{
int bType;
VERTEX vBoundingCoordinates[4];
unsigned int uiBranches[4];
unsigned int uiVertexStrip1[8];
unsigned int uiVertexStrip2[8];
unsigned int uiVertexStrip3[8];
unsigned int uiVertexStrip4[8];
unsigned int uiID;
unsigned int uiParentID;
}NODE;
變量bType告訴我們節點的類型，可以為NODE_TYPE or LEAF_TYPE，如果我們畫樹的話，他用 來作為一個標志告訴程序停止或畫一些三角形（LEAF_TYPE），或繼續向下解析樹（NODE_TYPE）。 下一個變量是一個包含4個頂點的數組，他用來保存節點的包圍坐標，VERTEX定義如下
typedef struct vertex
{
float x,y,z;
}VERTEX;
我們還有一個叫做uiBranches的數組，他保存了四個索引值，代表了節點的四個子節點，如果本 節點類型是LEAF_TYPE，就不使用。
由於我們說每個葉節點保存16個多邊形，這裡有四個數組，名為uiVertexStrip1到uiVertexStrip4， 每個數組保存四個三角形。在本向導中，他們沒被使用
變量uiID保存了QUADTREE的節點ID，在我解釋他以前，QUADTREE就如同一個節點的數組，這個ID就是 數組的索引
T讓我們看看最後一個變量，uiParentID，它是父節點的索引，讓我們用自己的方法來遍歷這棵樹，對 於給定的節點，我們可以從它的父節點遍歷到它的子節點，對於下面給定一個樹，我們如何遍歷他呢，
NODE *pNodeList;
這是一個pNodeList的指針，它是一個QUADTREE，注意：我們使用數組pNodeList[0] 作為根節點。
上面的公式給出了葉節點的數目，葉寬指的是每個葉的三角形數目，這裡我們稱葉節點為單元，也可以說每 個單元包含16個三角形，那麼這裡的葉寬為4個三角形，Grid Width 指的是格子的寬度，由於每個單元有4個 三角形，Grid Width 為16個單元乘以4是64，為了求出樹中的節點數，使用下面的函數:
un
From:http://tw.wingwit.com/Article/program/yxkf/201311/11083.html