基于四叉樹空間劃分的地形實時渲染方法

地形是計算機圖形的一個重要組成部分，而它又具有特殊的形態。地形往往覆蓋面積極廣，且精度要求很高，使得我們必須用許多多邊形來描述。這樣的特點使得我們不能像對待其他普通模型那樣對待地形。要想實時地渲染地形，我們需要一些特殊的方法。

    地形渲染一直以來都是計算機圖形學中一個重要的研究領域。并且在這一方面已經誕生了許多優秀的算法。其中包括基于體素的渲染方法，也有基于多邊形的渲染方法。早期的游戲，如三角洲特種部隊就是采用體素渲染法的成功例子。體素法類似光線追蹤渲染，它從屏幕空間出發，找到地形與屏幕像素發出的射線交點，然后確定該像素的顏色。這種方法不依賴具體的圖形硬件，整個渲染過程完全使用CPU處理，因此它不能使用現代硬件來加速，并且對于一個場景來說，往往不只是地形，還有其他使用多邊形描述的物體，體素法渲染的圖像很難與硬件渲染的多邊形進行混合，因此這種方法現在用得極少。而多邊形渲染方法則成為一種主流。選擇多邊形來描述和渲染地形有很多的理由和優點。最重要的是它能夠很好地使用硬件加速，并且能夠和其他多邊形對象一起統一管理。

    已有大量優秀的基于多邊形的地形渲染算法。比較經典的算法有M. Duchaineau等人提出ROAM算法。這個算法采用一棵三角二叉樹來描述整個地形。一個地形在最初的層次上由兩個較大的等腰直角三角形組成，這兩個等腰直角三角形可以被不斷地細分來展現地形的更多細節。每一次細分過程都向直角三角形的斜邊的中點處增加一個由高程數據所描述的頂點，該點將所在的直角三角形一分為二，同時該算法也定義了一些規則來保證地形中不會因相鄰兩個三角形細節層次的不同而出現裂縫。這個算法已被許多游戲所采用。還有一類算法，通過將地形在X-Z投影面上不斷地規則細分來得到不同的細節，這就是本文要介紹的四叉樹空間劃分算法。另外，最新提出的一個地形算法也不得不提，Hugues Hoppe在2004年提出的幾何裁剪圖方法(Geometry Clipmaps)，算法使用了最新硬件所支持的頂點紋理來定義地形的外觀，并且對于距離攝影機不同遠近的地方采用不同的紋理層，最大限度地使用硬件加速了地形渲染的過程。這個方法聽起來非常美妙，但它目前只被較少的硬件支持。因為頂點紋理是Shader Model 3.0才支持的功能，也就是說只有DirectX 9.0c級別的顯卡才能支持這種算法。這對于某些有普及性要求的圖形應用程序，尤其是對游戲來講不是一件好的事情。因此大多數人現在還在使用經典的地形渲染方法。

    首先，基于四叉樹的地形渲染方法使用高程數據作為數據源。且算法要求高程數據的大小必須為2ⁿ+1的正方形。所謂高程數據，即色彩范圍在0-255的灰度圖片，不同的灰度代表了不同的高度值。如果某高程數據指出這個高程數據最高處的Y坐標值是4000，那么在高程數據中一個值為255的像素點就表示這個點所代表的地形區域的高度是4000，同理如果該像素值是127那么就表示這個點所代表的地形區域的高度是4000×(127/255)=2000。高程數據的每個像素都對應所渲染網格中的一個頂點。另外還有一個參數描述頂點與頂點之間的水平距離，以及一個描述最大高度的參數。因此地形的基本數據結構如下：

    struct Terrain
    {
        char **DEM; //一個描述高程數據的二維數組
        float CellSpace;
        float HeightScale; 
    }

    其中，各變量的具體意義如下圖所示：

    有了這些參數，我們可以很容易地由高程數據的參數值得到它所表述的多邊形網格。得到這個網格之后，可以簡單地把它放入頂點數組，并為之建立一個頂點索引，就可以傳入硬件進行渲染了。然而，事情并不是這么簡單。對于較小尺寸的高程數據(如129×129)，這樣做確實可行，但隨著高程數據規模的增大，所需的頂點數和描述網格的三角形數會急劇膨脹。這個數值很快就會大到最新的顯卡也無法接受。比如一個1025×1025的高程數據，我們需要1025×1025=1050625個頂點，以及1050625×2=2101250個三角形。就算你的顯卡每秒能夠渲染1000萬個三角形，你也只能得到不到5fps的渲染速度，況且你的場景可能還不只包括地形。因此我們必須想辦法在不影響視覺效果的情況下縮減所渲染的三角形數量，另外還應該注意一次性將最多的數據預先傳給硬件以節約帶寬。

    這里要講解的算法，目的就是在不影響或在視覺可以接受的范圍內縮減所渲染三角形的數量，以達到實時渲染的要求。根據測試，本算法在漫游大小為1025*1025的地形時速度穩定在150fps以上(在nVidia Geforce 6200 + P4 1.6GHz的硬件上得到)。

    由于地形覆蓋范圍廣，但它的投影在XZ平面上均勻分布(以下采用OpenGL中的右手坐標系，Y軸為豎直向上的坐標軸)，因此我們有必要考慮對地形進行空間劃分。正是由于這樣的均勻分布，給我們的劃分過程帶來了便利。我們不需要具體地去分割某個三角形，只要選擇那些過頂點且和X或Z軸垂直的平面作為劃分面即可。例如對于一個高程數據，我們可以以坐標原點作為地形的中心點，然后沿著X軸和Z軸依次展開來分布各個頂點。如下如所示。

    首先，我們可以選擇X=0和Z=0這兩個平面，將地形劃分為等大的四個區域，然后對劃分出來的四個子區域進行遞歸劃分，每次劃分都選擇交于區域中心點并且互相垂直的兩個平面作為劃分面，直到每個子區域都只包含一個地形單元塊（即兩個三角形）而不能再劃分為止。例如對于上圖所示9*9大小的地形塊，經過劃分之后如下圖所示：

    由圖可知，只有高程數據滿足大小2ⁿ+1的正方形這個條件，我們才可能對地形進行均勻劃分。我們可以把劃分結果用一棵樹來表述，由于每次劃分之后產生四個子節點，因此這棵樹叫四叉樹。那么，這棵樹中應該存儲那些信息呢？首先對于每個節點，應該指定這個節點所代表的地形的區域范圍。并不是把地形網格中實際的頂點放入樹中，而是要在樹中說明這個節點覆蓋了地形的那些區域。比如一個子節點應該有一個Center(X,Y)變量，指定這個節點的中心點所對應的頂點索引，或編號。為了方便起見，可以把地形中心點編號為(0,0)然后沿著坐標軸遞增。此外還要有個變量指定這個節點到底覆蓋了地形的多少個頂點。如下圖所示。

    我們目前的四叉樹的數據結構如下：

    struct QuadTreeNode
    {
        QuadTreeNode *Children[4];
        int CenterX,CenterY;
        int HalfRange;
    }

    有了四叉樹之后，如何利用它的優勢呢？首先我們考慮簡單的視見體裁剪(View Frustum Culling，以下簡稱VFC)。相信很多接觸過基本圖形優化的人都應該熟悉VFC，VFC的作用既是對那些明顯位于可見平截頭體之外的多邊形在把它們傳給顯卡之前剔除掉。這個過程由CPU來完成。雖然簡單，但它卻非常有效。VFC過程如下：

    1.為每個節點計算包圍球。包圍球可以簡單的以中心頂點為球心，最大坐標值點(節點所覆蓋的所有頂點的最大X、Y、Z值作為此點的坐標值)到球心的距離為半徑。

    2.根據當前的投影和變換矩陣計算此時可視平截頭體的六個平面方程。這一步可以參考Azure的Blog上的一篇文章，這篇文章給出了VFC的具體代碼。單擊這里。

    3.從樹的根結點以深度優先的順序遍歷樹。每次訪問節點時，測試該節點包圍球與視見體的相交情況。在下面的情況下，包圍球與視見體相交：

        1) 球心在六個平面所包圍的凸狀區域內部。
        2) 球心在六個平面所包圍的凸狀區域外部，但球心到某個平面的距離小于半徑。

    4.如果相交測試顯示包圍球和視見體存在交集，繼續遞歸遍歷此節點的4個子節點，如果此節點已經是葉節點，則這個節點應被繪制。如果不存在交集，放棄這個節點，對于這個節點的所有子節點不再遞歸檢查。因為如果一個節點不可見，那么其子節點一定不可見。

    這樣，我們剔除了那些不在視見體內的地形區域，節約了一些資源。但這還不夠。在某些情況下，VFC可能還會指出整個地形都可見，在這種情況下，將這么多三角形都畫出顯然是不可取的。

    因此還要考慮地形的細節層次(LOD)。我們應該考慮到，地形不可能所有部分都一樣平坦或陡峭。對于平坦的部分，我們用過多的三角形去描述是沒有意義的。而對于起伏程度較大的區域，只有較多的三角形數量才不讓人感到尖銳的棱角。再者，無論地形起伏程度如何，那些距離視點很遠的區域，也沒有必要花費太多的資源去渲染，畢竟它們投影到屏幕上的面積很小，對其進行簡化也是必要的。

    既然我們要對起伏程度不同的區域采用不同的細節級別，我們首先必須找到一種描述地形起伏程度的量。與其說起伏程度，不如說是地形的某個頂點因為被簡化后而產生的誤差。要計算這個誤差，我們先要了解地形是如何被簡化的。

    考慮下圖所示的地形塊，它的渲染結果如下圖右圖所示。

   現在如果要對所需渲染的三角形進行簡化，我們可以考慮這個地形塊每條邊中間的頂點(下圖左側紅色點)：

   如果將這些紅色的頂點剔除，我們可以得到上圖右邊所示的簡化后的網格。誤差就在這一步產生。由于紅色的頂點被剔除后，原本由紅色頂點所表示的地形高度現在變成了兩側黑色頂點插值后的高度。這個高度就是誤差。如下圖。

    因此，對于每個節點，我們先計算這個節點所有邊中點被刪除后所造成的誤差，分別記為ΔH1, ΔH2, ΔH3, ΔH4。如果這個節點包含子節點，遞歸計算子節點的誤差，并把四個子節點的誤差記為ΔHs1, ΔHs2, ΔHs3, ΔHs4。這個節點的誤差就是這八個誤差值中的最大值。由于這是一個遞歸的過程，因此應該把這個過程加到四叉樹的生成過程中，并向四叉樹的數據結構中加入一個誤差變量。如下。

    struct QuadTreeNode
    {
        QuadTreeNode *Children;
        int CenterX,CenterY;
        int HalfRange;
        float DeltaH;  //節點誤差值
    }

    下面來看一下地形的具體渲染過程。

    首先，我們位于四叉樹的根結點。我們此時考慮根結點的誤差，如果這個誤差小于一個閾值，直接使用根結點的中心點以及此節點的四個邊角點作為頂點渲染一個三角扇形，這個三角扇形就是渲染出來的地形。但是更經常的情況下，根結點的誤差值是很大的，因此算法認為要對根結點進行細分，以展現更多細節。于是對于根結點的每個子節點，重復這個步驟，即檢查它的誤差值是否大于閾值，如果大于，直接渲染這個節點，如果小于，遞歸細分節點。目前我們的算法偽代碼如下。

    procedure DrawTerrain(QuadTreeNode *node)
    {
      if (node->DeltaH > k)
      {
           for (i=0;i<4;i++)
           {
                DrawTerrain(node->Children[i]);//遞歸劃分
           }
      }
      else
      {
           GraphicsAPI->DrawPrimitive(node);//以節點的中心點和四個邊角點繪制三角扇形
      }   
    }

    這個偽代碼在一個較高的層次上表述了算法的基本思想。然而我們還有許多問題要考慮。其一是目前我們僅僅考慮了地形的細節層次和地形表面起伏程度的關系，但還應該考慮地形塊距離視點遠近跟地形細節層次的關系。解決這個問題很簡單，我們只需在偽代碼的條件中加入距離這一因素即可。即把

        if (node->DeltaH > k)
        {
            ...
        }
        else ...

    改為：

        if (node->DeltaH / d > k)
        {
            ...
        }
        else ...

    其中d為節點中心點與視點之間的距離。而事實上，當細節程度與距離的平方成反比時，能夠減少更多的三角形，而且視覺效果更好，只要閾值k設置得當，根本感覺不出地形因為視點的移動而發生幾何形變。因此，我們最終的條件式為：

    node->DeltaH / d² > k

    還有一個很重要的問題，就是這個算法所產生的地形會因為節點之間細節層次的不同而產生裂縫。下圖說明了裂縫的產生原因。

    有兩個方法可以解決這個問題，一個方法是刪除左側節點中產生裂縫的頂點，使兩條邊能夠重合。另一種方法是人為地在右側地形塊中插入一條邊，這條邊連接中心點和造成裂縫的頂點，從而消除裂縫。在渲染地形時，可以采取下面的辦法避免裂縫的產生：

    1.在預處理階段，為所有頂點創建一個標記數組，標記以該頂點為中心點的節點在某一幀是否被細分。如果被細分則標記為1，否則標記0。

    2.從根節點開始，以廣度優先的順序遍歷四叉樹，使用之前提出的條件式判斷節點是否需要分割。如果公式表明需要分割，并且與節點相鄰的四個節點的中心點都被標記為1，那么把這個節點及其四個子節點的標記設為1，并遞歸細分這個節點。否則，將這個節點的標記設為1，把這個節點的四個子節點的標記設為0，然后采用下面的方法繪制這個地形塊：

        1)將節點的中心頂點和四個邊角點添加到即將繪制的三角扇形列表中。
        2)依次檢查與四條邊相鄰的節點的標記數組，如果相應的標記為1，那么將該點添加到三角扇形的頂點列表中，否則跳過該點。
        3)繪制三角扇形。

    我們最終的偽代碼如下。

    另外，一個重要的優化是利用硬件的緩沖區或頂點數組(對于不支持頂點緩沖的硬件而言)。因為地形無論怎樣簡化，頂點數據總是固定不變的。我們在每一幀動態產生的僅僅是頂點索引，因此我們有必要實現將地形的所有頂點數據輸入到頂點緩沖中，然后在渲染時一次性將所有的索引傳給顯卡，以提高速度。實驗表明，使用頂點緩沖比直接使用glBegin/glEnd繪制圖形要快5倍以上。

    以上講述了如何做到實時地渲染大型地形。主要應用了LOD和VFC兩種手段來精簡三角形數量。然而VFC只能剔除不在視見體內的圖形，而對于在視見體內但被其他更近的物體遮擋的情況卻無能為力。如果要實現地形的自遮擋剔除，地平線算法是一個好的選擇。然而當你的場景不僅僅是包含地形時，地平線算法也只能處理地形的自遮擋情況。因為地平線算法只對2.5D的地圖(即在XZ平面上無重合投影的場景)有效。對于完全3D場景，地平線并不能很好的工作。所以當你在引擎中使用地形時，可以考慮將地形分塊后放入場景的管理樹中，如BSP或Octree等。然后根據引擎的性質使用入口(Portal)、PVS或者遮擋測試(Occlusion Culling)等方法進行遮擋剔除。值得強調的是，遮擋測試是一個非常靈活的實時的剔除算法，且無需任何預計算過程。但要想有效的實現它并不是一件容易的事。我曾將地形分塊后使用遮擋剔除來完成地形的自遮擋，但是渲染速度不但沒有提升，反而有輕微的下降。因此如果要使用遮擋剔除的話必須和引擎結合起來統一進行遮擋測試，才有可能提高效率。

    現在你應該了解了基本的地形實時渲染方法。要想讓地形的外觀更加真實，我們還需要更多的工作。我們需要為地形加上紋理貼圖和光照。首先考慮地形的光照。由于地形的多邊形網格是實時產生的，它會隨著視點的移動而變化，因此如果你直接使用OpenGL內置的頂點光照，你會得到極度不穩定的光照效果。你會看到地形表面會因為你的移動而不斷跳動。因此我們必須使用其他的光照方法來避免這個問題。我們想到了光照貼圖。光照貼圖是一個游戲中常用的光照技術。它是一個覆蓋了場景中所有多邊形的貼圖。通過給貼圖賦值，我們可以得到多邊形表面復雜的光照效果。使用好的算法計算出來的光照貼圖可以模擬極度逼真的光影效果。它給我們帶來的視覺享受遠遠地超過了OpenGL的內置光照。有關光照貼圖的計算可以參考我翻譯的一篇文章：輻射度算法(Radiosity)

   

   你可以簡單地為地形覆蓋上單一的紋理，這看起來些許增加了地形的真實性：

    在上圖中，我們創建了一個地形，并運用了一個重復的紋理。這個過程讓地形的無論哪一個區域看起來都是一樣的（例如都是草地）。這顯然不太真實，也過于乏味。或許你會創建了一幅超大的圖片，以拉伸覆蓋的方式映射到地形表面。這樣做的后果是內存開銷過于龐大，這樣做也很會受到硬件的限制。因此我們應該使用一種更好的紋理貼圖方式，紋理索引貼圖。

    紋理索引貼圖對三個可重復的紋理進行索引貼圖。所謂索引貼圖，就是對三個可重復紋理進行索引，以決定地形的哪些區域需要使用哪些紋理的混合來貼圖。因為對于任意的貼圖，都由一組包含3個顏色通道（即R、G、B）的像素組成。用于索引的貼圖的像素并不表示地形的某個區域的具體顏色，而是表示地形的某個區域用何種具體的紋理貼圖。因為具體的紋理細節存儲在這三個可重復的紋理中，因此索引貼圖的貼圖方式也為拉伸到地形表面，但它的分辨率可以大大降低。

    紋理索引貼圖的工作方式如下：對于地形投影到屏幕上的像素，查找該像素所映射到索引貼圖上的像素。然后根據這一像素R、G、B分量的不同，決定R、G、B分量所代表的具體紋理貼圖的混合因子。根據這個混合因子混合三個可重復貼圖后，將混合得到的最終顏色值輸出到屏幕上。

    例如，令索引貼圖的R分量代表沙灘的紋理，G分量代表草地，B分量代表巖石。如果索引貼圖上一個像素的值是(0,255,0)，即綠色，則這個像素所對應的地形區域的具體紋理就為草地。如果該像素顏色值是(127,127,0)，即黃色，則該像素所對應的地形區域的紋理為草地和沙灘的混合，看起來既有草，又有沙。又如下圖顯示了一個樣本索引貼圖，以及使用該貼圖索引紋理之后的渲染效果。

    原理很簡單，下面講解一下具體的實現過程。首先，我們準備4個紋理，其中1個紋理索引貼圖，它將被拉伸覆蓋整個地形，然后3張細節貼圖，并將它們綁定到相應的紋理通道上。然后使用Vertex Shader為每個頂點自動計算索引貼圖的紋理坐標，在Fragment Shader里，對索引貼圖進行紋理查找，使用查找得到的顏色值的RGB顏色信息混合3張細節貼圖，得到當前像素的顏色。最后還應該把這個顏色和光照貼圖中的值相乘，得到最終的結果。下面是相關的Shader代碼，使用GLSL編寫。

    最后，如果你對本文有不解之處，歡迎和我共同討論。

posted on 2008-05-11 13:54 RedLight 閱讀(1344) 評論(1)  編輯 收藏 引用 所屬分類: 3D渲染技術