作者：Jonathan Ferraris 翻譯:Dreams woo
原理：什么是Quadtrees?
由于3D圖形卡消費(fèi)市場(chǎng)的變革，現(xiàn)在3D游戲越來越流行了，他們中大部分是第一人稱射擊游戲，這 是一個(gè)很好的理由，這個(gè)理由是室內(nèi)環(huán)境，當(dāng)和室外環(huán)境相比它非常簡(jiǎn)單。對(duì)于室外環(huán)境，它沒有方便 的通往下一關(guān)的樓梯，門，或墻來阻擋你的視線。室外環(huán)境都是連續(xù)的。對(duì)于傳統(tǒng)的幾何學(xué)來說這是非 常棘手的，請(qǐng)打入quadtrees來學(xué)習(xí)下面的知識(shí)。
注意：下面的圖示都是從上到下看一個(gè)3D地形，方格顯示了在X和Y軸上的地形，并看不見現(xiàn) 實(shí)中的物體高度，因?yàn)槲覀兪琼樦鳼軸看的。
Figure 1
設(shè)想你的地形是一個(gè)非常大的方格，在一個(gè)X和Z的面上擴(kuò)展，如圖1。我們有一個(gè)攝象機(jī)在地形的右 下角，它的可視截面（藍(lán)三角）擴(kuò)展為在相同方向上的小單元，這樣在優(yōu)化前，繪制地形的程序代碼看 起來象這樣:
for(int ctr=0; ctr<num_of_cells; ctr++)
{
DrawCell();
}
注意：一個(gè)小單元就是一個(gè)包含一些三角形的正方形，它是地形的一部分），看起來非常好，但是本 來我們只是占用了16個(gè)單元，可是畫了256個(gè)。這是非常大的浪費(fèi)，在我們的可視截面里只有5個(gè)單元。 現(xiàn)在第一個(gè)優(yōu)化：我們要測(cè)試所有的單元是否在可視截面里，如果在就畫他，現(xiàn)在的代碼如下：
for(int ctr=0; ctr<num_of_cells; ctr++)
{
if(cell is in frustum) DrawCell();
}
如果單元在我們的可視截面中，就畫他，非常正確。現(xiàn)在我們只畫了5個(gè)單元，而不是256個(gè)，我們只 是更改很少的代碼。在上面，我們保存了我們沒有繪出的251個(gè)單元，每次都是，這是非常的浪費(fèi)，如下圖：
Figure 2
我將一些單元變成了蘭色，這樣我們可以建立一個(gè)包圍盒，如果蘭色的單元不在截面內(nèi)，我們可以安全 的說這個(gè)單元在區(qū)域A中，如果我們知道蘭色的單元不在截面內(nèi)，我們?nèi)绾稳y(cè)試區(qū)域A中的其他144個(gè)單元 呢，這由quadtrees 來工作
quadtrees 是從地形中獲得的，把它分割成四個(gè)較小的部分，每一個(gè)部分繼續(xù)分下去，直到一個(gè)分到 一個(gè)設(shè)定的大小，這看起來有點(diǎn)亂，讓我結(jié)合圖片解釋一下，首先，從我們的網(wǎng)格出發(fā)，現(xiàn)在將他分為四份。
Figure 3
如圖三，我們現(xiàn)在有四個(gè)子地形，繼續(xù)分下去，知道一個(gè)部分只有一個(gè)單元，，在下圖中，我們把第一個(gè) 小部分分成了四個(gè)更小的部分。
Figure 4
然后繼續(xù)：
Figure 5
然后繼續(xù)：
Figure 6
好了，現(xiàn)在第一個(gè)部件只有一個(gè)單元大小，我們告訴樹停止分割第一個(gè)部件，分割下一個(gè)，直到 全部分割完畢。當(dāng)然你也可以將樹分割到合適的三角形數(shù)目停止，在我們的例子中為16個(gè)三角形，第 一，這個(gè)樹是父子關(guān)系，每個(gè)子節(jié)點(diǎn)有一個(gè)父節(jié)點(diǎn)，每個(gè)父節(jié)點(diǎn)有四個(gè)子節(jié)點(diǎn)，葉節(jié)點(diǎn)例外，他只有 一個(gè)父節(jié)點(diǎn)沒有子節(jié)點(diǎn)。葉節(jié)點(diǎn)是我們?cè)试S的最小的子節(jié)點(diǎn)，第二，每個(gè)樹都有一個(gè)根節(jié)點(diǎn)，它沒有 父節(jié)點(diǎn)，但有四個(gè)子節(jié)點(diǎn)。
再看一下圖，暗紅的邊界就是根節(jié)點(diǎn)，在圖3中，我們分割根節(jié)點(diǎn)，分配給他的子節(jié)點(diǎn)。藍(lán)線描繪 的正方形是根節(jié)點(diǎn)的四個(gè)子。稱為節(jié)點(diǎn)2，3，4，5。在圖4 ，我們把節(jié)點(diǎn)2分為四份，這些正方形是 節(jié)點(diǎn)的子，稱為節(jié)點(diǎn)6，7，8，9。繼續(xù)由節(jié)點(diǎn)6分割出10，11，12，13，由節(jié)點(diǎn)10分割為14，15， 16，17。這是他們的葉節(jié)點(diǎn)。停止分割。分割節(jié)點(diǎn)11，分完后是12和13，然后是7，8，和9。然后是 3，4，5。完成。
quadtrees 使用一個(gè)節(jié)點(diǎn)的包圍坐標(biāo)工作，我們說我們的圖形0-16在X軸上，0-16在Z軸上。由于 這個(gè)原因，我們整個(gè)地圖的包圍坐標(biāo)為左上為（0，0，0）右上（16，0，0）左下（0，0，16）右下 （16，0，16）當(dāng)我們分割父節(jié)點(diǎn)時(shí)，我們就分割他的包圍坐標(biāo)，于是節(jié)點(diǎn)2的包圍坐標(biāo)為：左上 （0，0，0）右上（8，0，0）左下（0，0，8）右下（8，0，8）如圖7.
Figure 7
Test 1
方法如下：我們從根節(jié)點(diǎn)開始問“攝象機(jī)是否在根節(jié)點(diǎn)的包圍坐標(biāo)內(nèi)？”我們說是。我們知道攝 象機(jī)在根節(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)內(nèi)，于是測(cè)試他們，“攝象機(jī)在節(jié)點(diǎn)2的包圍坐標(biāo)內(nèi)嗎？”這里回答不， 于是我們離開節(jié)點(diǎn)2和它的子節(jié)點(diǎn)。這樣我們就可以不用測(cè)試節(jié)點(diǎn)2的64個(gè)單元了，不壞，不壞。
Figure 8
Test 2
你可以看圖8，我移出了節(jié)點(diǎn)2和它的子節(jié)點(diǎn)。繼續(xù)測(cè)試，“攝象機(jī)在節(jié)點(diǎn)3的包圍坐標(biāo)內(nèi)嗎？” ，回答不，于是我們可以安全的離開節(jié)點(diǎn)3和它的子節(jié)點(diǎn)。
Figure 9
Test 3
繼續(xù)“攝象機(jī)在節(jié)點(diǎn)4的包圍坐標(biāo)內(nèi)嗎？”回答不測(cè)試節(jié)點(diǎn)5。
Figure 10
Test 4
這時(shí)，攝象機(jī)在節(jié)點(diǎn)5的包圍坐標(biāo)內(nèi)，我們測(cè)試它的子節(jié)點(diǎn)，我們給他的子節(jié)點(diǎn)命名為A，B，C，D， 測(cè)試第一個(gè)子節(jié)點(diǎn)“攝象機(jī)在節(jié)點(diǎn)A的包圍坐標(biāo)內(nèi)嗎？”如圖10，不在，于是我們離開節(jié)點(diǎn)A和它的子節(jié) 點(diǎn)。
Figure 11
Test 5
現(xiàn)在測(cè)試節(jié)點(diǎn)5的第二個(gè)子節(jié)點(diǎn)，“攝象機(jī)在節(jié)點(diǎn)B的包圍坐標(biāo)內(nèi)嗎？”如圖11。不在
Figure 12
Test 6
現(xiàn)在測(cè)試節(jié)點(diǎn)5的第三個(gè)子節(jié)點(diǎn)，“攝象機(jī)在節(jié)點(diǎn)C的包圍坐標(biāo)內(nèi)嗎？”如圖12。不在
Figure 13
Test 7
OK，他一定在節(jié)點(diǎn)D中，“攝象機(jī)在節(jié)點(diǎn)D的包圍坐標(biāo)內(nèi)嗎？”，是的，太好了，我們將在這里停止。 考慮一下上面的測(cè)試，共有16次測(cè)試（節(jié)點(diǎn)D內(nèi)），結(jié)果是有5個(gè)單元被看見，測(cè)試總數(shù)是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.
我們需要:
一個(gè)保存我們QUADTREE數(shù)據(jù)的結(jié)構(gòu)
一個(gè)建立樹的函數(shù)
一個(gè)保存三角形數(shù)據(jù)的結(jié)構(gòu)
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告訴我們節(jié)點(diǎn)的類型，可以為NODE_TYPE or LEAF_TYPE，如果我們畫樹的話，他用 來作為一個(gè)標(biāo)志告訴程序停止或畫一些三角形（LEAF_TYPE），或繼續(xù)向下解析樹（NODE_TYPE）。 下一個(gè)變量是一個(gè)包含4個(gè)頂點(diǎn)的數(shù)組，他用來保存節(jié)點(diǎn)的包圍坐標(biāo)，VERTEX定義如下
typedef struct vertex
{
float x,y,z;
}VERTEX;
我們還有一個(gè)叫做uiBranches的數(shù)組，他保存了四個(gè)索引值，代表了節(jié)點(diǎn)的四個(gè)子節(jié)點(diǎn)，如果本 節(jié)點(diǎn)類型是LEAF_TYPE，就不使用。
由于我們說每個(gè)葉節(jié)點(diǎn)保存16個(gè)多邊形，這里有四個(gè)數(shù)組，名為uiVertexStrip1到uiVertexStrip4， 每個(gè)數(shù)組保存四個(gè)三角形。在本向?qū)е?，他們沒被使用
變量uiID保存了QUADTREE的節(jié)點(diǎn)ID，在我解釋他以前，QUADTREE就如同一個(gè)節(jié)點(diǎn)的數(shù)組，這個(gè)ID就是 數(shù)組的索引
T讓我們看看最后一個(gè)變量，uiParentID，它是父節(jié)點(diǎn)的索引，讓我們用自己的方法來遍歷這棵樹，對(duì) 于給定的節(jié)點(diǎn)，我們可以從它的父節(jié)點(diǎn)遍歷到它的子節(jié)點(diǎn)，對(duì)于下面給定一個(gè)樹，我們?nèi)绾伪闅v他呢，
NODE *pNodeList;
這是一個(gè)pNodeList的指針，它是一個(gè)QUADTREE，注意：我們使用數(shù)組pNodeList[0] 作為根節(jié)點(diǎn)。
Formula 1.
上面的公式給出了葉節(jié)點(diǎn)的數(shù)目，葉寬指的是每個(gè)葉的三角形數(shù)目，這里我們稱葉節(jié)點(diǎn)為單元，也可以說每 個(gè)單元包含16個(gè)三角形，那么這里的葉寬為4個(gè)三角形，Grid Width 指的是格子的寬度，由于每個(gè)單元有4個(gè) 三角形，Grid Width 為16個(gè)單元乘以4是64，為了求出樹中的節(jié)點(diǎn)數(shù)，使用下面的函數(shù):
unsigned int CalcNodeNum(unsigned int max,unsigned int min)
{
int ctr=0;
int var = 0;
while(var==0)
{
ctr+=max;
max=max/min;
if(max==1)
{var=1;}
}
ctr++;
return ctr;
}
這里函數(shù)CalcNodeNum 有兩個(gè)參數(shù)，葉節(jié)點(diǎn)的數(shù)目（MAX）和葉寬（MIN），在這里葉寬為4 個(gè)三角形，葉節(jié)點(diǎn)的數(shù)目包含在上面的公式中，為了更好的理解上面的函數(shù)，給出下面的代碼:
unsigned int Temp =(GridWidth/4)*(GridWidth/4);
unsigned int Temp2 = CalcNodeNum(Temp,4);
pNodeList = (NODE*)malloc(sizeof(NODE)*Temp2);
首先計(jì)算葉節(jié)點(diǎn)的總數(shù)，其次保存節(jié)點(diǎn)的總數(shù)到變量Temp2，第三行是為指針分配內(nèi)存，現(xiàn)在 我們已經(jīng)技術(shù)了節(jié)點(diǎn)的總數(shù)并分配了內(nèi)存，接著調(diào)用QUADTREE的建立函數(shù)。
但是首先，讓我們回憶一下遞歸的代碼，如果我們想顯示數(shù)目1到10，我們可以這樣做：
void Count(int num)
{
cout<<num<<"\n";
}
void main()
{
Count(0);
Count(1);
Count(2);
Count(3);
Count(4);
Count(5);
Count(6);
Count(7);
Count(8);
Count(9);
return;
}
這樣做很乏味，可以這樣
for(int ctr=0;ctr<10;ctr++)
{
Count(ctr);
}
雖然上面的代碼沒有任何錯(cuò)誤，但在QUADTREE中使用他簡(jiǎn)直是噩夢(mèng)，在上面我們調(diào)用了10次，如 果我們想調(diào)用20次，我們不得不告訴FOR循環(huán)使用20次，而遞歸只需要一次。他不需要FOR或WHILE結(jié) 構(gòu)，正確的代碼如下：
void Count(int num)
{
static int ctr = 0;
if(ctr>num)
{return;}
else
{
cout<<ctr<<"\n";
ctr++;
Count(num);
}
}
void main()
{
Count(ctr);
return;
}
現(xiàn)在讓我們看看函數(shù)CreateNode，象它的名字一樣，他用來建立節(jié)點(diǎn)，實(shí)際他不僅可以建立一個(gè) 節(jié)點(diǎn)，還可以建立整個(gè)樹，我們只要調(diào)用函數(shù)一次，
void CreateNode(unsigned int Bounding[4],unsigned int ParentID,unsigned int NodeID)
在一個(gè)2D數(shù)組中擴(kuò)展為高度為0的X和Z的面，為發(fā)現(xiàn)左上坐標(biāo)，使用下面的公式
右上為:
左下?
右下?
數(shù)學(xué)并不困難，現(xiàn)在準(zhǔn)備調(diào)用:
unsigned int uiBoundingCoordinates[] =
{0,GridWidth,(GridHeight*(GridWidth+1)),((GridHeight)*(GridWidth+1))+GridWidth};
CreateNode(uiBoundingCoordinates,0,0);
父節(jié)點(diǎn)已經(jīng)建立好了，我們可以通過CreateNode來工作了。.
void CreateNode(unsigned int Bounding[4],unsigned int ParentID,unsigned int NodeID)
{
static unsigned int TotalTreeID = 0;
unsigned int uiNodeType;
unsigned int uiWidth,uiHeight;
OK，靜態(tài)變量TotalTreeID保存了當(dāng)前的節(jié)點(diǎn)數(shù)目，我們最后使用他來將子節(jié)點(diǎn)與他們的ID聯(lián)系起 來，uiNodeType保存節(jié)點(diǎn)的類型，uiWidth,uiHeight保存節(jié)點(diǎn)的寬和高，由于我們傳送的是包圍坐 標(biāo)，實(shí)際上我們并不知道節(jié)點(diǎn)的大小，我們使用uiWidth,uiHeight來告訴節(jié)點(diǎn)是葉節(jié)點(diǎn)還是普通節(jié)點(diǎn) ，現(xiàn)在需要從包圍坐標(biāo)中獲得uiWidth,uiHeight:
uiWidth = fVerts[(Bounding[1]*3)] - fVerts[(Bounding[0]*3)];
uiHeight = fVerts[(Bounding[2]*3)+2] - fVerts[(Bounding[0]*3)+2];
T這里假設(shè)fVerts是一個(gè)包含頂點(diǎn)列表的數(shù)組，每個(gè)頂點(diǎn)包含3個(gè)部件，X，Y，Z，如果我們有頂點(diǎn)的 索引，就可以獲得指向這個(gè)頂點(diǎn)的指針，
Figure 14
如同你看見的一樣，索引0指向element[0]，element[0]是頂點(diǎn)0的X部件，依次類推。 現(xiàn)在，我們說我們的葉節(jié)點(diǎn)是4*4的三角形，這意味著葉寬為4三角形，由于我們知道節(jié)點(diǎn)的寬度（存儲(chǔ) 在uiWidth），如果我們分割寬度的結(jié)果為2，那么意味著這個(gè)寬度為4，這個(gè)節(jié)點(diǎn)就是一個(gè)葉節(jié)點(diǎn)，
if(0.5*uiWidth==2)
{
uiNodeType = LEAF_TYPE;
}
else
{
uiNodeType = NODE_TYPE;
}
接著，我們想得到一個(gè)指向我們節(jié)點(diǎn)的指針，pNodeList包含所有我們的節(jié)點(diǎn)，我們需要選擇一個(gè)。
NODE *pNode = &pNodeList[NodeID];
向節(jié)點(diǎn)內(nèi)填充內(nèi)容
pNodeList[NodeID].uID = Whatever;
我們可以簡(jiǎn)單的做:
pNode->uiID = Whatever;
用我們得到的值填充
pNode->uiID = NodeID;
pNode->uiParentID = ParentID;
pNode->vBoundingCoordinates[0].x = fVerts[(Bounding[0]*3)];
pNode->vBoundingCoordinates[0].y = fVerts[(Bounding[0]*3)+1];
pNode->vBoundingCoordinates[0].z = fVerts[(Bounding[0]*3)+2];
pNode->vBoundingCoordinates[1].x = fVerts[(Bounding[1]*3)];
pNode->vBoundingCoordinates[1].y = fVerts[(Bounding[1]*3)+1];
pNode->vBoundingCoordinates[1].z = fVerts[(Bounding[1]*3)+2];
pNode->vBoundingCoordinates[2].x = fVerts[(Bounding[2]*3)];
pNode->vBoundingCoordinates[2].y = fVerts[(Bounding[2]*3)+1];
pNode->vBoundingCoordinates[2].z = fVerts[(Bounding[2]*3)+2];
pNode->vBoundingCoordinates[3].x = fVerts[(Bounding[3]*3)];
pNode->vBoundingCoordinates[3].y = fVerts[(Bounding[3]*3)+1];
pNode->vBoundingCoordinates[3].z = fVerts[(Bounding[3]*3)+2];
pNode->bType = uiNodeType;
現(xiàn)在我們還沒有處理葉節(jié)點(diǎn)，一旦我們分配了葉節(jié)點(diǎn)，我們將返回調(diào)用函數(shù)，在真實(shí)的世界里，你 或許希望得到一個(gè)指向數(shù)組或三角形的葉節(jié)點(diǎn)指針，如果你仔細(xì)看過NODE結(jié)構(gòu)，你將注意變量 uiVertexStrip1...4，如果你愿意的話，可以在里面填充三角形，.
if(uiNodeType == LEAF_TYPE)
{
return;
}
else
{
下面，我們需要處理節(jié)點(diǎn)的子節(jié)點(diǎn)
unsigned int BoundingBox[4];
TotalTreeID++;
pNode->uiBranches[0] = TotalTreeID;
//Top-Left i.e. b[0]
BoundingBox[0] = Bounding[0];
//Between b[0] and b[1]
BoundingBox[1] = Bounding[0]+((Bounding[1]-Bounding[0])/2);
//[between b[0] and b[2]
BoundingBox[2] = Bounding[0]+((Bounding[2]-Bounding[0])/2);
//middle of node
BoundingBox[3] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2);
CreateNode(BoundingBox,NodeID,TotalTreeID);
很簡(jiǎn)單，自己看吧，
//******************************************************************************
TotalTreeID++;
pNode->uiBranches[1] = TotalTreeID;
// Between b[0] and b[1]
BoundingBox[0] = Bounding[0]+((Bounding[1]-Bounding[0])/2);
//Top-Right i.e. b[1]
BoundingBox[1] = Bounding[1];
//middle of node
BoundingBox[2] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2);
//between b[1] & b[3]
BoundingBox[3] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0]));
CreateNode(BoundingBox,NodeID,TotalTreeID);
//******************************************************************************
TotalTreeID++;
pNode->uiBranches[2] = TotalTreeID;
//between b[0] and b[2]
BoundingBox[0] = Bounding[0]+((Bounding[2]-Bounding[0])/2);
//middle of node
BoundingBox[1] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2);
//Bottom-Left i.e. b[2]
BoundingBox[2] = Bounding[2];
//between b[2] and b[3]
BoundingBox[3] = Bounding[2]+((Bounding[3]-Bounding[2])/2);
CreateNode(BoundingBox,NodeID,TotalTreeID);
//******************************************************************************
TotalTreeID++;
pNode->uiBranches[3] = TotalTreeID;
//middle of node
BoundingBox[0] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2);
//between b[1] and b[3]
BoundingBox[1] = Bounding[0]+((Bounding[2]-Bounding[0])/2) + uiWidth;
//between b[2] and b[3]
BoundingBox[2] = Bounding[2]+((Bounding[3]-Bounding[2])/2);
//Bottom-Right i.e. b[3]
BoundingBox[3] = Bounding[3];
CreateNode(BoundingBox,NodeID,TotalTreeID);
}
All we need to do is return nothing and end CreateNode's curly brackets:
return;
}
And that's about it. You can download the fully annotated source and executable here.
posted on 2008-05-06 16:26
李陽(yáng) 閱讀(1153)
評(píng)論(0) 編輯 收藏 引用