分形算法調(diào)和的海浪模擬方法

印桂生，王海玲，張菁，陳懷友

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 1 50001)

隨著虛擬現(xiàn)實(shí)和計(jì)算機(jī)圖形學(xué)技術(shù)的發(fā)展，動態(tài)海面作為三維游戲系統(tǒng)、虛擬現(xiàn)實(shí)系統(tǒng)、軍事仿真系統(tǒng)的重要組成部分得到了多方的重視．眾所周知，海面是一個形態(tài)復(fù)雜，變化不規(guī)則的，這給高真實(shí)感的波浪建模帶來了一定難度，因此，如何在滿足實(shí)時性要求的基礎(chǔ)上進(jìn)行高真實(shí)感的海浪建模成為了研究重點(diǎn)．目前，水面建模方法主要分為基于物理［1］、基于幾何構(gòu)造［2］和面向視覺效果［3］3 類方法．基于物理的方法遵行水體的運(yùn)動原理，通過求解流體力學(xué)方程——Navier Stokes方程(NSF)來得到水面的速度場、壓力場景，從而生成波浪運(yùn)動形態(tài)，其方法公式求解復(fù)雜，計(jì)算量巨大，實(shí)時性較差，多用于數(shù)值分析和工程應(yīng)用．為了避開大量的物理方程計(jì)算，學(xué)者們開始從波浪的幾何形狀入手，利用數(shù)學(xué)方法構(gòu)造波浪形態(tài)，這種方法的構(gòu)造函數(shù)相對簡單，計(jì)算速度快，得到了游戲、影視特效等領(lǐng)域的青睞，但仍存在著波浪模型單一，波動規(guī)則的弊端．面向視覺效果的方法是采用紋理貼圖或者圖像疊加的方法來合成水面效果，這類方法是迎合實(shí)時性要求很高的產(chǎn)物，它形成的波形局限性較大，近視點(diǎn)觀察時，視差效果消失，真實(shí)感降低．

虛擬現(xiàn)實(shí)系統(tǒng)對水面繪制的實(shí)時性和真實(shí)性要求較高，為了解決這一問題，提出一種分形算法調(diào)和的海面模擬方法．該算法將海浪模型分解為大尺度基波、小尺度細(xì)節(jié)和視覺效果三部分，通過余弦波疊加對基波建模，有效地降低了計(jì)算量;算法的核心是引入MPRD算法，充分利用分形算法自相似性和fBm特性來擬合海面的分形細(xì)節(jié)．文中不是簡單地應(yīng)用分形算法，而是通過對海浪的分析，提取具有海面特征的分形隨機(jī)變量，用于優(yōu)化分形參數(shù)，控制細(xì)節(jié)的變化;同時在多分辨率網(wǎng)格模型基礎(chǔ)上，結(jié)合視點(diǎn)距離、人眼特性及視點(diǎn)變化速度等因素生成不同遞歸深度的細(xì)節(jié)層次，并根據(jù)設(shè)定的標(biāo)準(zhǔn)將基波與分形細(xì)節(jié)進(jìn)行調(diào)和，合成的波形不僅具有各向同性的波浪特征，還具有各向異性的細(xì)節(jié)特性，實(shí)現(xiàn)了視相關(guān)的海面建模．算法力求完成實(shí)時的高真實(shí)感海面建模，在建模的過程中，利用GPU硬件特性進(jìn)行海面視覺效果模擬，有效地保證了算法的繪制速度．

1 大尺度基波建模

根據(jù)線性波浪理論［4-5］，采用如下大尺度基波模型:

式中:H(x，z，t)表示多個余弦波組成的多向隨機(jī)波;Ai是波幅;ki是波數(shù)，Ki=2π/Li，Li是波長;θi為波浪傳播的方向角，θi∈［-π，π］;φi隨機(jī)初始相位，φi∈［0，2π］;ωi為第 i項(xiàng)角頻率，ω2=gKtanh(Kh)，對于深水波，=gK，h是水深，g 重力常數(shù)．Ls是平均波長，決定了高頻波和低頻波的比例;?為波形測度系數(shù)，決定海面形態(tài)．

式中:φ為風(fēng)向角度，λ是波浪擴(kuò)散程度的調(diào)整系統(tǒng)．為了提高波浪的動力學(xué)特性，在求解各種參數(shù)后，將在約束中隨機(jī)產(chǎn)生某些參數(shù)，隨著時間參數(shù)t的變化，生成大尺度波浪形態(tài)．

2 波浪的分形細(xì)節(jié)建模

分形理論(FT)是由Mandelbrot首先引入自然科學(xué)領(lǐng)域［6］．FT的自相似性具有膨脹/收縮對稱性，適合描述各向同性的現(xiàn)象;而其自仿射性的膨脹/收縮的對稱性不同，適合描述各向異性的現(xiàn)象，這些性質(zhì)與海面波動特征相同，因此引入分形算法來添加波形細(xì)節(jié)具有很好的理論支撐．

2．1 MPRD算法的引入

MPRD是一種快速細(xì)分方法，假如海面網(wǎng)格的大小為(2n+1)×(2n+1)，網(wǎng)格間距為l00，對任一網(wǎng)格元，假設(shè) Hij、Hij+1、Hi+1j、Hi+1j+1是其 4 個頂點(diǎn)的高度值，網(wǎng)格的MPRD分形過程為:首先進(jìn)行網(wǎng)格元中心點(diǎn)的插值，網(wǎng)格元的中心點(diǎn)高度值Hic為

式中:Hit、Hir、Hib、Hil是與 Hic相鄰的網(wǎng)格元中心點(diǎn)高度值，Ric、Rit、Rir、Rib、Ril是自定義的隨機(jī)值位移，此時，網(wǎng)格間距為

式(5)是式(2)的特殊形式，說明MPRD可用于海面形態(tài)模擬過程．MPRD完成細(xì)分后，網(wǎng)格數(shù)量變?yōu)樵瓉淼?2i倍，i=1，2，…，n 為遞歸深度，隨著遞歸深度增加，分形細(xì)節(jié)越來越粗糙．從上面的公式可以看出，參與細(xì)分的數(shù)據(jù)有已知的頂點(diǎn)高度值和隨機(jī)位移量，并者體現(xiàn)了點(diǎn)與點(diǎn)的相關(guān)性，而后者體現(xiàn)了點(diǎn)與點(diǎn)的差異性．

2．2 特征約束的隨機(jī)變量

隨機(jī)變量決定分形波浪的形態(tài)特征和多樣性，以往的隨機(jī)變量形式難以保證分形的局部穩(wěn)態(tài)，因此，設(shè)計(jì)一個好的隨機(jī)變量至關(guān)重要．由 FT知，MPRD滿足fBm的冪指數(shù)規(guī)律:

那么，細(xì)分的點(diǎn)與任一相鄰網(wǎng)格點(diǎn)滿足上式關(guān)系，式(4)可表述為如下方式:

將式(7)展開，得

式中:H，σ是分形特征參數(shù)．由式(8)可求出隨機(jī)變量的形式為

構(gòu)建MPRD的最大難點(diǎn)在于消除分形曲面的折痕，保證變量取值的合理性十分關(guān)鍵，由式(9)及分形變量特征，定義MPRD的隨機(jī)變量如下:

式中:l是調(diào)節(jié)函數(shù)，控制變量的隨機(jī)性，Gauss為服從N(0，1)的高斯函數(shù)．

余弦疊加的波浪具有各向同性和各向異性，若估計(jì)出頻域和方向域的變化程度，則可修正分形參數(shù)，控制分形結(jié)果．文中引入水面波向、視向及水面熵特征參數(shù)來改進(jìn)分形特征，對于分形特征取值窗口W為M×N的海面網(wǎng)格，特征提取的公式如下．

1)波向特征值Hh．

式中:Δh 為采樣步長，P(x，y)為海面坐標(biāo)(x，y)處的高度值，mh(Δh)為分形窗口的相對高度值，保證了分形參數(shù)與領(lǐng)域頂點(diǎn)信息的相關(guān)性．不同的采樣步長，可以得到對應(yīng)的mh(Δh)值，根據(jù)隨機(jī)過程屬性有:

將式(12)取對數(shù):

通過最小二乘法的逼近原理，對不同Δh和mh(Δh)擬合(lg‖Δh‖，lgmh)，使用擬合直線的斜率求出參數(shù)Hh的估計(jì)．

2)視向特征值Hv．

如上述方法，可求出參數(shù)Hv的估計(jì)．

3)水面熵特征值Hs．

為了體現(xiàn)分形區(qū)域內(nèi)所有頂點(diǎn)的相關(guān)性，確保分形穩(wěn)態(tài)性，對網(wǎng)格窗口 作整體度量，定義水面熵Hw:

hij是相對高度分布，?是調(diào)節(jié)值，Pl=min{Pi;i，j=1，2，…，m}，同理可求出 Hs，σs．

FT指出，參數(shù)H可以反映曲面變形程度，其值越小，曲面越粗糙．為了計(jì)算簡單，改進(jìn)的分形特征表示如下:

2．3 多分辨分形

人眼在觀察場景時存在視覺敏感區(qū)，且由于視點(diǎn)的運(yùn)動性，海面細(xì)節(jié)無需過高．因此，方法在文獻(xiàn)［7］的基礎(chǔ)上改進(jìn)，為不同區(qū)域的海面添加不同分形細(xì)節(jié)．

圖1 視域劃分Fig．1 View field division

首先根據(jù)視截體判定視場，如圖1所示，V是視點(diǎn)位置，V'是視點(diǎn)垂足，V0是其在場景中的投影，he是視點(diǎn)高度，Pn是最近可視點(diǎn)，dn是最近可視點(diǎn)距離，Pf是最遠(yuǎn)可視點(diǎn)，df為可見的最遠(yuǎn)點(diǎn)距離，α視向角，視場角為fO．計(jì)算出可視區(qū)域后，假設(shè)Vs將進(jìn)一步劃分層次級別，而對Vs以外的區(qū)域直接剪裁．在可視區(qū)域內(nèi)，頂點(diǎn)與視點(diǎn)的距離不同，視覺敏感度也不同，距離越近，敏感性越強(qiáng)，海面細(xì)節(jié)也應(yīng)相對增加．則視域的敏感分層可表達(dá)如下:

式中:Δθ是不同敏感度間的遞增角度，η為敏感層次數(shù)，Δθ=f0/2η，V0=Pn+(Pf-Pn)cos α，稱為敏感點(diǎn)，rO是最高級的敏感區(qū)域半徑，ri是不同LOD層的半徑．

由Nyquist定理，設(shè)定網(wǎng)格與波長關(guān)系是1/4min(L/Li，i=1，2，…，n)≤L00＜ 1/2min(L|Li，i=1，2，…，n)，此外，視點(diǎn)的運(yùn)行速度也是影響分形的重要因素，視點(diǎn)運(yùn)動很快，對海面區(qū)域認(rèn)知性較少，不需要對海面增加分形細(xì)節(jié)．因此，分形遞歸的影響函數(shù)可定義為

式中:ν是視點(diǎn)單位時間內(nèi)的變化速度，θh是視點(diǎn)左右的變化角度，θv是前后移動時引起的視角變化．ν值越小，說明視點(diǎn)變化比較快，視覺效果分辨率較低，不用進(jìn)行分形變化．μ(p，ε)分形的測度函數(shù)，A為波浪振幅，ε=κ×Δτ尺度的測度，Δτ采樣間隔，f(ri，di)是與視點(diǎn)相關(guān)的調(diào)整因子，νf、vn分別是視域的調(diào)整系數(shù)，di是視線與場景的距離．

海面細(xì)分時，通過設(shè)置閾值來控制分形變化．正弦波和與分形算法細(xì)節(jié)加權(quán)求和的海面形態(tài)方程可寫為 ζ=H+ γHf，ζ是組成波在時間 t時點(diǎn)(x，z)處的波形;H代表海浪譜波形;Hf表示分形細(xì)節(jié)結(jié)果;γ =cos(α +idθ)(i=0，1，2，…，η -1)是波浪調(diào)和系數(shù)，取值為［0，1］間的任意實(shí)數(shù)．可以證明，函數(shù)ζ是周期為2π的周期函數(shù)，當(dāng)γ由0連續(xù)變化到1時，海浪也由細(xì)節(jié)豐富的波浪逐漸過渡到基于譜的波形．

3 面向GPU的海面視覺效果

光照是提高海面的視覺效果的重要因素，基于物理方法的實(shí)時計(jì)算海面光照屬性計(jì)算量大．為了進(jìn)一步提高計(jì)算效率，算法利用GPU技術(shù)特性實(shí)現(xiàn)海面的紋理貼圖和光照效果．文中海面的視覺效果主要由3部分組成，近似表示為

式中:Ws海面基色，Wrfl是水面的反射效果，Wrfr是水面的折射效果，ψ是菲涅爾系數(shù)，表示了光在表面發(fā)生反射和折射現(xiàn)象的概率，決定兩者對海面作用的相對比重，ψ∈［0．1，1．0］，其中，ζ= ηa/ηw-sin2α，ζ'=(cos α(ζ+cos α)-1)2，ζ″=(cos α(ζ-cos α)+1)2，ηa和ηw分別是空氣和水的折射率，α是入射光與海面法向的夾角．

3．1 菲涅爾系數(shù)

海面是連續(xù)變化的，若實(shí)時計(jì)算菲涅爾系數(shù)會比較費(fèi)時，如果將ψ值的求解在預(yù)處理階段完成，則節(jié)省了大量實(shí)時運(yùn)算時間．通過頂點(diǎn)shader獲得海面頂點(diǎn)信息，將其轉(zhuǎn)換到切空間坐標(biāo)中，記錄不同視向時的所有入射角，然后將這些信息保存在紋理中，然后制作成菲涅爾系數(shù)的紋理圖，圖像中的信息作為像素shader的輸入，像素shader程度過程中針對海面頂點(diǎn)進(jìn)行視覺效果融合．

3．2 海面基色

基色是海面的自身顏色，沒有任何外界環(huán)境的影響，文中采用Wang tile貼圖方法［8］進(jìn)行映射海面的基色紋理．根據(jù)頂點(diǎn)shader記錄的波浪高度值及視點(diǎn)向量，對紋理進(jìn)行尋址，然后在像素shader中計(jì)算對應(yīng)視點(diǎn)的海面頂點(diǎn)顏色．

3．3 反射效果

海面的反射效果采用平面反射貼圖實(shí)現(xiàn)，以海面為裁減平面，將海面以上的場景渲染為反射貼圖．然后由法線圖得到法向量，根據(jù)視線方向計(jì)算入射光，并以此為依據(jù)計(jì)算投影紋理坐標(biāo)，采樣顏色信息，動態(tài)調(diào)整紋理．

3．4 折射現(xiàn)象

文中在反射貼圖的基礎(chǔ)上，計(jì)算折射網(wǎng)格，把海平面作為折射掩碼記錄到幀緩存的Alpha通道中，用以界定折射區(qū)域，使用法線圖，施加一個很小的擾動值對紋理坐標(biāo)進(jìn)行位移，最后使用擾動后的紋理坐標(biāo)查找對應(yīng)的反射貼圖中的值來實(shí)現(xiàn)折射效果．

4 實(shí)驗(yàn)結(jié)果分析

本文方法的硬件實(shí)驗(yàn)平臺是奔騰4、3．00 GHz CPU、1GB內(nèi)存和nVIDIA GeForce 6800顯卡;海面模擬程序運(yùn)行于Window XP系統(tǒng)下，軟件環(huán)境是Visual studio2005、DirectX圖形庫和CG語言．

圖2為引入分形算法的海浪模擬實(shí)驗(yàn)，圖2(a)與圖2(b)是固定參數(shù)σ，τ后，分形特征參數(shù)H對海面形態(tài)的影響，可以看出，H控制著海面波浪的起伏程度，H越小，波浪起伏幅度越小．圖2(c)和圖2(d)是固定參數(shù)H，τ后的海面形態(tài)的變化情況，可以看出，σ控制著分形值的分布，σ越小，波浪形態(tài)分布越均勻，說明只要合理的控制H，σ，就可生成更真實(shí)的波浪模型．圖2(e)～(h)是根據(jù)波浪特性對分形參數(shù)進(jìn)行特征約束后的實(shí)驗(yàn)效果，實(shí)驗(yàn)表明，窗口取值和分形影響函數(shù)的閾值都直接影響著分形效果，閾值越大，分形遞歸深度越大，波浪形態(tài)越多樣．

圖3是在小波浪級別情況下加入光照視覺效果的海面場景，圖3(a)遠(yuǎn)視點(diǎn)的海面光照效果，圖3(b)是近視點(diǎn)海面光照效果，在遠(yuǎn)點(diǎn)時，視角較大，反射光較多，折射光比例較少，海面顏色呈現(xiàn)偏藍(lán)效果;而近視點(diǎn)時，視角較小，此時折射光相比反射光比較要大，海面顏色出現(xiàn)青色效果．

圖3 海面的光照效果Fig．3 Wave surface with optic

在海面繪制效率方面，圖4給出了3種海面模擬方法的繪制速度對比，實(shí)驗(yàn)數(shù)據(jù)是對100 s內(nèi)的速率進(jìn)行采樣而得，可以看出，海面繪制的初始階段，由于加載數(shù)據(jù)，初始化等，繪制幀率較低，隨后繪制速度逐漸平穩(wěn)．其中，Tessendorf方法和文中方法達(dá)到了較好的繪制速度，但文中方法比Tessendorf方法的繪制效率更高，在普通運(yùn)行環(huán)境中，平均幀率可達(dá)60 f/s以上．

圖4 波浪模擬方法的幀率對比Fig．4 Frame ratio of algorithms

在海面模擬的性能方法，圖5給出了不同規(guī)模海面模擬，GPU加速與否的性能對比．圖5(a)海面網(wǎng)格數(shù)據(jù)為64×64，大尺度波的疊加數(shù)為4，分形影響函數(shù)的閾值為0．3，實(shí)線表示利用GPU加速的模擬效率，虛線表示僅采用CPU的效率，由圖可知，GPU加速的繪制速率更高，速率高于后者將近1．15倍．圖5(b)是不同網(wǎng)格數(shù)量下的繪制速率，當(dāng)波面網(wǎng)格數(shù)量小于256×256時，文中方法仍然能達(dá)到較好實(shí)時性，說明本文方法可以滿足中等區(qū)域的海浪模擬．當(dāng)網(wǎng)格規(guī)模大于256×256，CPU的繪制速率下降較快，這說明模擬規(guī)模對繪制效率影響較大，因此，采用GPU技術(shù)可有效提高繪制速度．

圖5 算法的性能對比Fig．5 Comparison of algorithm efficiency

表1列出了不同LOD層數(shù)在不同分形閾值控制下的模擬效率．增加波數(shù)或增加LOD層數(shù)都會增加系統(tǒng)計(jì)算量，且分形函數(shù)也影響繪制速度．由表中數(shù)據(jù)看出，在網(wǎng)格規(guī)模小于256×256，波數(shù)為4時，方法可以得到高真實(shí)感的海面效果，且具有很好的繪制速度．

海面網(wǎng)格數(shù)LOD×4 LOD×5 0．3 0．5 0．3 0．5 64 ×64 67．42 60．27 63．19 60．23 128 ×128 60．26 57．31 56．24 51．27 256 ×256 52．64 47．39 49．82 46．61 512 ×512 40．83 37．68 37．93 34．37

5結(jié)論

提出一種高效的海浪模擬方法，將波浪分為大尺度基波和小尺度細(xì)節(jié)，通過分形算法增加海面細(xì)節(jié)，同時利用GPU實(shí)現(xiàn)海面的視覺效果．該算法有以下優(yōu)點(diǎn):

1)將海浪譜建模方法與分形算法相結(jié)合，實(shí)時了真實(shí)的波浪變形，并可實(shí)時控制變形程度．

2)對分形算法進(jìn)行優(yōu)化，利用海浪譜的頻率特性、方向特性和海面曲度控制分形參數(shù)，并結(jié)合視相關(guān)、人眼敏感特性及視點(diǎn)變化等因素控制細(xì)節(jié)級別．

3)面向GPU實(shí)現(xiàn)光照效果，充分利用GPU的加速特性提高算法效率．文中將菲涅爾系數(shù)的計(jì)算結(jié)果存儲為紋理圖，減少了系統(tǒng)計(jì)算量．實(shí)驗(yàn)表明，文中算法可以實(shí)現(xiàn)實(shí)時繪制的高真實(shí)感波浪場景．

［1］CHEN J X，LOBO N V．Toward interactive-rate simulation of fluids with moving obstacles using Navier-Stokes equations［J］．Graphics Models Image Processing，1995，57(2):107-116．

［2］TESSENDORF J．Simulating ocean water［J］．Radiosity of the Ocean Environment，2004:2-25．

［3］PHARR M，F(xiàn)ERNANDO R．GPU Gems 2:programming techniques for high-performance graphics and general-purpose computation［M］．［s．l．］:Addison-Wesley Professional，2005:283-294．

［4］俞聿修．隨機(jī)波浪及其工程應(yīng)用［M］．3版．大連:大連理工大學(xué)出版社，2003:131-137．YU Yuxiu．Random wave and its applications to engineering［M］．3rd．ed．Dalian:Dalian University of Technology Press，2003:131-137．

［5］HENRY D．On Gerstner's water wave［J］．Journal of Nonlinear Mathematical Physics，2008，15(2):87-95．

［6］MARTYN T．Realistic rendering 3D IFS fractals in realtime with graphics accelerators［J］．Computers＆ Graphics，2010，34:167-175．

［7］JOHANSON C．Real-time water rendering［D］．Lund:Lund University，2004:14-25．

［8］韓建偉，王青，周昆，等．基于Wang Tiles的幾何紋理合成［J］．軟件學(xué)報(bào)，2009，20(12):3254-3264．HAN Jianwei，WANG Qing，ZHOU Kun，et al．Wang Tiles based geometric texture synthesis［J］．Journal of Software，2009，20(12):3254-3264．