線上訂房服務-台灣趴趴狗聯合訂房中心
發文 回覆 瀏覽次數:1698
推到 Plurk!
推到 Facebook!

Quadtrees

 
axsoft
版主


發表:681
回覆:1056
積分:969
註冊:2002-03-13

發送簡訊給我
#1 引用回覆 回覆 發表時間:2002-11-27 14:26:23 IP:61.218.xxx.xxx 未訂閱
Quadtrees  by Jonathan Ferraris mailto:ferrit@pimp.co.uk    翻譯 Dreams woo    資料來源:http://www.gameres.com/Visual/3D/Roam/Quadtrees.htm    原理:什麼是Quadtrees? 由於3D圖形卡消費市場的變革,現在3D遊戲越來越流行了,他們中大部分是第一人稱射擊遊戲,這 是一個很好的理由,這個理由是室內環境,當和室外環境相比它非常簡單。對於室外環境,它沒有方便 的通往下一關的樓梯,門,或牆來阻擋你的視線。室外環境都是連續的。對於傳統的幾何學來說這是非 常棘手的,請打入quadtrees來學習下面的知識。     注意:下面的圖示都是從上到下看一個3D地形,方格顯示了在X和Y軸上的地形,並看不見現 實中的物體高度,因為我們是順?Y軸看的。     Figure 1 設想你的地形是一個非常大的方格,在一個X和Z的面上擴展,如圖1。我們有一個攝象機在地形的右 下角,它的可視截面(藍三角)擴展為在相同方向上的小單元,這樣在優化前,繪制地形的程序代碼看 起來象這樣:
for(int ctr=0; ctr
注意:一個小單元就是一個包含一些三角形的正方形,它是地形的一部分),看起來非常好,但是本 來我們隻是佔用了16個單元,可是畫了256個。這是非常大的浪費,在我們的可視截面裡隻有5個單元。 現在第一個優化:我們要測試所有的單元是否在可視截面裡,如果在就畫他,現在的代碼如下:
for(int ctr=0; ctr
如果單元在我們的可視截面中,就畫他,非常正確。現在我們隻畫了5個單元,而不是256個,我們隻 是更改很少的代碼。在上面,我們保存了我們沒有繪出的251個單元,每次都是,這是非常的浪費,如下圖:     
Figure 2    我將一些單元變成了蘭色,這樣我們可以建立一個包圍盒,如果蘭色的單元不在截面內,我們可以安全 的說這個單元在區域A中,如果我們知道蘭色的單元不在截面內,我們如何去測試區域A中的其他144個單元 呢,這由quadtrees 來工作    quadtrees 是從地形中獲得的,把它分割成四個較小的部分,每一個部分繼續分下去,直到一個分到 一個設定的大小,這看起來有點亂,讓我結合圖片解釋一下,首先,從我們的網格出發,現在將他分為四份。      
Figure 3    如圖三,我們現在有四個子地形,繼續分下去,知道一個部分隻有一個單元,,在下圖中,我們把第一個 小部分分成了四個更小的部分。      
Figure 4    然後繼續:      
Figure 5    然後繼續:      
Figure 6    好了,現在第一個部件隻有一個單元大小,我們告訴樹停止分割第一個部件,分割下一個,直到 全部分割完畢。當然你也可以將樹分割到合適的三角形數目停止,在我們的例子中為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.      
Figure 7    Test 1
方法如下:我們從根節點開始問“攝象機是否在根節點的包圍坐標內?”我們說是。我們知道攝 象機在根節點的一個子節點內,於是測試他們,“攝象機在節點2的包圍坐標內嗎?”這裡回答不, 於是我們離開節點2和它的子節點。這樣我們就可以不用測試節點2的64個單元了,不壞,不壞。       
Figure 8    Test 2
你可以看圖8,我移出了節點2和它的子節點。繼續測試,“攝象機在節點3的包圍坐標內嗎?” ,回答不,於是我們可以安全的離開節點3和它的子節點。      
Figure 9    Test 3
繼續“攝象機在節點4的包圍坐標內嗎?”回答不測試節點5。      
Figure 10    Test 4
這時,攝象機在節點5的包圍坐標內,我們測試它的子節點,我們給他的子節點命名為A,B,C,D, 測試第一個子節點“攝象機在節點A的包圍坐標內嗎?”如圖10,不在,於是我們離開節點A和它的子節 點。      
Figure 11    Test 5
現在測試節點5的第二個子節點,“攝象機在節點B的包圍坐標內嗎?”如圖11。不在      
Figure 12    Test 6
現在測試節點5的第三個子節點,“攝象機在節點C的包圍坐標內嗎?”如圖12。不在      
Figure 13    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] 作為根節點。 Formula 1. 上面的公式給出了葉節點的數目,葉寬指的是每個葉的三角形數目,這裡我們稱葉節點為單元,也可以說每 個單元包含16個三角形,那麼這裡的葉寬為4個三角形,Grid Width 指的是格子的寬度,由於每個單元有4個 三角形,Grid Width 為16個單元乘以4是64,為了求出樹中的節點數,使用下面的函數:
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;
}
這裡函數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<
這樣做很乏味,可以這樣
for(int ctr=0;ctr<10;ctr  )
{
  Count(ctr);
}
雖然上面的代碼沒有任何錯誤,但在QUADTREE中使用他簡直是噩夢,在上面我們調用了10次,如 果我們想調用20次,我們不得不告訴FOR循環使用20次,而遞歸隻需要一次。他不需要FOR或WHILE結 構,正確的代碼如下:
void Count(int num)
{
  static int ctr = 0;      if(ctr>num)
    {return;}
  else
  {
    cout<
現在讓我們看看函數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] = 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. 聯盟----Visita網站http://www.vista.org.tw ---[ 發問前請先找找舊文章 ]---
系統時間:2024-03-29 20:02:24
聯絡我們 | Delphi K.Top討論版
本站聲明
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇!