| 導購 | 订阅 | 在线投稿
分享
 
 
 

詳細介紹四叉樹Quadtrees(下)

來源:互聯網  2008-05-19 00:43:49  評論

這裏函數CalcNodeNum 有兩個參數,葉節點的數目(MAX)和葉寬(MIN),在這裏葉寬爲4 個三角形,葉節點的數目包含在上面的公式中,爲了更好的理解上面的函數,給出下面的代碼:

unsigned int Temp =(GridWidth/4)*(GridWidth/4);

unsigned int Temp2 = CalcNodeNum(Temp,4);

pNodeList = (NODE*)malloc(sizeof(NODE)*Temp2);

首先計算葉節點的總數,其次保存節點的總數到變量Temp2,第三行是爲指針分配內存,現在 我們已經技術了節點的總數並分配了內存,接著調用QUADTREE的建立函數。

但是首先,讓我們回憶一下遞歸的代碼,如果我們想顯示數目1到10,我們可以這樣做:

void Count(int num)

{

cout

}

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

{

Count(ctr);

}

雖然上面的代碼沒有任何錯誤,但在QUADTREE中使用他簡直是噩夢,在上面我們調用了10次,如 果我們想調用20次,我們不得不告訴FOR循環使用20次,而遞歸只需要一次。他不需要FOR或WHILE結 構,正確的代碼如下:

void Count(int num)

{

static int ctr = 0;

if(ctrnum)

{return;}

else

{

cout

ctr++;

Count(num);

}

}

void main()

{

Count(ctr);

return;

}

現在讓我們看看函數CreateNode,象它的名字一樣,他用來建立節點,實際他不僅可以建立一個 節點,還可以建立整個樹,我們只要調用函數一次,

void CreateNode(unsigned int Bounding[4],unsigned int ParentID,unsigned int NodeID)

在一個2D數組中擴展爲高度爲0的X和Z的面,爲發現左上坐標,使用下面的公式

右上爲:

左下?

右下?

數學並不困難,現在准備調用:

unsigned int uiBoundingCoordinates[] =

{0,GridWidth,(GridHeight*(GridWidth+1)),((GridHeight)*(GridWidth+1))+GridWidth};

CreateNode(uiBoundingCoordinates,0,0);

父節點已經建立好了,我們可以通過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,靜態變量TotalTreeID保存了當前的節點數目,我們最後使用他來將子節點與他們的ID聯系起 來,uiNodeType保存節點的類型,uiWidth,uiHeight保存節點的寬和高,由于我們傳送的是包圍坐 標,實際上我們並不知道節點的大小,我們使用uiWidth,uiHeight來告訴節點是葉節點還是普通節點 ,現在需要從包圍坐標中獲得uiWidth,uiHeight:

uiWidth = fVerts[(Bounding[1]*3)] - fVerts[(Bounding[0]*3)];

uiHeight = fVerts[(Bounding[2]*3)+2] - fVerts[(Bounding[0]*3)+2];

T這裏假設fVerts是一個包含頂點列表的數組,每個頂點包含3個部件,X,Y,Z,如果我們有頂點的 索引,就可以獲得指向這個頂點的指針,

Figure 14

如同你看見的一樣,索引0指向element[0],element[0]是頂點0的X部件,依次類推。 現在,我們說我們的葉節點是4*4的三角形,這意味著葉寬爲4三角形,由于我們知道節點的寬度(存儲 在uiWidth),如果我們分割寬度的結果爲2,那麽意味著這個寬度爲4,這個節點就是一個葉節點,

if(0.5*uiWidth==2)

{

uiNodeType = LEAF_TYPE;

}

else

{

uiNodeType = NODE_TYPE;

}

接著,我們想得到一個指向我們節點的指針,pNodeList包含所有我們的節點,我們需要選擇一個。

NODE *pNode = &pNodeList[NodeID];

向節點內填充內容

pNodeList[NodeID].uID = Whatever;

我們可以簡單的做:

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;

現在我們還沒有處理葉節點,一旦我們分配了葉節點,我們將返回調用函數,在真實的世界裏,你 或許希望得到一個指向數組或三角形的葉節點指針,如果你仔細看過NODE結構,你將注意變量 uiVertexStrip1...4,如果你願意的話,可以在裏面填充三角形,.

if(uiNodeType == LEAF_TYPE)

{

return;

}

else

{

下面,我們需要處理節點的子節點

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);

很簡單,自己看吧,

//******************************************************************************

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] = Bou

  這裏函數CalcNodeNum 有兩個參數,葉節點的數目(MAX)和葉寬(MIN),在這裏葉寬爲4 個三角形,葉節點的數目包含在上面的公式中,爲了更好的理解上面的函數,給出下面的代碼:   unsigned int Temp =(GridWidth/4)*(GridWidth/4);   unsigned int Temp2 = CalcNodeNum(Temp,4);   pNodeList = (NODE*)malloc(sizeof(NODE)*Temp2);   首先計算葉節點的總數,其次保存節點的總數到變量Temp2,第三行是爲指針分配內存,現在 我們已經技術了節點的總數並分配了內存,接著調用QUADTREE的建立函數。   但是首先,讓我們回憶一下遞歸的代碼,如果我們想顯示數目1到10,我們可以這樣做:   void Count(int num)   {   cout   }   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   {   Count(ctr);   }   雖然上面的代碼沒有任何錯誤,但在QUADTREE中使用他簡直是噩夢,在上面我們調用了10次,如 果我們想調用20次,我們不得不告訴FOR循環使用20次,而遞歸只需要一次。他不需要FOR或WHILE結 構,正確的代碼如下:   void Count(int num)   {   static int ctr = 0;   if(ctrnum)   {return;}   else   {   cout   ctr++;   Count(num);   }   }   void main()   {   Count(ctr);   return;   }   現在讓我們看看函數CreateNode,象它的名字一樣,他用來建立節點,實際他不僅可以建立一個 節點,還可以建立整個樹,我們只要調用函數一次,   void CreateNode(unsigned int Bounding[4],unsigned int ParentID,unsigned int NodeID)   在一個2D數組中擴展爲高度爲0的X和Z的面,爲發現左上坐標,使用下面的公式         右上爲:         左下?         右下?         數學並不困難,現在准備調用:   unsigned int uiBoundingCoordinates[] =   {0,GridWidth,(GridHeight*(GridWidth+1)),((GridHeight)*(GridWidth+1))+GridWidth};   CreateNode(uiBoundingCoordinates,0,0);   父節點已經建立好了,我們可以通過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,靜態變量TotalTreeID保存了當前的節點數目,我們最後使用他來將子節點與他們的ID聯系起 來,uiNodeType保存節點的類型,uiWidth,uiHeight保存節點的寬和高,由于我們傳送的是包圍坐 標,實際上我們並不知道節點的大小,我們使用uiWidth,uiHeight來告訴節點是葉節點還是普通節點 ,現在需要從包圍坐標中獲得uiWidth,uiHeight:   uiWidth = fVerts[(Bounding[1]*3)] - fVerts[(Bounding[0]*3)];   uiHeight = fVerts[(Bounding[2]*3)+2] - fVerts[(Bounding[0]*3)+2];   T這裏假設fVerts是一個包含頂點列表的數組,每個頂點包含3個部件,X,Y,Z,如果我們有頂點的 索引,就可以獲得指向這個頂點的指針,      Figure 14   如同你看見的一樣,索引0指向element[0],element[0]是頂點0的X部件,依次類推。 現在,我們說我們的葉節點是4*4的三角形,這意味著葉寬爲4三角形,由于我們知道節點的寬度(存儲 在uiWidth),如果我們分割寬度的結果爲2,那麽意味著這個寬度爲4,這個節點就是一個葉節點,   if(0.5*uiWidth==2)   {   uiNodeType = LEAF_TYPE;   }   else   {   uiNodeType = NODE_TYPE;   }   接著,我們想得到一個指向我們節點的指針,pNodeList包含所有我們的節點,我們需要選擇一個。   NODE *pNode = &pNodeList[NodeID];   向節點內填充內容   pNodeList[NodeID].uID = Whatever;   我們可以簡單的做:   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;   現在我們還沒有處理葉節點,一旦我們分配了葉節點,我們將返回調用函數,在真實的世界裏,你 或許希望得到一個指向數組或三角形的葉節點指針,如果你仔細看過NODE結構,你將注意變量 uiVertexStrip1...4,如果你願意的話,可以在裏面填充三角形,.   if(uiNodeType == LEAF_TYPE)   {   return;   }   else   {   下面,我們需要處理節點的子節點   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);   很簡單,自己看吧,   //******************************************************************************   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] = Bou
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 熱帖排行
 
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有