靳碧鵬

(中國(guó)西南電子技術(shù)研究所,成都 610036)

1 引 言

毫米波防撞雷達(dá)是針對(duì)直升機(jī)在惡劣氣候條件下低空飛行時(shí),無(wú)法清晰判斷前方危險(xiǎn)障礙物,進(jìn)而影響飛機(jī)飛行安全的情況而設(shè)計(jì)的。這種障礙物防撞功能,要求雷達(dá)終端顯示界面能夠非常直觀、準(zhǔn)確地顯示障礙物目標(biāo),以方便飛行員及時(shí)作出反應(yīng)。目前,國(guó)內(nèi)雷達(dá)的終端顯示都是以二維方式為主,主要有PPI顯示、B型顯示、C型顯示3種,但都有各自的缺陷:PPI顯示方式以極坐標(biāo)的形式顯示目標(biāo)的距離和方位,B型顯示以直角坐標(biāo)的形式顯示目標(biāo)的距離和方位,兩種方式都無(wú)法直觀地表示目標(biāo)高度;C型顯示方式能夠清晰地顯示目標(biāo)的高度,卻無(wú)法直觀地顯示目標(biāo)的距離。在毫米波防撞雷達(dá)中,我們提出采用3D(三維)方式顯示雷達(dá)目標(biāo),這種方式不僅可以直觀地顯示目標(biāo)的三維位置,還能真實(shí)地再現(xiàn)掃描空域內(nèi)的實(shí)際場(chǎng)景。然而,這種方式在具體實(shí)現(xiàn)時(shí),卻面臨一些問(wèn)題:由于嵌入式圖像處理板的硬件限制,圖像繪制速度慢,無(wú)法達(dá)到系統(tǒng)的實(shí)時(shí)性要求;由于繪制效率的原因,無(wú)法考慮地形真實(shí)感方面的問(wèn)題,形成的地形場(chǎng)景單一,無(wú)法反映不同高度的地貌特征,或者沒(méi)有添加陰影效果,繪制的地形立體感不強(qiáng)。在這種背景下,本文提出了地形分塊加速繪制算法,以及隨機(jī)紋理與頂點(diǎn)顏色相融合的地形著色方法。

2 地形分塊加速算法

本文算法是一種規(guī)則網(wǎng)格地形繪制算法。目前基于規(guī)則網(wǎng)格的地形繪制算法在實(shí)際中應(yīng)用較多的包括實(shí)時(shí)連續(xù)細(xì)節(jié)層次繪制(基于四叉樹(shù)結(jié)構(gòu)LOD)[1]、實(shí)時(shí)的最優(yōu)自適應(yīng)網(wǎng)格(ROAM)[2]、基于GeoMipMap的繪制[3]、嵌套網(wǎng)格算法[4]。

本文設(shè)計(jì)的地形分塊加速繪制算法源自基于四叉樹(shù)結(jié)構(gòu)的LOD算法思想,將地形分塊,不同塊采用不同的細(xì)節(jié)描繪。不同的是,LOD算法是自頂向下遞歸細(xì)分地形,從而建立多分辨率的地形層次模型;本文算法僅僅是建立兩層分辨率的地形模型,其過(guò)程是:首先將地形分成若干個(gè)大小相同的方塊(除邊界方塊外),然后利用一定的準(zhǔn)則判斷本次分塊是否合理,如果不合理,將地形進(jìn)一步細(xì)分為更多的方塊(地形塊個(gè)數(shù)是上一次的2倍),如此遞歸,直到找出滿足算法準(zhǔn)則的分塊方式。這種分塊算法相比較四叉樹(shù)結(jié)構(gòu)的LOD算法實(shí)現(xiàn)更為簡(jiǎn)單,而且每次地形數(shù)據(jù)發(fā)生變化時(shí),地形分塊和地形渲染完全分離,大大提高了繪制速度。另外,本算法不需要滿足四叉樹(shù)結(jié)構(gòu)LOD算法中頂點(diǎn)個(gè)數(shù)必須為2n×2n的條件,適應(yīng)于任意頂點(diǎn)個(gè)數(shù)的地形繪制。

2.1 分塊算法描述

假設(shè)地形頂點(diǎn)的個(gè)數(shù)為M×N,分塊后每個(gè)地形方塊包含K行、K列個(gè)地形頂點(diǎn)。第一次分塊時(shí),設(shè)置K等于M、N的最大公約數(shù),那么地形被等分為 m×n個(gè)方塊,其中,m=Round(M/K),n=Round(N/K)。

(1)設(shè)置 m×n個(gè)方塊的信息,存儲(chǔ)到數(shù)組Quad[m][n]中。地形方塊的信息結(jié)構(gòu)體定義如下:

其中,f Ratio=C/K×K,C為地形方塊中表示障礙物的頂點(diǎn)(頂點(diǎn)高度大于地面高度)個(gè)數(shù),f Ratio表示了地形方塊中障礙物頂點(diǎn)所占的比例。

(2)遍歷數(shù)組Quad[m][n]中的每個(gè)Quad[i][j],統(tǒng)計(jì)屬性 fRatio=0的方塊個(gè)數(shù)Q,計(jì)算其所占的比例a:

式中,a代表所有方塊中無(wú)障礙物目標(biāo)的方塊所占的比例,如果a較大,說(shuō)明劃分后無(wú)障礙物目標(biāo)的方塊占的比例比較多,繪制時(shí)可以采用較少的細(xì)節(jié)描繪;如果a較小,說(shuō)明無(wú)障礙物目標(biāo)的方塊數(shù)目占的比例較少,需要繼續(xù)細(xì)分方塊,降低細(xì)節(jié)層次。

計(jì)算屬性f Ratio≠0時(shí),fRatio的平均值s:

式中,s代表障礙物頂點(diǎn)在方塊中所占的平均比例,如果s較大,說(shuō)明方塊中分布了較密集的障礙物頂點(diǎn),無(wú)法再細(xì)分;如果 s較小,說(shuō)明方塊中障礙物頂點(diǎn)分布非常稀疏,還可以繼續(xù)細(xì)分,分離出無(wú)障礙物目標(biāo)的方塊。

(3)依據(jù)a、s的值判斷此次分塊是否為最優(yōu)分塊。在試驗(yàn)中,我們尋找的最佳經(jīng)驗(yàn)值為:如果a<0.4,或者a≥0.4并且s<0.2時(shí),需要繼續(xù)細(xì)分地形,此時(shí)設(shè)置K=K/2,依據(jù)頂點(diǎn)個(gè)數(shù)K重新劃分地形,生成m×n個(gè)地形方塊,轉(zhuǎn)到步驟1進(jìn)行新一輪的判斷。

(4)如果不滿足步驟3的條件或者K=1時(shí),說(shuō)明此次分塊是最優(yōu)分塊或者無(wú)法再細(xì)分,則停止分塊。

2.2 網(wǎng)格渲染與裂縫修補(bǔ)

地形合理分塊后,以塊為單位繪制所有地形塊。繪制時(shí),判斷地形方塊的屬性 fRatio的值,如果fRatio=0,說(shuō)明地形塊中沒(méi)有障礙物目標(biāo),只需要采用較少的細(xì)節(jié)描繪,只需繪制方塊的4個(gè)頂點(diǎn)構(gòu)成的兩個(gè)三角形面,如圖 1中的C2、C3,圖中圓形頂點(diǎn)為地形頂點(diǎn);如果 fRatio≠0,說(shuō)明地形塊中有障礙物,需要保持地形的細(xì)節(jié),因此需要繪制方塊內(nèi)所有頂點(diǎn)構(gòu)成的三角形面,如圖2中的C1,三角形個(gè)數(shù)較 C2、C3的多。

圖1 地形分塊渲染示意圖Fig.1 Quad rendering in terrain

圖2 補(bǔ)畫(huà)裂縫示意圖Fig.2 Four cases of mending a crack between quads

可以看出,分塊加速繪制算法的核心是盡量分離出不包含障礙物目標(biāo)的地形方塊,以減少繪制的三角形個(gè)數(shù),提高繪制速度。

但是,由于一個(gè)頂點(diǎn)只屬于一個(gè)地形塊,以塊為單位繪制地形,相鄰兩個(gè)方塊之間會(huì)出現(xiàn)裂縫。為了消除裂縫,每個(gè)方塊繪制結(jié)束后,必須補(bǔ)畫(huà)它與右邊相鄰方塊、上邊相鄰方塊之間的裂縫。補(bǔ)畫(huà)裂縫時(shí),判斷相鄰兩個(gè)方塊的屬性fRatio是否都為0,如果是,繪制兩個(gè)方塊之間相鄰的4個(gè)頂點(diǎn)構(gòu)成的兩個(gè)三角形,如圖2(a)演示了C1與右邊相鄰方塊C2補(bǔ)畫(huà)裂縫的三角形面,圖2(c)演示了C1與上邊相鄰方塊C2補(bǔ)畫(huà)裂縫的三角形面;如果有一個(gè)方塊的屬性fRatio≠0,那么繪制相鄰兩行或者兩列上所有頂點(diǎn)構(gòu)成的三角形,如圖2(b)、(d)所示,此時(shí)的三角形個(gè)數(shù)較多。

3 快速地形著色方法

在顯示界面中,不但要表現(xiàn)地形的真實(shí)感,而且需要突出表現(xiàn)地形的高度層次,以提示障礙物的危險(xiǎn)級(jí)別。多紋理混合繪制算法[5]能夠較好地反映地形的層次感和立體感,但是,這種算法在每次地形數(shù)據(jù)變化時(shí),都需要重新將多種紋理混合成一張與地形匹配的紋理圖像,CPU占用時(shí)間長(zhǎng),系統(tǒng)實(shí)時(shí)性差。本文提出了利用Diamond-Square算法[6]生成帶有隨機(jī)陰影的紋理圖模擬地形表面凹凸不平的細(xì)節(jié),再混合多種顏色表現(xiàn)地形的高度層次,這種混合著色的方法占用內(nèi)存少,處理速度快,能夠很好地滿足系統(tǒng)的實(shí)時(shí)性要求。

3.1 利用Diamond-Square算法生成紋理

(1)首先利用Diamond-Square算法生成地形的高程數(shù)據(jù),算法描述如下:

1)初始化二維數(shù)組n×n(n=2m+1),并將4個(gè)角設(shè)為相同高度。圖3以一個(gè)5×5的數(shù)組為例,其中4個(gè)角放入初始高度值,用圓點(diǎn)表示,此為遞歸細(xì)化過(guò)程的起點(diǎn);

2)Diamond步:取5×5正方形的4個(gè)點(diǎn)構(gòu)成的正方形,用二維隨機(jī)中點(diǎn)位移法為其對(duì)角線交點(diǎn)生成一個(gè)隨機(jī)高度值,作為此點(diǎn)的高度值,如圖3(b)所示;

3)將5×5正方形細(xì)分成4個(gè)3×3正方形,如圖3(c)所示;

4)Square步:取3×3正方形的棱錐中心和4個(gè)頂點(diǎn)的平均值,再加上一個(gè)與Diamond步相同的隨機(jī)位移,可以計(jì)算出每條邊的中心值,在計(jì)算位于邊界上的點(diǎn)時(shí),選用正方形另外一條邊附近的對(duì)稱點(diǎn)作為求平均值的點(diǎn);

5)對(duì)上述過(guò)程進(jìn)行迭代,直至達(dá)到所有的細(xì)分網(wǎng)格點(diǎn)被填充為止。

圖3 Diamond-Square算法Fig.3 The step of Diamond-Square algorithm

(2)將算法生成的高程數(shù)據(jù)繪制為三維地形,打開(kāi)光照,增加陰影效果。

(3)讀取幀緩存中的圖像數(shù)據(jù),此時(shí),圖像為真彩色圖像,將其轉(zhuǎn)化為灰度圖,轉(zhuǎn)換公式為

其中,nRed、nGreen、nBlue分別代表紅色分量、綠色分量、藍(lán)色分量。

(4)將灰度圖載入地形紋理內(nèi)存,供紋理映射使用。

3.2 生成地形的顏色信息

對(duì)于某一個(gè)地形頂點(diǎn)Vi,設(shè)置顏色的過(guò)程如下。

(1)找出地形網(wǎng)格中與頂點(diǎn) Vi有邊連接的6個(gè)頂點(diǎn),比較7個(gè)頂點(diǎn)的高度,找出其中的最大高度值H,如圖4所示,中間的方形頂點(diǎn)是頂點(diǎn)Vi,圓形頂點(diǎn)是與頂點(diǎn)Vi有邊連接的6個(gè)頂點(diǎn)。

圖4 相鄰頂點(diǎn)示意圖Fig.4 The neighbor vertex connect with a certain vertex

(2)依據(jù)高度 H的大小,設(shè)置頂點(diǎn) Vi的顏色,分以下幾種情況:如果H等于地面高度,頂點(diǎn)Vi的顏色為綠色,代表草地;如果H低于載機(jī)高度,頂點(diǎn)Vi的顏色為灰白色,代表一般障礙物;如果H高于載機(jī)高度,頂點(diǎn)Vi的顏色為黃色,代表危險(xiǎn)地形。

渲染地形時(shí),設(shè)置紋理映射方式為混合模式,為每個(gè)地形頂點(diǎn)指定紋理坐標(biāo)和RGB顏色,混合渲染后的地形不但立體感強(qiáng),而且地形層次非常清晰。由于著色方法使用的分形紋理是在初始化時(shí)生成的,因此程序在運(yùn)行過(guò)程中只需要維護(hù)一組與高程數(shù)據(jù)相匹配的顏色數(shù)據(jù),占用的內(nèi)存少,計(jì)算量小,處理速度快,很好地滿足了系統(tǒng)的速度要求。圖5顯示了利用雷達(dá)數(shù)據(jù)生成的三維地形效果圖。

圖5 地形渲染效果圖Fig.5 The terrain rendered by coloredmethod

4 場(chǎng)景漫游

系統(tǒng)中,每隔一幀產(chǎn)生一組新的地形數(shù)據(jù),為了反映載機(jī)在真實(shí)場(chǎng)景中的飛行,場(chǎng)景視點(diǎn)的位置在一幀的時(shí)間間隔內(nèi)需隨載機(jī)速度移動(dòng),當(dāng)新一幀的地形數(shù)據(jù)產(chǎn)生時(shí),場(chǎng)景視點(diǎn)返回零點(diǎn),然后重新開(kāi)始隨載機(jī)速度向前移動(dòng),直到新的地形數(shù)據(jù)再次產(chǎn)生。

視點(diǎn)在場(chǎng)景中移動(dòng)的距離按如下公式計(jì)算:

式中,D是視點(diǎn)移動(dòng)的距離,V是載機(jī)速度,T是一幀的時(shí)間間隔,FACT是三維場(chǎng)景與真實(shí)場(chǎng)景之間的縮小比例。

如果僅僅靠移動(dòng)視點(diǎn)來(lái)顯示載機(jī)的運(yùn)動(dòng),每次幀切換、場(chǎng)景變化、視點(diǎn)返回零點(diǎn)時(shí),視覺(jué)上有一種被強(qiáng)行拉回的感覺(jué),這是因?yàn)樵谝粠瑫r(shí)間間隔內(nèi),視點(diǎn)不斷向前移動(dòng)而地形紋理始終不變引起的。為了幀切換時(shí)也能有流暢的漫游效果,地形紋理需要隨視點(diǎn)位置的變化而同步移動(dòng)。軟件中,紋理移動(dòng)通過(guò)變換紋理坐標(biāo)來(lái)實(shí)現(xiàn),每次渲染時(shí),累加視點(diǎn)移動(dòng)的距離,計(jì)算其對(duì)應(yīng)到紋理圖上的偏移值,將該偏移值添加到每個(gè)紋理坐標(biāo)上。這種紋理與視點(diǎn)同步移動(dòng)的漫游方法,使得每次地形數(shù)據(jù)更新,場(chǎng)景交替時(shí)的畫(huà)面非常流暢自然。

5 實(shí)驗(yàn)與結(jié)論

本文的三維終端顯示軟件在嵌入式圖像處理板上運(yùn)行,硬件配置為:CPU為Intel Core Duo處理器U2500,頻率為1.2 GHz,內(nèi)存為1 GB,顯卡為 Intel945GM chipset,顯存為128 MB,采用Visual C++6.0和OpenGL編程。本系統(tǒng)中,三維地形的頂點(diǎn)個(gè)數(shù)固定為300×400,對(duì)于圖5所示的地形場(chǎng)景,未使用分塊加速算法時(shí),三角形個(gè)數(shù)為238602個(gè),繪制時(shí)間為142 ms;采用分塊加速算法后,繪制的三角形個(gè)數(shù)變?yōu)?2736個(gè),繪制時(shí)間縮短為31 ms。實(shí)驗(yàn)證明,本文采用的地形分塊算法、著色方法、場(chǎng)景漫游完全滿足了防撞雷達(dá)系統(tǒng)的性能需求,繪制速度快,場(chǎng)景交替自然流暢,能夠真實(shí)顯示載機(jī)飛行前方的地形場(chǎng)景,為飛行員提供直觀可靠的信息。另外,本文提出的算法也同樣適用于其它背景的三維地形繪制。

[1]Lindstrom P,Koller D,Ribarsky W,et al.Real-time continuous level of detail rendering of height fields[C]//Proceedings of Annual Conference on Computer Graphics Series.New Orleans,LA:ACM,1996:109-118.

[2]Bryan Turner.Real-Time Dynamic Level of Detail Terrain Rendering with ROAM[EB/OL].(2000-04-03)[2006-10-12].http://www.gamasutra.com/features/20000403/turner-01.htm.

[3]de Boer Willem H.Fast Terrain Rendering Using Geometrical Mip-mapping[EB/OL].(2001-02-12)[2006-10-12].http://www.flipcode.com/tutorials/geomipmaps.pdf.

[4]Losasso F,Hoppe H.Geometry Clipmaps:Terrain Rendering Using Nested Regular Grids[J].ACM Transactions onGraphics,2004,23(3):769-776.

[5]黃忠,張佑生.基于約束四叉樹(shù)的真實(shí)感地形繪制[J].合肥工業(yè)大學(xué)學(xué)報(bào),2008,31(6):854-857.HUANG Zhong,ZHANG You-sheng.Realistic rendering of terrain based on restricted quadtree[J].Journal of Hefei University of Technology(Natural Science),2008,31(6):854-857.(in Chinese)

[6]王麗芳.基于隨機(jī)分形的地形場(chǎng)景的研究[J].山西電子技術(shù),2007(5):15-16.WANG Li-fang.Research of Terrain Scenes Based on Random Fractal[J].Shanxi Electronic Technology,2007(5):15-16.(in Chinese)