基於LOD的大規模真實感室外場景實時渲染技術的初步研究

NO IMAGE
目錄

基於LOD的大規模真實感室外場景實時渲染技術的初步研究

西北工業大學軟體學院,R093班

學生:潘李亮
學號:993754
2003 年 4 月

效果截圖

關鍵字與術語

LOD , (level of detail)、ROAM ( Real-time optimize adaptive mesh).、公告板、多遍紋理對映、運動模糊、 Lens Flare 、天空體、亮度圖、Object-Error、Space-Error、四叉樹、 Perlin Noise、Diamond Fractal.、Voxel、二叉剖分空間(BSP)、OpenGL、DirectX。Gama Control.

Abstract

The large scale terrain rendering is a hot issue in the Computer Graphics. It play an important role in GIS (Geographic Information System). Flight simulator and video game. The main two problem of the large scale terrain rendering are how to hold the terrain data and how to reduce the large amount triangles. For video game solution. I use a quad-tree based LOD algorithm to reduce the triangles count. I also introduce some other technology to improve the realism of the scene without reducing too much FPS. Such as motion blur.

I implement an outdoor game’s render engine in this paper. Not like other systems. The video game need to running on the PCs, the interactive FPS is needed too. Generally 30 FPS is the best in a video game. . In this paper’s LOD algorithm. The quad-tree is stored in a two dimension array,instead of in a linkage structure. The triangles (the quad tree nodes) not in the view frustum is culled before send them to the render API.。.

The key technology is LOD algorithm. I use the view-dependent and terrain’s roughness to determine the terrain detail. Before render the terrain. I refinement the terrain mesh. Only the vertices are needed will rendered. So the mesh is irregular .The far from the viewer, the less detail. The stronger roughness of the terrain, the more detail. Like other LOD algorithm. I subdivide a terrain node until the desire detail. The subdividing depend on the node level, the terrain’s roughness and the distance between the viewer and the node. The roughness factor is pre-calculated to improve speed.

This paper’s major purpose is the LOD algorithm , So some problem such as

Geomorphing, are still exit. Another important problem is storage layout, I only try a little to settle this problem, so the terrain data storage system is not so effective.

摘要

大規模的地形渲染技術一直是圖形學裡的熱點問題之一。它在GIS、飛行模擬器、視訊遊戲裡有重要的作用。大規模地形渲染的兩個主要問題是地形資料儲存問題和三角形數目問題。針對視訊遊戲,本文使用了一種基於四叉樹的LOD演算法來解決大規模地形渲染中的三角形數目問題。並且使用了其它一些技術,在保證渲染速度的前提條件下,有效的提高了場景的視覺真實程度。如運動模糊。

本文基本上實現了一個室外遊戲的渲染引擎。不同於其它的應用系統,視訊遊戲一般要求在PC機上執行,而且要求比較高的互動性幀率。一般認為30 FPS是比較合適的速度,因此速度是第一前提。在本文的LOD演算法中,四叉樹資訊被儲存在一個二維陣列中,而不是傳統的鏈式結構。大部分不在視體內的三角形(四叉樹節點)在送入渲染API之前就被切除掉。同時本文的演算法只用了一遍四叉樹遍歷,從而大大提高了渲染速度。

本文的關鍵是LOD演算法,我使用了視點相關以及和地形本身起伏程度相關的技術來決定地形應有的細節程度。在每次渲染前,我們都動態的更新地形網格,只渲染我們需要的節點。因此地形網格是不規則的。離觀察者越遠,細節越少,地面越粗糙,細節越多。和其它的 LOD 演算法一樣,我們遞迴的分割一個節點,直到到達需要的細節程度。這種分割依賴於節點的大小,節點內地形的起伏程度,以及觀察者離節點的距離。地形的起伏程度事先被計算出來以提高速度。

本文主要的目的是實現LOD演算法,所以其它的一些問題如同幾何形變依舊存在。另外的一個主要問題:資料儲存佈局也不是十分的有效,在這個問題上我只是做了一些簡單的嘗試。

注:本人重新整理這篇論文的目的是方便還在尋找的人有個地方能看到。另外,本人宣告本文的技術已經落伍,切勿模仿,否則鄙視之,潘李亮於2009。

目錄

第一部分:簡介

第一章:大規模室外場景渲染技術簡介

    第一節:室內Vs.室外

    第二節:Voxel Vs.LOD

    第三節:動態地形Vs.靜態地形

    第四節:其他

第二部分:基於LOD演算法的地形簡化

第二章:LOD簡介

第三章:相關的研究

第四章:LOD演算法

    第一節:基本思想

    第二節:資料儲存

    第三節:節點評價系統

    第四節:網格的渲染

    第五節:網格的生成

    第六節:優化

第五章:裁剪

第六章:效能測試

第三部分:真實感場景的生成技術

第七章:天空體和鏡頭眩光

第八章:公告板技術

第九章:地表的細節

第十章:景深處理

第十一章:運動模糊

第四部分:結論和展望

附錄

A:地形資料的生成

B:參考文獻

第一部分:簡介

室外場景的實時渲染技術是遊戲程式設計世界中的熱點技術. 同時它在其它領域也有著同樣重要的作用。如 GIS 系統,飛行模擬系統,VR系統以及數字地球技術等都離不開室外場景的實時渲染技術。一個優秀的室外場景實時渲染技術在保證實時性以外還能創造出非常逼真的、有說服力的虛擬自然環境。如Nova Logic公司的著名的3D射擊遊戲Delta Force 系列,它除了能模擬出各種如雪地、草地、沙漠等地形以外,還能模擬出各種樹木,雜草,以及各種天氣效果。

室外場景的實時渲染有許多技術上的難點,在以下的章節裡我們將作詳細的介紹以及針對一些主要問題的解決方案。

本文的主要內容分兩個部分:一、大規模地形的渲染。二、如何提高場景的真實性。分別第二部分和第三部分。

3D場景的渲染離不開3D API。目前流行的3D API有兩種,SGI公司的OpenGL和微軟公司的Direct3D。兩種API各自有自己的優點,均能很好的使用硬體加速功能。但是OpenGL是一種開放性的標準,有更好的移植效能,它能在Linux 和FreeBSD 下工作。甚至還可以使用硬體加速(nVidia公司專門為Linux /FreeBSD推出了驅動程式)。因此在本文裡,我使用了OpenGL。不過如果熟悉原理,其實也大同小異,D3D到8.0以後做的非常的像OpenGL.

第一章:大規模室外場景渲染技術簡介

第一節:室外 Vs. 室內

下面我們把室內場景和室外場景做一個對比,來看看室外場景的實時渲染的主要難點。

目前最成功的商業室內遊戲引擎有Quake /DOOM系列、Unreal系列引擎。他們都基於BSP技術的。通過BSP技術,再加上PVS , Portal等技術可以大量減少場景的複雜程度,通過Portal技術甚至可以把一個室內場景和一個室外場景連線起來,關於室內引擎的渲染的進一步已經超出了本文的範圍。

我們知道,當我們站在一個房間裡的時候,我們能欣賞到的景物不過是這個房間的擺設以及透過這個房間的門和窗能看到的景物而已。你只能在牆壁的約束範圍內走動。換句話說,我們處在一個有限的空間內。我們有足夠的理由阻止人們穿過牆進入牆外的世界,也有足夠的理由把視野約束在高牆以內。

圖(1-1),一個典型的室內場景,使用id Software的Quake III地圖檔案,用www.GameToturials.net 的程式渲染

但是,這些約束在一個室外的場景中都是不可能的。在一個飛行模擬器中,理論上你可以駕駛飛機朝任何一個無限遠的飛去。因為事實也是如此,如果你願意的話,你可以駕駛飛機繞著地球飛行而不用擔心有牆來阻止你的前進。換句話說,一個室外場景的理想大小是無限的大!除了場景的大小以外,同時視野也是無限的。如果你站在高處,你可以俯視任何比你的底的地方,也就是說你有幾乎無限的視野。

圖(1-2),典型室外場景,圖片來自北航王正盛的Demo :Nature Wing2.0截圖

我們知道,無限的大的場景需要無限的場景資料。但是這是不可能的,我們只能希望場景越大越好,室外場景的主要部分是地形的渲染,地形資料的多少決定了場景的大小。所以如何儲存這些地形資料成了首要的問題。(但是在現在儲存器成本迅速下降的今天,這個問題已經變的不是十分的突出。)其次是無限的視野問題,無限的視野就表示渲染無限的圖元(圖元即是3DAPI支援的簡單的幾何圖形,詳見OpenGL/Direct3D SDK),這也是不可能。圖元的數量是以場景大小的平方的速度增長的。光考慮地形資料,一個2048X2048的地形,如果不考慮減低細節程度和裁剪的話,它將要渲染8M的三角形,這樣的三角形量在PC級別上目前還是遠不能實現互動式幀率的。所以,如何減少要渲染地形時候的圖元數目成了室外場景實時渲染的關鍵問題。

其他的情況還有如野外的地表衍生物:樹木、雜草、地貌等。同時天氣效果,如下雨、下雪,颳風和閃電等.這些東西在一個室內的環境下基本上是不需要考慮的。而且模擬這些效果都需要很高的代價,有些甚至根本就沒有辦法模擬。

第二節:Voxel Vs.LOD

綜上,我們知道,室外場景實時性渲染的關鍵地形的渲染。我們需要一種技術來降低地形渲染的開銷。

目前的地形渲染技術主要有兩種Voxel和LOD,下面我來做個簡單的介紹。

Voxel也就是Volumetric Pixel。也就是所謂的“體素”,它是相對於畫素來說的,如果說畫素是一個二維的矩形的話,那麼Voxel就是一個三維的立方體。它的原理是比較簡單的。James Sharman自稱他在1995年時就想出了這種方法。前面的提到的Delta Force遊戲就是使用了Voxel 技術。關於Voxel的細節技術不是本文的重點,我不準備做深入的介紹。Voxel有一個天生的優點就是渲染的時候它和場景的大小沒有關係,而且絕對不會渲染多餘的東西(自帶裁剪功能)。它的複雜度只和我們需要的視野,以及解析度有關。而且可以在不使用硬體加速的情況下達到比較理想的速度(Delta Force I就沒有使用硬體加速),生成的圖象也比較的細膩。它的缺點就是不夠的靈活。

LOD也就是層次細節(Level of Detail)的簡稱,不同於Voxel技術,它是一種使用多邊形的,真正的3D渲染技術。它根據一定的規則來簡化物體的細節,我們可以根據需要來選擇不同細節程度的物體表達方式。如離觀察者近的選擇較高的細節程度、反之選擇較底的細節程度。用在地形渲染中,有時我們也稱它為多解析度地形(Muti-resolution terrain)渲染技術。

圖(1-3),基於Voxel的渲染場景,圖片來自中國遊戲開發者網路,陳鵬《自己動手編Voxel 3D引擎》

圖(1-4),基於LOD的渲染結果,圖片來自本文的Demo: Sim-Nature.

LOD演算法處理起來比較複雜,但是它讓我們可以足夠自由的去控制我們的場景渲染,更加方便的使用顯示卡的硬體加速功能。而且可以很容易的在場景中組合其他的物體。如樹木,太陽以及粒子系統等,天空如它可以方便的讓觀察者以任意的角度去觀察場景,我們只要讓攝影機旋轉一定的角度就可以了。但是這在Voxel中是比較困難的,因為Voxel在處理非水平的視線的時候非常的麻煩。

LOD技術是本文將要使用和實現的地形渲染技術。

圖(1-5),經過LOD處理的地形網格,有不同的細節。圖片來自本文的Demo: Sim-Nature.

第三節:動態地形Vs.靜態地形

地形的渲染通常分為動態和靜態的兩種。

靜態的地形的細節可以是均勻的,也可以是不均勻的。但是細節通常在事先就計算好了,不均勻細節的靜態地形有許多的優點:如平原的地貌可以使用較底的細節,而起伏頻繁的地方使用較高的細節等級。更為直觀的一個例子是賽車一類的對可以到達地方有一定限制的應用,我們可以在離賽道近的地方建立起比較高的細節等級,而在較遠的地方使用較少的細節。用這種方式也可以建立起不規則的地形。比如說,它可以沿著賽道的方向建立起一個地形模型,這樣可以節省大量的空間。

動態的地形是視點相關的。它是本文將要採用和實現的方法。隨著視點的移動,地形網格將被更新。相對於靜態地形來說這是一種更為先進的演算法。這種方式建立起來的場景更加符合人的視覺特性,即看到的細節是變化的。動態地形網格的建立和更新要耗費額外的時間,但是這種開銷是值得的。動態地形網格的建立是比較複雜的,它需要注意很多東西:如何決定細節,如何避免裂縫是兩個主要的問題。同時它還應該把不可見的地形部分切除,幾何形變(隨著細節改變,地形表面的呼吸現象)也應該被考慮到。這些問題都在以後的章節被詳細的討論到。

第四節:其他

       我們說過,在一個室外場景的渲染中。除地形以外其他的一些元素也是十分的重要的,這些元素可以提高場景的真實性。本文將實現其中的一部分元素,這包括:樹木、地面細節,太陽、天空已經運動模糊等效果。他們將在本文第三部分集中討論。

第二部分:基於LOD演算法的地形簡化

引言

地形渲染是一個室外渲染引擎的核心部分。而實現一個大規模的地形渲染系統的關鍵是如何簡化地形,拋棄不必要的渲染動作(如看渲染不見的三角形和不必要的細節)來加快渲染速度。動態 LOD技術無疑是一個強有力的解決方案。

第二章:LOD簡介

當我們要生具有相當真實感的場景的時候,由於場景本身的複雜性,要實現實時性往往時不太可能的。我們必須從場景的本身的幾何特性入手,通過適當的方法來簡化場景的複雜性。層次細節(Levels of Details )技術就是在這樣的情況下提出來的。

我們知道,當場景中的物體離觀察者很遠的時候,它們經過觀察、投影變換後在螢幕上往往只是幾個畫素而已。我們完全沒有必要為這樣的物體去繪製它的全部細節,我們可以適當的合併一些三角形而不損失畫面的視覺效果。對於一般的應用,我們通常會為同一個物體建立幾個不同細節層度的模型,如下圖的牛的模型,最左邊的有最高的細節層度,而最右邊的則經過了相當的簡化。這樣的技術在地形渲染中,我們也稱之為多解析度地形(Multi-Resolution Terrain)。

(圖2.1)牛的層次細節模型,圖片來自清華大學遠端教育網

這些不同細節層度的模型可以時在程式執行前建立的。也可以是在執行時刻計算生成的。我們可以從一個全細節的模型出發,通過一系列簡化操作生成底細節層度的模型,簡化操作可以分成三種(見[參考文獻 31]):頂點刪除,邊壓縮和麵片收縮技術。通過這樣處理後,我們可以在特定的場合下選擇合適的模型,而不必每次都選用全細節的模型,這樣大大的降低場景三角形數量。

地形作為一種特殊的幾何物體,我們在運用LOD法則的時候有一些特殊的技巧。因為地形通常是一個規則的矩形網格。其簡化模式可以有兩種:規則的簡化和非規則的簡化,規則的簡化通常是對這個矩形網格採用自頂向下(Up-to-Down)、分而治之的策略,典型的有四叉樹和二叉樹,它們從場景的最低細節層度開始,按需要不斷的提高細節。非規則的簡化通常是採用自底向上(Down-to-Up)的方法來處理的。它的實現則通常比較少。

     

(圖2.2)規則的簡化(左邊)和非規則的簡化方式(右邊)。圖片來自[參考文獻2,12]

實現LOD演算法時,除了如何對幾何物體進行簡化以外,還有一個很重要的問題就是如何決定是否對一個物體進行簡化,或者說在某個時刻該如何決定使用哪個層次細節度的模型來表示物體。我們需要建立一個評價系統,由這個評價系統來決定要對物體簡化到何種層度。這種評價系統通常是視點相關的,離視點遠的物體通常只需要較少的細節,反之則需要比較多的細節。除此之外,物體本身的特性也必須考慮在內。比如說,一個平坦的表面只需要很少的三角形就能較好表現出來。而一個凹凸不平的表面是理所當然的需要更多的三角形去描繪的。

用LOD 演算法渲染地形的時候,還有一個很重要的問題就是幾何變形(Geomorphing)問題,由於對一些細節的丟棄,隨著視點的移動,遠處原來沒有的細節很可能會突然出現,這種現象也稱為“跳出”(“Pop”)。我們必須消除這種現象,或者至少要把它控制在可以接受的範圍以內。

由上可知,LOD演算法其實並不很複雜,本文認為其關鍵處可概括如下:

  1. 資料的儲存佈局,資料在記憶體中的佈局必須要方便演算法的實現,同時最好還要降低作業系統缺頁中斷的次數,也就是降低內外存之間的資料交換的次數。
  2. 如何在生成連續的LOD化的地形網格,在地形LOD化過程中,要讓兩個由不同層度的細節的區域之間能平滑的過度。
  3. 節點評價系統,這個系統必須要使生成的網格能儘量的減少幾何形變,儘量的使畫面質量能接近全解析度時候的地形。同時還要保證實時性。

第三章:相關的研究

在過去的幾年中,已經由相當的數量的實用的演算法被開發出來。Bryan Turner在他的論文[參考文獻 32]中提到,LOD地形法則可以由三篇優秀的論文來概括,它們為[參考文獻12 ,4 和 7],在[參考文獻12]中,Hoppe 描述了一個Progressive Mesh的模型,它是使用自底向上的模式。[參考文獻4]作者是Lindstrom,它則使用了一種基於四叉樹的資料結構,他用四叉樹遞迴的把一個地形分割成一個一個小塊(tessellates)並建立一個近似的高度圖。[參考文獻7]的作者是Duchaineau,他描述了一個基於二元三角樹結構的法則ROAM(實時優化自適應網格)。這裡每一個小片(Patch)都是一個單獨的正二等邊三角形,從它的頂點到對面斜邊的中點分割三角形為兩個新的正等邊三角形,分割是遞迴進行的可以被子三角形重複直到達到希望的細節等級。後兩篇論文采用的都是規則的簡化的模式,並採用分而治之的策略。而Hoppe採用的則是一種不規則的簡化模式,它可以往任何一個三角形裡增加細節,也可以刪除任何一個頂點和邊。

Hoppe的法則使用比較少,很難在他以外的文章以外地方見到,Lindstrom 和Duchaineau的方法則不同,它們分別代表了當前的兩大主流法則:基於四叉樹的LOD地形分割和基於二叉樹的LOD地形分割。

以上三篇文章是相當出色和精彩的。但是有一定的難度和複雜。本文更多的則是採用的是[參考文獻2 和 13]中的技術。兩者都採用了四叉樹的思想,這基本上同[參考文獻4],但是更加的簡單和快速,同時[參考文獻2]提供的頂點評價系統非常的快速。遺憾的是兩者都沒有建立完善的記憶體資料佈局來解決來地形資料的儲存問題。

作為遊戲開發領域的熱點問題,自然有LOD演算法是源於遊戲開發人員的,如上的[參考文獻13]就是出自2000年的GDC。同時也已經有相當一部分遊戲成功的採用了各種不同的LOD演算法,如Tread Marks ,Myth ,Soul Ride等。[參考文獻8]的作者Thatcher Ulrich在他的文章裡以 Soul Ride遊戲開發者的身份描述了應用於Soul Ride的基於四叉樹的演算法(詳見www.Gamasutra.com)。不同於學院派的演算法,遊戲開發者的演算法通常更加的簡潔和快速。

第四章:LOD演算法

第一節:基本思想

在提出基本的演算法之前,為了簡單起見,本文必須對要渲染的地形做如下的規定:地形必須是一正方形區域。而且大小必須是 . 同時取樣間隔必須均勻。

(圖4.1)一個地形的四叉樹表示,左圖中每一個正方形為四叉樹的一個節點,粉紅色的為觀察者能看到的區域。

如圖4.1所示,我們採用四叉樹的概念來描述一個多解析度地形,圖中的每一個正方形為四叉樹的一個節點,每個節點儲存了一定區域的資訊,包括:中心點的高度,從整個完整的地形出發,我們遞迴的把地形不斷的分割(Sub-divide)成相等的四個區域,分割的深度越大,則得到的解析度越高。即分割深度每提高一層,取樣密度提高一倍。圖4.2演示了分割的過程。

圖4.2,分割過程示意圖,level 1到2時,只對兩個節點進行了分割

圖4.3給出了我們在一個四叉樹節點中要儲存的資訊。在本章的第四節中將看到,如何用這些資訊渲染這個節點表示的地形區域。

(圖4.3) 一個節點中記錄的資訊,紅色的為中心點,黑色的為邊點,藍色的角點。一共9個點。

採用四叉樹的概念來表示多解析度地形有許多優點,一個最直接有效的受益就是裁剪,如圖4.1所示,其中紅色的區域為觀察者能看到的部分。我們很容易知道觀察者能看到的只是綠色的節點,白色的節點則根本不需要考慮。因此,我們可以在節點遞迴分割的初期只花很少的代價就可直接把這些看不到的區域簡單的丟棄掉。

有了地形的邏輯表示後,我們還要建立一個節點評價系統來判定一個節點何時需要被繼續分割,何時被直接丟棄(當這個節點不能被觀察者看到的時候,節點將被直接丟棄)。如果一個節點沒有被丟棄,也不需要繼續分割,那麼這個節點將被送入渲染API進行圖元渲染。

第二節:資料儲存

地形資料通常儲存在高度圖裡,在記憶體的結構即為一個二維陣列。我們知道二叉樹可以有順序結構和鏈式結構,同理四叉樹也可以採用類似的順序結構。不同的是這裡我們採用二維陣列而不是一維陣列。我們把全解析度的地形資料儲存在一個二維陣列中,四叉樹節點的資訊(9個頂點的資訊)可以直接通過索引在陣列中讀取。同時還要建立一個和這個地形資料陣列大小相同的標誌陣列,這個標誌陣列指示四叉樹節點的狀態。如果一個節點需要被繼續分割,我們則把相應的位置標記為1,否則標記為0,如圖4.4,標著問號的表示沒有被訪問到,(注意沒有被訪問到的地方的數值是不確定的)。

由圖4.4的陣列易知地形大小為什麼要滿足 。(對於不滿足大小要求的地形,我們必須把把它分割成滿足要求的大小,然後進行拼接。)出於演算法的簡潔性,本文只考慮大小為 的地形。

   

(圖4.4) 一個地形標記陣列(9×9 )示意圖,右邊為用這個標記陣列渲染的地形,其中黑點表示當前節點需要繼續分割,空心點表示不需要繼續分割。

二維陣列的存取是按行或者按列的。考慮到觀察者移動的區域性,本文嘗試使用了一種按區域儲存的二維陣列,即在物理上把地形資料分成等大小的塊,塊的大小不能太大,也不能太小。考慮到Intel的CPU的記憶體頁大小是4K,塊的大小應該為64×64比較合適,本文采用了32×32的塊。這樣的儲存結構在一定層度上能提高儲存效率,降低記憶體缺頁的次數。關於如何使儲存結構更加有效的方法在很多文章都有介紹,[參考文獻1]就給出了一種稱為分簇的記憶體資料結構,能有效的降低記憶體缺頁帶來的效能影響。

第三節:節點評價系統

首先我們要建立一個節點評價系統,決定一個何時該對一個節點進行繼續分割。我們把這個評價系統分成兩個部分,一是視點相關的,二是地形本身的粗糙層度。裁剪器理論上也該是節點評價系統的一部分,但是考慮到它的特殊性,我們將在單獨一章中介紹。

(圖4.5)視點距離因素示意圖,l為視點離節點中心的距離。d為節點的尺寸

①我們希望離觀察者近的地方細節越多,反之則越少。將距離因素應用於一個節點的時候,還必須考慮到節點的大小。因此,結合圖4.5我們如下的公式:

(C為一個可以調節的因子)

其中l為節點的中心位置到視點的距離,d為節點的大小,當它們滿足這個公式的時候,節點需要繼續分割。其中C為一個可以調節的因子,C越大,地形細節越多。反之則細節越少。

②第二個需要考慮的因素是地形本身的粗糙程度,我們希望地形起伏比較崎嶇的區域有較高的細節程度,而平坦的地方則不需要我們浪費過多的圖元。

如圖4.6所示,首先我們考慮一個節點包含的9個頂點,其中中心點4個邊點在節點被分割和不被分割時候會引起一定的誤差,這5個誤差值為圖4.6左圖所示的dh0 – dh4。它們的數值越大表示這個節點表示的地形越粗糙。除此之外,我們還要考慮到這個節點的所有四個子節點的粗糙程度dh5 – dh8,如圖4.6右圖所示。(如果這個節點達到了最高解析度表示的地形,則不需要考慮這一步)。我們取這九個值(dh0 – dh8)中的最大的一個除以節點的大小作為這個節點粗糙度的評價值,即 r = Max(dh0,…dh8)/d。由此可見,粗糙度的計算是一個遞迴的過程,考慮到計算的複雜性和它值的不變性,我們需要事先把粗糙度的評價值計算出來,同樣把它儲存在一個二維陣列中。

圖4.6,地形粗糙程度的度量,左圖表示了一個節點內部5個粗糙度資訊,右圖則表示了它本身的粗糙度資訊和它所有子節點的粗糙度資訊

現在我們給出第二個評價公式即粗糙度評價公式:

 ( 為粗糙度調節因子)

為粗糙度調節因子, 越大,細節程度越高。綜合以上兩個公式,我們將得到最終的節點評價公式。

<!–

–>

公式中的字母含義同上,當滿足f<1時候,節點需要繼續分割。

至此,整個節點評價系統已經建立完成,但是我還必須提一下幾何形變(Geomorphing)的概念。幾何形變會造成“跳出”現象,即隨著視點的改變,有些細節會突然消失和出現。解決這種現象的辦法是比較困難的,目前在有些文章中,通過專門的方法甚至是插值的方式來消除或者降低幾何形變([參考文獻12]等),但是實現這樣的系統很困難,計算代價也很大。其次的方法就是把r值進行投影變換到螢幕空間,得到的值稱為Projected pixel error([參考文獻3]等)。但是通過實驗,我不認為這是一種好的方法(詳細原因可見[參考文獻8])。因此本文並沒有採用這種pixel error的概念。其實本文並沒有採用任何專門的消除幾何形變的系統,但是我們可以通過適當的調節C和C2的值來降低幾何形變,因為對於一個視訊遊戲來說,只要能把幾何形變控制在一個可以接受的範圍內就可以了。

第四節:網格的渲染

地形最終也是通過一個遞迴的過程來實現的。我們遍歷整個四叉樹,當我們到達四叉樹的葉子的時候,即一個節點不再被分割的時候,我們就可以把這個節點給繪製出來。

本文采用三角形扇(Triangle Fan)的方式來繪製節點,這是一種很自然的方式,因為一個節點包含了一箇中心點和若干個圍繞著中心點的點,這樣的排列剛好形成一個三角形扇,如圖4.7a所示。

(a) (b) (c) (d)

圖4.7

生成網格的時候,我們還有一個注意的地方就是兩個不同解析度的節點拼接的地方會產生 T 型裂縫,如圖4.7b所示。我們必須消除這種裂縫,圖4.7c演示了在拼接地方增加一條邊的方法來消除裂縫,圖4.7d則採用了去掉一條邊的方法。相對來說,第一種方法更加的複雜,但是也更加的全面,因為拼接處的兩個節點的解析度可以相差任意大。第二種方法則更加簡單,它要求拼接處的兩個節點的層次差距最多不超過1。本文采用第二種方法,對於如何滿足這個要求在下面的網格的生成一小節中將作詳細的介紹。

結合圖4.8的例子,我們詳細介紹一下如何生成滿足要求的三角形扇。圖中灰色區域為我們當前進行渲染的部分。首先,我們保證一個節點的四個角點(Corner vertex 見圖4.3)肯定被用到三角形扇中,對於剩下的四個邊點(Edge vertex)我們則要檢查和這個節點相鄰的節點,因為邊點要和其它的節點共享,如果相應的鄰接節點沒有被啟用,我們就要跳過這個邊點,如這個節點正上方鄰接節點沒有被分割,則我們要跳過標有X 標記的那個邊點。

圖4.8,地形網格的渲染示意圖其中灰色的節點為當前進行渲染的區域

第五節:網格的生成

在渲染網格之前,我們必須更新四叉樹,生成如何符合規範的四叉樹,在前一小節中,我們曾給出相鄰的兩個節點的層次最大不能相差1,否則在拼接的地方會出現裂縫,圖4.9a給出了一個符合規範的四叉樹例子,圖4.9b給出了一個非法的四叉樹例子。

 (a) 合法 (b)非法

圖4.9符合規範的和不符合規範的四叉樹的例子

因此,我們必須要有一套規則來保證生成的四叉樹的合法性

通常,我們採用的是兩次遍歷四叉樹的方法,我們在第一次遍歷的時候,生成地形網格,第二次渲染網格,同時消除節點之間的層次差異。

這裡,我們採用一種更加有效的方法來生成四叉樹—-按廣度優先的原則遍歷四叉樹。即一次生成一個層次的節點,而且只需要遍歷四叉樹一次。我們使用兩個佇列,一個佇列儲存著當前正在處理的層次的所有節點,另外一個佇列則儲存著下處理當前層次節點後生成的所有的下一個層次的節點。當處理完所有當前層次佇列中的節點以後,就可以進入下一個層次(簡單交換兩個佇列就可以了)的節點處理。對那些不要繼續分割的節點和已經到達最大解析度的節點,我們就把它們送入渲染API進行渲染。

這樣做有很多的優點。首先因為我們每檢查一個節點的時候,和該節點層次相同的節點都已經生成。我們可以通過檢查所有和這個節點相鄰的節點,看它們是不是存在,如果它們都存在,則可以對這個節點進行繼續分割,反之則不能對它進行分割。同時,我們還可以在第一遍遍歷四叉樹的時候有足夠的資訊讓我們繪製三角型扇,根據本章第四節的方法,渲染一個節點的時候,我們只需要檢查解析度比該節點小的節點。而這些節點在此之前已經全部生成。

其次,我們還不必要每次都復位四叉樹的狀態(清空標記陣列)。這對提高速度是很有幫助的。舉個例子,假如一個地形的大小是2048×2048。那麼這個標記陣列的大小是4M。要清空一個4M大小的陣列在時間上是一個不小的開銷。在本文的程式中,測試一個2048×2048的地圖,清空標記陣列時的FPS值為35。不清空時的FPS為78。相差一倍多!

下面我給出生成網格的虛擬碼:

Function  GenerateMesh
Begin
Push  the root node to the cur_Queue   level =  0
Loop  Not reach the Full resolution)
{
For Each Quad-Tree Node in Cur_Queue
{
If(Node is not inside the view  frustum)
{
Simple Skip this Node
}
else if(level = Full Resolution level –1 )
{
Draw The Node
}
else
{
For Each Sub-Node in this Node
Check dependcy
If(SubNodeCanSubdivid() and SubNodeNeedActive())
{
Push this sub  Node to Next_level_Queue
Set this sub  Node flag to VS_ACTIVE
}
Else
{
Set this sub Node flag to VS_Disable
}End if
End for
If No sub Node is active
{
Disable this Node
Set all four sub-node  flag to VS_DISABLE
Draw the Node
}
else if Some Sub-Node is active
{
Draw the Node
}End if
}End if
} End for
Swap (cur_Queue,Next_level_Queue);
level = next level
}End  Loop
End  Function
Function NodeCanSubdivid as BOOL
Begin
Check the four Neighbor Node.
If All  Neighbor Node is Active
return TRUE
Else
return FALSE
End  If
End Function

第六節:優化

上面介紹的演算法在理論上是比較嚴謹的,但是稍微顯的有些複雜,同時速度也不是十分的快。下面,我將對它進行一些優化和簡化。

在上面的演算法中,當一個節點的四個子節點中有一部分被分割,另一部分不被分割的時候,給我們渲染帶來很大的麻煩,而且每處理一個節點的時候,我們都要檢查四個子節點,比較麻煩。為此參照[參考文獻13]給出如下規則:當一個節點的四個子節點中任何一個需要繼續分割的時候,四個子節點都進行分割。在本文的程式裡,這個規則進一步成:一個節點需要分割的時候,就把其四個子節點都生成並放入到下一層次的佇列中去。

按照這種簡化的思想,圖4.4 中的標記陣列對應的地形網格最終將如圖4.10所示。對比圖4.4右圖,我們發現其實簡化後的演算法生成的地形細節更多,也就是說需要繪製更多的三角形。但是由於需要判斷的條件少的多,因此在運速度上,反而是簡化後的演算法要更佔有優勢。

圖4.10(圖4.4 )中的標記陣列對應地形的簡化生成演算法

下面我給出優化後的虛擬碼,對比上面的演算法,它顯得更加的簡潔了。

Function  GenerateMesh
Begin
       Push  the root node to the cur_Queue
    level =  0
    Loop  while Not reach the Full resolution
      {
              For Each Quad-Tree Node in Cur_Queue
              {
                            If(Node is not inside the view  frustum)
                            {
                                   Simple Skip this Node
}
else if(level = Full Resolution level –1 )
{
       Draw The Node
}
                            else if( NodeCanSubdivid() and  NodeNeedActive())
                            {
                                          Sub Divide this Node
                                          Set all four sub-node  flag to VS_ACTIVE
                                          Push the for sub-node  to the next_level_Queue
                            }
                            else
                            {
                                          Disable The Node
                                          Set all four sub-node  flag to VS_DISABLE
                                          Draw this Node
                            }End if
              } End for
              Swap (cur_Queue,Next_level_Queue);
              level = next level
       }End  Loop
End  Function

第五章:裁剪

通常,3D API都會提供內建的裁剪系統,但是這些裁剪系統都是在經過檢視、投影變換以後的。即裁剪是投影空間中進行的。因此我們需要建立一種方法,在頂點進行矩陣變換之前就進行裁剪,同時我們的裁剪系統還必須要有能力裁剪一個四叉樹的節點。

在投影過程中,有一個投影體,只有當物體處於這個投影體中的時候,我們才能看到這個物體,否則物體將被裁剪掉。因此這個投影體也通常被稱為視見體(View Frustum)。在進行正交投影的時候,投影體為一個長方體,在進行透視投影的時候,投影體則為一個平頭錐體。下面我們以平頭錐體為例子來匯出我們的裁剪系統。

如圖5.1,一個投影體由六個面組成,一個平面的方程可以表示為 。我們規定朝投影體內部的方向為平面的正方向,判斷一個頂點是否在投影體內部時,我們只要把頂點座標代入到六個面的方程中,通過檢查結果的符號就可以判斷點是不是在投影體內部(所有的符號都為正)。下面我們推導世界空間中的投影體的六個面的方程。

圖5.1投影體,左圖為世界空間中的投影體。右圖為經過投影變換後的投影體。

圖5.2變換後的投影範體的尺寸。

世界空間的投影體在經過投影變換後,會成為一個範體,如圖5.1右圖所示。這個範體的尺寸見圖5.2。我們很容易得到這個範體的六個面的方程,它們是

我們假設這六個平面中某個平面上有一個點(x0,y0,z0,1),在進行投影變換之前的座標為( )。

這個平面的方程為。

投影變換前,在世界空間中的方程為。

則點必須滿足和。

      

 

如果變換矩陣為T。則

結合這三個等式,我們立即就可以得到。

結合投影空間中範體的六個面的方程,我們現在可以很容易的得到世界空間中的投影體的六個面的方程。

我們已經有了裁剪體的方程,當我們需要裁剪一個頂點的時候,這六個方程已經足夠了。但是我們要判斷一個區域的可見性時,我們進行一些額外的計算。如圖5.3所示,一個物體和投影體的關係大致可以分為:包圍、被包圍、相交和相離四種情況。圖中最大的淺藍色的矩形包圍了整個投影體。深綠色的小矩形則完全被投影體包圍。淺綠色的矩形和投影體相交。這三種情況下物體都是可以被看到的。剩下紅色的矩形則和投影體相離、只有它完全不可見。

圖5.3物體和投影體的關係。

當處理節點的可見性的時候,由於節點的不規則性。我們還需要引入包圍體的概念。所謂的包圍體,就是用一個比較簡單的幾何體去度量另外一個比較複雜的幾何體,讓它剛好能包圍另外一個幾何體。比較合適的包圍體外形有矩形、正方形和球體。其中球體處理最為簡單,但是近似度也最差。我們為每一個節點都建立一個包圍體,只要測試這個包圍體,我們就可以決定一個節點的可見性,由於包圍體肯定大於這個節點,因此我們可以保證不會有任何可見的節點被裁剪在投影體之外。

第六章:效能測試

  1. 記憶體消耗量:本文的LOD演算法的記憶體消耗量只和地形的大小有關,而且這種關係是線性的。對於地形中的每一個頂點,我們需要的資訊如下:高度資訊(1位元組),粗糙度資訊(浮點型,4位元組)。四叉樹資訊(1位元組)。因此每個頂點需要6個位元組來儲存。對於一個4097×4097的地圖,我們需要96M的儲存空間,這在連PC機的RAM大小都幾乎要以GB來計算的今天,應該不是很大的問題。同時考慮到本文采用的都是靜態的資料結構,在記憶體消耗方面應該還存在著很多的優化餘地。
  2. 速度和影象質量:本文的演算法既沒有在進行恆定的速度控制,也沒有進行恆定三角形數量的控制。生成三角形的數量除了和C,C2的大小有關以外,還和地形本身的起伏程度有關。本文的演示程式在一般情況下,C=3,C2=30左右就能達到比較好的效果。當C=4.5時候,就基本不存在幾何形變的問題。而且FPS均在120以上(使用了細節紋理),速度完全達到要求。
  3. 例項測試:我選擇的測試地圖大小為2049×2049和4097×4097。地圖使用PhotoShop的分層雲彩功能製作,用本文演示程式的地圖工具進行修改加工。紋理為區域地貌紋理加亮度圖調製混合得到。細節紋理被關閉(即只進行了一遍紋理對映)。測試平臺為Intel賽揚II 1.2G,nVidia GForce 2/MX400,128M RAM。作業系統為Windows 2000sp2。顯示卡驅動版本為4345官方釋出版。注意驅動程式必須安裝正確,Windows2000提供的驅動並不能很好的支援OpenGL。

  表6.1:2049×2049地圖的渲染結果。

測試用的高度圖,大小為2049×2049.

使用雙色模式渲染。用來演示生成的三角形扇,三角形扇的中心紅色,周圍的點為白色。中心為藍色的三角形扇表示這個地方達到了全解析度。

C=25,C2=2.5. 三角形數量6529。視野距離600。FPS=167

C=50,C2=5.0.三角形數量11192。視野距離600。FPS=138

C=25,C2=2.5. 三角形數量2174。視野距離600。FPS=237。網格著色模式

C=50,C2=5.0. 三角形數量13221。視野距離600。FPS=124。網格著色模式

  表6.1:4097×4097地圖的渲染結果。

 

用的高度圖

C=35,C2=3.5.三角形數量10877。視野距離6000。FPS=137

本演算法的速度基本上只和C,C2有關,圖6.1為這兩個因子和速度、三角形數量之間的關係。圖中的測試資料中C=35恆定,C2從2.5到10.0。由於這兩個由圖可見,速度和三角形的數量和C×C2大致是先線性關係。

 

圖6.1 三角形數量,FPS和C×C2之間的關係。紅線為FPS值,綠線為三角形數量

在選擇4097×4097的地圖時,演算法執行速度上沒有任何的變化,因為需要渲染的地形區域僅限於視見體內部。當選擇8193×8193的地圖時候,由於記憶體缺頁引起的丟幀就比較嚴重,如果在Windows98下就基本不能執行。

第三部分:真實感場景的生成技術

引言

一個室外場景渲染引擎必須要具有真實感的渲染能力,這些能力包括讓地形表面有更多的細節、渲染地表植被等,甚至各種天氣效果。所有的這些都能讓場景看起來更加的自然,更加的逼真。在下面的幾章中,本文將實現其中幾種主要的項。

第七章:天空體和鏡頭眩光

1.天空體:如果一個室外場景中看不到天空是不可想象的。藍天白雲的天空能讓視野中的變的清朗。而佈滿了烏雲的天空則能讓場景看起來更加的壓抑。通常天空體的實現有圓形的和盒狀的。圓形的天空體有很多的優點,但是比較複雜,尤其是對映紋理的時候。盒狀的天空體則非常的簡單,它的主要缺點是離天空邊緣近的時候天空會有非常明顯的變形。關於天空體幾何模型的生成很多文章都有介紹,如[參考文獻33]就是一篇很好的天空體制作教程。

 

圖7.1圓形天空體示意圖。左邊為半球狀天空體,右邊弧頂狀天空體。圖片來自[參考文獻33]

天空體最難的是紋理的生成,當然你可以找一張天空的照片,但是這樣天空是靜態的。其次是用演算法動態生成天空的紋理,生成這種紋理的演算法通常是使用Perlin Noise。關於生成天空的精彩文章在http://freespace.virgin.net/hugo.elias可以找到。這種方法生成的雲彩真實性非常的好,但是致命的缺點生成大紋理的時候速度不夠快,雖然能達到一定的實時性,但是應用到整個引擎中的時候,速度就非常的慢。最後的方法是用天空的視訊檔案做紋理,這種方法雖然速度還不是十分的快,但是它比用Perlin Noise生成紋理的速度還是要快的多。(本文的演示程式附帶了一個演示視訊紋理的程式,它使用DirectShow來播放視訊檔案,將播放結果作為紋理對映到幾何體上。)

2.鏡頭眩光:稍微有一點攝影經驗的人都知道,當我們把攝影機的鏡頭對準發光物體的時候,會有光暈現象產生,這種光暈也稱為鏡頭眩光。光暈的大小和鏡頭有關。當我們在場景中放置一個太陽的時候,如果實現了這種光暈現象會有很驚人的效果。

太陽的模擬非常的簡單。只要在場景的特定位置放置一個圓形物體就可以了。鏡頭光暈則需要一些額外的處理。首先我們來看一個眩光體的位置的。如圖7.2所示。

  

圖7.2鏡頭眩光示意圖,左圖為用Photoshop生成的效果圖,右圖為其組成部分示意圖。

鏡頭光暈由一系列的光環組成,所有的光環排列在一條直線上。這條直線由發光物體位置和螢幕中心確定。這些光環的形狀則有多中方式,通常用一張放射線狀的圖用來作為發光物體的光芒,另外的則用不同厚度的環狀影象。

我們組合這些光環的時候需要使用Alpha Blending功能把這些光環疊加起來自然的融合到場景中去。通常我們採用的Alpha Blending公式為

所有的光環都是作為二維物體繪製到場景中去的。因此,發光物體在螢幕上的位置需要通過自己計算得到,在計算髮光物體在螢幕上的位置的同時我們還可以得到這個位置的Z-Buffer的資訊來判斷是否能看到發光物體,當發光物體不可見的時候,光暈自然也不可見。下圖為一個用上面演算法生成的鏡頭光暈的例子。

 

圖7.3,鏡頭光暈示意圖,左圖為獨立效果,右圖為組合到場景中後的效果圖。圖片來自本文的Demo

最後必須注意的是,眩光體必須在場景中所有的物體都繪製完畢後才繪製。

第八章:公告板技術

公告板(Billboard)是一種始終朝著觀察者的一個物體。通常它是一個多邊形。室外場景中通常有一些物體,比如說樹木,柱子一類的物體,要麼是細節非常的多以至無法用模型來表示,要麼是從任何一個方向都一樣(如柱子)。我們就簡單的把這些物體用一個多邊形加紋理對映來近似的表示。

用Billboard來表示樹木非常的有效,著名的模擬駕駛遊戲Need for Speed 5中的樹木就是用這種技術實現的。我們所看到的樹木其實只是一個矩形,如圖8.1所示,矩形可以繞著一根軸旋轉,使矩形始終對著觀察者。因此無論你從哪一個角度去看,你都只能看到矩形的正面,而不會看到扁的一面。

圖8.1Billboard模擬樹木的示意圖

除此之外,Billboard通常還用在粒子系統之中,因為3D場景中的粒子要始終正對著觀察者。這種應用的典型例子就是Quake III和Unreal中絢麗的子彈光焰。

Billboard的實現關鍵在兩個地方,其一是紋理貼圖的模式,對於像繪製樹木這一類形狀不規則的物體,通常是採用透明貼圖的模式,在OpenGL/Direct3D裡我們可以採用Alpha test的功能。對於想粒子系統則一般採用Alpha Blending的功能。第二個關鍵的地方就是如何讓多邊形的一個面始終朝著觀察者,如圖8.2所示。

圖8.2Billboard旋轉角度的計算,其中紅的箭頭為攝影機的朝向,藍色的箭頭為Billboard原來的朝向,z為轉動的中心軸

我們只要把多邊形旋轉一個角度r就可以了。角度r的大小可以用如下的公式去計算:  。轉動的中心軸則可以通過如下公式計算:

第九章:地表的細節

地表細節涉及的方面非常的多,主要的有如下的方面:地面紋理,地面陰影(亮度圖)。

1.地面紋理由於室外的場景比較大,通常需要一個很大的紋理來表達地面的細節資訊。但是太大的地表紋理一來要佔用很大的紋理記憶體,二來圖形卡也不一定能支援。

解決這個問題的方法通常有兩種,一是把大紋理分割成小的單位,動態載入需要的紋理(這種技術也稱為Texture Tiling,詳見[參考文獻24])。另一種方法是採用多遍紋理對映(Multi-Stage Texture mapping),它用一個較大一點紋理來表達地形的大概特徵,然後再用一個小的紋理來和第一個地形調製(Texture blending)再一起,第二個紋理通常採用迴圈貼圖(即貼圖的u,v座標大於1)。不同的細節紋理可以表達不同的地貌。

相比之下,第二種方法更加的簡單,效果也更好,唯一需要注意的是不同細節紋理過渡的地方。要事先混合好過渡處的紋理,不然在不同的細節紋理過渡處的地貌變化會非常的生硬,十分的難看。

                      

圖9.1細節紋理示意圖,左圖為沒有使用細節紋理,右圖為使用了細節紋理。圖片來自本文的Demo

2亮度圖在一個3維場景中增加光照和陰影效果可以更加提高場景的真實程度。

光照的計算需要為各個三角形指定法向量,動態計演算法向量速度太慢,事先計算好法向量則需要大量的額外儲存空間,而且在LOD演算法中儲存法向量也不是一件容易的事情。另一個問題是陰影問題,實時陰影的生成一直是圖形學中的一個難點。何況在室外大場景下,實時動態生成的陰影基本是不可能的。

解決以上兩個問題的一個折中方法是使用亮度圖,然後把亮度圖和地面的紋理進行調製,得到最終的地面紋理圖,這種方法在執行時刻不需要額外的計算,也不需要額外的儲存空間。

計算亮度圖的時候,我們需要給場景指定一個光源的位置,這個位置通常是鏡頭光暈的發光體(太陽)的位置。一個點的亮度由所有共享這頂點的三角形決定。其中任何一個三角形的亮度計算如下圖:

圖9.2。亮度圖的計算,其中r 為三角形法向量和光線方向的夾角

根據常識,只有朝著光源的面才會被照亮。假設全場景的環境光的強度為Ie,則這個如圖9.2中三角形的亮度I由下面的演算法決定:

if cos (r) > 0

    I = cos (r) × (1 – Ie) Ie;

Else

    I = Ie;

陰影的計算則如下圖所示:

圖9.3,陰影的示意圖,其中A點在陰影區內,B直接被照亮

確定一個頂點是否在陰影區內的時候,我們需要逐個檢查這個頂點和光源之間的頂點,驗證是否由頂點擋住了光源的光線,如圖9.3,很明顯光源的光線不能直接照到A,所以A在陰影區內。如果一個點在陰影區內,則它的亮度就直接等於環境光的亮度Ie。否則它的亮度由圖9.2匯出的演算法決定。

最後我們還需要把計算得到的亮度圖和紋理調製到一起,本文采用最簡單的方式,就是把亮度值(0-1.0)乘紋理圖上對應點的各個顏色的分量即可。

第十章:景深處理

通常使用計算機渲染得到的影象都非常的犀利,不管遠的還是近的的物體看上去都是很清晰。但是事實並不是這樣的,離觀察者遠的東西看上去會顯得模糊一些,而不是處於兩隻眼睛觀察的焦點上的物體也會模糊一些。

實現第二現象的方法在[參考文獻24]的4.2和9.2節由詳細介紹,而且實現這種效果也不是十分的必要,對渲染速度的影響也很大。這裡就不作介紹。至於第一種現象,最簡單有效的方法就是使用霧。關於霧的詳細內容在幾乎所有的OpenGL,Direct3D的書籍上都有介紹。

霧的計算方程通常有三種,本文推薦採用的公式為 。使用了霧效果的另外一個好處就是可以把遠處的(位於視見體外部的)三角形裁剪掉也不至於產生“跳出”現象,因為遠處的景物已經完全成為霧的顏色。它能提供一種無限遠視野的假象。下圖是使用了霧效果和沒有使用霧效果的圖例。

                          

圖10.1左圖為開啟了霧效果,右圖為關閉了霧效果。圖片來自本文的Demo

第十一章:運動模糊

運動模糊一種動態的效果,它是由於攝影機的底片的曝光需要一定時間,如果在曝光過程種場景發生改變,就會在底片上產生模糊效果,這種效果稱為運動模糊。運動模糊現象在電影、攝影上非常的常見。

運動模糊在運動的場景中非常重要,你會發現如果缺少了運動模糊會帶來嚴重的失真,看一下沒有采用運動模糊的計算機動畫,你會發現物體快速移動時,畫面缺乏連貫性和真實感。在前面提到過的模擬駕駛遊戲Need for Speed中,地面在賽車高速運動的時候就會變的模糊,給人一種撲面而來的感覺。

圖11.1運動模糊示意圖。圖片來自[參考文獻19]

實現運動模糊的方法在[參考文獻19]裡有詳細的介紹,在這篇文章裡作者採用了時間過取樣的方式來實現運動模糊,這是一種精確的運動模糊的實現方式,通常這種方法要使用“累積快取”(Accumulation Buffer)來實現,關於累積快取的使用方法在OpenGL,Direct3D的書籍中均可以找到。一般情況下,我們只要累積3到5次就可以達到比較理想的運動效果了,但是這種有一個很大的缺點就是嚴重降低執行速度,當我們進行n次累積的時候,執行速度就是沒有進行運動模糊時的1/n。這樣的代價在一個遊戲程式裡是不能被接受的。

作為一種其次的解決方案,我們可以把先前的渲染結果儲存起來,然後按一定的比例削弱以後混合到當前的渲染結果中去。假設當前的渲染結果為P1,先前的幀為 P2,最後得到的當前幀為P。混合的公式如下:P=(1-f)×P1 f×P2。其中f為模糊因子,f越大,運動模糊越明顯。這種方法只需要渲染一次場景,對執行速度影響不是很大。下面給出這種方法在OpenGL下的實現步驟:

1.首先建立一個足夠大的紋理,

2.渲染場景到幀緩衝區中。

3.把儲存先前幀內容的紋理設定為當前紋理。

4.繪製一個和視口一樣大的矩形,把這個矩形按上面給出的公式和步驟3中渲染結果混合在一起。

5.把混合結果拷貝到紋理物件中(glCopySubTexImage)。

6.重複步驟2-5繪製下一幀。

由於有些OpenGL的驅動不支援直接渲染到紋理的操作,因此用OpenGL實現起來比較麻煩而且速度受到的影響也比較大一些。在Direct3D中可以通過直接改變渲染目標來把場景渲染到紋理中,在速度上受到的影響要小一些,在實現上也要簡單一些,但是基本原理還是相同的,這裡不再贅述。下圖是一個使用了這種方法的例子。

圖11.2運動模糊。圖片來自本文的Demo

第四部分:結論和展望

本文已經基本上實現了一個室外3D遊戲引擎的渲染核心部分。雖然提供的演算法不是十分的精確,但是速度非常的快,用本文演算法實現的Demo可以在當前流行的個人電腦上非常流暢的執行。加上本文第三部分的技術後,畫面質量得到很大幅度的提升。下圖為本文的演示程式的螢幕截圖。所有的效果都已經開啟。

但是急待解決的問題還很多,主要有以下幾個:

1.記憶體管理本文采用的記憶體資料結構雖然在一定的程度上考慮了記憶體缺頁的問題,但是效果不是很好。由於地圖是作為一個二維陣列載入的,採用的是線性結構。資料的冗餘比較大。可以考慮採用鏈式的資料結構來改善。

2.幾何形變。

3.無限重複地圖一個地圖再大也有一定的限度,當前許多的主流遊戲採用的都是地圖迴圈的方式,即沿著一個方向走到地圖的邊緣以後會返回到開始的地方,觀察者永遠也走不到地圖的盡頭。

4.水面的模擬室外的場景中水的存在是很正常的,比如說湖面,小河等。水面應該倒影四周的場景,繪製倒影一般藉助於模板緩衝區繪製兩次場景,但是這對於室外大場景的開銷非常大而且實現也很困難。我們需要一種更加有效的模擬水面的方法。

5.各種天氣效果本文只是簡單的實現了天空體,真實的自然界中還有很多現象,比如下雨,閃電,下雪,颳風等。加上這些天氣效果會使場景看上去更加的多變。

附錄

A:地形資料的生成

生成地形資料的方法主要有兩種:

一是使用使稱為Perlin Noise的隨機函式來生成高低起伏不平地形。Perlin Noise用來生成地形特別有效,關於這種方法在[參考文獻14]裡有詳細的介紹。

第二種方法是分形,通常也叫Diamond—Square演算法。這種方法則在用來生成幾座山的時比較有效。關於這種演算法可以在www.fractal3d.com上找到詳細的介紹。

B:參考文獻

參考文獻

[1]. XiaoHong Bao and Renato Pajarola LOD-based Clustering Techniques for Optimizing Large-scale Terrain Storage and Visualization” Department of Information & Computer Science University of California .Irvine.

[2]. Stefan Röttger , Wolfgang Heidrich and Philipp Slusalleck,Hans-Peter Seidel   Real-Time Generation of Continuous Levels of Detail for Height Fields   University Erlangen-Nürnberg

[3] P Lindstrom and V.Pascucci   Visualization of Large Terrains Made Easy   Lawrence Livermore National Laboratory August 7, 2001

[4] P.Lindstrom and V.Pascucci   Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core  Lawrence Livermore National Laboratory May 8, 2002

[5] P.Lindstrom , David Koller , William Ribarsky, Larry F. Hodges, Nick Faust and Gregory A. Turner    Real-Time, Continuous Level of Detail Rendering of Height Fields   In SIGGRAPH 96 Conference Proceedings, pp. 109-118, Aug 1996.

[6]  Reinhard Klein and Andreas Schilling   Efficient Multi-resolution Models for progressive Terrain Rendering

[7] Mark Duchaineau, Murray Wolinski, David E. Sigeti, Mark C. Miller, Charles Aldrich and Mark B. Mineev-Weinstein.  ROAMing Terrain: Real-time, Optimally Adapting Meshes. Proceedings of the Conference on Visualization ’97, pp. 81-88, Oct 1997

[8] Thatcher Ulrich   Continuous LOD Terrain Meshing Using Adaptive Quad-trees   www.Gamasutra.com

[9] Luis Sempé, Terrain Rendering using Heightmaps   March 2002, http://www.sphergames.com/

[10] Renato Pajarola, ETH Zürich  Large Scale Terrain Visualization Using The Restricted Quadtree Triangulation

[11] 王巨集武董士海《一個視點相關的動態多解析度地形模型》北京大學計算機圖形研究所

[12] Hugues Hoppe   Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering    Microsoft Research

[13] Louis Castle, Jonathan Lanier and James McNeill Real-time continuous level of detail (LOD) for PCs and Consoles  Technical Presentation GDC 2000

[14] Hugo   Perlin Noise

[15] 中國遊戲開發者網路《BillBoard 技術詳解》

[16] 中國遊戲開發者網路《BillBoard》

[17]中國遊戲開發者網路 《基於視錐包含的不可見物體消除演算法》

[18]中國遊戲開發者網路 《OpenGL的渲染成紋理技術》(OpenGL Render-to-Texture

[19] 中國遊戲開發者網路   《運動模糊》(Motion Blur 原文見Hugo的主頁) 

[20] Michael Tanczos The Art of Modeling Lens Flares http://www.gamedev.net/

[21] Alan Gordie  Lens Flare Tutorial  http://www.gamedev.net/

[22]Jackie Neider ,Tom Davis and  Mason Woo  《OpenGL程式設計權威指南》(OpenGL Programming Guide)  OpenGL ARB Addsion-Weslly

[23]《OpenGL 超級寶典》人民郵電出版社

[24] Tom McReynolds  Programming with OpenGL: Advanced Rendering  SGI SIGGRAPH `97 Course

[25] Microsoft DirectX SDK Document

[26] Mesa Lib 4.03 Source Code

[27] Microsoft MSDN –OpenGL section

[28] OpenGL Specification (version 1.1 ,version 1.2,version 1.3 version 1.4)

[29]《計算機圖形學演算法基礎》機械工業出版社

[30]孫家廣等《計算機圖形學》清華大學出版社

[31] 清華大學遠端教育《計算機圖形學》第4章第7節《實時真實感圖形學技術》

[32] Bryan Turner (Dreams Woo翻譯)《ROAM實時動態LOD地形渲染》

[33]Luis R. Sempé, Sky Demo   http://www.spheregames.com/

資源

NeHe’s OpenGL Tutorials Nehe.gamedev.net

FlipCode   www.flipcode.com

GameTutorials: http://www.gametutorials.net/

nVidia: Developer.nvidia.com

OpenGL: www.opengl.org/

Mesa:   www.mesa3d.org

DirectX: www.microsoft.com/directX/

GameDev: www.gamedev.net

中國遊戲開發者:Mays.soage.com

中國遊戲資源網:www.gameres.com