基于World Wind 三維模型加載的視錐裁剪改進(jìn)算法研究

劉洋洋　盧小平　李向陽

摘要：為了解決World Wind中三維模型加載速度慢、效率低、占用內(nèi)存高、顯示效果不佳等問題。該文通過研究World Wind運(yùn)行機(jī)制，分析三維模型的顯示原理并對其顯示過程中所采用的視錐裁剪算法進(jìn)行了改進(jìn)。實(shí)驗(yàn)結(jié)果表明，該文提出的視錐裁剪改進(jìn)算法可有效提高三維模型加載速度，減小內(nèi)存占用率，為基于World Wind的后續(xù)研究打下良好基礎(chǔ)。

關(guān)鍵詞：World Wind；三維模型；視錐裁剪

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）10-2414-04

Abstract： In order to solve the problem of 3D Model loading in the World Wind， for example low speed， low efficiency， high memory and the display effect is not well and so on. By studying the World Wind running mechanism. This paper analysis of the 3D model which used for the display principle and improved the frustum culling algorithm which be used in the process of showing . the experimental results shows that the 3D model loading becomes faster and the footprint smaller. Now there will be a good basis of the further research based on World Wind.

Key words： World Wind；3D model；frustum culling

隨著地理信息技術(shù)的快速發(fā)展，越來越多的科研機(jī)構(gòu)和科技公司開始研發(fā)三維地理信息系統(tǒng)。在眾多三維地理信息系統(tǒng)中，美國NASA開發(fā)的World Wind因其開源性而受到了廣大科研人員的青睞。在多數(shù)以World Wind為平臺(tái)的科研開發(fā)中，一般需要先將三維模型加載于其中，而后再依照所需進(jìn)行后續(xù)研究。然而三維模型在加載World Wind的過程中，往往會(huì)出現(xiàn)加載速度慢、效率低、占用內(nèi)存高、顯示效果不佳等問題，為后續(xù)科研帶來很大不便。

針對以上問題，該文基于World Wind的運(yùn)行機(jī)制，對其內(nèi)部的瓦片金字塔結(jié)構(gòu)以及用于三維模型顯示的視錐裁剪算法進(jìn)行了研究。在對World Wind視錐裁剪算法分析后發(fā)現(xiàn)三維模型加載問題大多與此有關(guān)。通過比較多種視錐裁剪算法后，基于World Wind特性，該文改進(jìn)了World Wind原有視錐裁剪算法[1]。經(jīng)實(shí)驗(yàn)表明，改進(jìn)后的視錐裁剪算法有效的解決了World Wind中三維模型加載速度慢等問題。

1 World Wind

1.1World Wind概述

World Wind是美國NASA研發(fā)的開放性三維地理信息系統(tǒng)。在數(shù)據(jù)源方面，World Wind依借NASA龐大的衛(wèi)星資源，可以隨時(shí)調(diào)用MODIS、Landsat、GLOBE、SRTM等多顆衛(wèi)星的數(shù)據(jù)信息[2]。同時(shí)再將Landsat衛(wèi)星數(shù)據(jù)圖像和雷達(dá)遙感數(shù)據(jù)結(jié)合后，通過World Wind界面，用戶可以感受到遨游三維地球的美妙體驗(yàn)。World Wind不僅提供了地球數(shù)據(jù)，還提供了月球數(shù)據(jù)。在瀏覽地球的同時(shí)，用戶還可以通過World Wind近距離的觀測月球。 World Wind還能自動(dòng)更新衛(wèi)星數(shù)據(jù)，這使得World Wind可以在全球范圍內(nèi)跟蹤火山爆發(fā)、海嘯、地震以及各種近期事件。而且根據(jù)用戶需要，World Wind還提供了城市、交通、經(jīng)緯線、國界等參考層。同時(shí)在World Wind三維地球儀上，還可以接收到來自GPS接收機(jī)的數(shù)據(jù)以及各種坐標(biāo)信息。

此外，用戶還可以對界面中的地球或者其他行星進(jìn)行放大、縮小、旋轉(zhuǎn)、傾斜等操作。同時(shí)World Wind還提供了與軟件功能相對應(yīng)的衛(wèi)星數(shù)據(jù)層次，用戶可按需進(jìn)行調(diào)整。如圖1所示。

1.2 World Wind瓦片金字塔體系

為了解決模型加載問題，該文深入World Wind內(nèi)部研究其運(yùn)行機(jī)制。在具體研究中，該文發(fā)現(xiàn)World Wind采用了瓦片金字塔模型結(jié)構(gòu)體系。把一幅圖像按照一定的比例尺寸分割成若干的小正方形柵格，其中每個(gè)柵格就是一張瓦片[3]。在瓦片的基礎(chǔ)上，把一幅圖像由小到大依次分割成多個(gè)區(qū)域。分割后，就會(huì)按照層級(jí)呈現(xiàn)出數(shù)據(jù)量由少至多、圖像比例由小到大的無頂金字塔結(jié)構(gòu)。如圖2所示。

根據(jù)瓦片金字塔結(jié)構(gòu)[4]，我們可以將World Wind分割成以下形態(tài)。如圖3所示。

構(gòu)建瓦片金子塔時(shí)，首先定義其第0層，把原始數(shù)據(jù)作為底層，然后按照需求進(jìn)行分塊，形成第0層瓦片矩陣。由第0層做基礎(chǔ)，按照每2*2個(gè)像素合成1個(gè)像素的方法構(gòu)建第1層，依照先例對其分塊，形成第1層瓦片矩陣。以此類推，最終構(gòu)成整個(gè)瓦片金字塔[5]。瓦片金子塔的優(yōu)勢在于它是一種類似于多分辨率的層次模型，能夠在提高顯示速度的前提下保證顯示精度。在地形繪制時(shí)，根據(jù)不同區(qū)域的特征，往往需要不同分辨率的紋理影像數(shù)據(jù)和高程模型數(shù)據(jù)。針對這種情況，影像金字塔和數(shù)字高程模型金字塔無需進(jìn)行實(shí)時(shí)重采樣就可為其提供數(shù)據(jù)。

作為大型三維地理信息系統(tǒng)，World Wind需要對海量的數(shù)據(jù)進(jìn)行處理。在具體的運(yùn)行中，得益于瓦片金字塔結(jié)構(gòu)體系，World Wind可以在減少完成地形繪制所需總耗時(shí)的前提下提高系統(tǒng)的輸出輸入執(zhí)行效率，進(jìn)而提升系統(tǒng)的整體性能。

2 三維模型加載

2.1 KML與KMZ

由于World Wind不提供房屋建筑等三維模型數(shù)據(jù)，所以在進(jìn)行與三維模型有關(guān)的研究時(shí)，首先需要去采集三維模型數(shù)據(jù)。由于制作三維模型費(fèi)時(shí)費(fèi)力，對科研進(jìn)度有很大影響。為了省時(shí)省力，在對三維模型沒有特定要求的情況下，科研人員一般都會(huì)選擇從互聯(lián)網(wǎng)上下載三維模型來進(jìn)行相關(guān)研究。

鑒于KML文件具有海量的模型庫，World Wind也提供了KML模型文件的加載接口。因此下載三維模型時(shí)，KML文件成為科研人員的首選。KML是一種基于XML文件格式和語法的語言，同XML一樣，KML里面包含了屬性、名稱等標(biāo)簽來顯示模型信息，如點(diǎn)坐標(biāo)、經(jīng)緯度、高度以及超鏈接等[6]。KML文件、dae文件、圖片文件夾，三者共同壓縮后形成可加載的KMZ三維模型文件。

2.2 KMZ文件批量加載的實(shí)現(xiàn)

由于World Wind提供的KMZ文件加載接口每次只能加載一個(gè)三維模型，而針對三維模型的研究往往需要對一定區(qū)域的多個(gè)三維模型進(jìn)行加載。為了解決這個(gè)問題，該文改進(jìn)了World Wind中加載三維模型的KMLViewer類，最終實(shí)現(xiàn)了三維模型在World Wind上的批量加載。

與此同時(shí)，問題也隨之出現(xiàn)。在對單個(gè)三維模型進(jìn)行加載時(shí)，World Wind三維模型加載速度慢、效率低、占用內(nèi)存高、顯示效果不佳等問題并不明顯。但是在多個(gè)三維模型批量加載時(shí)，可以明顯的看到World Wind出現(xiàn)了卡滯現(xiàn)象，而且多數(shù)三維模型的紋理加載失敗呈現(xiàn)透明狀態(tài)，左邊框架里的選項(xiàng)也消失不見，CPU內(nèi)存使用率急劇升高，電腦瀕臨死機(jī)狀態(tài)。如圖4所示。

World Wind中三維模型批量加載的問題嚴(yán)重影響了后續(xù)研究的開展。為了解決這個(gè)問題，該文對三維模型批量加載類的代碼進(jìn)行分析后，最終選擇改進(jìn)視錐裁剪算法來解決該問題。

3 視錐裁剪

視錐體是指采用空間變換矩陣計(jì)算出的一個(gè)由六個(gè)面組成的有效顯示范圍[7]。如圖5所示。

根據(jù)視錐裁剪算法原理，三維地理信息系統(tǒng)只顯示視錐體范圍內(nèi)的三維模型，對范圍外的模型一律不再顯示，因此視錐裁剪算法能有效地提高三維地理信息系統(tǒng)的顯示效率。通過研究java版World Wind代碼，該文發(fā)現(xiàn)World Wind中的視錐體首先顯示球面數(shù)據(jù)，而后顯示新加載的模型區(qū)域。這雖然能顯示球體完整的DEM等數(shù)據(jù)，但會(huì)影響World Wind中新加載的三維模型顯示效率，造成模型加載速度慢、效率低、內(nèi)存占用高等問題。

基于以上問題，該文在研究對比了多種視錐裁剪算法后，對World Wind中的視錐裁剪算法進(jìn)行了改進(jìn)。劉牧曾提出對模型區(qū)域建立最小包圍球體的想法[8]，在針對單個(gè)模型或小面積模型區(qū)域時(shí)，這種方法還比較有效。但隨著模型區(qū)域面積的擴(kuò)大，長和寬也會(huì)隨之變大，但高度基本不變。所以在對大面積模型區(qū)域進(jìn)行包裹時(shí)，最小包圍球其實(shí)只有小半個(gè)球體包圍著模型區(qū)域，這就造成了空間上的大量冗余，加重了程序運(yùn)行負(fù)擔(dān)。由于大面積模型區(qū)域類似于一個(gè)不規(guī)則的長方體，所以長方體會(huì)更加合適包裹三維模型區(qū)域。該文對視錐裁剪算發(fā)改進(jìn)的基礎(chǔ)思想就是構(gòu)建一個(gè)基于三維模型區(qū)域的最小長方體，通過對視錐裁剪算法的改進(jìn)，讓視錐體優(yōu)先顯示最小長方體中的三維模型區(qū)域，而后顯示球體的DEM等數(shù)據(jù)，這樣能有效的解決三維模型加載速度慢、效率低、占用內(nèi)存高等問題。算法步驟如下：

首先，按照模型區(qū)域的長寬高來定義一個(gè)包圍它的最小長方體。其次，通過長方體中兩條對角線的交點(diǎn)找到長方體的中心點(diǎn)L，設(shè)L的坐標(biāo)為（x0，y0，z0），x0，y0，z0可為任意值。長方體的具體構(gòu)建將在World Wind的JOGL中予以實(shí)現(xiàn)。然后，分別定義視錐體的六個(gè)面為A、B、C、D、E、F，通過World Wind中的frustum類找到與六個(gè)面相對應(yīng)的投影矩陣。如圖6所示。

根據(jù)投影矩陣得出對應(yīng)六個(gè)面的個(gè)基本平面方程。以左剪切平面為例可得以下方程：

其中的x.y.z則代表任意一點(diǎn)的坐標(biāo)。將x.y，z代入其中，如果所得值大于0，則說明此點(diǎn)在左切面內(nèi)側(cè)。同理，將此點(diǎn)坐標(biāo)分別代入六個(gè)面的方程中，如果都大于0，則此點(diǎn)在視錐體內(nèi)。根據(jù)視錐裁剪算法原理，視錐體只顯示與其相交或者在其內(nèi)部的物體，于是六個(gè)方程計(jì)算數(shù)值都大于0的此點(diǎn)可顯示，否則不予顯示。最后，將包圍模型區(qū)域的最小長方體中心點(diǎn)L的坐標(biāo)（x0。y0.z0）分別代入六個(gè)平面方程中。如果結(jié)果全部大于0，則說明該中心點(diǎn)在視錐體內(nèi)，可判定最小長方體與視錐體相交或者在視錐體內(nèi)部，按照視錐體的顯示原理，判定對此最小長方體中的三維模型區(qū)域予以顯示，否則不予顯示。

4 實(shí)驗(yàn)對比與結(jié)果

最后，該文通過實(shí)驗(yàn)來驗(yàn)證該算法的可行性。首先選擇一塊三維模型較多的區(qū)域作為實(shí)驗(yàn)區(qū)。由于美國華盛頓市KMZ模型資源比較豐富，所以本文選擇華盛頓某地作為實(shí)驗(yàn)區(qū)域。

由于World Wind加載模型后無法讓球體自動(dòng)顯示加載區(qū)域。為了方便進(jìn)行實(shí)驗(yàn)，該文對World Wind的KMZ加載類進(jìn)行改進(jìn)，在World Wind加載模型后，球體會(huì)自動(dòng)旋轉(zhuǎn)到模型區(qū)域并放大進(jìn)行顯示。運(yùn)行World Wind后，按照前文給出的方法對模型區(qū)域的三維模型進(jìn)行批量加載。打印顯示最小長方體的視錐體六個(gè)面坐標(biāo)，在與Google Earth中三維模型區(qū)域?qū)嶋H坐標(biāo)對比后，可以看出新建的最小長方體成功鎖定了視錐體，使其精準(zhǔn)的固定在三維模型區(qū)域位置范圍內(nèi)。如圖7所示。

隨后查看World Wind中三維模型區(qū)域顯示效果。效果如圖8所示。

通過實(shí)驗(yàn)對比可以看出，改進(jìn)視錐裁剪算法后的World Wind中三維模型區(qū)域顯示效果較好。右上角360軟件顯示的CPU占有率只有百分之四十一，相比改進(jìn)前的百分之九十二，節(jié)省了一倍還多。而且在實(shí)際加載中，速度也得到明顯提高，沒有出現(xiàn)卡滯現(xiàn)象。

5 結(jié)論

鑒于科學(xué)研究對World Wind中多個(gè)三維模型加載顯示的需求，該文改進(jìn)了World Wind中的視錐裁剪算法，經(jīng)過實(shí)驗(yàn)驗(yàn)證，最終解決了World Wind中三維模型加載顯示速度慢、效率低、內(nèi)存占用率高、顯示效果不佳等問題。

作為一個(gè)開源三維地理信息系統(tǒng)，World Wind從發(fā)布以來就一直被開發(fā)者進(jìn)行完善和提高。該文站在前人的基礎(chǔ)上，對World Wind又進(jìn)行了一定的改進(jìn)，希望能為后續(xù)的研究提供便利。

參考文獻(xiàn)：

[1] Ulf Assarsson & Tomas Moller.Optimized.View Frustum Culling Algorithms for Bounding Boxes[J].Journal of Graphics Tools，2000（1）：9-22.

[2] Bell D G.， Kuehnel， F.NASA World Wind： Opensource GIS for MissionOperations.Aerospace Conference，2007（10）：1-9.

[3] 周波，祝忠明，劉再東.遙感影像的瓦片金字塔切割與邊界填充研究[J].計(jì)算機(jī)與信息技術(shù)，2011（10）：29-31.

[4] 盧小平，田繼輝，張劍偉，等.多尺度DEM數(shù)據(jù)的組織與管理方法研究[J].測繪通報(bào)，2010，（6）：12-15.

[5] 戴晨光，張永生，鄧雪清.一種用于實(shí)時(shí)可視化的海量地形數(shù)據(jù)組織與管理方法[J].系統(tǒng)仿真學(xué)報(bào)，2005 （2）：406-409.

[6] 袁琪，閔棟，鄒俊偉.KML文件的信息隱藏技術(shù)[J].北京郵電大學(xué)學(xué)報(bào)，2011（1）：140-144.

[7] 張芹，吳北平，孫華等.視景體可視范圍的確定及應(yīng)用[J].測繪科學(xué)，2009（4）：179-181.

[8] 劉牧.實(shí)時(shí)三維漫游系統(tǒng)中關(guān)鍵技術(shù)研究與實(shí)現(xiàn)[D].濟(jì)南：山東大學(xué)，2009：23-24.