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

詳細介紹四叉樹Quadtrees(上)

2008-05-19 00:44:09  編輯來源:互聯網  简体版  手機版  評論  字體: ||
 
  原理:什麽是Quadtrees?
  由于3D圖形卡消費市場的變革,現在3D遊戲越來越流行了,他們中大部分是第一人稱射擊遊戲,這 是一個很好的理由,這個理由是室內環境,當和室外環境相比它非常簡單。對于室外環境,它沒有方便 的通往下一關的樓梯,門,或牆來阻擋你的視線。室外環境都是連續的。對于傳統的幾何學來說這是非 常棘手的,請打入quadtrees來學習下面的知識。
  注意:下面的圖示都是從上到下看一個3D地形,方格顯示了在X和Y軸上的地形,並看不見現 實中的物體高度,因爲我們是順著Y軸看的。
  
  Figure 1
  設想你的地形是一個非常大的方格,在一個X和Z的面上擴展,如圖1。我們有一個攝象機在地形的右 下角,它的可視截面(藍三角)擴展爲在相同方向上的小單元,這樣在優化前,繪制地形的程序代碼看 起來象這樣:
  for(int ctr=0; ctr
  {
  DrawCell();
  }
  注意:一個小單元就是一個包含一些三角形的正方形,它是地形的一部分),看起來非常好,但是本 來我們只是占用了16個單元,可是畫了256個。這是非常大的浪費,在我們的可視截面裏只有5個單元。 現在第一個優化:我們要測試所有的單元是否在可視截面裏,如果在就畫他,現在的代碼如下:
  for(int ctr=0; ctr
  {
  if(cell is in frustum) DrawCell();
  }
  如果單元在我們的可視截面中,就畫他,非常正確。現在我們只畫了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,爲了求出樹中的節點數,使用下面的函數:
  un
 
  原理:什麽是Quadtrees?   由于3D圖形卡消費市場的變革,現在3D遊戲越來越流行了,他們中大部分是第一人稱射擊遊戲,這 是一個很好的理由,這個理由是室內環境,當和室外環境相比它非常簡單。對于室外環境,它沒有方便 的通往下一關的樓梯,門,或牆來阻擋你的視線。室外環境都是連續的。對于傳統的幾何學來說這是非 常棘手的,請打入quadtrees來學習下面的知識。   注意:下面的圖示都是從上到下看一個3D地形,方格顯示了在X和Y軸上的地形,並看不見現 實中的物體高度,因爲我們是順著Y軸看的。         Figure 1   設想你的地形是一個非常大的方格,在一個X和Z的面上擴展,如圖1。我們有一個攝象機在地形的右 下角,它的可視截面(藍三角)擴展爲在相同方向上的小單元,這樣在優化前,繪制地形的程序代碼看 起來象這樣:   for(int ctr=0; ctr   {   DrawCell();   }   注意:一個小單元就是一個包含一些三角形的正方形,它是地形的一部分),看起來非常好,但是本 來我們只是占用了16個單元,可是畫了256個。這是非常大的浪費,在我們的可視截面裏只有5個單元。 現在第一個優化:我們要測試所有的單元是否在可視截面裏,如果在就畫他,現在的代碼如下:   for(int ctr=0; ctr   {   if(cell is in frustum) DrawCell();   }   如果單元在我們的可視截面中,就畫他,非常正確。現在我們只畫了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,爲了求出樹中的節點數,使用下面的函數:   un
󰈣󰈤
 
 
 
>>返回首頁<<
 
 
 
 
 熱帖排行
 
王朝網路微信公眾號
微信掃碼關註本站公眾號 wangchaonetcn
 
  免責聲明:本文僅代表作者個人觀點,與王朝網絡無關。王朝網絡登載此文出於傳遞更多信息之目的,並不意味著贊同其觀點或證實其描述,其原創性以及文中陳述文字和內容未經本站證實,對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾,請讀者僅作參考,並請自行核實相關內容。
 
© 2005- 王朝網路 版權所有