王青云,羅 澤

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 計(jì)算機(jī)網(wǎng)絡(luò)信息中心,北京 100190)

基于LOD的海量地形數(shù)據(jù)并行渲染技術(shù)①

王青云1,2,羅 澤2

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 計(jì)算機(jī)網(wǎng)絡(luò)信息中心,北京 100190)

隨著地球空間信息技術(shù)的發(fā)展,建立具有海量空間數(shù)據(jù)的大規(guī)模虛擬地形場景越來越重要. 然而,面對海量的地形數(shù)據(jù),如何簡化地形,提升繪制與渲染效率,是地形渲染的關(guān)鍵. 本文對LOD地形渲染技術(shù)、大規(guī)模數(shù)據(jù)集的分析與處理、并行計(jì)算等相關(guān)技術(shù)進(jìn)行了研究,提出了基于LOD的海量地形數(shù)據(jù)并行渲染技術(shù). 該技術(shù)首先使用LOD四叉樹簡化地形,其次結(jié)合多核CPU并行計(jì)算的方法提升效率,最后結(jié)合大規(guī)模數(shù)據(jù)調(diào)度策略,實(shí)現(xiàn)了海量地形數(shù)據(jù)的并行渲染,并分析對比了非并行和并行情況下的實(shí)驗(yàn)結(jié)果. 本文所取得的理論與技術(shù)方面的成果可為大規(guī)模場景渲染提供新的技術(shù)思路.

LOD 技術(shù); 并行計(jì)算; 海量數(shù)據(jù); 地形渲染

1 引言

1.1 研究背景與意義

隨著地球空間信息技術(shù)的發(fā)展,建立具有海量空間數(shù)據(jù)的大規(guī)模虛擬地形場景越來越重要. 地形渲染是場景渲染的核心部分,一直是圖形學(xué)領(lǐng)域的熱點(diǎn)問題之一. 它是視頻游戲、地理信息系統(tǒng)(GIS)、虛擬現(xiàn)實(shí)(VR)系統(tǒng)中重要的組成部分[1]. 隨著遙感技術(shù)的發(fā)展,大范圍高分辨率的遙感數(shù)據(jù)已經(jīng)可以被獲取,包含上千萬多邊形的場景變得越來越常見,遠(yuǎn)遠(yuǎn)超過圖形硬件的繪制能力. 如此大容量的數(shù)據(jù)要在應(yīng)用中發(fā)揮實(shí)際作用,必須要有高效、快速的大規(guī)模地形渲染系統(tǒng)的支持. 因此,如何簡化地形,提升地形繪制與渲染效率,是實(shí)現(xiàn)一個(gè)大規(guī)模的地形渲染系統(tǒng)的關(guān)鍵.

提升地形繪制與渲染效率,主要從兩個(gè)方面著手:一方面是合理地組織地形數(shù)據(jù),采用合理的數(shù)據(jù)模型和數(shù)據(jù)調(diào)度策略,在不影響視覺效果的前提下,減少需要渲染的三角形的數(shù)據(jù)量; 另外一方面是采用加速渲染算法,提高單位時(shí)間地形數(shù)據(jù)的處理量[2].

1.2 國內(nèi)外研究現(xiàn)狀

減少需要渲染的地形數(shù)據(jù)方面,主要使用LOD(Level of detail) 多層次細(xì)節(jié)技術(shù)實(shí)現(xiàn),LOD 技術(shù)是目前大規(guī)模的地形場景渲染的研究重點(diǎn)之一. 地形LOD技術(shù)是在不影響畫面視覺效果的前提條件下,根據(jù)地形的不同復(fù)雜程度和人眼觀察地形的特點(diǎn),對地形的不同區(qū)域采取不同細(xì)節(jié)的描述和繪制. 通過逐次簡化景物的表面細(xì)節(jié)來減少場景的幾何復(fù)雜性,從而提高繪制算法的效率. LOD方法能夠靈活地調(diào)度資源,處理數(shù)據(jù),既減少了運(yùn)算量,又不會降低圖像的顯示效果[2-4].

目前LOD算法的主要實(shí)現(xiàn)方式有:靜態(tài)層次細(xì)節(jié)LOD技術(shù)和動態(tài)層次細(xì)節(jié)LOD技術(shù). 靜態(tài)LOD技術(shù)是在進(jìn)行地形渲染前,采用Top-down方式對地形進(jìn)行化簡,從最高精度開始,從地形數(shù)據(jù)中逐層地去掉地形的頂點(diǎn)數(shù)據(jù),每層數(shù)據(jù)對應(yīng)一個(gè)分辨率. 動態(tài)LOD技術(shù)是用連續(xù)變化的分辨率根據(jù)當(dāng)前視點(diǎn)位置的實(shí)時(shí)動態(tài)來繪制層次細(xì)節(jié)模型. 如表1是動態(tài)LOD與靜態(tài)LOD的區(qū)別.

表1 動態(tài) LOD 與靜態(tài) LOD 的區(qū)別

動態(tài)LOD技術(shù)的優(yōu)點(diǎn)是更符合人眼觀察的特點(diǎn),保證了地形渲染的連續(xù)性和一致性,同時(shí)也有效減少了地形數(shù)據(jù)的冗余. 缺點(diǎn)是在渲染過程中需要實(shí)時(shí)計(jì)算、繪制不同分辨率的地形模型,過程相對復(fù)雜,會占用一定的計(jì)算資源. 本文將主要研究基于四叉樹的動態(tài)LOD地形算法與其并行化實(shí)現(xiàn).

加速渲染算法方面,主要是通過軟硬件加速算法實(shí)現(xiàn)的,如: 數(shù)據(jù)存儲訪問優(yōu)化技術(shù)、GPU加速繪制技術(shù)及并行渲染技術(shù)等,其中并行渲染技術(shù)是軟件加速方法的重要組成部分之一.

隨著并行計(jì)算的發(fā)展以及多核CPU的出現(xiàn),并行化成為了提高算法效率的重要手段之一. 在計(jì)算機(jī)圖形學(xué)中,根據(jù)不同的分類標(biāo)準(zhǔn),并行渲染也有不同的分類體系. 根據(jù)數(shù)據(jù)調(diào)度和功能實(shí)現(xiàn)的方式分類,并行渲染算法可以分為數(shù)據(jù)并行算法和功能并行算法兩種.根據(jù)圖元?dú)w屬判斷發(fā)生的方式和時(shí)機(jī),Molnar等于1994年將并行圖形渲染系統(tǒng)劃分為Sort-first、Sortmiddle和Sort-last三種體系結(jié)構(gòu). 根據(jù)實(shí)現(xiàn)平臺分類,可分為高性能計(jì)算機(jī)、計(jì)算機(jī)集群和多核微機(jī)三種[3].

微機(jī)是個(gè)人用戶使用最多的三維瀏覽客戶端,隨著個(gè)人用戶對三維圖形逼真度要求的提高和微機(jī)硬件的升級,微機(jī)平臺上的并行渲染將成為研究的熱點(diǎn)之一. 目前基于多核微機(jī)平臺的并行渲染研究還處于起步階段,尚未出現(xiàn)令人滿意的并行渲染系統(tǒng).

1.3 本文的主要內(nèi)容

目前,對單機(jī)渲染系統(tǒng)采用流水線并行技術(shù)的應(yīng)用較少,少部分實(shí)現(xiàn)了部分并行化效果. 三維地形渲染方面對于多核CPU并行計(jì)算挖掘不足,尚未能做到真正意義上的并行渲染[4,5]. 因此,基于多核CPU的并行計(jì)算對于提高算法效率具有非常重要的意義.

本文針對這一現(xiàn)狀,提出了一套完善的并行化處理算法,較為有效地實(shí)現(xiàn)了在個(gè)人計(jì)算機(jī)上的地形渲染并行化. 本文在研究DEM數(shù)據(jù)組織及數(shù)據(jù)調(diào)度的基礎(chǔ)上,實(shí)現(xiàn)基于緩存區(qū)間的大規(guī)模數(shù)據(jù)調(diào)度算法; 在地形繪制階段,本文提出四叉樹LOD算法,并基于多核CPU產(chǎn)生多線程并行處理地形數(shù)據(jù),實(shí)現(xiàn)了地形LOD并行繪制算法,并測試性能. 本文所取得的理論與技術(shù)方面的成果可為大規(guī)模場景渲染提供新的思路.

本文的主要內(nèi)容如下: 第一節(jié)主要是引言部分,介紹了大規(guī)模LOD地形渲染技術(shù)的研究背景意義與國內(nèi)外研究現(xiàn)狀; 第二節(jié)主要是基于四叉樹LOD技術(shù)的并行化算法; 第三節(jié)主要是大規(guī)模DEM數(shù)據(jù)調(diào)度算法,提出了基于緩存區(qū)的數(shù)據(jù)調(diào)度及數(shù)據(jù)實(shí)時(shí)更新機(jī)制; 第四節(jié)主要是本文的實(shí)驗(yàn)設(shè)計(jì)、性能分析等. 最后一節(jié)內(nèi)容主要是結(jié)論與展望.

2 LOD 地形算法的并行化

2.1 四叉樹LOD算法

基于四叉樹的LOD方法是采用四叉樹結(jié)構(gòu)存儲DEM數(shù)據(jù),在進(jìn)行地形渲染時(shí),首先自頂向下遍歷四叉樹,再實(shí)時(shí)計(jì)算節(jié)點(diǎn)可見性,即判斷節(jié)點(diǎn)是否需要四叉分割.

在四叉樹結(jié)構(gòu)表示地形模型的過程中,每一個(gè)地形塊都可以由四叉樹中的節(jié)點(diǎn)表示,每個(gè)節(jié)點(diǎn)都對應(yīng)一個(gè)地形區(qū)域. 四叉樹的邏輯結(jié)構(gòu)如圖1所示. 當(dāng)一個(gè)節(jié)點(diǎn)被判斷為可見時(shí),會被細(xì)分為8個(gè)三角形網(wǎng)格,并繼續(xù)往下一層判斷其子節(jié)點(diǎn)的可見性. 當(dāng)一個(gè)節(jié)點(diǎn)不可見時(shí),該節(jié)點(diǎn)細(xì)分為兩個(gè)三角形網(wǎng)格,不再繼續(xù)細(xì)分[6,7].

圖1 四叉樹的邏輯結(jié)構(gòu)

在生成四叉樹,需要不斷地將節(jié)點(diǎn)細(xì)分,那么如何決定一個(gè)節(jié)點(diǎn)是否需要分割就是一個(gè)關(guān)鍵的問題. 節(jié)點(diǎn)評價(jià)標(biāo)準(zhǔn)決定了在某一時(shí)刻,該節(jié)點(diǎn)是否可見,也就是該節(jié)點(diǎn)是否需要細(xì)分. 這種標(biāo)準(zhǔn)通常有兩個(gè)決定性的因素. 其中之一是視點(diǎn),離視點(diǎn)較近的部分分辨率較高,細(xì)節(jié)較多,反之,離視點(diǎn)較遠(yuǎn)細(xì)節(jié)較少. 另外一個(gè)影響因素是地形本身的特征. 比如起伏不大的地表面分辨率較低,很少的細(xì)節(jié)就能很好地表現(xiàn)出來,而不平整的地表面則需要更多的細(xì)節(jié)來表現(xiàn)它的地理特征[8-10].

綜合考慮視距和地形特征,設(shè)觀察者所處位置為V(Vx,Vy,Vz),地形頂點(diǎn)坐標(biāo)P(Px,Py,Pz). 則按照如下公式?jīng)Q定某個(gè)節(jié)點(diǎn)是否被激活:

其中L1為視距的近似值,error為節(jié)點(diǎn)的頂點(diǎn)誤差,Threshold為細(xì)節(jié)閾值常量,細(xì)節(jié)閾值常量是人為設(shè)置的一個(gè)常量參數(shù),它是LOD模型的分辨率的控制參數(shù).Threshold越大,模型分辨率越高,反之分辨率越低.Enabled為節(jié)點(diǎn)激活標(biāo)識,當(dāng) Enabled為 1時(shí),表示該節(jié)點(diǎn)需要激活. 當(dāng) Enabled 不為 1 時(shí),則屏蔽該點(diǎn). 對四叉樹的每一個(gè)節(jié)點(diǎn)進(jìn)行激活標(biāo)志計(jì)算,得出節(jié)點(diǎn)可見性,這個(gè)過程稱為頂點(diǎn)測試.

為了減小計(jì)算量,在實(shí)時(shí)計(jì)算節(jié)點(diǎn)可見性的過程中,一般不會對每個(gè)節(jié)點(diǎn)進(jìn)行頂點(diǎn)測試,而是對地形塊先進(jìn)行盒測試. 類似于頂點(diǎn)測試,以地形塊為單位判斷該塊的可見性,再決定是否需要分割.

2.2 生產(chǎn)者消費(fèi)者模型

在進(jìn)行四叉樹裁剪的過程中,系統(tǒng)一方面要根據(jù)用戶控制下的視點(diǎn),不斷的遍歷基于當(dāng)前視點(diǎn)的四叉樹; 另一方面,要對四叉樹的每一個(gè)節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)激活判斷,在本文中,四叉樹的深度最深可達(dá)到 19 層,總節(jié)點(diǎn)數(shù)目多達(dá)(219+1)*(219+1),系統(tǒng)需要實(shí)時(shí)遍歷節(jié)點(diǎn),并計(jì)算每個(gè)節(jié)點(diǎn)的可見性,對系統(tǒng)的計(jì)算性能有很高的要求,因此,本文采用多線程并行化方法,以充分利用系統(tǒng)的計(jì)算資源.

本系統(tǒng)采用生產(chǎn)者消費(fèi)者模型,生產(chǎn)者消費(fèi)者模型是一個(gè)并行化處理中常用的模型,如圖2. 它擁有一個(gè)隊(duì)列容器,并借此來解決生產(chǎn)者和消費(fèi)者的單線程轉(zhuǎn)換為多線程的并行化問題. 本文使用一個(gè)線程(生產(chǎn)者)用于遍歷四叉樹節(jié)點(diǎn),和多個(gè)線程(消費(fèi)者)用于計(jì)算四叉樹中的節(jié)點(diǎn)可見性.

圖2 生產(chǎn)者消費(fèi)者模型

生產(chǎn)者的具體職責(zé)是,將一份大量數(shù)據(jù)進(jìn)行拆分,并產(chǎn)生多份待處理的數(shù)據(jù). 而消費(fèi)者的功能是逐份處理產(chǎn)生的多份待處理數(shù)據(jù). 二者之間不直接傳遞數(shù)據(jù),而是通過一個(gè)數(shù)據(jù)隊(duì)列來緩存待處理的數(shù)據(jù). 所以,當(dāng)生產(chǎn)者完成待處理數(shù)據(jù)的生產(chǎn)之后,不用等待消費(fèi)者處理,而是直接將待處理數(shù)據(jù)放入緩存隊(duì)列,然后繼續(xù)生產(chǎn)下一份待處理數(shù)據(jù). 消費(fèi)者無需直接接觸海量數(shù)據(jù),也不需要與生產(chǎn)者交換數(shù)據(jù),而是從緩存隊(duì)列里直接取出待處理數(shù)據(jù)進(jìn)行計(jì)算.

2.3 并行化算法

為了實(shí)現(xiàn)四叉樹LOD算法的并行化,可以建立一個(gè)節(jié)點(diǎn)隊(duì)列,用于儲存四叉樹節(jié)點(diǎn)的指針. 然后使用生產(chǎn)者線程,通過廣度遍歷算法不斷實(shí)時(shí)生成節(jié)點(diǎn)隊(duì)列.再使用多個(gè)消費(fèi)者線程,在滿足節(jié)點(diǎn)父子順序的條件下,實(shí)時(shí)處理隊(duì)列中的節(jié)點(diǎn)(即判斷點(diǎn)的可見性),即可實(shí)現(xiàn)四叉樹節(jié)點(diǎn)可見性更新的并行化.

生產(chǎn)者線程的主要任務(wù)是根據(jù)隨著視點(diǎn)變換,從四叉樹根節(jié)點(diǎn)開始,通過廣度遍歷算法不斷實(shí)時(shí)生成節(jié)點(diǎn)隊(duì)列. 本文中生產(chǎn)者通過一個(gè)先進(jìn)先出隊(duì)列存儲四叉樹的節(jié)點(diǎn)隊(duì)列. 獲取每個(gè)節(jié)點(diǎn)的激活標(biāo)志,如果節(jié)點(diǎn)被激活,則該節(jié)點(diǎn)進(jìn)行四叉分割,將四個(gè)子節(jié)點(diǎn)加入節(jié)點(diǎn)隊(duì)列; 反之,將該節(jié)點(diǎn)從節(jié)點(diǎn)隊(duì)列彈出. 重復(fù)以上操作,直到節(jié)點(diǎn)隊(duì)列為空為止.

消費(fèi)者線程的主要任務(wù)是根據(jù)生產(chǎn)者生成的節(jié)點(diǎn)隊(duì)列,計(jì)算隊(duì)列中每個(gè)節(jié)點(diǎn)的可見性. 本文采用多個(gè)消費(fèi)者,通過一個(gè)先進(jìn)先出隊(duì)列,存儲節(jié)點(diǎn)隊(duì)列中每一個(gè)點(diǎn)的可見性,更新節(jié)點(diǎn)的激活標(biāo)志. 直到節(jié)點(diǎn)隊(duì)列為空.

使用生產(chǎn)者-消費(fèi)者模型進(jìn)行LOD算法的并行化的關(guān)鍵在于如何解決多線程遍歷多叉樹的數(shù)據(jù)同步問題. 本文采用mutex互斥量來維持生產(chǎn)者與消費(fèi)者線程之間的同步機(jī)制. 互斥量是一種表現(xiàn)互斥現(xiàn)象的數(shù)據(jù)結(jié)構(gòu),來保證共享數(shù)據(jù)操作的完整性. 本算法使用了兩類互斥鎖: 四叉樹節(jié)點(diǎn)隊(duì)列鎖mutex1和四叉樹中的節(jié)點(diǎn)鎖mutex2,分別用于來保證四叉樹節(jié)點(diǎn)隊(duì)列和四叉樹節(jié)點(diǎn)的數(shù)據(jù)操作完整性.

本系統(tǒng)中,結(jié)合生產(chǎn)者消費(fèi)者模型的多線程四叉樹LOD并行算法流程圖如圖3所示. 其流程如下:

1) 每當(dāng)視點(diǎn)變換時(shí),緩存數(shù)據(jù)更新,四叉樹根節(jié)點(diǎn)對應(yīng)的地形數(shù)據(jù)隨之更新,四叉樹也隨之更新.

2) 并行四叉樹LOD算法,激活多個(gè)線程(包含生產(chǎn)者、消費(fèi)者).

3) 從根節(jié)點(diǎn)開始,首先生產(chǎn)者線程將根節(jié)點(diǎn)加入節(jié)點(diǎn)隊(duì)列,消費(fèi)者從隊(duì)列中取出根節(jié)點(diǎn),更新激活標(biāo)志為可見.

4) 生產(chǎn)者判斷當(dāng)前節(jié)點(diǎn)隊(duì)列是否為空,讀取當(dāng)前節(jié)點(diǎn)隊(duì)列中最后一個(gè)節(jié)點(diǎn)的可見性,如果為可見,產(chǎn)生四個(gè)子節(jié)點(diǎn),并加入節(jié)點(diǎn)隊(duì)列. 如果不可見,將該節(jié)點(diǎn)彈出隊(duì)列.

5) 消費(fèi)者判斷當(dāng)前節(jié)點(diǎn)隊(duì)列是否為空,從節(jié)點(diǎn)隊(duì)列中取出節(jié)點(diǎn),并計(jì)算節(jié)點(diǎn)可見性,更新節(jié)點(diǎn)激活標(biāo)志.

重復(fù)4)、5)直到節(jié)點(diǎn)隊(duì)列為空. 更新視圖模型并進(jìn)行繪制.

圖3 LOD 并行化算法流程圖

3 大規(guī)模 DEM 數(shù)據(jù)調(diào)度

3.1 GLSDEM數(shù)據(jù)集

全球地形數(shù)字高程模型(GLSDEM)是NASA和USGS組織公開的全球地形地貌空間數(shù)據(jù),由多個(gè)數(shù)據(jù)集的綜合處理而成,它實(shí)現(xiàn)了覆蓋全球大部分地區(qū)的地形記錄. GLSDEM數(shù)據(jù)集的地形分辨率為3弧秒(90 m),地理坐標(biāo)基于 WGS-84 標(biāo)準(zhǔn). GLSDEM 數(shù)據(jù)集以GeoTIFF格式儲存. GLSDEM數(shù)據(jù)集包含了19234個(gè)GeoTIFF文件. 每一個(gè)GeoTIFF文件大小為2.75 MB,總數(shù)據(jù)量為51.8 GB.

文件讀取使用GDAL開源C++代碼庫后,讀取文件后可以得到每個(gè)GeoTIFF文件的地形分辨率,1201*1201,其覆蓋范圍為球面上邊長為1弧度的正方形. 根據(jù)GLSDEM數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)可將三維空間坐標(biāo)轉(zhuǎn)換為全球坐標(biāo).

3.2 大規(guī)模數(shù)據(jù)集調(diào)度算法

本文使用的地形數(shù)據(jù)集數(shù)據(jù)量巨大(大小為51.8 G),采用了數(shù)據(jù)分塊的組織方式,以GeoTIFF文件為單位,采用數(shù)組的數(shù)據(jù)結(jié)構(gòu)存儲地形數(shù)據(jù). 由于內(nèi)存限制,普通電腦無法一次性將所有數(shù)據(jù)加載至內(nèi)存供CPU使用. 此外,一次性加載所有地形數(shù)據(jù),由于硬盤傳輸速度慢,會導(dǎo)致程序讀取全部地形數(shù)據(jù)時(shí)間過長,啟動速度極慢. 因此,為了實(shí)現(xiàn)實(shí)時(shí)讀取硬盤中大規(guī)模地形數(shù)據(jù)以及大量地形數(shù)據(jù)向三維空間的映射,本文設(shè)計(jì)了內(nèi)存緩沖區(qū)和實(shí)時(shí)數(shù)據(jù)更新機(jī)制.

3.2.1 內(nèi)存緩沖區(qū)

內(nèi)存緩沖區(qū)用于緩存硬盤中的地形數(shù)據(jù). 由于視點(diǎn)變換的需要,渲染完一幀以后需要重新加載新的一幀所需要的地形數(shù)據(jù),新的地形數(shù)據(jù)便被讀取并加載至內(nèi)存. 在渲染過程中,首先將地形數(shù)據(jù)加載到緩存區(qū),一旦視點(diǎn)發(fā)生變化,內(nèi)存數(shù)據(jù)需要更新,都是將緩存區(qū)作為數(shù)據(jù)源,而不是直接從外存讀取數(shù)據(jù).

本文設(shè)置了300個(gè)文件單位的緩存區(qū),約825 mb的緩存容量. 當(dāng)視野發(fā)生變化時(shí),載入視野范圍內(nèi)的數(shù)據(jù),刪除兩倍視野范圍以外的數(shù)據(jù). 即保留了一倍視野范圍的緩沖. 本文的實(shí)現(xiàn)方式是首先在內(nèi)存中分配一塊固定大小區(qū)域作為緩存區(qū),然后通過GDAL庫的讀取波段數(shù)據(jù)接口函數(shù)RasterIO()從外存中讀取數(shù)據(jù)并存入緩存.

3.2.2 數(shù)據(jù)更新機(jī)制

在數(shù)據(jù)更新方面,本文采用的是根據(jù)視點(diǎn)變換,實(shí)時(shí)動態(tài)渲染地形數(shù)據(jù)塊. 視點(diǎn)的變換會導(dǎo)致視景體和緩存區(qū)的變化,使得內(nèi)存數(shù)據(jù)和緩存數(shù)據(jù)發(fā)生變化.

本文將視點(diǎn)的變換歸納為旋轉(zhuǎn)、平移、縮放這三類. 本文通過調(diào)用OpenGL的視圖矩陣類ViewMatrix類,它會根據(jù)視點(diǎn)的位置、朝向等變化,實(shí)時(shí)更新視圖模型. 當(dāng)鼠標(biāo)或者鍵盤移動,視點(diǎn)發(fā)生變化,首先調(diào)用Glut庫的消息處理函數(shù),監(jiān)聽窗口大小改變、鍵盤和鼠標(biāo)事件. 將這些用戶事件對應(yīng)到不同類型的視點(diǎn)變換操作,接著根據(jù)視點(diǎn)變化類型,調(diào)用前面提到的的三種不同視點(diǎn)變換函數(shù). 最后,根據(jù)視點(diǎn)位置的移動距離,方向,視角大小等計(jì)算出需要更新的視野范圍,實(shí)時(shí)更新模型視圖矩陣,然后調(diào)用glutSwapBuffers()方法將緩存數(shù)據(jù)加載到內(nèi)存并進(jìn)行渲染輸出.

3.2.3 數(shù)據(jù)調(diào)度算法

本文采用數(shù)組的數(shù)據(jù)結(jié)構(gòu)存儲地形數(shù)據(jù),并通過固定長度為300的一個(gè)先進(jìn)先出隊(duì)列history,控制緩存區(qū)的大小. data 是所有的緩存文件數(shù)據(jù),data[*]是一個(gè)文件數(shù)據(jù),data[*][*]是一個(gè)DEM文件中的一個(gè)點(diǎn).

視點(diǎn)的運(yùn)動會導(dǎo)致緩存數(shù)據(jù)更新、視圖模型的更新. 需要采用一定的調(diào)度算法來保證內(nèi)存數(shù)據(jù)和緩存數(shù)據(jù)的穩(wěn)定. 本文釆用如圖4所述調(diào)度算法.

圖4 數(shù)據(jù)調(diào)度算法流程圖

1) 獲取當(dāng)前視點(diǎn)位置,得出內(nèi)存和緩存區(qū)需要加載的數(shù)據(jù)索引(地址).

2) 采用數(shù)組 data[*]存儲緩存區(qū)地形數(shù)據(jù),并通過固定長度的先進(jìn)先出隊(duì)列history,記錄被加載到緩存區(qū)的數(shù)據(jù)文件以控制緩存區(qū)的大小.

3) 當(dāng)視點(diǎn)發(fā)生變化時(shí),判斷是否需要更新內(nèi)存數(shù)據(jù).

4) 如果需要更新的內(nèi)存數(shù)據(jù)在緩存區(qū)內(nèi),直接從緩存區(qū)讀取數(shù)據(jù)即可; 如果需要更新的內(nèi)存數(shù)據(jù)不在緩存區(qū)內(nèi),需要先計(jì)算緩存數(shù)據(jù)更新范圍,清除緩存區(qū)中無用數(shù)據(jù)并載入外存數(shù)據(jù)至緩存區(qū); 當(dāng)視點(diǎn)發(fā)生變化時(shí),載入視點(diǎn)可視范圍內(nèi)的數(shù)據(jù),刪除兩倍視野范圍以外的數(shù)據(jù). 即保留了一倍視野范圍的緩存區(qū). 重復(fù)3)和4).

4 試驗(yàn)與總結(jié)

4.1 實(shí)驗(yàn)設(shè)計(jì)

本文使用了C++作為開發(fā)語言,以O(shè)penGL作為三維渲染引擎,在 Xcode的環(huán)境下,使用GLUT、GDAL庫,實(shí)現(xiàn)了基于四叉樹的LOD地形實(shí)時(shí)動態(tài)顯示系統(tǒng). 本系統(tǒng)運(yùn)行在雙核CPU的微機(jī)上,采用四線程,硬件配置如表2.

表2 開發(fā)環(huán)境配置

4.2 結(jié)果對比

如圖5、6、7所示,對應(yīng)現(xiàn)實(shí)空間坐標(biāo)點(diǎn)為北緯23度,東經(jīng)121度,實(shí)際空間地理位置為臺灣的不同視點(diǎn)渲染效果圖.

4.3 性能分析

本文實(shí)現(xiàn)了基于四叉樹的LOD地形實(shí)時(shí)動態(tài)顯示系統(tǒng),分別采用并行渲染的方式與非并行渲染的方式以進(jìn)行性能比較(參見表3). 可以看出,采用并行渲染的幀率明顯高于非并行渲染幀率,內(nèi)存占用量基本保持在825 M左右(300個(gè)緩存地形數(shù)據(jù)塊文件),說明多核CPU并行渲染可以有效的提高三維DEM渲染的性能,并且內(nèi)存數(shù)據(jù)也穩(wěn)定在合適的規(guī)模;釆用并行渲染的幀率遠(yuǎn)遠(yuǎn)高于非并行渲染方式,說明并行的效果顯著,達(dá)到了提高渲染性能的目標(biāo).

5 結(jié)語

本文利用多核CPU微機(jī)的并行計(jì)算能力,在大規(guī)模DEM三維地形數(shù)據(jù)渲染過程中,采用并行計(jì)算的方式,提高了系統(tǒng)的渲染效率. 本文所包含的工作主要分為以下幾個(gè)部分: 首先,實(shí)現(xiàn)了基于四叉樹的LOD地形渲染算法,基于此,結(jié)合并行計(jì)算方法,采用生產(chǎn)者消費(fèi)者模型,實(shí)現(xiàn)了 LOD 算法的并行化. 除此之外,在研究并行技術(shù)的同時(shí),研究了大規(guī)模地形渲染時(shí)的海量數(shù)據(jù)的組織與調(diào)度方法,通過設(shè)置一定區(qū)域的內(nèi)存緩沖區(qū)以及數(shù)據(jù)更新機(jī)制實(shí)現(xiàn)了大規(guī)模數(shù)據(jù)的加載與處理.

圖5 不同細(xì)節(jié)閾值對比圖

圖6 不同細(xì)節(jié)閾值對比圖(線框模式)

圖7 不同高度對比圖

表3 地形渲染實(shí)驗(yàn)結(jié)果性能對比

地形渲染是大規(guī)模場景渲染的核心部分,隨著微機(jī)硬件的發(fā)展,在微機(jī)上實(shí)現(xiàn)大規(guī)模三維地圖渲染已經(jīng)具有一定的硬件基礎(chǔ). 本文基于多核CPU,實(shí)現(xiàn)了大規(guī)模地形數(shù)據(jù)渲染的實(shí)驗(yàn),所取得的理論與技術(shù)方面的成果可作為大規(guī)模場景渲染的理論基礎(chǔ)和技術(shù)基礎(chǔ).

同時(shí),關(guān)于大規(guī)模場景渲染,還有很多問題值得我們進(jìn)一步研究與探討. 比如DEM三維可視化的仿真效果,如何更好的模擬真實(shí)的地理環(huán)境,在渲染地形數(shù)據(jù)的同時(shí),也渲染出光照、紋理、陰影、不同的地貌特征等; 比如結(jié)合GPU和本文使用的多核CPU共同實(shí)現(xiàn)三維地形渲染,從而實(shí)現(xiàn)更高效率的并行計(jì)算,這些都是需要進(jìn)一步開展的研究內(nèi)容.

1陳路. 3D游戲引擎技術(shù)—大規(guī)模場景實(shí)時(shí)圖形渲染的研究與實(shí)現(xiàn)[碩士學(xué)位論文]. 成都: 電子科技大學(xué),2005.

2陳景廣,佘江峰,宋曉群,等. 基于多核 CPU 的大規(guī)模DEM并行三維渲染. 武漢大學(xué)學(xué)報(bào)?信息科學(xué)版,2013,38(5): 618–621.

3Zhai R,Lu K,Pan WG,et al. GPU-based real-time terrain rendering: Design and implementation. Neurocomputing,2016,171: 1–8. [doi: 10.1016/j.neucom.2014.08.108]

4王沖. 大規(guī)模地形的快速幾何繪制與實(shí)時(shí)紋理映射技術(shù)研究[碩士學(xué)位論文]. 天津: 中國民航大學(xué),2009.

5劉曉平,凌實(shí),余燁,等. 面向大規(guī)模地形 LOD 模型的并行簡化算法. 工程圖學(xué)學(xué)報(bào),2010,31(5): 16–21.

6周發(fā)亮. 基于四叉樹的LOD技術(shù)在地形渲染中的應(yīng)用. 計(jì)算機(jī)仿真,2007,24(1): 188–191.

7Wu J,Yang YF,Gong SR,et al. A new quadtree-based terrain LOD algorithm. Journal of Software,2010,5(7):769–776.

8Yu WL,Zhang LM,Zhang BQ,et al. Large-scale LOD adaptive terrain rendering. Applied Mechanics and Materials,2012,220-223: 2450–2453. [doi: 10.4028/www.scientific.net/AMM.220-223]

9任宏萍,靳彪. 基于4叉樹的LOD地形實(shí)時(shí)渲染技術(shù). 華中科技大學(xué)學(xué)報(bào) (自然科學(xué)版),2011,39(2): 6–10.

10趙慶. 大規(guī)模地形數(shù)據(jù)調(diào)度與繪制技術(shù)研究與實(shí)現(xiàn)[碩士學(xué)位論文]. 成都: 電子科技大學(xué),2011.

11鄭笈,李思昆,陸筱霞. 大規(guī)模場景繪制的存儲數(shù)據(jù)調(diào)度組織研究. 節(jié)能環(huán)保 和諧發(fā)展——2007中國科協(xié)年會論文集 (一). 武漢,中國. 2007. 6.

12Yang C,Dai SY,Wu LD,et al. Smoothly rendering of largescale vector data on virtual globe. Applied Mechanics and Materials,2014,631-632: 516–520. [doi: 10.4028/www.scientific.net/AMM.631-632]

Parallel Rendering of Massive Terrain Data Based on LOD

WANG Qing-Yun1,2,LUO Ze2

1(University of Cinese Academy of Sciences,Beijing 100049,China)
2(Computer Network Information Center,Chinese Academy of Sciences,Beijing 100190,China)

With the development of geo spatial information technology,it is more important to build large scale virtual terrain scene with massive spatial data. However,in the face of massive terrain data,how to simplify terrain,improve rendering and rendering efficiency,is the key to the terrain rendering. After the research of the terrain rendering technology of LOD,the analysis and processing of large scale data sets,parallel computing and other related technologies,the parallel rendering technology of massive terrain data based on LOD is proposed. At first,quadtree LOD is used to simplified terrain,secondly it is combined with multi-core CPU parallel computing method to enhance efficiency,then it is combined with the large data scheduling strategy,finally it realizes the parallel rendering of massive terrain data,and it analyzes the non-parallel and parallel experiments under the same conditions. The theoretical and technical achievements in the research can provide a new idea for large scale scene rendering.

LOD technology; parallel computing; massive data; terrain render

王青云,羅澤.基于LOD的海量地形數(shù)據(jù)并行渲染技術(shù).計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(12):200–206. http://www.c-s-a.org.cn/1003-3254/6113.html

2017-03-15; 修改時(shí)間: 2017-03-31; 采用時(shí)間: 2017-04-10