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

　　

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