【導(dǎo)讀】3D游戲特別是網(wǎng)絡(luò)在線游戲中，室外大場景渲染是一塊非常重要的內(nèi)容，它也是3D圖形引擎的核心。數(shù)據(jù)可視化等，其重要性不容置疑。隨著硬件的不斷發(fā)展，行業(yè)對渲染場景的規(guī)模和真實感提出了更高的。師的指導(dǎo)下進行的研究工作及取得的成果。盡我所知，除文中特別加。而使用過的材料。均已在文中作了明確的說明并表示了謝意。究所取得的研究成果。不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。究做出重要貢獻的個人和集體，均已在文中以明確方式標(biāo)明。全意識到本聲明的法律后果由本人承擔(dān)。本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)大學(xué)可以將本學(xué)位。然而，由于我國的軟件業(yè)起步較晚，3D游戲的核心技術(shù)被歐美、日韓等牢牢占據(jù)。鐘處理上億個三角形已不再困難。很多計算如幾何變換和光柵處理都可以交給GPU去計算。

　　

【正文】 排除不需要渲染的面片。 用四叉樹 (Quadtree)管理空間 四叉樹結(jié)構(gòu)是每個父節(jié)點對應(yīng)四個子節(jié)點的數(shù)據(jù)結(jié)構(gòu)。我們可以把地形的三維空間近似看作 XZ 的二維空間，根節(jié)點表示整個正方形地形區(qū)域，其子節(jié)點分別可以表示 “左上 ， “右上 ’’， “左下 和 “右下 ”四個象限區(qū)域，那這四個子區(qū)域又可以遞歸劃分下去，如圖 ： 四叉樹中的陰影節(jié)點就是代表了地形中的陰影區(qū)域。四叉樹的葉子節(jié)點代表了地形的最小可分區(qū)域。當(dāng)要查找某一個區(qū)域時只需要遍歷這個完全四叉樹就可以了。 空間四叉樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)可以描述如下： 用八又樹 (Octree)管理空間 八叉樹是在四 叉樹的基礎(chǔ)上演變而來的。四叉樹只可以描述二維空間，八叉樹它可以描述三維空間。如圖： 八叉樹的空間管理一般用在有很多其他物體的場景中，比如建筑，樹木等物體參與到游戲中來的時候，可以通過八叉樹對這些物體進行統(tǒng)一管理，方便進行碰撞檢測、視錐體剔除等。如果只是針對地形的裁剪，用四叉樹足夠了。 用空間四叉樹節(jié)點做視錐剔除 我們從上到下，依次遍歷四叉樹的節(jié)點，判斷節(jié)點代表的區(qū)域與視錐體的位置屬于哪一種： 體相交， ， 。 如果是情況 a，遞歸判斷這個節(jié)點的四個子節(jié)點。 如果是情況 b，剔除該節(jié)點。 如果是情況 C，渲染這個節(jié)點代表的地形。 得到可渲染節(jié)點的代碼如下： 地形遮擋剔除，背面剔除 ●背面剔除 當(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)系如 圖所示： 當(dāng)視線與網(wǎng)格平面法向量之間夾角大于 90。時，表示這個多邊形位于起伏地形 的背面，需要剔除，否則不被剔除。 在實際編程時，地形網(wǎng)格的法向量可以預(yù)先計算并存儲在內(nèi)存中，當(dāng)漫游時，只需要直接計算視線與法向量的夾角就可以判斷網(wǎng)格是否要被剔除。如果對每個三角形面片都去判斷其是否是背面的話，計算量是很大的，這增加了 CPU 的負擔(dān)，雖然能夠最小化參與繪制的面片，但是 CPU 的計算很容易形成效率瓶頸，結(jié)果繪制效率有可能反而沒有不剔除背面的做法高。因此，這種算法必須針對具體情況，適當(dāng)選取。如果場景大多是峰巒疊嶂，這時就可以考慮使用此算法。 ●遮擋剔除 遮擋剔除大致可分為兩類：針對視點的遮 擋剔除和針對視點單元區(qū)域的遮擋剔除。前者判斷兩個物體之間相對于一個視點而言的遮擋關(guān)系；后者則判斷兩者間相對于一個連通區(qū)域 (即所謂視點單元區(qū)域 )的遮擋關(guān)系，由此得到的兩個物體之間是否遮擋的斷言對該區(qū)域中每一視點都成立。 針對視點的遮擋剔除算法大都需要根據(jù)視點位置將挑選出的遮擋物在圖像空間離散化，并將其離散表示組織成層次結(jié)構(gòu)，剔除時將場景中物體的層次包圍盒自頂向下地與遮擋物的層次離散表示作比較，迅速拒絕被遮擋物體。由于對遮擋物采用了離散表示，可以很容易地實現(xiàn)多個遮擋物的融合，但由于離散化往往需要借助于圖形加 速卡，而從圖形加速卡中讀取數(shù)據(jù)相對較慢。另一些針對視點的遮擋剔除方法直接在三維物體空間中判斷遮擋關(guān)系，但這使得多個遮擋物的融合變得困難。由于針對視點的遮擋剔除不一定需要嚴格的可見性信息，而只需知道潛在的可視的物體集合 (Potentially Visible Set，簡稱 PV$)。由此發(fā)展出另一類以 PVS 計算為核心的算法。 PVS 的好處就是數(shù)據(jù)為靜態(tài)，渲染的時候不需要計算，但它對動態(tài)物體的判斷不夠好。 總的來說，由于現(xiàn)在顯卡對三角形面片的吞吐量快速增加，如果為了少量剔除遮擋和背面的面片而增加 CPU 很多計算， 那將是不值得的。所以，目前的背面剔除和遮擋剔除算法的使用只適合于地形交疊起伏厲害的場景。 用動態(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ù)主要包括高度圖、紋理索引圖、光照貼圖、紋理貼圖等。 靜態(tài)加載方案 這是最簡單的辦法，也是目前常用的方式。所謂靜態(tài)加載是指在渲染場景前必須等待讀入場景數(shù)據(jù)，讀入后人物只能在這個固定的場景里漫游。在場景一定的位置設(shè)置下一個場景的開啟點，使得人物一旦到達此區(qū)域就觸發(fā)事件，讀入下一個場景的數(shù)據(jù)，經(jīng)過數(shù)據(jù)讀取后，角色便切換 到了這一場景中。如圖 所示： 這種方法不要求場景間無縫銜接，通常會把單個場景設(shè)計得大一些，避免頻繁的場景切換等待。對于一般游戲的渲染細節(jié)要求，一個 1025 X 1025 大小的場景已經(jīng)能表現(xiàn)很開闊的場景了。 這種方法的優(yōu)點是邏輯簡單，系統(tǒng)開銷小。但是由于場景的切換等待，存在不能連續(xù) 漫游超大無縫場景等缺點，極大影響游戲體驗。所以現(xiàn)在很多游戲正試圖采用其他方案跳出這種限制。 動態(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è)為 256256，緩沖池取為 25 個 Tile 大小比較合適。如果能有效的利用這種技術(shù)，那么角色可以在游戲中自由漫游，理論上游戲場景的大小只受限于磁盤的數(shù)據(jù)容量。技術(shù)的關(guān)鍵在于使 CPU、 GPU、 I／ O三者的效率達到一種平衡，在任何一個環(huán)節(jié)不能出現(xiàn)瓶頸。 緩沖池的建立與維護 所謂動態(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)于何時更新，如圖 所示： 圖中的每個小格子代表一個 Tile，也 就是緩沖池維護線程要加載的最小單位。在本程序中每個 Tile 為256256 大小。當(dāng)角色在點 a 位置時，在他周圍相鄰的 Tiles 是以 TilelOIilel4 為邊長的正方形。一共 25個 Tiles，他們就是此時緩沖池中擁有的 Tiles。角色向 b 點移動，假設(shè)角色現(xiàn)在的坐標(biāo)是 (X’， Y’)，比較的基準位置為 a 點，其坐標(biāo)為 (X， Y)，那么 當(dāng) X’X= 或者 Y’Y=Ti 時觸發(fā)緩沖區(qū)更新事件。 同時把基準位置設(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)該比左方的高。 ’ 本章小結(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ù)。 第四章 場景的真實感渲染技術(shù) 第三章討論了怎樣有效繪制地形的三角形面片，關(guān)于怎么在面片上表現(xiàn)真實的地表 (草地、沙粒 )，以及怎么表現(xiàn)光照、天空、植物等，這一系列問題涉及的就是場景的真實感渲染技術(shù)。 紋理映射技術(shù) 概念 在游戲設(shè)計中，由于客觀世界千變?nèi)f化、錯綜復(fù)雜，要把真實世界的各種細微結(jié)構(gòu)直接用幾何模型表示出來，不僅模型難以建立，而且計算量龐大，難以滿足實時顯示的需要，比如一張曲面可以用許多微小的多邊形 (或曲面片 )表示其表面細節(jié)，假定每個微小多邊形具有近似相同的表面特征，要顯示這樣一 個曲面，就必須對這些微小多邊形 (或曲面片 )進行分別處理，這將需要大量的存儲空間和處理時間，因此在實際應(yīng)用中，為了獲得比較高的顯示速度，往往以犧牲圖形的真實感為代價。盡管這樣，顯示一幅比較復(fù)雜的圖像仍然需要很長時間。于是，人們就想象是否可以用 “貼墻紙 的方法將反映物體表面的細節(jié)的圖案貼到物體表面，從而開辟了一個新的研究領(lǐng)域一紋理映射 (Texture Mappirig)。處理過程如下圖： 紋理映射的方式主要分為三種： 顏色紋理映射：最簡單和最基本的應(yīng)用是將一幅花紋圖案映射到物體表面，采用與表面上點的位置有關(guān)的值 (如：參數(shù)曲面上一點的參數(shù)值 )來確定紋理坐標(biāo)并采樣包含圖案的紋理，采樣值用定義該點的顏色。通過此類方法在圖案和表面點之間建立的固定聯(lián)系，不會因視線的改變而改變。當(dāng)花紋或圖案繪上之后，表面仍光滑如故，這種紋理稱為顏色紋理，形如在物體表面繪制了一些花紋圖案。 凸凹紋理映射：根據(jù)粗糙表面 的光反射原理，通過一個擾動函數(shù)擾動物體表面法向量，使光滑表面得到調(diào)制，并在光線下呈現(xiàn)出凸凹不平的形狀，這種紋理稱為凸凹紋理 (或幾何紋理 )。利用擾動函數(shù)可以很好的模擬皮毛、頭發(fā)、衣服之類的物體。 過程紋理映射：過程紋理映射屬于三維紋理，它就是將三維的紋理函數(shù)映射到三維物體上。也就是說在物體的內(nèi)部也會受到紋理的影響。例如，木材和大理石的紋理，需要考慮每一個相鄰面的紋理映射，通常每個面分別進行顏色紋理映射時，由于面的邊界處紋理不連續(xù)，往往難以表現(xiàn)出自然的紋理，這種場合定義三維的紋理函數(shù)進行立體紋理映射是非常有 效的。用過程紋理模擬物體表面細節(jié)，能夠在非常復(fù)雜的曲面上表現(xiàn)連續(xù)的紋理，且紋理效果不受物體表面形狀的影響，可以很大程度的解決紋理走樣問題。 OpenGL 實現(xiàn)紋理映射的步驟