基于OpenGL的地形建模技術(shù)的研究與實現(xiàn)
畢業(yè)論文
基于OpenGL的地形建模技術(shù)的研究與實現(xiàn)
誠信聲明
本人鄭重聲明：本設(shè)計（論文）及其研究工作是本人在指導教師的指導下獨立完成的，在完成設(shè)計（論文）時所利用的一切資料均已在參考文獻中列出。
本人簽名： 年 月 日
畢業(yè)設(shè)計（論文）任務(wù)書
畢業(yè)設(shè)計（論文）題目： 基于OpenGL的地形建模技術(shù)的研究與實現(xiàn)
課題意義及目標
地形建模是游戲開發(fā)的基礎(chǔ)。本課題要求使用OpenGL開發(fā)一個以三角形網(wǎng)格劃分的具有貼圖紋理映射的三維地形。主要任務(wù)
學習四叉樹構(gòu)建地形；消除四叉樹裂縫；對地形實現(xiàn)紋理貼圖；地形高度使用灰度圖片實現(xiàn)；
預期成果：開發(fā)一個等均勻度的地形；如果能納入LOD技術(shù)就達到了更高的要求。主要參考資料
[1] 柯希林,曾軍.動態(tài)LOD四叉樹虛擬地形繪制[J].測繪通報,2005,(06):10.
[2] 潘李亮,基于LOD的大規(guī)模真實感室外場景實時渲染技術(shù)的初步研究[J].西安工業(yè)大學軟件學院,2009,(04):112-115.
[3] 王宏武,董士海.一個與視點相關(guān)的動態(tài)多分辨率地形模型[J].計算機輔助設(shè)計與圖形學學報,2000,(08):05-06.
4．進度安排
審核人： 年 月日
基于OpenGL的地形建模技術(shù)的研究與實現(xiàn)
摘要
為了旅游區(qū)規(guī)劃以及游戲?qū)Φ匦畏矫娴拈_發(fā)需求，本文圍繞“地形”這個話題展開。生成地形的方法有分形生成地形，多邊形模擬算法，曲面擬合地形仿真算法。本文分別采用分形生成和四叉樹算法來繪制地形。首先解釋了高度是一個存儲了二維數(shù)組的地形文件，然后利用兩種算法來構(gòu)建地形，分形生成地形通過diamond-square算法來生成地形，四叉樹則通過節(jié)點信息對高度圖中的數(shù)據(jù)進行索引來形成地形，并且采用在裂縫中增加一條邊的方法對產(chǎn)生的裂縫進行修補。最后對地形進行紋理貼圖，將所有的紋理都繪制在一張圖上，再指派對應(yīng)紋理坐標進行渲染。
通過對以上方法的對比，四叉樹具有層次的結(jié)構(gòu)要比分形的正三角形結(jié)構(gòu)繪制效率高，四叉樹形成一個連續(xù)平滑且具有動態(tài)的層次細節(jié)的多分辨率地形，使場景更加逼真。
關(guān)鍵詞：地形建模，OpenGL ， 高度圖 ， 分形 ， 四叉樹
Research and?Implementation of?Terrain?Modeling?Technology?Based on OpenGL
Abstract
When it comes to tourism plan meet the terrain's development requirements of game, the paper is expounded around the topic of "terrain".Methods of generating terrain includes fractal generation terrain,polygon simulation algorithm, surface fitting terrain simulation algorithms. The paper uses fractal generation and quad-tree algorithm to draw the terrain. Firstly, the paper explains that the height is the terrain file to store two-dimensional array, and then build the terrain by two algorithms. The fractal generation terrain generates terrain by using diamond-square algorithm and quad-tree algorithm forms terrain through node information indexing the data in the height map, and repairs cracks by the way of increasing one edge in the crack. Finally, the texture for the terrain should be mapped. All the textures are plotted on a graph and then assign the corresponding the texture coordinates for rendering.
By contrasting to the above method, the regular structure of quad-tree is more efficient to draw than fractal triangle structure. The quad-tree algorithm forms a terrain which is continuous,smooth,dynamic and detailed multi-resolution,it makes the scene more realistic.
Keywords:?Terrain modeling, OpenGL , height map , Fractal , quad tree
目錄
1 緒論11
1.1 課題研究目的及意義11
1.1.1 課題研究的目的11
1.1.2 課題研究的意義11
1.1.3 國內(nèi)外研究的現(xiàn)狀11
1.2 開發(fā)環(huán)境22
1.2.1 開發(fā)環(huán)境的選擇22
1.2.2 開發(fā)環(huán)境的介紹22
1.2.3 OpenGL介紹33
1.2.4動態(tài)LOD技術(shù)33
2 分形地形的生成44
2.1 高度圖的概念44
2.2 分形44
2.2.1 地形分形的概念44
2.2.2 隨機分形地形的生成55
2.3 過程生成77
3 四叉樹（quad tree）算法88
3.1 基本思想88
3.2 四叉樹的數(shù)據(jù)存儲99
3.3 節(jié)點判斷系統(tǒng)99
3.4 網(wǎng)格的生成1111
3.4.1生成網(wǎng)格的意義1111
3.4.2 生成網(wǎng)格的方法1111
3.5 網(wǎng)格的渲染1111
3.5.1 網(wǎng)格的渲染過程介紹1212
3.5.2 網(wǎng)格的渲染方法1212
3.6 裂縫的消除1212
3.6.1 裂縫的形成1212
3.6.2 裂縫的消除1313
4 紋理貼圖1313
4.1 地形紋理貼圖1414
4.1.1 地形紋理的概念1414
4.1.2 地形紋理過程生成算法1414
4.2 高度區(qū)域的紋理貼圖1515
4.2.1 區(qū)域高度的概念1515
4.2.2 高度區(qū)域的算法介紹1515
4.3 區(qū)域高度以及紋理貼圖的算法1515
4.3.1 分配一個管轄的高度區(qū)域1515
4.3.2 如何遍歷紋理圖1717
5 裁剪1818
5.1 裁剪的介紹1919
5.2 投影技術(shù)的實現(xiàn)1919
6 天空盒子1919
6.1 天空盒概念2020
6.2 天空盒的制作2020
7 性能測試2020
7.1 兩種繪制方法比較2121
7.2 紋理貼圖的比較2121
8 論文的結(jié)論和展望2222
8.1 論文結(jié)論2323
8.2 展望2323
參考文獻2424
致謝2626
1 緒論
1.1?課題研究目的及意義
1.1.1 課題研究的目的
地形場景的實時繪制是目前一個熱點研究的周高點問題，目前的地理信息都是通過三維來表現(xiàn)出來。地形中存在很多自然景物,具有復雜多樣、數(shù)據(jù)大的特點。了解三維地形的概念,在深入研究了建模技術(shù),了解地形實時繪制之后,完成了一個基于OpenGL的地形建模。
1.1.2?課題研究的意義
從地形的構(gòu)造、地物數(shù)據(jù)模型和數(shù)據(jù)結(jié)構(gòu)三方面進行研究,地形建模的研究是實現(xiàn)三維可視化地形的關(guān)鍵，三維地形占有著重要地位,在游戲和旅游區(qū)規(guī)劃開發(fā)上有著重要的前景, 研究具有實踐意義。
1.1.3 國內(nèi)外研究的現(xiàn)狀
在三維空間數(shù)據(jù)結(jié)構(gòu)算法方面，楊必勝和李清泉研究出了一種按照多分辨率三維模型基礎(chǔ)上提出一種穩(wěn)健算法，龔健雅則提出了面向?qū)ο蟮氖噶繓鸥窦蓴?shù)據(jù)模型[6]。鄧念東，侯恩科提出了一種顧及維數(shù)的三維空間拓撲描述框架[7]。Klein采用一種與視點相關(guān)的TIN數(shù)據(jù)結(jié)構(gòu)來表示交互中的集合信息，當視點改變時，采用Delaunav三角剖分法重構(gòu)側(cè)TIN[21]。Luebke等提出了一種基于頂點數(shù)的簡化算法，它可以對任意幾何模型進行簡化[10]。Hoppe將他提出的漸進式網(wǎng)格模型也應(yīng)用到地形當中，并且提供了與視點相關(guān)的支持，為了有效避免三角剖分過多給全局帶來的影響，他在算法中將地形分成大小不等的若干塊，在塊內(nèi)進行逐一的網(wǎng)格剖分。這在一定程度上提高了模型簡化的效率[5]。
本文通過高度圖來創(chuàng)建地形，并且對地形進行紋理貼圖，然后納入動態(tài)LOD技術(shù)，用四又樹對地形進行編寫，實現(xiàn)了三維虛擬地形的實時繪制。如圖1.1所呈現(xiàn)的地形形式。
圖1.1 本文最后制作成功的地形
1.2 開發(fā)環(huán)境
1.2.1?開發(fā)環(huán)境的選擇
現(xiàn)有的可供地形建模的開發(fā)工具很多，開發(fā)工具對準確合理的開發(fā)出地形有著重要意義。所以根據(jù)不同的開發(fā)工具，通過對他們之間的相互比較，最后選擇基于Visual C++6.0的開發(fā)平臺，并且結(jié)合OpenGL進行程序的編制[4]。
1.2.2?開發(fā)環(huán)境的介紹
Visual C++6.0是美國微軟公司基于面向?qū)ο蟮腃++語言開發(fā)的工具和編譯器。在圖形學領(lǐng)域，Visual C++有著不可比擬的優(yōu)勢。
使用OpenGL的目的是計算機圖形開發(fā)與設(shè)計人員可以不去了解具體繁瑣的硬件系統(tǒng)，支持OpenGL語言的硬件在平臺上都可以執(zhí)行[15]。用戶可以通過在地形中進行游走操作，初始化OpenGL函數(shù)庫，設(shè)置窗口大小和渲染等等，都需要消息響應(yīng)來完成。在編寫地形仿真程序時，消息響應(yīng)是非常重要的[14]。見圖1.2。
圖1.2 Visual C++的消息映射機制
1.2.3?OpenGL介紹
OpenGL(開放性圖形庫)是由SGI開發(fā)的高性能圖形軟件處理系統(tǒng)。是圖形硬件的軟件界面[13]，它可以實現(xiàn)圖形的定點描述，將像素保存到紋理內(nèi)存，像素值被送到幀緩沖器實現(xiàn)圖形顯示。
1.2.4動態(tài)LOD技術(shù)
LOD中文翻譯過來是“細節(jié)層次”， LOD技術(shù)在圖形學中是一個大的話題，所涉及的不光是地形這么一個領(lǐng)域。對于地形我們追求的有兩個目標：質(zhì)量和性能。這是一對互為矛盾的指標，任何一方的提升都要以對方的降低作為代價。層次細節(jié)就是通過降低多邊形數(shù)量達到一個性能的提高。設(shè)計一個評估系統(tǒng)，用這個標準來評估我們將要劃分出多個層次，模型的表示方法為級別越高的多邊形越多，反之則越低。舉個列子說明：采用“近大遠小”原理，當在遠處看地形的時候，因為我們離著地形遠，所以這里的多邊形就比較少，反之則大。如果把地形起伏度也用這個描述的話，那么越是陡峭的地方多邊形越多越詳細，平緩的地方則不需要太多的多邊形來繪制。
2 分形地形的生成
2.1 高度圖的概念
高度圖實際上就是一個存儲數(shù)據(jù)的文件，在其中存放了地形高度數(shù)據(jù)，經(jīng)過程序?qū)λ淖x取，形成地形。高度圖的文件格式有很多，比如bmp，jpg，tga等等。
接下來介紹一下圖形學中頂點的顯示。顯而易見，在三維坐標系中，一定需要3個數(shù)據(jù)：即分別x軸、y軸、z軸的分量。在一個區(qū)域內(nèi)繪制五個點，x軸和y軸分量都是已知的，則知道5個y軸分量即可。假設(shè)現(xiàn)在提供一個513*513的區(qū)間（也就是有513*513個頂點），需要513*513個y軸分量，不難發(fā)現(xiàn)高度圖的圖片尺寸也是513*513。所以說高度圖它就是存儲了一堆y軸數(shù)據(jù)而已。高度圖一般用灰階圖表示，如圖2.1所示其中的灰度的不同就表示高度的不同。灰度圖中越亮的地方代表越高，越暗的地方代表越低。如圖2.1所示。
圖2.1 左圖為一張高度圖（灰度值0-255），右圖對應(yīng)生成的地形
2.2 分形
2.2.1?地形分形的概念
“分形”這個概念在數(shù)學領(lǐng)域中相當復雜。下面圖2.2所示，就是一張Mandelbrot集的圖片。這類圖片最大的特點就是它的局部跟它的整體很相似，但是他們之間的差異還是存在的。
圖2.2 曼德勃羅集
結(jié)合地形建模，實際上，高低不平的山脈就表現(xiàn)為一種分形。放眼望去，可以看到高高矮矮的山巒參差不齊。如果使用鏡頭來看，即使在局部，他們都是高低不平的，所以我們要在地形中運用分形技術(shù)[11]。
2.2.2?隨機分形地形的生成
這里我們采用“菱形-正方形”算法，其思想是這樣的：一個大而空的代表點的二維數(shù)組陣列開始。這個陣列應(yīng)該是個正方形。而且每一條邊的尺寸應(yīng)該是2的N次方再加1（比如33x33， 65x65， 129x129等等）。將四個角點假設(shè)成一樣的值。以一個5x5組成的正方形的數(shù)組為例。在圖2.3（a）中，被賦值點用黑色顯示：
圖2.3 “菱形-正方形”算法過程
此算法分為兩個階段
（1）“菱形”階段
圖b所示，把左邊的兩個邊角點，連同那個中心點連起來，順序是：左上點->中心點->左下點。得到了一個菱形的右半部分。其實是循環(huán)順延到了右邊，也就是右上點->中心點->右下點構(gòu)成了這個菱形的左半部分。如果把半個菱形就可以算是菱形。那么這里一共有四個菱形：左上點->中心點->左下點、右上點->中心點->右下點、左上點->中心點->右上點、左下點->中心點->右下點。
（2）“正方形”階段
通過圖c可以看出，左上點->中上點->中心點->左中點構(gòu)成了一個正方形，容易看出該圖一共排布著4個這樣的正方形。
這個階段生成一個隨機值。此時一共有四個菱形。它們?nèi)肯嘟灰粋€點，就是在原正方形的中心點。所以我們要分別計算這四個菱形的中心點。對每一個菱形，求它的四個邊角值的平均值，再加上那個隨機值，就是各自中心點的值[16]。如圖c所示，用黑色來表示新產(chǎn)生的點，灰色表示已經(jīng)存在的點。
通過兩個階段，可以總結(jié)出來正方形和菱形的個數(shù)各是滿足公式2^(I*2)的，其中I代表有幾個正方形，所以可以解釋為只有1個正方形；I=1時（第一次迭代），出現(xiàn)4個正方形；I=2時（第二次迭代），16個正方形；I=3時（第三次迭代），64個正方形。
現(xiàn)在讓我們來了解一下粗糙度常數(shù)H，隨機值取值范圍每次乘的數(shù)是2^(-H)?。如果定這個常數(shù)為1，那么隨機值取值范圍每次都乘1/2，即第一次在[0,1]內(nèi)取一個隨機值，第二次在[0,0.5]內(nèi)取，第三次在[0，0.25]內(nèi)取。H是通過控制2^(-H)?來間接控制隨機值取值范圍的。
把圖c得到的點用線連起來，就會得到線框圖的變化過程如下圖2.4：
圖2.4 圖c隨機生成的線框圖
再次以“菱形”階段開始。首先，我們這次有了4個正方形，計算這4個正方形的中心點。這次隨機值的取值區(qū)間要被縮減。我們設(shè)置的H值為1的話，開始的取值范圍為(-1.0 ，1.0），經(jīng)過縮減得取值范圍為(-0.5，0.5)。如圖d所示，我們用黑色點表示計算出來的正方形的中心點。
到了圖數(shù)組中的25個點已經(jīng)全部生成。就會得到線框圖的變化過程如下圖2.5：
圖 2.5 圖e隨機生成的線框圖
2.3 過程生成
過程生成是一種依靠程序，按某種算法動態(tài)生成數(shù)據(jù)的一種技術(shù)。這樣看來，我們就可以把高度圖，分形，過程生成三個概念聯(lián)系起來。繪制出地形需要的高度圖數(shù)據(jù)[9]。如果我們用這種方法，不僅可以展現(xiàn)出逼真的地形地貌，而且可以省去手工環(huán)節(jié)，減輕開發(fā)人員的負擔。但是缺點就是要繪制的東西必須符合“分形”特征，其次，程序員無法干涉會生成什么，所有的地形都是隨機生成。
3?四叉樹（quad?tree）算法
3.1?基本思想
通過了解了分形創(chuàng)建地形之后，我們再用四叉樹來構(gòu)建地形，運用四叉樹算法我們?yōu)榱吮阌诶斫猓匦我?guī)定為（2n+1）×（2n+1），而且要均勻的采樣。
第一次分割成四個正方形，淘汰沒有目標節(jié)點的正方形，只對有目標節(jié)點的正方形再分割，隨著分割的不斷變大，所得到地形的分辨率變高。如圖3.1展示了了分割的過程。
圖3.1 分割過程示意圖
如圖3.2所示，四叉樹其中每個節(jié)點中都存儲著信息，規(guī)定為紅色位置的為中心點，4個邊點，四個角點。共9個點。
圖3.2 一個節(jié)點記錄的信息，包括中點，角點，邊點
采用四叉樹的概念來表示多分辨率的地形有很多優(yōu)點，這種方法很容易的就可以在分割初期去掉不需要的節(jié)點，去掉節(jié)點之后仍需考慮節(jié)點是不是能再分割，為此還要建立一個判斷條件，確定節(jié)點何時被丟棄，當節(jié)點不在視線范圍內(nèi)的時候就直接丟棄，而且當一個節(jié)點不能再分割的時候，被送入API渲染。
3.2?四叉樹的數(shù)據(jù)存儲
四叉樹地形數(shù)據(jù)是以二維數(shù)組的方式存儲在高度圖中。高度圖中采用順序結(jié)構(gòu)，把數(shù)據(jù)放到二維數(shù)組中，通過四叉樹的節(jié)點信息可以直接通過索引被讀取，四叉樹本身還要建立一個標志性數(shù)組，通過這個數(shù)組來指示四叉樹各個節(jié)點的狀態(tài)，如圖3.3所示，標記1的代表節(jié)點可以再分割，標記？表示沒有被訪問過，標記0的則不需要再分割。為了算法的簡單易懂，本文只拿（2n+1）×（2n+1）的地形數(shù)組來解釋算法。對于不滿足的地形，把它們分割成符合的要求，再按照方法進行分割。
? ？ ？ ？ ？ ？ ？ ？ ？
? 1 ？ 1 ？ 0 ？ 1 ？
? ？ 1 ？ ？ ？ 1 ？ ？
? 0 ？ 0 ？ 0 ？ 0 ？
? ？ ？ ？ 1 ？ ？ ？ ？
? ？ ？ ？ ？ ？ ？ ？ ？
? ？ 0 ？ ？ ？ 0 ？ ？
? ？ ？ ？ ？ ？ ？ ？ ？
? ？ ？ ？ ？ ？ ？ ？ ？
圖3.3 （9×9）標記數(shù)組，分別標記的可分割，不可分割，沒有訪問到的節(jié)點
3.3?節(jié)點判斷系統(tǒng)
節(jié)點判斷系統(tǒng)可以大致由兩個因素決定：
（1）與人看地形的視點有關(guān)
當距離人眼越近的話這個地方細節(jié)就會越多，反之則越少。所謂視點是由人眼到節(jié)點的距離和節(jié)點的大小決定的[3]。結(jié)合圖3.4得到如下的公式：
L/d<C（C為可以調(diào)節(jié)的因子） （1）
其中L為節(jié)點的中點到人眼睛的距離，d為節(jié)點邊的大小，如果滿足上面公式，節(jié)點則要繼續(xù)的分割。C越大，地形細節(jié)就越多。反之則少。
圖3.4 視點：眼睛到節(jié)點的距離
（2）與地形本身的粗糙度有關(guān)
地形高低不平的區(qū)域要求有較高的細節(jié)層次，平坦的地方不要求有過多的細節(jié)。
圖3.5 表示粗糙度信息
圖3.5左圖所示引起誤差的點一共有五個，分別是四個邊點和一個中點，這幾個點所表示的數(shù)值越大證明越是粗糙，如圖3.5右的四個子節(jié)點，我們?nèi)∵@九個點中的最大的一個除以節(jié)點的大小作為這個節(jié)點粗糙度的判斷值，即 r = Max(dh0,?dh8)/d，可以看出，粗糙度的計算方法也是一個遞歸的過程，然而我們需要事先把粗糙度評價值計算出來，讓它在運行的時候不再進行額外的計算。再存儲二維數(shù)組中[1]。我們得到第二個評價公式：
1/r<C2（C2 仍然為粗糙度調(diào)節(jié)因子） （2）
C2可以理解為可調(diào)節(jié)的粗糙度因子，數(shù)值越大，細節(jié)越高。
綜合（1）和（2）中得到的公式，得到最終節(jié)點判斷公式：
f=L/d×r×C×C2<1 （3）
當公式（3）中f<1時，節(jié)點會被繼續(xù)分割。我們來調(diào)節(jié)C、C2的數(shù)值，可以調(diào)節(jié)粗糙度。
3.4?網(wǎng)格的生成
3.4.1生成網(wǎng)格的意義
在我們渲染網(wǎng)格之前，最主要的一點就是更新四叉樹，讓它生成符合我們規(guī)定的四叉樹，相鄰節(jié)點間最多不能超過一個層次，否則會造成在兩個不同層次的
節(jié)點拼接的地方產(chǎn)生裂縫，生成合法的網(wǎng)格有利于渲染工作。
3.4.2?生成網(wǎng)格的方法
遍歷四叉樹我們按照廣度優(yōu)先方法。把同一層次的所產(chǎn)生的節(jié)點在同一次生成，這樣我們只需要遍歷一次就可以。處理完當前層次隊列以后，就可以進入下一個層次的節(jié)點處理。分辨率達到最大和不能分割的節(jié)點直接渲染。這樣做的好處是每檢查一個節(jié)點的時候，下一節(jié)點就早已經(jīng)產(chǎn)生。通過檢查看它們是否存在，若它們都存在，則繼續(xù)分割這個節(jié)點，同時，在第一遍遍歷四叉樹的時候有信息讓我們繪制三角型扇，根據(jù)下一節(jié)的方法，渲染一個節(jié)點的時候，我們只需要檢查分辨率比該節(jié)點小的節(jié)點。而這些節(jié)點在上一層已經(jīng)都生成。
3.5?網(wǎng)格的渲染
3.5.1?網(wǎng)格的渲染過程介紹
通過一個遞歸的過程來實現(xiàn)對地形網(wǎng)格的渲染。當遍歷四叉樹時，當遍歷到四叉樹的葉子時，當一個節(jié)點不再被分割時，就可以把節(jié)點繪制出。
3.5.2 網(wǎng)格的渲染方法
本文通過應(yīng)用三角形扇（Triangle Fan）的方式來繪制，其原理就是中心點和圍繞著這個點的點形成一個三角扇區(qū)。如圖中棕色區(qū)域是渲染的部分。如圖4.6所示，四個角點會被用到三角形扇組成中，邊點則要檢查與其相鄰的節(jié)點，因為我們知道邊點是用來共享的，如果相應(yīng)的鄰接節(jié)點沒有被激活的話，我們就可以跳過這個邊點，如圖3.6中的0三角扇，不渲染。
0
圖3.6 節(jié)點當前被渲染區(qū)域
3.6 裂縫的消除
3.6.1 裂縫的形成
生成網(wǎng)格的時候，如果兩個節(jié)點的分辨率以及它們的層次大于1時，會產(chǎn)裂縫，如圖3.7所示，黑點部分為裂縫點，消除這種裂縫的方法有兩種，可以在裂縫產(chǎn)生的地方增加一條邊或者去掉一條邊，相對來說，去掉一條邊方法更加的復雜，因為拼接處的節(jié)點的分辨率可以相差任意大，所以本文采用增加一條邊的方法，它要求拼接處的兩個節(jié)點的層次差距最多不超過1[2]。
圖3.7 裂縫的產(chǎn)生過程
3.6.2?裂縫的消除
構(gòu)建限制四叉樹，通過圖3.8所示通過增加一條邊來消除裂縫，限定相鄰四叉樹節(jié)點之間的繪制精度等級最多不能超過1層，通過相鄰地形節(jié)點塊的繪制等級，在相鄰塊的節(jié)點處增加面片來解決消除裂縫。
圖4.8 裂縫的消除
圖3.8 裂縫的消除
4?紋理貼圖
4.1?地形紋理貼圖
4.1.1?地形紋理的概念
使用紋理貼圖可以提高變換視角看物真實性。本質(zhì)上它就是貼在多邊形上的一張普通紋理[20]。通過貼圖可以使上一章介紹的高度圖變得真實，有色彩，讓它看上去像一個真的地形，場景變得逼真。由于地形是動態(tài)生成的，事先開發(fā)人員并不清楚會生成什么樣的多邊形，連多邊形都無法指定，紋理映射又不能確定從哪里開始，用動態(tài)方法最方便，也就是用過程生成技術(shù)生成的。
圖4.1 一張紋理貼圖
4.1.2 地形紋理過程生成算法
首先，籠統(tǒng)介紹一下該算法的概念：為已經(jīng)動態(tài)生成的高度圖“配送”一幅恰當?shù)募y理圖。這幅紋理圖應(yīng)該是動態(tài)生成，應(yīng)該設(shè)計自己想要的地形進行紋理貼圖，達到真實的效果。
在進行紋理貼圖時候，就會遇到一個問題，那就是高度。然后根據(jù)高度不同來計算出它應(yīng)該具有的像素值。也就是說每一個像素都對應(yīng)著高度圖里面的一個高度值，我們按順序去讀取高度圖中的像素值。所以要生成紋理，需要一張高度圖和多張紋理圖，根據(jù)算法和高度圖數(shù)據(jù)來把它們結(jié)合在一塊，得到的產(chǎn)物就是紋理圖。假設(shè)我們有四張紋理圖和一張高度圖，根據(jù)算法來實現(xiàn)對其的調(diào)和[19]。具體過程通過圖3.2可以加深理解。
+
++ + +=
+
圖4.2 紋理生成過程
4.2?高度區(qū)域的紋理貼圖
4.2.1?區(qū)域高度的概念
在地形中，我們看到的都是參差不齊，高矮不一的畫面，在紋理貼圖時，要為我們現(xiàn)有的多張紋理（根據(jù)地形高低制作出來的）進行高度分配，使畫面?zhèn)€更加逼真。
4.2.2?高度區(qū)域的算法介紹
從上一小節(jié)寫到了根據(jù)高度圖來紋理貼圖，其中提到的算法重點部分是為每一張紋理圖分配一個自己所管轄的高度區(qū)域。
4.3?區(qū)域高度以及紋理貼圖的算法
4.3.1?分配一個管轄的高度區(qū)域
假設(shè)圖形編號為“黃土”--01，“雪地”--02，“草地”--03，“巖石”--04 。從前到后所對應(yīng)的管轄高度區(qū)域越來越高。圖3.4形象的表現(xiàn)出來了這一效果。所以要改進設(shè)計，達到重合的效果。設(shè)計要讓每一個紋理圖的管轄高度與和它相鄰的紋理圖的管轄高度進行部分區(qū)域的重合，重合部分兩個區(qū)域共同影響，計算出一個混合它們的顏色值。
為了實現(xiàn)高度區(qū)域的劃分，需要定義三個邊界點：高點、適中點、低點，其中規(guī)定適中點高度最高。如圖4.3所示，邊界點設(shè)置。
圖4.3 每個管轄區(qū)域的三個邊界點
對“管轄區(qū)域”這個結(jié)構(gòu)做了細致的規(guī)定之后，現(xiàn)在關(guān)鍵的問題就是怎么實現(xiàn)平滑過渡：每個管轄區(qū)域目前有了兩個區(qū)間，重合的方法就是把低一級管轄區(qū)域的optimal - high區(qū)間與相鄰高一級管轄區(qū)域的low - optimal區(qū)間重合。如此一層搭一層，就像搭樓梯一樣。圖3.5展示了明確的意思。
圖4.4 沒有過度的紋理貼圖
圖4.5 重合之后，一層搭一層
圖4.4和4.5可以看出紋理圖的管轄區(qū)域：紋理01的管轄高度為0 — 60，其中，low為0 ，optimal為30，high為60；紋理02的管轄高度為30 — 90，其中，low為30，optimal為60，high為90；紋理03的管轄高度為60 — 120，其中，low為60，optimal為90，high為120；紋理04的管線高度為90 — 150，其中，low為90，optimal為120，high為150。
這個例子中，是人為規(guī)定的，但是并不準確，不知道地形的高度區(qū)域。所以我們要設(shè)計一個算法來實現(xiàn)區(qū)域高度。具體方法為篩選出高度圖中最大的高度值，假設(shè)為max_height，然后就知道整體的跨度為0 — max_height，整體的長度就為max_height。四張圖和重合的部分可以分成5各部分，除以5，得到的值就是管轄區(qū)域中的、每個區(qū)間的長度。注意，是管轄區(qū)域中的單位區(qū)間的長度，不是管轄區(qū)域本身的長度。這個例子中得到的值就是30。有了它，就可以算出具體該為每個紋理分配多大的管轄區(qū)域長度了，不僅如此，還同時可以算出其內(nèi)部low、optimal、high的值。
4.3.2?如何遍歷紋理圖
若高度圖為5x5，9x9 ，17x17，.... 513x513 。紋理圖則可以為4x4，8x8，16x16，.... 512x512。這是由硬件決定的。高度圖和紋理圖的尺寸規(guī)律：它們相似但卻不同。
高度圖尺寸和紋理圖尺寸匹配。如果說高度圖的邊長為2^N+1，紋理圖則為2^N 。比如，高度圖尺寸是513x513，那么要求紋理圖尺寸是512x512。這樣就達到最佳匹配。這并不是最優(yōu)化的設(shè)計，暫且先拿這個模型討論，之后再做優(yōu)化?，F(xiàn)在可以得出結(jié)論，一旦指定了高度圖的尺寸，紋理圖的尺寸也就指定了[18]。假設(shè)紋理圖尺寸就是512x512。我們開辟一個對應(yīng)的內(nèi)存空間，用來裝載計算出來的紋理像素了。
還要注意一下制作好的那幾張紋理圖。對它們的尺寸沒有什么特殊的要求，因為它們并不會被送到渲染API中；它們沒有必要和生產(chǎn)的紋理圖一樣大，當需要采集的像素位置超出它們的實際位置時，用一個余除的手法就能讓它到正確的位置上。如圖4.6所示。
0 255 256(=0)
圖4.6 遍歷到（0，256）點的時候，也就回到了（0，0）點。
這個簡單的手法就是“余除”。
采用嵌套方式，來索引紋理圖：索引它們的每一行，然后在索引每一行的每一個像素，開始時候要找到高度圖所在位置，直接從高度圖中讀取這個點，然后從紋理圖中找到這個點對應(yīng)的像素。若所提供的紋理圖和需要的尺寸不匹配，我們采用方法是之前提到的“余除”方法，通過一個小小的轉(zhuǎn)換設(shè)計，就不用擔心在取原紋理圖時超出范圍。
通過上面介紹的算法，采用的紋理圖尺寸是和高度圖尺寸非常匹配的（只差一行和一列的大小）。其實，采用的紋理圖尺寸和高度圖可以沒有什么關(guān)聯(lián)，只要滿足計算機要求基本的2^N邊長即可。換句話說，可以任意決定生成的紋理圖大小。這就是優(yōu)化方案。相比之下，上面的方法不僅非常簡單，而且紋理圖必須和高度圖尺寸綁定，假如高度圖的尺寸很大，紋理圖也要尺寸很大，然而優(yōu)化方案可以令紋理圖尺寸大大減小，這樣處理巨大地形時，紋理圖就會節(jié)省大量的CPU運行空間，把內(nèi)存的空余出來，提高CPU的工作效率。這種優(yōu)化方案就是巧妙運用了“比例”的思想。對于一張并不匹配的紋理圖和高度圖，當紋理圖遍歷到某一個像素中時，根據(jù)該像素在本紋理圖中的位置，找到高度圖中等比例的位置的像素，然后讀取它的高度值。
5 裁剪
5.1 裁剪的介紹
當我們把地形以及所有的場景都建立完畢后，我們不難發(fā)現(xiàn)一個問題，其實我們的電腦看上去只是一個平面，所以本章重點研究的是怎么將我們的3D模型轉(zhuǎn)換到成2D，并且在這個2D平面中展現(xiàn)出3D效果。簡單的說投影就是將一個實物（3D）體投影到電腦屏幕（2D）的過程，也就是到最后我們看到的顯示器上的畫面。
5.2 投影技術(shù)的實現(xiàn)
本文采用透視投影，經(jīng)過投影矩陣裁剪后的坐標，比如定義一個攝像機，也就是視覺坐標，這個攝像機看到的范圍是有限的，有一個夾角和一個近距離和遠距離。夾角外的看不到，設(shè)置一個近距離裁剪，就是太近的也當做看不見，太遠的也看不見。也就是將上述的視覺坐標定義了一個裁剪體，在這個范圍內(nèi)的才渲染，同時將這個視覺坐標這些3D的頂點投影到這個視景體中，也就是最后2D的畫面了。如圖6.1。
圖 6.1 攝像機代表人的視角
6 天空盒子
6.1?天空盒概念
為了中模擬天空，天空盒制作是必要的。一般天空的構(gòu)造可以使用天空盒。天空盒子可以用正方體來繪制，然后再貼圖。然后這個四方體包裹著地形，這樣就為地形加入了天空，做到了場景的進一步逼真。
6.2?天空盒的制作
文采用一個正方體貼圖的方法來制作天空盒子，也就是把紋理映射到立方體的六個面，首先我們要準備紋理圖，如圖5.1，所采用的圖片來制作天空盒，因為程序中加載的是tga圖片文件，所以先通過Photoshop把圖片格式改過來，然后把圖片轉(zhuǎn)換成紋理圖。再將紋理正確貼到四邊形上，必須將紋理的右上角映射到四邊形的右上角，紋理的左上角映射到四邊形的左上角，紋理的右下角映射到四邊形的右下角，紋理的左下角映射到四邊形的左下角。如果映射錯誤的話，圖像顯示時可能上下顛倒，側(cè)向一邊或者什么都不是。以此方式制作的天空盒子如圖6.1右圖所示。
6.1 左圖為天空盒子制作的素材，右圖為制作出來的盒子
7 性能測試
7.1 兩種繪制方法比較
我們分別采用兩種方法來繪制地形，分別是分形地形和四叉樹地形，其中分形地形是通過正三角形來繪制地形，而四叉樹則是通過細節(jié)層次來繪制，兩種繪制出來的地形網(wǎng)格如圖7.1所示。左邊為分形地形產(chǎn)生的網(wǎng)格，右圖為四叉樹產(chǎn)生的網(wǎng)格。當我們采用四叉樹繪制地形的時候可以，其中繪制效率可以提高很多，分形地形必須把整個地形所需的三角形全部繪制出來，然而四叉樹繪制的時候和視點有關(guān)系，在視點內(nèi)的進行繪制，不在視點內(nèi)，直接忽略，這樣會大大節(jié)省空間。
圖7.1 兩種方法產(chǎn)生的地形網(wǎng)格
7.2 紋理貼圖的比較
在進行紋理貼圖的時候，我們可以看到分形地形中貼完紋理之后，當我們通過鍵盤在其中漫游的時候，它就像一個靜態(tài)的死物一樣在屏幕中呈現(xiàn)出來，不會隨著視點的改變而改變，然而四叉樹構(gòu)建的地形貼完紋理之后，隨著在其中的漫游，它的細節(jié)層次也展現(xiàn)出來。我們可以看到當我們移動到某個點，隨著距離的減小，地形會不斷的變化，慢慢的變得非常詳細。反之，我們離著地形越遠，則三角形會慢慢的減少，這也能說明當我們離地形很遠時，只是用了很少的三角形來繪制。這樣大大提高了繪制效率。圖7.2展示了這一過程。
圖7.2 四叉樹的網(wǎng)格隨著遠近的不同，詳細程度也不同
8?論文的結(jié)論和展望
8.1?論文結(jié)論
介紹了高度圖的概念，地形的數(shù)據(jù)都是存儲在高度圖里面，通過對高度圖的數(shù)據(jù)讀取，生成地形，但是這種方法要事先去規(guī)定高度圖，所以本文又引進了一種方法，分形生成地形，其中采用“菱形-正方形”算法，其算法主要表現(xiàn)為一種隨機生成地形形態(tài)。主要是一個大而空的代表點的二維數(shù)組陣列開始。這個陣列應(yīng)該是個正方形。而且每一條邊的尺寸應(yīng)該是2的N次方再加1，然后通過正方形和菱形的不斷交換來生成我們需要的點，其中每一個菱形和正方形的中點都會產(chǎn)生一個高度值。就是地形的高度把所有高度表現(xiàn)出來就成了地形。
然后進行紋理貼圖，從生成的高度圖中得到了地形的各個區(qū)域的高度。所以根據(jù)高度可以進行貼圖，這其中最難理解的就是區(qū)域高度的劃分，我們通過為四張紋理圖根據(jù)不同的高度進行紋理貼圖，來實現(xiàn)了每個高度區(qū)域有一張紋理圖，對“管轄區(qū)域”這個結(jié)構(gòu)做了細致的規(guī)定之后，實現(xiàn)平滑過渡：每個管轄區(qū)域目前有了兩個區(qū)間，重合的方法就是把低一級管轄區(qū)域的optimal - high區(qū)間與相鄰高一級管轄區(qū)域的low - optimal區(qū)間重合。其中重合部分，通過像素所對應(yīng)的顏色值來混合，實現(xiàn)平滑過度。
以上方法實現(xiàn)的地形模型是由許多三角形來繪制的，三角形的數(shù)量非常大，要在每一幀顯示所處理的數(shù)據(jù)。這樣會造成CPU的吃不消。不能更好的實現(xiàn)漫游。事實上，我們只是在觀察地形的某一個區(qū)域，所以引進四叉樹算法來編寫地形，這樣也使整個地形納入了動態(tài)的LOD技術(shù)，從而也達到了更高的要去，四叉樹算法主要是把地形分成具有層次細節(jié)的正方形再通過視點與節(jié)點的距離來進行層析劃分，給我們的效果就是當靠近地形時候，就會產(chǎn)生更多的節(jié)點。當們視野遠離地形時就會減少節(jié)點數(shù)量。對編寫過程中產(chǎn)生的裂縫進行消除，得出結(jié)論，相鄰節(jié)點間的層次差別不能大于1。最后對地形進行渲染，渲染過程中，是通過三角扇來渲染的，節(jié)點中角點必定在三角扇中，而邊點是否渲染，則要看與其相連的節(jié)點是否被激活，如果沒有激活，就不渲染這個邊點所在的三角扇。
通過對兩種方法的對比發(fā)現(xiàn)，四叉樹構(gòu)建地形要比分形生成地形的效率要提高一倍。
8.2?展望
通過對本論文運用到方法進行總結(jié)，發(fā)現(xiàn)此課題還有很多值得研究的方向：
在多分辨率領(lǐng)域研究現(xiàn)有的算法，能否結(jié)合本文提出的算法，在地形動態(tài)管理方向研究出更高效的算法。
研究更好的數(shù)據(jù)分析方法。
結(jié)合GIS進行相關(guān)研究，尋找更優(yōu)的新算法。
參考文獻
[1] 柯希林,曾軍.動態(tài)LOD四叉樹虛擬地形繪制[J]. 測繪通報,2005,(06):10.
[2] 潘李亮,基于LOD的大規(guī)模真實感室外場景實時渲染技術(shù)的初步研究[J].西安工業(yè)大學軟件學院,2009,(04):112-115.
[3] 王宏武,董士海.一個與視點相關(guān)的動態(tài)多分辨率地形模型[J]. 計算機輔助設(shè)計與圖形學學報,2000,(08):05-06.
[4] 勒海亮,高井祥,康建榮.基于VC和OpenGL的地形三維可視化[J].微計算機應(yīng)用,2006,(5):577-581.
[5] Hugues Hoppe.Smooth View-Dependent Level-of-Detail Control and its application to Terrain Rendering[C].IEEE Visualization 1998,October 1998:35-42.
[6] 楊必勝,李清泉,龔健雅.一種快速生成和傳輸多分辨率三維模型的穩(wěn)健算法[J],科學通報 ,2006,51(13):1589-1594.
[7] 鄧念東,侯恩科,霍正東.應(yīng)用SURPAC實現(xiàn)礦床三維可視化地質(zhì)模型動態(tài)更新[J].陜西煤炭,2006,(03):7-9.
[8] 齊安文,吳立新.基于類三棱柱的三維地質(zhì)模擬與拓撲研究[J].礦山測量,2003,(3):65-66.
[9] 魏海濤. 計算機圖形學[M]. 北京:電子工業(yè)出版社,2006(1):285-288.
[10] David Luebke,Carl Erikson.View-Dependent Simplification of Arbitrary Polygonal EnVironme-nts[C].In:SIGGRAPH’97 Proceedings,1997.
[11] 白燕武,史惠康.OpenGL三維圖形庫編程指南[M].北京:機械工業(yè)出版社,1998:208-230.
[12] 張嚴辭,劉學慧,吳恩華.基于圖像的實時漫游[J].計算機輔助設(shè)計與圖形學學報,2008(4):8-10.
[13] 向世明. Visual C++數(shù)字圖像與圖形處理[M]. 北京: 電子工業(yè)出版社,2002:168.
[14] 瀟湘工作室.OpenGL超級寶典[M].北京:人民郵電出版社,2001.
[15] 呂鳳翥.C++語言程序設(shè)計[M].北京:電子工業(yè)出版社,2002(2):4-16.
[16] 曹曉光.隨機中點位移算法的改進[J].中國圖象圖形學報,1997,2(4):235-238.
[17]丁 瑋,齊東旭.分形生成的遞歸細化算法[J].中國圖象圖形學報,1998,3(2):123-127.
[18] 黃超超,凌永順,呂相銀.地形紋理映射方法研究[J].計算機仿真,2005,21(1):209-212.
[19] 孔令德.計算機圖形學基礎(chǔ)教程(Visual C++版)[M].北京:清華大學出版社,2013,3(2):310-324.
[20] 馮磊,宋現(xiàn)鋒,石泰來. 3DGIS中復合地形紋理生成與應(yīng)用[J].地理與地理信息科學,2009,25(2):15-18.
[21] Reinhard Klein,Tobias Huttner. Simple Came-radependent approximation of terrain surfaces for fast visualization and animation[C].In:RYangel editor,visualization 96 ACM,1996-11.
致謝
通過幾個月的努力，我完成了畢業(yè)設(shè)計以及論文，在這個時候，我首先要感謝我的指導老師孔令德教授，感謝孔老師這幾個月來對我細心指導，在這段時間里，老師敏捷的思維和獨有的個性給了我很大的啟發(fā)，讓我學會了在以后的社會生活中怎樣去把自己的優(yōu)點無保留的發(fā)揮出來。在這期間我也了解到了孔老師的知識淵博和嚴謹?shù)慕虒W態(tài)度，早已具備了站在知識制高點的能力。通過和孔老師的相處，發(fā)現(xiàn)孔老師是一個對生活積極樂觀、充滿自信且淡泊名利的人。這對我以后的生活會有很大的影響。
在我即將畢業(yè)之際，我要飽含深情的感謝我的母校，感謝太原工業(yè)學院以及計算機系的領(lǐng)導和老師，四年里，在老師的悉心教導下，我已成為一個具有知識的大學生，并且我也一直鍛煉自己，不怕困難，勇敢向前，慢慢的我也走向了成熟，到了現(xiàn)在，我已經(jīng)做好了一切準備準備服務(wù)于社會，請母校放心。
我還要真摯感謝我的家人、我的女友、和我的朋友們，你們多年來對我的關(guān)心、照顧、理解和支持讓我感覺到我人生的很美好，和你們在一起的成長經(jīng)歷是我人生的寶貴財富，是你們讓我有動力去完成學業(yè)，完成人生需要的每一步。有你們，無所畏懼！
感謝所有幫助過我、關(guān)心過我的人！
