【文章內(nèi)容簡(jiǎn)介】 要研究的是基于多邊形面片的場(chǎng)景渲染。本章從圖形學(xué)原理出發(fā)，討論了基于多邊形面片的 3D 渲染的基本流程以及其中涉及的數(shù)學(xué)模型。另外，還介紹了應(yīng)用廣泛的圖形庫(kù) OpenGL，為下面章節(jié)的具體算法討論和軟件實(shí)現(xiàn)做基礎(chǔ)鋪墊。 第三 章 室外場(chǎng)景地形的實(shí)時(shí)繪制技術(shù) 地形的繪制是指讀取虛擬世界的地圖信息，繪制出場(chǎng)景的地表，并實(shí)現(xiàn)角色在場(chǎng)景中實(shí)時(shí)漫游。它是室外場(chǎng)景實(shí)時(shí)繪制中最重要的部分，也一直是計(jì)算機(jī)圖形學(xué)中一個(gè)重要的研究領(lǐng)域。盡管地形的繪制在不同的游戲中所采用技術(shù)會(huì)有所不同，但是他們總體上還是遵從一定的流程，如圖 所示： 以下章節(jié)會(huì)逐步分析相關(guān)技術(shù)。需要說(shuō)明的是本章探討的 “繪制 ”還不包括真實(shí)感的表現(xiàn)，可以理解為線框模式下的繪制。 地形繪制所需數(shù)據(jù) 地形繪制所涉及的數(shù)據(jù)主要有：地形的高度圖、縮放標(biāo)尺、地表紋理圖、地表紋理索引等。在游戲設(shè)計(jì)中，表現(xiàn)一個(gè)場(chǎng)景所需要的一系列數(shù)據(jù)往往打包放在一起。 高度圖 對(duì)基于三角形面片渲染的 3D 場(chǎng)景來(lái)說(shuō)，地形的頂點(diǎn)信息就是指組成地形的所有三角形面片每個(gè)頂點(diǎn)的三維坐標(biāo)。最簡(jiǎn)單最有效的地形頂點(diǎn)表示方法是使用高度圖 (heightmap)u 利。 通常高度圖是一 張灰度圖，它的長(zhǎng)寬通常滿足 (2^n+1)。每個(gè)像素的灰度值表示地形相應(yīng)位置的高度值，用連續(xù)的三角形面片來(lái)連接這些三維空間中的頂點(diǎn)就構(gòu)成了地形的面片。高度值的值域范圍 0255 足以表現(xiàn)游戲中場(chǎng)景的地形起伏，如果需要也可以使用雙字節(jié)，四字節(jié)或更高來(lái)描述高度值。在設(shè)計(jì)中很多游戲由于封裝數(shù)據(jù)的需要，通常自定義高度圖的格式，而不采用灰度圖，但是其存儲(chǔ)的數(shù)據(jù)本質(zhì)上是一樣的。 縮放標(biāo)尺 地形信息還應(yīng)包括縮放標(biāo)尺，用來(lái)表示在繪制時(shí)高度圖中相鄰兩個(gè)灰度值之間相隔的 X， Z 方向上的距離值。比如一張 3333 的 高度圖的縮放標(biāo)尺是 l 米，則在游戲中我們可以看到一個(gè) 32MX 32M 大小的場(chǎng)景。此外，在 Y 方向上也有一個(gè)縮放標(biāo)尺，負(fù)責(zé)地形高度的縮放。 頂點(diǎn)法向量 地形網(wǎng)格上的各點(diǎn)都需要一個(gè)表面法向量。它可以用來(lái)計(jì)算光照，進(jìn)行背面剔除，檢測(cè)與表面的碰撞等。一個(gè)三角形的法向量可以通過(guò)三角形上兩向量叉乘的方法輕松獲得，而頂點(diǎn)級(jí)法向量可以通過(guò)共享此頂點(diǎn)的所有三角形的法向量求平均值來(lái)模擬，在很多情況下，這樣的效果已經(jīng)能夠達(dá)到要求了。頂點(diǎn)處其實(shí)是沒(méi)有法向量定義的，因?yàn)榇颂幘W(wǎng)格表面不連續(xù)。 多種地表紋理及 光照貼圖 為了表現(xiàn)地形的真實(shí)感，目前游戲中的做法是通過(guò)多重紋理混合貼圖來(lái)實(shí)現(xiàn)的。其中用到的貼圖通常以各種圖片格式保存。關(guān)于這種技術(shù)的討論在真實(shí)感渲染章節(jié)會(huì)詳細(xì)介紹。 單個(gè)場(chǎng)景地形的數(shù)據(jù)結(jié)構(gòu) 由以上的分析我們就可以得到單個(gè)場(chǎng)景地形的數(shù)據(jù)結(jié)構(gòu)，如下所示： 面片的構(gòu)成 任何多邊形模型都可以轉(zhuǎn)換成三角形的集合，所以地形網(wǎng)格也是三角形的集合。如果三角形被各自獨(dú)立地送至圖形硬件進(jìn)行繪制，共享的頂點(diǎn)數(shù)據(jù)就需要執(zhí)行重復(fù)冗余的運(yùn)算，并且相同的數(shù)據(jù)還被傳送至少兩次以上。降低這些額外開(kāi)銷(xiāo)的一個(gè)方法就是把彼此相鄰的三角形構(gòu)建成三角帶 (strip)。首先，把第一個(gè)三角形的三個(gè) 頂點(diǎn)放至 strip 之中，然后將其余的三角形頂點(diǎn)依照相鄰順序依次放至 strip 中，每個(gè)三角形只需要加入二個(gè)頂點(diǎn)。缺省條件下，在 strip 中彼此相鄰的頂點(diǎn)都構(gòu)成了連接兩個(gè)相鄰三角形的公共邊。如果連接規(guī)則 (順時(shí)針或者逆時(shí)針順序 )需要發(fā)生改變，則可以使用 swap 命令交換頂點(diǎn)順序，或者重新將某一個(gè)頂點(diǎn)放入 strip 之中。扇形三角形帶 (Triangle fans)可以看作是三角帶的一種退化形式，只是其中所有的三角形都共享一個(gè)公共頂點(diǎn)。圖 是三角形帶的表示方法： V0， V1， V2， V3， V4 五個(gè)頂點(diǎn)構(gòu)成了表示三個(gè)三角形的三角形帶。注意描述三角形帶時(shí)，頂點(diǎn)的順序很重要，因?yàn)槭亲裱欢ㄟB接規(guī)則 (順時(shí)針或逆時(shí)針 )的。在 OpenGL 中生成最右方的三角形帶的代碼如下： LOD 地形網(wǎng)格簡(jiǎn)化算法的基本思想及意義 所謂地形網(wǎng)格的簡(jiǎn)化是指通過(guò)算法減少提交到顯卡的頂點(diǎn)，以減少每幀同屏渲染的三角形數(shù)量，借以提高渲染速度。 細(xì)節(jié)層次 (LOD， levels of Details)技術(shù)是一種符合人視覺(jué)特性的網(wǎng)格簡(jiǎn)化技術(shù)。我們知道，當(dāng)場(chǎng)景中的物體離觀察者很遠(yuǎn)的時(shí)候，它們經(jīng)過(guò)觀察、投影變換后在屏幕上往往只是幾個(gè)像素甚至是一個(gè)象素。我們完全沒(méi)有必要為這樣的物體去繪制它的全部細(xì)節(jié)，可以適當(dāng)?shù)暮喜⒁恍┤切?而不損失畫(huà)面的視覺(jué)效果。對(duì)于一般的應(yīng)用，我們通常會(huì)為同一個(gè)物體建立幾個(gè)不同細(xì)節(jié)層度的模型。這樣的技術(shù)應(yīng)用在地形渲染中，也稱(chēng)之為多分辨率地形 (Multi—Resolution Terrain)。下圖就是一個(gè)多分辨率地形網(wǎng)格： 在開(kāi)發(fā) 3D 游戲時(shí)也有不采用基于 LOD 的地形網(wǎng)格簡(jiǎn)化算法的做法。典型 的游戲有韓國(guó)游戲公司開(kāi)發(fā)的著名 3D 網(wǎng)游《奇跡》，每個(gè) Tile 場(chǎng)景地形它用 257257 的高度圖構(gòu)成，采用靜態(tài)載入場(chǎng)景數(shù)據(jù)的方案同樣產(chǎn)生出了美妙的場(chǎng)景。對(duì)于這么小的場(chǎng)景，當(dāng)然沒(méi)有必要做地形網(wǎng)格的簡(jiǎn)化，現(xiàn)在的一般顯卡足以能夠應(yīng)付。之所以他能成功應(yīng)用這種方式，是因?yàn)樵谠O(shè)計(jì)場(chǎng)景時(shí)限制了地形的高低起伏，使地形趨于簡(jiǎn)單，縮放標(biāo)尺取得很大，同時(shí)用紋理和光照貼圖來(lái)彌補(bǔ)地形本質(zhì)上的單調(diào)。另外，如果運(yùn)用基于外存的動(dòng)態(tài)數(shù)據(jù)載入算法，理論上也可以不用基于 LOD 的地形網(wǎng)格簡(jiǎn)化算法。 隨著 3D 游戲的成熟，玩家需要有更真實(shí)的體驗(yàn)，因 此地形變得更加復(fù)雜，場(chǎng)景變得更加巨大，地形的繪制需要很多數(shù)據(jù)參與，對(duì)系統(tǒng)資源消耗巨大。如果一點(diǎn)也不進(jìn)行地形網(wǎng)格簡(jiǎn)化，試想一個(gè) 1025 X1025的場(chǎng)景就將生成 2M 個(gè)三角形，渲染大的場(chǎng)景時(shí)顯卡的處理能力很難跟上。在顯卡的數(shù)據(jù)吞吐能力有限的情況下，游戲場(chǎng)景渲染中普遍基于 LOD 的思想，減小繪制多邊形數(shù)目。它能在犧牲適量 CPU 資源的前提下大大減輕圖形卡的數(shù)據(jù)負(fù)載，使 CPU 與 GPU 之間沒(méi)有明顯的瓶頸，從而達(dá)到實(shí)時(shí)渲染大地形的目的。 基于 LOD 的地形網(wǎng)格簡(jiǎn)化算法分為動(dòng)態(tài) LOD 和靜態(tài) LOD 算法。動(dòng)態(tài) LOD 算法是在每幀 渲染之前都經(jīng)過(guò)計(jì)算重新確定送入顯卡的頂點(diǎn)。所有的頂點(diǎn)數(shù)據(jù)全部需要參與運(yùn)算。 ROAM 算法和基于四叉樹(shù)的動(dòng)態(tài)LOD 算法都屬于此類(lèi)， GeoMipMap 算法則是靜態(tài) LOD 算法的代表。 ROAM 算法 1997 年， Duchaineau 提出了實(shí)時(shí)優(yōu)化適應(yīng)性網(wǎng)格 (ROAM， RealtimeOptimalAdaptive Meshes)算法瞳 1，它是一種基于規(guī)則網(wǎng)格的連續(xù) LOD 網(wǎng)格構(gòu)造算法。其基本思想是在對(duì)地形進(jìn)行三維顯示時(shí)，依據(jù)視點(diǎn)的位置和視線的方向等多種因素，對(duì)表示地形表面的三角形圖元進(jìn)行一系列基于三角形 二叉剖分分裂與合并，最終形成和原始表面近似且無(wú)縫無(wú)疊的簡(jiǎn)化連續(xù)三角形表面。 ROAM 的基礎(chǔ)是等腰直角三角形的一個(gè)性質(zhì)。等腰直角三角形可以從直角頂點(diǎn)到斜邊引一條垂線，這條垂線把這個(gè)三角形分成了兩個(gè)小的等腰直角三角形，并無(wú)限制的遞歸分下去。而從另一個(gè)角度來(lái)看，這正好構(gòu)成了一個(gè)二叉樹(shù)，每個(gè)三角形都是把它分開(kāi)而生成的兩個(gè)小三角形的父母 (parent)。根據(jù)這條性質(zhì)，只要計(jì)算出哪些三角形需要被分割開(kāi)、哪些三角形需要合并成為自己的父母，就可以做到控制 LOD(分開(kāi)就是增加 LOD，合并就是減少 LOD)。圖 顯示了 1～ 4 層三角形二叉樹(shù)和相應(yīng)的層次結(jié)構(gòu)。 當(dāng)把一個(gè)三角形分成兩個(gè)的時(shí)候，會(huì)在斜邊上增加一個(gè)頂點(diǎn)，是由斜邊的兩個(gè)端點(diǎn)插值求得。不過(guò)高度卻不能插值。因?yàn)楦叨仁前凑障鄳?yīng)的地圖數(shù)據(jù)來(lái)的 (比如 heightmap)。所以，就存在一個(gè)插值以后的高度和實(shí)際高度不匹配的問(wèn)題 (會(huì)產(chǎn)生裂縫 )。為了解決這個(gè)問(wèn)題，就需 要調(diào)整 Y 軸上的值來(lái)升高或者降低這個(gè)頂點(diǎn)，這個(gè)頂點(diǎn)高度的調(diào)整距離就稱(chēng)為誤差量。 要確定一個(gè)三角形是否要被分割，就要看它是否能精確的描述地形的高度數(shù)據(jù)。如果可以的話，自然就不用分割了，多邊形越少越好。如果不能的話，就細(xì)化它，也就是分割掉，直到所有的小三角形都能夠精確表示地形數(shù)據(jù)為止。 通過(guò)不停的分割，三角形越來(lái)越小，每個(gè)三角形在高度圖上所覆蓋的面積也越來(lái)越小。那么，總會(huì)分割到足夠小，使得三角形的面積和高度圖上一個(gè)點(diǎn)的面積之比為 l： l，分到這里就不用再分了。通過(guò)檢查所有孩子的誤差量，我們就找到了一個(gè)描述三 角形是否需要分割的精確方法。當(dāng)遞歸的遍歷這棵樹(shù)以后，就能夠找到這棵樹(shù)里面的最大誤差量，就是所謂的 largest error metri c。這個(gè)最大誤差量如果是 O 那就是完全符合實(shí)際高度了，這個(gè)值越大，就越不符合。 用每個(gè)三角形的誤差量和鏡頭到該三角形的距離比較，用以判斷是否一個(gè)三角形需要分裂。用以給每個(gè)三角形做測(cè)試的值是人為定義的，這個(gè)值又叫錯(cuò)誤容忍度 (error metric tolerated)。通過(guò)錯(cuò)誤容忍度對(duì)每個(gè)三角形做測(cè)試，小于這個(gè)容忍度的三角形就被留下 (不分裂 )，大于這個(gè)的就被分裂掉，然后再 分別對(duì)被分裂的三角形的兩個(gè)兒子做分裂。如果加入了視角依賴(lài) (view—dependence)的話，就需要通過(guò)鏡頭到三角形的距離來(lái)調(diào)整這個(gè)容忍度了。鏡頭越遠(yuǎn)，容忍度就越大，而鏡頭越近，容忍度就越小。 ’ 此算法的優(yōu)點(diǎn)在于：可動(dòng)態(tài)的改變每個(gè)網(wǎng)格；可在渲染時(shí)控制每個(gè)網(wǎng)格的生成與否；可以和紋理坐標(biāo)很好的結(jié)合在一起；可控制地形三角形的最大數(shù)目；可以根據(jù)坡度的不同自動(dòng)調(diào)整 LOD 的細(xì)節(jié)程度，也就是說(shuō)在地形坡度大的地方 LOD 細(xì)節(jié)程度高，在地形坡度小的地方 LOD 細(xì)節(jié)程度低；可以根據(jù)到觀察點(diǎn)的距離自動(dòng)調(diào)整 LOD 的細(xì)節(jié)程度，也就 是說(shuō)在離觀察點(diǎn)近的地方 LOD 細(xì)節(jié)程度高，在離觀察點(diǎn)遠(yuǎn)的地方 LOD細(xì)節(jié)程度低。 基于四叉樹(shù)的動(dòng)態(tài) LOD 算法 算法思想 此算法是 Lindstrom 提出的 n 劓，他用了一個(gè)叫四叉樹(shù) (Ouad Tree)的結(jié)構(gòu)來(lái)描述地形，先把可視范圍內(nèi)的地形分割成四等份矩形子塊，依靠計(jì)算判定因子檢測(cè)四個(gè)子塊，如果檢查到某個(gè)子塊的網(wǎng)格精度達(dá)到所 要求的繪制精度就不需要往下再分割；否則就把此子塊再分割成四等份更小的子塊，依次遞歸分割下去，直到所有子塊中的矩形網(wǎng)格都達(dá)到渲染精度。 此算法涉及的難點(diǎn) ●對(duì) T 形裂縫的處理 由于不同層次間的采樣間隔不同，在可視化過(guò)程中會(huì)出現(xiàn)縫隙，這種縫隙必須進(jìn)行專(zhuān)門(mén)的處理 .如圖所示，上方矩形具有較高的分辨率，而下方矩形的分辨率較低，這使得矩形間的連接處出現(xiàn)了末被覆蓋的區(qū)域 (陰影處 )，從而在地形繪制時(shí)就產(chǎn)生了 “裂縫 ”。 每個(gè) .LOD 層次區(qū)域節(jié)點(diǎn)均為正 方形，在分辨率低的四叉樹(shù)區(qū)域節(jié)點(diǎn)上，四個(gè)方向均可能出現(xiàn)縫隙，所以必須依次用自身節(jié)點(diǎn)的分辨率大小比較四個(gè)方向上臨近節(jié)點(diǎn)的分辨率大小。如果前者小于后者，則必須通過(guò)在相鄰邊上加一條邊來(lái)實(shí)現(xiàn)裂縫的消除。當(dāng)自身節(jié)點(diǎn)分辨率與相鄰節(jié)點(diǎn)的分辨率相差不止一級(jí)，那么還必須遞歸比較并添加邊，直到完全消除裂縫。 ●判定是否細(xì)分 子塊離視點(diǎn)的距離和地形的平坦度共同確定是否需要進(jìn)一步細(xì)分以達(dá)到所要求的渲染精度，從而使最終分割后的葉子節(jié)點(diǎn)達(dá)到最優(yōu)。離觀察者視點(diǎn)越近的地方細(xì)節(jié)越多，地形越不平坦細(xì)節(jié)越多。 子塊離視點(diǎn)的距離 d 可以 用公式表示如下： 其中 (Xl， Y1， Z1)為視點(diǎn)坐標(biāo)， (XO， YO， ZO)為子塊的中心坐標(biāo)。對(duì)一個(gè)子塊區(qū)域平坦度的計(jì)算如圖 所示： 對(duì)于圖中這個(gè)子塊的平坦度，先計(jì)算出高度值 h 卜 h8，找出其中最大的高度值 hMax，最小的高度值bMin，令 err=hMax—hMin。 err 即是此子塊的平坦度。 err 的值越大就意味著子塊越不平坦，網(wǎng)格細(xì)節(jié)應(yīng)該越多。 最終，綜合考慮距離和平坦度兩個(gè)因素得出判斷是否細(xì)化的標(biāo)準(zhǔn)： 如果 err*r／ d—kO 則繼續(xù)細(xì)化，反之則不。 (k 為一個(gè)可變的控制值， r 為子塊的 i／ 2 邊長(zhǎng)， err 為子塊平坦度， d 為子塊到視點(diǎn)的距離 )。 算法運(yùn)行步 驟 (1)初始化頂點(diǎn)數(shù)組，建立完全四叉樹(shù)并初始化，使每個(gè)節(jié)點(diǎn)描述清楚自己對(duì)應(yīng)的區(qū)域地形。 (2)實(shí)時(shí)渲染：首先對(duì)每個(gè)四叉樹(shù)節(jié)點(diǎn)進(jìn)行視錐體裁剪，確定進(jìn)行渲染的四叉樹(shù)節(jié)點(diǎn)，再渲染這些節(jié)點(diǎn)。 。 ： 先計(jì)算本節(jié)點(diǎn)所管理的地形區(qū)域離視點(diǎn)的距離，再計(jì)算其平坦度，兩者共同確定渲染精度值。 根據(jù)渲染精度值和判定標(biāo)準(zhǔn)來(lái)確定是否需要進(jìn)一步細(xì)分，對(duì)于需要細(xì)分的就按四叉樹(shù)思想遞歸細(xì)分，而不需要細(xì)分的就設(shè)置它的渲染標(biāo)志位為真。 ，渲染標(biāo)志位為真的節(jié) 點(diǎn)，并判定本節(jié)點(diǎn)區(qū)域網(wǎng)格在渲染時(shí)是否會(huì)出現(xiàn) T 型裂縫。判定方法是通過(guò)和四周相鄰的節(jié)點(diǎn)比較細(xì)節(jié)分辨率值，如果小于相鄰節(jié)點(diǎn)則做修補(bǔ)裂縫處理。 (3)釋放資源。 算法相關(guān)代碼 以下是 10251025 大的高度圖用基于四叉樹(shù)的 LOD 算法在線框模式下生成的地形網(wǎng)格： 游戲中地形繪制更好的方案 . 隨著圖形卡數(shù)據(jù)吞吐能力的不斷提高，每秒鐘處理上億個(gè)三角形己不再困難。很多計(jì)算，比如幾何變換和光柵處理都可以交給 GPU 去計(jì)算。所以在 GPU 數(shù)據(jù)吞吐量很大的情況下，如果 一個(gè)算法在剔除渲染頂點(diǎn)的過(guò)程中占用了