詳細介紹四叉樹Quadtrees(下)

這裏函數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

詳細介紹四叉樹Quadtrees(下)
  這裏函數CalcNodeNum 有兩個參數,葉節點的數目(MAX)和葉寬(MIN),在這裏葉寬爲4 個三角形,葉節點的數目包含在上面的公式中,爲了更好的理解上面的函數,給出下面的代碼:  unsigned int Temp =(GridWidth...查看完整版>>詳細介紹四叉樹Quadtrees(下)
 
Sony Ericsson PC-Suit V1.10.71之二、 同步詳細介紹
Sony Ericsson PC-Suit V1.10.71之二、 同步詳細介紹
同步功能的使用方法詳解 同步管理器使用戶能夠對設備和計算機中的內容進行同步,同步之前用戶必須通過以下方式之一將設備正確連接到計算機: 1. 使用線纜 (USB) 連接 找到計算機上的 US...查看完整版>>Sony Ericsson PC-Suit V1.10.71之二、 同步詳細介紹
 
詳細介紹ORACLE sqlplus命令
jxdco 一、Oracle的啓動和關閉1、在單機環境下要想啓動或關閉ORACLE系統必須首先切換到ORACLE用戶,如下su - oraclea、啓動ORACLE系統oracle>svrmgrlSVRMGR>connect internalSVRMGR>startupSVRMGR>quitb...查看完整版>>詳細介紹ORACLE sqlplus命令
 
詳細介紹Cisco IOS框架
詳細介紹Cisco IOS框架
  專用網絡服務  IOS可以概念化爲一個操作系統,爲一個全面的協議族提供全面的網絡服務。網絡服務可以被分成許多不同的功能;下圖將它們分成通用和專用服務。專用服務包括交換、路由以及幾乎適用于跨局域網、廣域...查看完整版>>詳細介紹Cisco IOS框架
 
詳細介紹Cisco Secure PIX535防火牆
  Cisco Secure PIX防火牆535提供的承載級的性能可以滿足大型企業網絡和服務提供商的需要。作爲世界領先的Cisco Secure PIX防火牆系列的組成部分,PIX 535能夠爲當今的網絡客戶提供無與倫比的安全性、可靠性和性能...查看完整版>>詳細介紹Cisco Secure PIX535防火牆
 
詳細介紹Cisco Secure PIX 525防火牆
  強壯的安全特性  Internet的發展爲企業、政府和專用網絡帶來了更大的安全風險。現有的解決方案如運行在應用層的基于代理的防火牆具有很多限制條件,包括性能低、需要昂貴的通用平台、使用開放系統如UNIX時本身...查看完整版>>詳細介紹Cisco Secure PIX 525防火牆
 
JAVA技術培訓詳細介紹
  技術培訓服務性的網絡依靠于中性平台技術。     服務性網絡提供各種服務,包括從端口到後端數據中心再到無中文的設備等。   Java平台的原動力和靈活性保證企業不斷創造各種應用程序,這些程序也許又將開辟...查看完整版>>JAVA技術培訓詳細介紹
 
詳細介紹:Apache+PHP+MySQL配置攻略
  一、系統要求:   本系統在REDHAT7.2版本測試通過   二、服務器端軟件要求:   1:到APACHE的網絡站下載APACHE WEB SERVER http://www.apache.org/   2. 到php的網絡站下載php解析器 http://www.php.net/...查看完整版>>詳細介紹:Apache+PHP+MySQL配置攻略
 
詳細介紹CSS的三種selector
  上一節開始我們討論 CSS (Cascading Style Sheet) 的基礎. 告訴你有三種 Selector. 但只介紹了其中的 HTML selector. 這一節我們把三種都詳細介紹給你HTML selector、class selector、ID selector:  HTML sele...查看完整版>>詳細介紹CSS的三種selector
 
 
回到王朝網路移動版首頁