室外大場景渲染技術(shù)研究與實現(xiàn) 游戲地圖加載
第三章 室外場景地形的實時繪制技術(shù)
地形的繪制是指讀取虛擬世界的地圖信息，繪制出場景的地表，并實現(xiàn)角色在場景中實時漫游。它是室外場景實時繪制中最重要的部分，也一直是計算機圖形學(xué)中一個重要的研究領(lǐng)域。盡管地形的繪制在不同的游戲中所采用技術(shù)會有所不同，但是他們總體上還是遵從一定的流程，如圖3.1所示：
以下章節(jié)會逐步分析相關(guān)技術(shù)。需要說明的是本章探討的“繪制”還不包括真實感的表現(xiàn)，可以理解為線框模式下的繪制。
3.1地形繪制所需數(shù)據(jù)
地形繪制所涉及的數(shù)據(jù)主要有：地形的高度圖、縮放標(biāo)尺、地表紋理圖、地表紋理索引等。在游戲設(shè)計中，表現(xiàn)一個場景所需要的一系列數(shù)據(jù)往往打包放在一起。
3.1.1高度圖
對基于三角形面片渲染的3D場景來說，地形的頂點信息就是指組成地形的所有三角形面片每個頂點的三維坐標(biāo)。最簡單最有效的地形頂點表示方法是使用高度圖(heightmap)u利。
通常高度圖是一張灰度圖，它的長寬通常滿足(2^n+1)。每個像素的灰度值表示地形相應(yīng)位置的高度值，用連續(xù)的三角形面片來連接這些三維空間中的頂點就構(gòu)成了地形的面片。高度值的值域范圍0--255足以表現(xiàn)游戲中場景的地形起伏，如果需要也可以使用雙字節(jié)，四字節(jié)或更高來描述高度值。在設(shè)計中很多游戲由于封裝數(shù)據(jù)的需要，通常自定義高度圖的格式，而不采用灰度圖，但是其存儲的數(shù)據(jù)本質(zhì)上是一樣的。
3.1.2縮放標(biāo)尺
地形信息還應(yīng)包括縮放標(biāo)尺，用來表示在繪制時高度圖中相鄰兩個灰度值之間相隔的X，Z方向上的距離值。比如一張33×33的高度圖的縮放標(biāo)尺是l米，則在游戲中我們可以看到一個32MX 32M大小的場景。此外，在Y方向上也有一個縮放標(biāo)尺，負責(zé)地形高度的縮放。
3.1.3頂點法向量
地形網(wǎng)格上的各點都需要一個表面法向量。它可以用來計算光照，進行背面剔除，檢測與表面的碰撞等。一個三角形的法向量可以通過三角形上兩向量叉乘的方法輕松獲得，而頂點級法向量可以通過共享此頂點的所有三角形的法向量求平均值來模擬，在很多情況下，這樣的效果已經(jīng)能夠達到要求了。頂點處其實是沒有法向量定義的，因為此處網(wǎng)格表面不連續(xù)。
3.1.4多種地表紋理及光照貼圖
為了表現(xiàn)地形的真實感，目前游戲中的做法是通過多重紋理混合貼圖來實現(xiàn)的。其中用到的貼圖通常以各種圖片格式保存。關(guān)于這種技術(shù)的討論在真實感渲染章節(jié)會詳細介紹。
3.1.5單個場景地形的數(shù)據(jù)結(jié)構(gòu)
由以上的分析我們就可以得到單個場景地形的數(shù)據(jù)結(jié)構(gòu)，如下所示：
3.1.6面片的構(gòu)成
任何多邊形模型都可以轉(zhuǎn)換成三角形的集合，所以地形網(wǎng)格也是三角形的集合。如果三角形被各自獨立地送至圖形硬件進行繪制，共享的頂點數(shù)據(jù)就需要執(zhí)行重復(fù)冗余的運算，并且相同的數(shù)據(jù)還被傳送至少兩次以上。降低這些額外開銷的一個方法就是把彼此相鄰的三角形構(gòu)建成三角帶(strip)。首先，把第一個三角形的三個頂點放至strip之中，然后將其余的三角形頂點依照相鄰順序依次放至strip中，每個三角形只需要加入二個頂點。缺省條件下，在strip中彼此相鄰的頂點都構(gòu)成了連接兩個相鄰三角形的公共邊。如果連接規(guī)則(順時針或者逆時針順序)需要發(fā)生改變，則可以使用swap命令交換頂點順序，或者重新將某一個頂點放入strip之中。扇形三角形帶(Triangle fans)可以看作是三角帶的一種退化形式，只是其中所有的三角形都共享一個公共頂點。圖3.2是三角形帶的表示方法：
V0，V1，V2，V3，V4五個頂點構(gòu)成了表示三個三角形的三角形帶。注意描述三角形帶時，頂點的順序很重要，因為是遵循一定連接規(guī)則(順時針或逆時針)的。在OpenGL中生成最右方的三角形帶的代碼如下：
3.2 LOD地形網(wǎng)格簡化算法的基本思想及意義
所謂地形網(wǎng)格的簡化是指通過算法減少提交到顯卡的頂點，以減少每幀同屏渲染的三角形數(shù)量，借以提高渲染速度。 #p#page_title#e#
細節(jié)層次(LOD，levels of Details)技術(shù)是一種符合人視覺特性的網(wǎng)格簡化技術(shù)。我們知道，當(dāng)場景中的物體離觀察者很遠的時候，它們經(jīng)過觀察、投影變換后在屏幕上往往只是幾個像素甚至是一個象素。我們完全沒有必要為這樣的物體去繪制它的全部細節(jié)，可以適當(dāng)?shù)暮喜⒁恍┤切味粨p失畫面的視覺效果。對于一般的應(yīng)用，我們通常會為同一個物體建立幾個不同細節(jié)層度的模型。這樣的技術(shù)應(yīng)用在地形渲染中，也稱之為多分辨率地形(Multi—Resolution Terrain)。下圖就是一個多分辨率地形網(wǎng)格：
在開發(fā)3D游戲時也有不采用基于LOD的地形網(wǎng)格簡化算法的做法。典型的游戲有韓國游戲公司開發(fā)的著名3D網(wǎng)游《奇跡》，每個Tile場景地形它用257×257的高度圖構(gòu)成，采用靜態(tài)載入場景數(shù)據(jù)的方案同樣產(chǎn)生出了美妙的場景。對于這么小的場景，當(dāng)然沒有必要做地形網(wǎng)格的簡化，現(xiàn)在的一般顯卡足以能夠應(yīng)付。之所以他能成功應(yīng)用這種方式，是因為在設(shè)計場景時限制了地形的高低起伏，使地形趨于簡單，縮放標(biāo)尺取得很大，同時用紋理和光照貼圖來彌補地形本質(zhì)上的單調(diào)。另外，如果運用基于外存的動態(tài)數(shù)據(jù)載入算法，理論上也可以不用基于LOD的地形網(wǎng)格簡化算法。
隨著3D游戲的成熟，玩家需要有更真實的體驗，因此地形變得更加復(fù)雜，場景變得更加巨大，地形的繪制需要很多數(shù)據(jù)參與，對系統(tǒng)資源消耗巨大。如果一點也不進行地形網(wǎng)格簡化，試想一個1025 X1025的場景就將生成2M個三角形，渲染大的場景時顯卡的處理能力很難跟上。在顯卡的數(shù)據(jù)吞吐能力有限的情況下，游戲場景渲染中普遍基于LOD的思想，減小繪制多邊形數(shù)目。它能在犧牲適量CPU資源的前提下大大減輕圖形卡的數(shù)據(jù)負載，使CPU與GPU之間沒有明顯的瓶頸，從而達到實時渲染大地形的目的。
基于LOD的地形網(wǎng)格簡化算法分為動態(tài)LOD和靜態(tài)LOD算法。動態(tài)LOD算法是在每幀渲染之前都經(jīng)過計算重新確定送入顯卡的頂點。所有的頂點數(shù)據(jù)全部需要參與運算。ROAM算法和基于四叉樹的動態(tài)LOD算法都屬于此類，GeoMipMap算法則是靜態(tài)LOD算法的代表。
3.3 ROAM算法
1997年，Duchaineau提出了實時優(yōu)化適應(yīng)性網(wǎng)格(ROAM，Real-timeOptimalAdaptive Meshes)算法瞳1，它是一種基于規(guī)則網(wǎng)格的連續(xù)LOD網(wǎng)格構(gòu)造算法。其基本思想是在對地形進行三維顯示時，依據(jù)視點的位置和視線的方向等多種因素，對表示地形表面的三角形圖元進行一系列基于三角形二叉剖分分裂與合并，最終形成和原始表面近似且無縫無疊的簡化連續(xù)三角形表面。
ROAM的基礎(chǔ)是等腰直角三角形的一個性質(zhì)。等腰直角三角形可以從直角頂點到斜邊引一條垂線，這條垂線把這個三角形分成了兩個小的等腰直角三角形，并無限制的遞歸分下去。而從另一個角度來看，這正好構(gòu)成了一個二叉樹，每個三角形都是把它分開而生成的兩個小三角形的父母(parent)。根據(jù)這條性質(zhì)，只要計算出哪些三角形需要被分割開、哪些三角形需要合并成為自己的父母，就可以做到控制LOD(分開就是增加LOD，合并就是減少LOD)。圖3.5顯示了1～4層三角形二叉樹和相應(yīng)的層次結(jié)構(gòu)。
當(dāng)把一個三角形分成兩個的時候，會在斜邊上增加一個頂點，是由斜邊的兩個端點插值求得。不過高度卻不能插值。因為高度是按照相應(yīng)的地圖數(shù)據(jù)來的(比如heightmap)。所以，就存在一個插值以后的高度和實際高度不匹配的問題(會產(chǎn)生裂縫)。為了解決這個問題，就需要調(diào)整Y軸上的值來升高或者降低這個頂點，這個頂點高度的調(diào)整距離就稱為誤差量。
要確定一個三角形是否要被分割，就要看它是否能精確的描述地形的高度數(shù)據(jù)。如果可以的話，自然就不用分割了，多邊形越少越好。如果不能的話，就細化它，也就是分割掉，直到所有的小三角形都能夠精確表示地形數(shù)據(jù)為止。
通過不停的分割，三角形越來越小，每個三角形在高度圖上所覆蓋的面積也越來越小。那么，總會分割到足夠小，使得三角形的面積和高度圖上一個點的面積之比為l：l，分到這里就不用再分了。通過檢查所有孩子的誤差量，我們就找到了一個描述三角形是否需要分割的精確方法。當(dāng)遞歸的遍歷這棵樹以后，就能夠找到這棵樹里面的最大誤差量，就是所謂的largest error metri c。這個最大誤差量如果是O那就是完全符合實際高度了，這個值越大，就越不符合。 #p#page_title#e#
用每個三角形的誤差量和鏡頭到該三角形的距離比較，用以判斷是否一個三角形需要分裂。用以給每個三角形做測試的值是人為定義的，這個值又叫錯誤容忍度(error metric tolerated)。通過錯誤容忍度對每個三角形做測試，小于這個容忍度的三角形就被留下(不分裂)，大于這個的就被分裂掉，然后再分別對被分裂的三角形的兩個兒子做分裂。如果加入了視角依賴(view—dependence)的話，就需要通過鏡頭到三角形的距離來調(diào)整這個容忍度了。鏡頭越遠，容忍度就越大，而鏡頭越近，容忍度就越小。’
此算法的優(yōu)點在于：可動態(tài)的改變每個網(wǎng)格；可在渲染時控制每個網(wǎng)格的生成與否；可以和紋理坐標(biāo)很好的結(jié)合在一起；可控制地形三角形的最大數(shù)目；可以根據(jù)坡度的不同自動調(diào)整LOD的細節(jié)程度，也就是說在地形坡度大的地方LOD細節(jié)程度高，在地形坡度小的地方LOD細節(jié)程度低；可以根據(jù)到觀察點的距離自動調(diào)整LOD的細節(jié)程度，也就是說在離觀察點近的地方LOD細節(jié)程度高，在離觀察點遠的地方LOD細節(jié)程度低。
3.4基于四叉樹的動態(tài)LOD算法
3.4.1算法思想
此算法是Lindstrom提出的n劓，他用了一個叫四叉樹(Ouad Tree)的結(jié)構(gòu)來描述地形，先把可視范圍內(nèi)的地形分割成四等份矩形子塊，依靠計算判定因子檢測四個子塊，如果檢查到某個子塊的網(wǎng)格精度達到所要求的繪制精度就不需要往下再分割；否則就把此子塊再分割成四等份更小的子塊，依次遞歸分割下去，直到所有子塊中的矩形網(wǎng)格都達到渲染精度。
3.4.2此算法涉及的難點
●對T形裂縫的處理
由于不同層次間的采樣間隔不同，在可視化過程中會出現(xiàn)縫隙，這種縫隙必須進行專門的處理.如圖所示，上方矩形具有較高的分辨率，而下方矩形的分辨率較低，這使得矩形間的連接處出現(xiàn)了末被覆蓋的區(qū)域(陰影處)，從而在地形繪制時就產(chǎn)生了“裂縫”。
每個.LOD層次區(qū)域節(jié)點均為正方形，在分辨率低的四叉樹區(qū)域節(jié)點上，四個方向均可能出現(xiàn)縫隙，所以必須依次用自身節(jié)點的分辨率大小比較四個方向上臨近節(jié)點的分辨率大小。如果前者小于后者，則必須通過在相鄰邊上加一條邊來實現(xiàn)裂縫的消除。當(dāng)自身節(jié)點分辨率與相鄰節(jié)點的分辨率相差不止一級，那么還必須遞歸比較并添加邊，直到完全消除裂縫。
●判定是否細分
子塊離視點的距離和地形的平坦度共同確定是否需要進一步細分以達到所要求的渲染精度，從而使最終分割后的葉子節(jié)點達到最優(yōu)。離觀察者視點越近的地方細節(jié)越多，地形越不平坦細節(jié)越多。
子塊離視點的距離d可以用公式表示如下：
其中(Xl，Y1，Z1)為視點坐標(biāo)，(XO，YO，ZO)為子塊的中心坐標(biāo)。對一個子塊區(qū)域平坦度的計算如圖3.7所示：
對于圖中這個子塊的平坦度，先計算出高度值h卜h8，找出其中最大的高度值hMax，最小的高度值bMin，令err=hMax—hMin。err即是此子塊的平坦度。
err的值越大就意味著子塊越不平坦，網(wǎng)格細節(jié)應(yīng)該越多。
最終，綜合考慮距離和平坦度兩個因素得出判斷是否細化的標(biāo)準(zhǔn)：
如果err*r／d—k>O則繼續(xù)細化，反之則不。(k為一個可變的控制值，r為子塊的i／2邊長，err為子塊平坦度，d為子塊到視點的距離)。
3.4.3算法運行步驟
(1)初始化頂點數(shù)組，建立完全四叉樹并初始化，使每個節(jié)點描述清楚自己對應(yīng)的區(qū)域地形。
(2)實時渲染：首先對每個四叉樹節(jié)點進行視錐體裁剪，確定進行渲染的四叉樹節(jié)點，再渲染這些節(jié)點。
a.對節(jié)點進行視錐體裁剪。
b.確定哪些節(jié)點需要渲染：
先計算本節(jié)點所管理的地形區(qū)域離視點的距離，再計算其平坦度，兩者共同確定渲染精度值。
根據(jù)渲染精度值和判定標(biāo)準(zhǔn)來確定是否需要進一步細分，對于需要細分的就按四叉樹思想遞歸細分，而不需要細分的就設(shè)置它的渲染標(biāo)志位為真。c.遍歷四叉樹，渲染標(biāo)志位為真的節(jié)點，并判定本節(jié)點區(qū)域網(wǎng)格在渲染時是否會出現(xiàn)T型裂縫。判定方法是通過和四周相鄰的節(jié)點比較細節(jié)分辨率值，如果小于相鄰節(jié)點則做修補裂縫處理。 #p#page_title#e#
(3)釋放資源。
3.4.4算法相關(guān)代碼
以下是1025×1025大的高度圖用基于四叉樹的LOD算法在線框模式下生成的地形網(wǎng)格：
3.5游戲中地形繪制更好的方案.
隨著圖形卡數(shù)據(jù)吞吐能力的不斷提高，每秒鐘處理上億個三角形己不再困難。很多計算，比如幾何變換和光柵處理都可以交給GPU去計算。所以在GPU數(shù)據(jù)吞吐量很大的情況下，如果一個算法在剔除渲染頂點的過程中占用了太多CPU資源，出現(xiàn)GPU等待CPU的情況，那么即使算法在剔除多余頂點方面做得很好，總體繪制效率也不是高效的。上面討論的兩種動態(tài)LOD算法(RoAM和基于四叉樹的動態(tài)LOD)都存在這方面的缺陷。并且，受硬件帶寬的限制，頻繁地傳輸海量頂點數(shù)據(jù)，使得時間集中消耗在數(shù)據(jù)“遷移"過程中。過多的DP(Draw Primitive)也使得圖形卡不能發(fā)揮最大功效，造成資源極大浪費。所以要適應(yīng)現(xiàn)代圖形卡的硬件架構(gòu)，算法必須改進，幾何多重映射(GeoMipMap，Geometrical Mipmapping)等算法由此產(chǎn)生。
本設(shè)計在GeoMipMap算法的基礎(chǔ)上，改進了原算法關(guān)于抑制不同細節(jié)分辨率模型之間突變的處理方法，使得在提高繪制效率的同時，保證了繪制圖形的質(zhì)量。通過使用查表法的分塊網(wǎng)格頂點數(shù)據(jù)組織方式，使得CPU的工作進一步減輕。此外，本設(shè)計還利用了現(xiàn)代圖形卡的存儲功能來優(yōu)化地形的繪制。
3.5.1 GeoMipMap算法
●基本思想
GeoMipMap算法是Willem根據(jù)紋理多重映射的概念提出的H3，他把整個地形場景在XZ平面上進行分塊(block)，比如用33×33的block把1025X 1025的地形表示為32×32個block。每個分塊可用不同分辨率的網(wǎng)格模型來描述。在同一分塊內(nèi)，網(wǎng)格模型的分辨率相同。采用隔行采樣的方式生成不同分辨率的網(wǎng)格。整個地形的模型表示和組織如圖3.9所示：
不同的block之間互相拼接時，如果分辨率不同則可能產(chǎn)生裂縫。為了消除裂縫，在較高分辨率的block邊界上，忽略一些點作為網(wǎng)格頂點，如圖3.10所示：
每個block分辨率是通過屏幕空間誤差H3來決定的。在地形數(shù)據(jù)預(yù)處理階段，取一個屏幕誤差閥值￡(一般取4個像素)，預(yù)先計算出當(dāng)e等于4個像素時，視點到block的距離d和相應(yīng)的block分辨率，并保存在查找表中。當(dāng)實時繪制時，根據(jù)視點到每個block的距離查找表中的d，查找決定該block的網(wǎng)格分辨率。
●優(yōu)點和不足
GeoMipMap算法的網(wǎng)格生成方式顯然和ROAM算法以及基于四叉樹的連續(xù)性LOD算法大不一樣。以基于四叉樹的連續(xù)性LOD算法為例，他是通過自頂向下的方式用四叉樹遞歸地將地形分成一個個小地形塊，越往下細分，地形塊越小，直至不能細分。當(dāng)視點發(fā)生改變時，所有的頂點都必須重新參與細分的遞歸運算，這種算法能根據(jù)實際情況最大程度確定整個地形的網(wǎng)格分辨率，但計算量很大，并且遞歸層次很多，CPU的負載極大。而對于GeoMipMap算法來說，當(dāng)
視點改變時，只需要判斷可見的每一個block的網(wǎng)格分辨率應(yīng)該是多少，block內(nèi)部的頂點并不參與計算。雖然這種做法不能最大化減少進入渲染管道的頂點，減少三角形面片，但是增加的這些渲染頂點對現(xiàn)代圖形卡來說是不會影響繪制速度的。相反，由于他減小了實時繪制時模型簡化的計算復(fù)雜度，速度得到極大提高，所以他是符合現(xiàn)代圖形卡硬件架構(gòu)的地形繪制算法。此外GeoMiaMap相對固定的三角形面片組織方式，也使得進入固定渲染管線的頂點能更好的組織成三角形帶，大大減少傳入圖形卡的頂點個數(shù)。
但是，這種算法由于不是連續(xù)的LOD算法，也就是說LOD的粒度比較粗放，因此在block的網(wǎng)格分辨率發(fā)生改變時，會產(chǎn)生網(wǎng)格形狀的突變，使得在地形漫游時，圖形過渡不自然。雖然通過屏幕投影誤差來選擇block的網(wǎng)格分辨率可以使突變的效果有所減輕，但對用戶來說仍比較明顯。本設(shè)計通過線性插值的思想，使層次過渡由突變轉(zhuǎn)為逐步遞進，極大減小了這方面的不足。 #p#page_title#e#
3.5.2 GeoM i pMap優(yōu)化算法
·地形數(shù)據(jù)的總體組織和表示
我們首先讀入一個場景的高度圖數(shù)據(jù)(heightmap)，保存在一個頂點線性表中，然后把這個場景在XZ平面上劃分成均勻大小的多個block。block的大小按需求而定，其邊長滿足2l+l，如9×9，17×17，33×33等。如果地勢總體比較平坦，我們可以選得大一點，如果對地形的細節(jié)要求較高我們可以選得小一點。本文以17×17作為block的大小。block通過頂點索引所組成的三角形帶描述他負責(zé)的一片小的區(qū)域。整個場景用一棵完全四叉樹把這些blocks組織起來。實時渲染時完全四叉樹負責(zé)場景的裁剪，決定哪些blocks應(yīng)該繪制，然后計算可見block的網(wǎng)格分辨率，從而得到整個地形要渲染的三角形面片。其數(shù)據(jù)組織圖如下所示：
用面向?qū)ο蟮姆绞矫枋龅匦螌ο螅?/p>
當(dāng)?shù)匦问浅蟮匦卫L制時，我們采用多線程機制加上場景緩沖池的方法實現(xiàn)大地形數(shù)據(jù)的動態(tài)調(diào)入和管理。每一個場景Tile作為動態(tài)加載單元，用一個緩沖池來管理，用單獨線程來維護。詳細討論在3.7節(jié)。
· block多分辨率網(wǎng)格模型的構(gòu)造和數(shù)據(jù)組織
Willem在他的論文中指出當(dāng)細節(jié)層次不同時block的頂點取舍方法，以及為了避免出現(xiàn)T型裂縫，block的邊界頂點應(yīng)該怎么調(diào)整。在他的思想基礎(chǔ)上，本設(shè)計提出一種基于查找表的block三角形帶生成方法。
我們把block的中心地帶和邊界分開對待。在預(yù)處理階段就生成五個頂點索引表。如圖3.12所示：
中心地帶索引表負責(zé)生成block中心的三角形條帶，其索引參數(shù)就是自身的網(wǎng)格分辨率。邊界索引表負責(zé)生成與其他block相鄰區(qū)域的三角形帶(防止T型裂縫)。索引參數(shù)有三個：自身的網(wǎng)格分辨率，相鄰的方向，相鄰block的網(wǎng)格分辨率。
網(wǎng)格都使用三角形帶(Triangle Strip)的方式生成，有些地方需要生成一些退化三角形，用于三角形帶的連接。運用三角形帶的方式比三角形扇和純粹三角形方式更能減少頂點個數(shù)，提高繪制效率。
這五個位置的網(wǎng)格所關(guān)聯(lián)的索引表一起就能夠描述任何一個block網(wǎng)格所有頂點的相對位置(在block區(qū)域內(nèi)的位置)。在場景渲染初始化時，我們讀入block的五個LOD頂點索引表，得到block的不同分辨率網(wǎng)格。在實時渲染的時候，針對一個特定的block，我們可以根據(jù)這個block在場景中的起始位置，他的網(wǎng)格分辨率，和他四周block的網(wǎng)格分辨率，直接查表得到這個block完整的三角形帶頂點索引，減少了CPU的判斷和計算量。內(nèi)存中只保存一個block網(wǎng)格頂點的相對索引，不是整個場景的所有block的頂點索引都保存，因此不會造成什么內(nèi)存消耗。
· 用面向?qū)ο蟮姆绞絹砻枋鯾lock
block是本算法很重要的對象，可以描述如下：
· 利用線性插值逐步過渡不同分辨率的網(wǎng)格模型
當(dāng)block的網(wǎng)格分辨率次發(fā)生變化時，其網(wǎng)格模型可能變化較大，由于變化是在瞬間完成的，極易被觀察者察覺。但如果我們把這種變化由突變改為漸變，用戶就不易察覺，其視覺影響也就可以忽略不計。
我們在預(yù)處理階段已經(jīng)得到一個合適的查找表，可以查出block的網(wǎng)格分辨率c與block到視點的距離d之間的對應(yīng)關(guān)系。我們假設(shè)d=lOOOm時c=n+l，d=2000m時c=n。
如果現(xiàn)在d=1500m，則網(wǎng)格的分辨率正處在n和n+l的過渡階段。我們?nèi)【W(wǎng)格頂點為c=n+l時的索引，他比c=rl時多出一些細節(jié)頂點，對這些多出的細節(jié)頂點，我們對其高度進行線性插值，使其緩慢在分辨率n+l和分辨率rl之間過渡。如圖3.13，v3為高分辨率時出現(xiàn)的細節(jié)頂點，v4為模型在低分辨率時v3的初始點。隨著網(wǎng)格向高分辨率過渡，v4逐步過渡到v3。v’的Y坐標(biāo)由下面的公式?jīng)Q定：
如3.13圖：
采用這種插值的手段后，只增加了很少的計算，視覺效果上卻得到了很大的提高。
·利用顯存保存地形的頂點表
現(xiàn)代圖形卡已經(jīng)支持把一定大小經(jīng)常使用的數(shù)據(jù)直接保存在顯存中，所以如果我們把經(jīng)常使用不頻繁變動的數(shù)據(jù)保存在顯存中，可以避免大量數(shù)據(jù)在渲染時頻繁從內(nèi)存?zhèn)鬏數(shù)斤@存。在實驗中通過0penGL的VBO(Vertex Buffer Object)方式把頂點線性表數(shù)據(jù)保存在顯卡中，經(jīng)比較渲染速度大幅提高。 #p#page_title#e#
·描述算法的流程
預(yù)處理階段：
(1)載入地形數(shù)據(jù)，初始化頂點線性表。
(2)初始化所有分辨率的block模型所對應(yīng)的三角形帶頂點索引表，此表保存的是組成三角形帶的相對頂點索引。生成描述整個地形場景的block數(shù)組，每個block記錄自身在場景中的絕對位置。
(3)構(gòu)造完全四叉樹，每個子節(jié)點對應(yīng)管理一片區(qū)域(一個或多個block)，設(shè)置包圍球半徑。每個葉子節(jié)點都對應(yīng)一個block索引。實時繪制階段：
(4)遍歷完全四叉樹，根據(jù)空間裁剪算法，得到可見block的索引。
(5)計算這些block的網(wǎng)格分辨率，根據(jù)分辨率和網(wǎng)格的三角形帶索引表，頂點表，可以得到組成地形網(wǎng)格的所有三角形帶頂點的完整信息。
(6)根據(jù)前面介紹的線性插值方法，調(diào)整相關(guān)頂點的高度信息。
(7)送入渲染管道繪制。
(8)回到(4)。
●測試結(jié)果
我們使用大小為2049×2049的高程圖作為實驗數(shù)據(jù)，以Athlon2500+，DDR IG，ATI 9550，128M顯存作為硬件環(huán)境對上述算法進行測試。程序用VC+OpenGL在windows平臺上完成。其中分塊大小為17×17，共分4個細節(jié)分辨率，以下是場景繪制的網(wǎng)格形式截圖：
從表3.1中的技術(shù)參數(shù)統(tǒng)計來看，新算法的渲染效率有很大提高，能滿足大規(guī)模地型的渲染要求。
3.6地形的空間管理和可見性剔除算法
我們只對地形進行分辨率上的簡化是不夠的，攝像機在場景中只有一個可見范圍，怎么樣有效的剔除不需要渲染的地形部分，這就要涉及到地形的空間管理算法，可見性裁剪算法口9|。四叉樹，八叉樹，Bsp樹，背面剔出等很多其他方法都是針對這個目的而提出的。本設(shè)計的可見性剔除采用了如下流程：
3.6.1按距離剔除
單靠視錐體剔除已經(jīng)能剔除大部分面片，但是在他之前有一步距離剔除也是有必要的，因為他的計算很簡單，就是通過計算地形block的包圍球心與視錐體的距離，距離大于系數(shù)k的blocks統(tǒng)統(tǒng)剔除。k的確定一般與天空盒子的大小有關(guān)。
3.6.2視錐體剔除
從3D到2D投影過程中，需要一個投影體，只有當(dāng)物體處于這個投影體中的時候，我們才能看到這個物體，否則物體將被裁剪掉。這個投影體通常被稱為視見體(View Frustum)。在進行正交投影的時候，投影體為一個長方體，在進行透視投影的時候，投影體則為一個平頭錐體，所以也叫視錐體。
空間中物體與視錐體的關(guān)系有三種：在視錐體內(nèi)，在視錐體外，與視錐體相交。只要我們排除在視錐體外的物體，也就是排除在視錐體外的三角形面片就能大幅提高渲染的效率。
·求視錐平面系數(shù)
視錐體有上、下、左、右、近、遠，共6個面組成。一個平面的方程可以表示為Ax+By+Cz+D=O。首先，把視錐體變換為長方體狀的裁剪空間。如圖3.16所示，左圖為世界空間中的視錐體。右圖為經(jīng)過變換后的裁剪體。
我們規(guī)定朝投影體內(nèi)部的方向為平面的正方向，判斷一個頂點是否在投影體內(nèi)部時，只要把頂點坐標(biāo)代入到六個面的方程中，通過檢查結(jié)果的符號就可以判斷點是不是在投影體內(nèi)部（所有的符號都為正）。世界空間的投影體在經(jīng)過投影變換后，會成為一個范體。我們很容易得到這個范體的六個面的方程。
我們假設(shè)這六個面中某個平面上有一個點(x0,y0,z0,1)，在進行投影變換之前的坐標(biāo)為(x0",y0",z0",1)。這個平面的方程為Ax+By+Cz+D=0。投影變換前，在世界空間中的方程為A"x+B"y+C"z+D=0，則點必須滿足：
如果變換矩陣為T，則投影前后的點要滿足(xO’，yO’，zO’，1)XT=(xO，yO，zO，1)。通過這三個等式，我們可以得到
再根據(jù)投影空間中范體的六個面的方程，我們現(xiàn)在可以很容易的得到世界空間中的投影體的六個面的方程。我們已經(jīng)有了裁剪體的方程，當(dāng)我們需要判定一個頂點是否在視錐體中的時候，這六個方程已經(jīng)足夠了。在OpenGL中得到裁剪體六個面的方程系數(shù)的偽代碼如下： #p#page_title#e#
·用包圍盒、包圍球做物體的視錐體剔除
對于物體是否在視錐體區(qū)域內(nèi)的判定，我們可以借助包圍球或者包圍盒隅1。在課題中，選用了包圍球，也就是地形的外接球。
視錐體和包圍球是否相交的經(jīng)典算法是檢查包圍球的球心到視錐體每一個平面的有向距離di，i∈[0，5]，設(shè)球體半徑為R，如果存在一個i∈[0，5]使得di≤一R，那么包圍球是在視錐體外，如果存在一個i∈[0，5]使得di≤R，那么包圍球和視錐體是相交，否則包圍球是在視錐體內(nèi)。代碼如下：
3.6.3地形的空間管理與視錐體剔除
對地形的三角形面片而言，怎么判斷哪些面片在視錐體中，我們不能把面片的所有頂點都計算判定一次，更好的算法是把整個場景分成一個個方便管理的區(qū)域，以每個區(qū)域為最小單位做視錐體剔除。由此空間管理算法出現(xiàn)，他的作用就是在空間上快速排除不需要渲染的面片。
· 用四叉樹(Quadtree)管理空間
四叉樹結(jié)構(gòu)是每個父節(jié)點對應(yīng)四個子節(jié)點的數(shù)據(jù)結(jié)構(gòu)。我們可以把地形的三維空間近似看作XZ的二維空間，根節(jié)點表示整個正方形地形區(qū)域，其子節(jié)點分別可以表示“左上"，“右上’’，“左下"和“右下”四個象限區(qū)域，那這四個子區(qū)域又可以遞歸劃分下去，如圖3.17：
四叉樹中的陰影節(jié)點就是代表了地形中的陰影區(qū)域。四叉樹的葉子節(jié)點代表了地形的最小可分區(qū)域。當(dāng)要查找某一個區(qū)域時只需要遍歷這個完全四叉樹就可以了。
空間四叉樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)可以描述如下：
·用八又樹(Octree)管理空間
八叉樹是在四叉樹的基礎(chǔ)上演變而來的。四叉樹只可以描述二維空間，八叉樹它可以描述三維空間。如圖：
八叉樹的空間管理一般用在有很多其他物體的場景中，比如建筑，樹木等物體參與到游戲中來的時候，可以通過八叉樹對這些物體進行統(tǒng)一管理，方便進行碰撞檢測、視錐體剔除等。如果只是針對地形的裁剪，用四叉樹足夠了。
·用空間四叉樹節(jié)點做視錐剔除
我們從上到下，依次遍歷四叉樹的節(jié)點，判斷節(jié)點代表的區(qū)域與視錐體的位置屬于哪一種：a.與視錐體相交， b.在視錐體外，c.在視錐體內(nèi)。
如果是情況a，遞歸判斷這個節(jié)點的四個子節(jié)點。
如果是情況b，剔除該節(jié)點。
如果是情況C，渲染這個節(jié)點代表的地形。
得到可渲染節(jié)點的代碼如下：
3.6.4地形遮擋剔除，背面剔除
●背面剔除
當(dāng)我們在三維場景中漫游時，只能看到地形起伏的正面部分，地形的背面部分被正面部分的網(wǎng)格面片遮擋，因此在繪制地形網(wǎng)格時，這部分網(wǎng)格可以不繪制。背面剔除算法的目的就是將這些看不到的背面網(wǎng)格去除掉，實現(xiàn)步驟如下：
(1)計算位于一個給定網(wǎng)格多邊形平面上的某兩個向量的矢量積，得到這個網(wǎng)格多邊形的法向量，這兩個向量可以通過多邊形頂點的差分來得到。在求解網(wǎng)格平面的法向量時必須保證兩個向量的矢量積的方向朝外，否則無法得到正確的法向量值。
(2)計算視點觀察方向與法向量之間標(biāo)量積的符號，由此決定它們之間是否形成大于90。的角。視線與網(wǎng)格平面之間的關(guān)系如3.20圖所示：
當(dāng)視線與網(wǎng)格平面法向量之間夾角大于90。時，表示這個多邊形位于起伏地形的背面，需要剔除，否則不被剔除。
在實際編程時，地形網(wǎng)格的法向量可以預(yù)先計算并存儲在內(nèi)存中，當(dāng)漫游時，只需要直接計算視線與法向量的夾角就可以判斷網(wǎng)格是否要被剔除。如果對每個三角形面片都去判斷其是否是背面的話，計算量是很大的，這增加了CPU的負擔(dān)，雖然能夠最小化參與繪制的面片，但是CPU的計算很容易形成效率瓶頸，結(jié)果繪制效率有可能反而沒有不剔除背面的做法高。因此，這種算法必須針對具體情況，適當(dāng)選取。如果場景大多是峰巒疊嶂，這時就可以考慮使用此算法。 #p#page_title#e#
●遮擋剔除
遮擋剔除大致可分為兩類：針對視點的遮擋剔除和針對視點單元區(qū)域的遮擋剔除。前者判斷兩個物體之間相對于一個視點而言的遮擋關(guān)系；后者則判斷兩者間相對于一個連通區(qū)域(即所謂視點單元區(qū)域)的遮擋關(guān)系，由此得到的兩個物體之間是否遮擋的斷言對該區(qū)域中每一視點都成立。
針對視點的遮擋剔除算法大都需要根據(jù)視點位置將挑選出的遮擋物在圖像空間離散化，并將其離散表示組織成層次結(jié)構(gòu)，剔除時將場景中物體的層次包圍盒自頂向下地與遮擋物的層次離散表示作比較，迅速拒絕被遮擋物體。由于對遮擋物采用了離散表示，可以很容易地實現(xiàn)多個遮擋物的融合，但由于離散化往往需要借助于圖形加速卡，而從圖形加速卡中讀取數(shù)據(jù)相對較慢。另一些針對視點的遮擋剔除方法直接在三維物體空間中判斷遮擋關(guān)系，但這使得多個遮擋物的融合變得困難。由于針對視點的遮擋剔除不一定需要嚴(yán)格的可見性信息，而只需知道潛在的可視的物體集合(Potentially Visible Set，簡稱PV$)。由此發(fā)展出另一類以PVS計算為核心的算法。PVS的好處就是數(shù)據(jù)為靜態(tài)，渲染的時候不需要計算，但它對動態(tài)物體的判斷不夠好。
總的來說，由于現(xiàn)在顯卡對三角形面片的吞吐量快速增加，如果為了少量剔除遮擋和背面的面片而增加CPU很多計算，那將是不值得的。所以，目前的背面剔除和遮擋剔除算法的使用只適合于地形交疊起伏厲害的場景。
3.7用動態(tài)數(shù)據(jù)加載實現(xiàn)超大地形的繪制 在前面章節(jié)中涉及的場景是有限大的，我們實現(xiàn)了2049 X2049高度圖的實時繪制。但是當(dāng)游戲中虛擬世界的地圖再擴大很多時，即使我們能對地形面片做很好的簡化，對地形區(qū)域做很好的剔除，也不能一次把數(shù)據(jù)全部讀入內(nèi)存進行渲染。所以，對于整個游戲虛擬世界的表現(xiàn)，實際游戲引擎中往往采取地圖數(shù)據(jù)的靜態(tài)加載和動態(tài)加載兩種方案。 我們把單個場景(Tile)看作組成整個游戲世界地圖的基本單元，那么整個虛擬世界就是所有場景的集合。在物理上，通常把單個場景(Tile)的數(shù)據(jù)打包在一起。不管采用什么樣的數(shù)據(jù)加載方式，都是以單個場景數(shù)據(jù)為基本單位的。在本課題中的單個場景數(shù)據(jù)主要包括高度圖、紋理索引圖、光照貼圖、紋理貼圖等。 3.7.1靜態(tài)加載方案 這是最簡單的辦法，也是目前常用的方式。所謂靜態(tài)加載是指在渲染場景前必須等待讀入場景數(shù)據(jù)，讀入后人物只能在這個固定的場景里漫游。在場景一定的位置設(shè)置下一個場景的開啟點，使得人物一旦到達此區(qū)域就觸發(fā)事件，讀入下一個場景的數(shù)據(jù)，經(jīng)過數(shù)據(jù)讀取后，角色便切換到了這一場景中。如圖3.21所示： 這種方法不要求場景間無縫銜接，通常會把單個場景設(shè)計得大一些，避免頻繁的場景切換等待。對于一般游戲的渲染細節(jié)要求，一個1025 X 1025大小的場景已經(jīng)能表現(xiàn)很開闊的場景了。 這種方法的優(yōu)點是邏輯簡單，系統(tǒng)開銷小。但是由于場景的切換等待，存在不能連續(xù)漫游超大無縫場景等缺點，極大影響游戲體驗。所以現(xiàn)在很多游戲正試圖采用其他方案跳出這種限制。 3.7.2動態(tài)加載方案實現(xiàn)無縫連接超大場景的實時繪制 ·地圖數(shù)據(jù)的動態(tài)加載機制 動態(tài)加載是指在場景渲染的同時更新內(nèi)存中要渲染區(qū)域的數(shù)據(jù)。本文通過維護一個區(qū)域數(shù)據(jù)緩沖池，根據(jù)角色所處位置，讀入磁盤文件系統(tǒng)中的場景數(shù)據(jù)，使得緩沖池中始終保存有角色周圍相關(guān)區(qū)域的場景數(shù)據(jù)(肯定不是整個世界的數(shù)據(jù))，場景渲染引擎只在緩沖池中挑選要進行渲染的數(shù)據(jù)。通常單獨開一個線程負責(zé)維護這個數(shù)據(jù)緩沖池，主線程負責(zé)場景的繪制。整個數(shù)據(jù)調(diào)度過程如下圖所示： 渲染主線程對數(shù)據(jù)加載是透明的，他只負責(zé)從緩沖池中挑選數(shù)據(jù)。這種技術(shù)的難點在于根據(jù)單位區(qū)域的數(shù)據(jù)量大小、磁盤I／O效率來決定緩沖池的大小。緩沖池太小會引起頻繁的I／0讀取，影響游戲流暢；緩沖池建得太大，占用內(nèi)存資源過多，預(yù)取的Tile數(shù)據(jù)也會增加。通過實驗得出，如果把每個Tile的高程圖大小設(shè)為256×256，緩沖池取為25個Tile大小比較合適。如果能有效的利用這種技術(shù)，那么角色可以在游戲中自由漫游，理論上游戲場景的大小只受限于磁盤的數(shù)據(jù)容量。技術(shù)的關(guān)鍵在于使CPU、GPU、I／O三者的效率達到一種平衡，在任何一個環(huán)節(jié)不能出現(xiàn)瓶頸。 #p#page_title#e# ·緩沖池的建立與維護 所謂動態(tài)加載必須使場景繪制和數(shù)據(jù)的取得分工協(xié)作，異步處理。所以緩沖池必須通過創(chuàng)建單獨線程來處理。關(guān)于緩沖池具體有以下幾個問題需要處理： (1)緩沖池維護線程的創(chuàng)建 對于緩沖池維護線程的生命周期有兩種方式。一種是當(dāng)繪制主線程發(fā)出更新緩沖池指令后得以創(chuàng)建，其生命周期在緩沖池維護工作(數(shù)據(jù)的讀取和刪除)后結(jié)束。第二種是在整個軟件初始化時期得到創(chuàng)建，其生命周期一直持續(xù)到整個軟件運行結(jié)束。通過與主線程共享數(shù)據(jù)區(qū)域中的一個緩沖池維護指令標(biāo)記來決定是否進行I／O操作。 (2)緩沖池維護線程與主線程的協(xié)作機制和通訊 出于效率的考慮，在線程間使用異步機制。主線程只在需要重新調(diào)整緩沖池的時候向緩沖維護線程發(fā)送消息，他在使用緩沖池資源的時候不需要采用鎖機制與維護線程互斥。通過為緩沖池中的每一個Tile建一個狀態(tài)標(biāo)記，主線程在查找數(shù)據(jù)的時候先看其對應(yīng)的標(biāo)記，如果標(biāo)記表明可以使用，才讓數(shù)據(jù)進入渲染引擎。反之，則不把這個Tile調(diào)入渲染引擎。通過在主線程發(fā)出更新緩沖池指令和維護線程從文件系統(tǒng)讀完數(shù)據(jù)之間預(yù)留足夠的時間，可以保證在最大程度上讓主繪制線程取到想要的數(shù)據(jù)。這么做最大的好處是效率很高，繪制線程不需要任何等待時間。軟件初始化時在內(nèi)存中開辟的一塊專用區(qū)域，兩個線程的數(shù)據(jù)都在這里得到共享。他們的消息傳遞也通過改變在這塊區(qū)域中的一些狀態(tài)標(biāo)記來實現(xiàn)。 在緩沖池中的每個Tile數(shù)據(jù)通過索引指針被繪制線程方便的使用。 (3)何時更新緩沖池，更新哪些 當(dāng)角色在場景中移動位置超出某個距離限制時，讓主線程通知緩沖池維護線程開始按主線程要求的最鄰近Tiles索引表來讀取新的Tiles文件，在池中刪除需要丟棄的Ti les空間(或許覆蓋更好)。關(guān)于何時更新，如圖3.23所示： 圖中的每個小格子代表一個Tile，也就是緩沖池維護線程要加載的最小單位。在本程序中每個Tile為256×256大小。當(dāng)角色在點a位置時，在他周圍相鄰的Tiles是以TilelO---Iilel4為邊長的正方形。一共25個Tiles，他們就是此時緩沖池中擁有的Tiles。角色向b點移動，假設(shè)角色現(xiàn)在的坐標(biāo)是(X’，Y’)，比較的基準(zhǔn)位置為a點，其坐標(biāo)為(X，Y)，那么 當(dāng)X’-X>=Tile.Width 或者Y’-Y>=Ti le.Height 時觸發(fā)緩沖區(qū)更新事件。 同時把基準(zhǔn)位置設(shè)為b點。通知緩沖池維護線程從池中剔除TilelO-一Tilel8，從文件系統(tǒng)讀入Tilel_Tile9。角色走過(X’一X)或者(Y’一Y)這段路程的時間就是預(yù)留給池維護線程動態(tài)讀取數(shù)據(jù)的時間，在本例中為256個高程圖單位，足夠了。 值得注意的是，繪制主線程只從緩沖池中挑選最鄰近他四周的9個Tile進入渲染引擎。如果在實際應(yīng)用中我們的硬盤讀取時間預(yù)留不是很足，讀取數(shù)據(jù)比較頻繁的話，可以通過增加進入緩沖區(qū)的Tile個數(shù)來調(diào)節(jié)。比如設(shè)置進入緩沖區(qū)的T兒e為36個。 另外，也可通過設(shè)定Tile的優(yōu)先級來更合理的決定進入和退出緩沖池的Tile。Tile的優(yōu)先級可以根據(jù)角色的運動方向來判定，比如人物向右移動，那右方Tile的優(yōu)先級顯然應(yīng)該比左方的高。’ 3.8本章小結(jié) 本章節(jié)討論比較了ROAM、基于四叉樹的LOD、GeoMipMap幾種基于LOD思想的網(wǎng)格簡化算法，提出一種優(yōu)化的GeoMipMap算法，并討論了其實現(xiàn)細節(jié)。另外，本章介紹了符合室外地形的空間管理算法一一基于四叉樹的空間管理。并討論了在其基礎(chǔ)上實現(xiàn)的視錐體裁剪，背面剔除算法和遮擋剔除算法。 此外，針對超大無縫地形的渲染，本文提出通過維護數(shù)據(jù)緩沖池來實現(xiàn)地圖數(shù)據(jù)動態(tài)加載的技術(shù)
