張潤花，劉樹群，趙付青

（1.甘肅建筑職業(yè)技術學院 基礎課部，蘭州 730050；2.蘭州理工大學 計算機與通信學院，蘭州 730050）

地形生成的細分隨機移位方法

張潤花1，2＊，劉樹群2，趙付青2

（1.甘肅建筑職業(yè)技術學院 基礎課部，蘭州 730050；2.蘭州理工大學 計算機與通信學院，蘭州 730050）

將4點細分格式推廣到三維表面，提出一種基于四邊形柵格4點細分格式的隨機移位地形生成方法.實驗結(jié)果表明提出的算法可以方便生成具有真實感、基本可控性的山脈地形，較好地解決了傳統(tǒng)隨機中點移位方法對生成地形的形狀無法預測和控制、裂縫和不真實的問題.

分形；地形；隨機中點位移法；細分；邊界

基于分形的自然景物模擬現(xiàn)已成為計算機圖形學研究的前沿課題，山體、地形是自然界最復雜的景物之一.三維地形可視化［1-2］在虛擬戰(zhàn)場環(huán)境、游戲、地形漫游、地理信息系統(tǒng)等眾多領域有著廣泛的應用［3-4］.更具真實感［5］、可控性的山脈地形模擬，逐漸得到人們的重視.

目前，國內(nèi)外學者已經(jīng)對三維地形真實感及細分方法做了大量的研究.最常見的隨機中點位移算法［6-8］有三角形細分法和正方形細分法；其中又以正方形細分法最為靈活，并避免了隨機中點位移方法中可能出現(xiàn)的折痕問題.由于傳統(tǒng)隨機中點移位方法存在對生成地形形狀無法預測和控制、裂縫和不真實的問題.本文將四點細分格式推廣到三維表面，提出了一種基于分形的地形生成細分的隨機移位方法.

1 地形生成的基本方法

基于細分［9］的地形生成的基本過程是在初始高度網(wǎng)格的基礎上遞歸地進行細分和改變頂點高度，直到滿意的細分尺寸.初始網(wǎng)格的產(chǎn)生有多種方法，如給定或交互編輯產(chǎn)生或通過隨機方法、IFS［10］、分形生長等.初始高度網(wǎng)格決定著地形的大尺度形態(tài).依據(jù)表面構網(wǎng)方式的不同，可分為三角形網(wǎng)格和四邊形網(wǎng)格.細分就是將高度網(wǎng)格加細，三角網(wǎng)格加細一般是在三角形每條邊的中點附近增加一個頂點，這樣可以將原三角形細為4個三角形（如圖1）.

圖1 三角形網(wǎng)格細分Fig.1 Triangle mesh subdivision

然后在各中點上增加一個高斯隨機偏移量，其標準偏差由式s＝α·2－kH給出，其中k為迭代次數(shù)，α是一個比例因子，H是Hurst指數(shù).為計算方便也可以使用f（k）＝αβk，其中α為初始范圍縮放因子，β為遞歸下降因子，β∈（0，1），α的作用是調(diào)節(jié)縮放遞歸過程范圍因子的比例.由于實際上只使用離散的值，因子可以用數(shù)值表設定每層遞歸的隨機范圍因子.

細分算法的最大優(yōu)點是它能夠從任意的初始網(wǎng)格出發(fā)產(chǎn)生光滑的曲面.目前的細分格式大體上分為兩類：逼近型細分和插值型細分.逼近型細分技術是一種割頂點方法，直觀效果稍差.而插值型細分技術保持初始網(wǎng)格頂點不變.相比較而言，插值型細分比逼近型細分更直觀，計算量更小，交互性更好，更具優(yōu)勢.

2 細分方法

細分方法的實質(zhì)是通過對初始控制點或者初始網(wǎng)格進行一系列的細化過程，細化的極限生成所需要的曲線或者曲面.細分是生成任意拓撲曲面強有力的方法.細分算法的最大優(yōu)點是它能夠從任意的初始網(wǎng)格出發(fā)產(chǎn)生光滑的曲面.

曲線的插值型四點格式按照下面的規(guī)則進行細分：

圖2 曲線細分的四點格式Fig.2 Four－point method of curve subdivision

可以將其用于曲面細分.記

圖3 曲面細分的四點格式Fig.3 Four－point method of surface subdivision

面上的細分點（面點）fij可以用水平和垂直方向的四點格式均值來表示：

水平和垂直方向的細分點可以使用邊線四點公式與垂直方向面點四點格式的加權平均值，λ∈（0，1），

實際上，可以有多種細分方案，而在每種方案下可以有多種分點計算方法.

3 邊界處理

在邊界處，如果簡單地使用線性插值，就會出現(xiàn)與隨機中點移位方法類似的問題.因此，一般選用與內(nèi)部網(wǎng)格細分次數(shù)相當?shù)募毞址椒ǎ疚倪x用局部三次插值.如果當前細分層的柵格為M×N，則每個邊界柵格最外層邊點的細分點要用到相鄰的4個點，其組合系數(shù)為

其中的“·”表示邊點的位置，如

其它三個角面點的組合系數(shù)是對上述矩陣旋轉(zhuǎn)90°、180°和270°的結(jié)果.

左側(cè)邊界面點的組合系數(shù)為（其它邊界面點的組合系數(shù)也要對下列矩陣進行旋轉(zhuǎn)）

非邊界面點的組合系數(shù)為

當然可以用三次格式進行細分來生成地形.

4 規(guī)范網(wǎng)格上的地形生成

規(guī)范柵格是指網(wǎng)格的尺寸為（2n＋1）×（2n＋1），如果當前柵格間隔為d＝2k（1＜k＜n），進一步細分的間距為2k－1，即x和y的值很容易獲得，細分過程只針對z進行，則新面點fi，j為

5 實驗

參數(shù)ω和λ的正常取值范圍為ω∈（0，1／8），λ∈ ［0，1］.隨機數(shù)使用rk＋1＝3.96 rk（1－rk）.范圍因子f（k）＝αβk中的α＝0.25，β＝0.5，圖4～圖5使用相同的初始網(wǎng)格.參數(shù)相同情況下的隨機中點移位方法（見圖4）的山峰凸尖，坡面平坦與雙線性曲面相對應，且會出現(xiàn)明顯的棱脊.使用本文方法生成的地形（見圖5）的山峰較厚重，坡面過度自然，沒有棱脊現(xiàn)象發(fā)生.參數(shù)在正常范圍取值時生成的地形都較自然，且ω和λ取值較大時山體陡峭，較小時平緩（見圖5）.ω＝0時退化為隨機中點移位方法.參數(shù)可以適當超出范圍，生成的地形一般會保持大尺度樣式，但小尺度會產(chǎn)生劇烈變化的表面，一般需要進行整體平滑處理.

6 結(jié)論與展望

圖4 隨機中點移位方法生成的地形Fig.4 Terrain generation based on the method of random mid－point displacement

圖5 細分隨機移位方法生成的地形（取ω＝0.0625，λ＝0.75）Fig.5 Terrain generation based on the method of random subdivision displacement（letω＝0.0625，λ＝0.75）

使用隨機中點移位方法生成地形時，當隨機范圍參數(shù)較大時，地形陡峭；一般需進行不同尺度的平滑處理，并因此造成生成的地表的大體形態(tài)與初始柵格之間形成較大差異.當隨機范圍參數(shù)較小時，會出現(xiàn)山峰過于尖凸、山體平整和缺少厚重感的缺陷（見圖4），也需要進行平滑處理.本文提出的細分隨機移位方法有效解決了這些問題，且生成的地形自然，從圖5可以看出，隨機范圍因子為0.75時仍能反應出最初柵格的形貌，當范圍因子縮小時與初始柵格的關聯(lián)更明顯（實際應用中多采用0.5），當使用相同的隨機條件進行交互控制時，初始柵格的變化與最終生成地形之間形成良好的預見關系.且因為省去了三次平滑處理而使總體計算復雜度有所下降.

需要進一步研究的內(nèi)容包括：對地形的形態(tài)、表面粗糙度、不同尺度的地形特征及連續(xù)過渡等具有更好控制能力的細分方法，以及各種方法的結(jié)合，研究適合地形拼接的細分方法，超大地形的局部及層次控制，不同需求的特征控制，交互式編輯等.

［1］李耀輝，周麗莉.虛擬現(xiàn)實中三維仿真地形的生成［J］.微計算機信息，2006，22（10）：280－282.

［2］韓 飛.面向虛擬環(huán)境的三維地形生成方法［J］.計算機工程，2010，36（19）：261－262，265.

［3］張劍飛，王艷濤，程 杰.大規(guī)模三維地形的生成和漫游［J］.哈爾濱理工大學學報，2010，15（2）：28－30，34.

［4］林喬木，張永剛.三維動態(tài)地形視景仿真技術［J］.海洋技術，2010，29（2）：101－103.

［5］李慶忠，高秀榮.三維可控真實感地形生成方法研究［J］.系統(tǒng)仿真學報，2008，20（11）：2938－2941.

［6］林 嵐.基于分形理論的高精度地形繪制算法研究［D］.武漢：華中科技大學，2006.

［7］Li J，Teng H Z.3Dvisualization technology and application of seabed terrain［J］.Ocean Surveying and Mapping，2004，24（4）：44－47.

［8］梁 俊，王 琪，劉坤良，等.基于隨機中點位移法的三維地形模擬［J］.計算機仿真，2005，22（1）：213－215，223.

［9］王占東.細分曲面關鍵技術研究［D］.南京：南京航空航天大學，2003.

［10］劉樹群，任到飛.迭代函數(shù)系統(tǒng)吸引子逼近的一個標記算法［J］.蘭州理工大學學報，2010，36（2）：83－87.

Terrain generation based on the method of random subdivision displacement

ZHANG Runhua1，2，LIU Shuqun2，ZHAO Fuqing2
（1.Department of Fundamental Courses，Gansu Construction Vocational Technical College，Lanzhou 730050；2.School of Computer and Communication，Lanzhou University of Technology，Lanzhou 730050）

In this paper，4－point subdivision scheme is extended to 3Dsurface，and a method of random subdivision displacement terrain generation based on quadrilateral grid 4－point subdivision scheme is proposed.The experimental results indicate that the algorithm is capable of creating the terrain of reality and fundamental controllability，which solves the unpredictable，unmanageable，crannied and untrue problems in terrain generation based on traditional random mid－point displacement method（RMD）.

terrain；topography；random mid－point displacement method；subdivision；boundary

TP391

A

1000－1190（2012）05－0533－04

2012－01－03.

國家自然科學基金項目（61064011）.

＊E－mail：zhangrh2010＠qq.com.