陳小潘，渠澗濤,，趙亞萌，王　鵬,，陳玉林

(1．河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開(kāi)封 475004； 2．中國(guó)科學(xué)院 遙感與數(shù)字地球研究所，北京 100012)

?

基于雙緩沖隊(duì)列的海量地形數(shù)據(jù)并行處理方法

陳小潘1，渠澗濤1,2，趙亞萌2，王鵬1,2，陳玉林1

(1．河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開(kāi)封 475004； 2．中國(guó)科學(xué)院 遙感與數(shù)字地球研究所，北京 100012)

摘要：海量地形數(shù)據(jù)處理過(guò)程中，硬件的性能優(yōu)勢(shì)不能得到充分利用，已成為制約大規(guī)模地形繪制速度的瓶頸.針對(duì)這一問(wèn)題，分析了影響硬件處理能力發(fā)揮的關(guān)鍵因素，采用雙緩沖隊(duì)列的設(shè)計(jì)思路，提出了一種支持海量地形數(shù)據(jù)的并行處理方法，即將大規(guī)模地形繪制分為數(shù)據(jù)處理和渲染繪制兩個(gè)獨(dú)立的過(guò)程，分別進(jìn)行并行處理：設(shè)立兩個(gè)緩沖隊(duì)列，將數(shù)據(jù)的讀、寫(xiě)操作區(qū)分開(kāi)來(lái)；充分考慮了瓦片加載的優(yōu)先級(jí)，并據(jù)此進(jìn)行任務(wù)分配.實(shí)驗(yàn)表明，該方法有效地提升了大規(guī)模地形繪制的整體速度.

關(guān)鍵詞：海量地形數(shù)據(jù)；雙緩沖隊(duì)列；并行化；大規(guī)模地形繪制；瓦片加載

0引言

大規(guī)模地形繪制在戰(zhàn)場(chǎng)模擬、虛擬現(xiàn)實(shí)以及地理信息系統(tǒng)中都有著廣泛的應(yīng)用[1-2].然而，用于生成地形瓦片模型的高程數(shù)據(jù)以及紋理數(shù)據(jù)的數(shù)據(jù)量大，無(wú)法一次性全部存入內(nèi)存.通常的解決方法是將數(shù)據(jù)按照金字塔模型的標(biāo)準(zhǔn)進(jìn)行切分，分塊調(diào)入內(nèi)存[3-5]，使得一個(gè)三維場(chǎng)景由相當(dāng)數(shù)量的地形瓦片模型構(gòu)成.在硬件處理能力不足的情況下，盡可能地簡(jiǎn)化地形瓦片模型的復(fù)雜度，是實(shí)現(xiàn)大規(guī)模地形繪制的一個(gè)重要手段[6].然而，隨著計(jì)算機(jī)圖形處理硬件性能的不斷提高，如何有效地調(diào)度及處理大量的瓦片數(shù)據(jù)，使得計(jì)算機(jī)的處理能力能夠得到充分利用，已經(jīng)成為提升大規(guī)模地形繪制速度的一個(gè)關(guān)鍵.

近幾十年來(lái)，國(guó)內(nèi)外學(xué)者在大規(guī)模地形實(shí)時(shí)繪制方面進(jìn)行了大量的研究，一個(gè)主流研究方向是基于層次細(xì)節(jié)模型(LOD, Levels of Detail)[7-10].該方法的主要思路是采用不同的標(biāo)準(zhǔn)篩選出每個(gè)無(wú)效的三角形并剔除，以減少待渲染三角形的數(shù)量.但近幾年，隨著CPU(Central Processing Unit)和GPU(Graphics Processing Unit)等硬件的處理能力不斷提升，通過(guò)一定的技術(shù)手段，充分發(fā)揮硬件的處理能力，已經(jīng)成為提升大規(guī)模地形繪制速度的一個(gè)新的方向[11-13].

基于以上研究現(xiàn)狀，筆者提出了一種基于雙緩沖隊(duì)列的海量地形數(shù)據(jù)并行處理方法：在依據(jù)瓦片加載優(yōu)先級(jí)進(jìn)行任務(wù)分配后，將地形數(shù)據(jù)處理與地形瓦片模型的渲染繪制分隔開(kāi)來(lái)，分別進(jìn)行并行處理，以充分發(fā)揮硬件的性能；同時(shí)，設(shè)計(jì)兩個(gè)緩沖隊(duì)列交替作為數(shù)據(jù)的讀隊(duì)列和寫(xiě)隊(duì)列，減少了線程間同步產(chǎn)生的開(kāi)銷(xiāo)，并利用WPF (Windows Presentation Foundation)技術(shù)完成任務(wù).

1問(wèn)題分析與整體架構(gòu)設(shè)計(jì)

大規(guī)模地形繪制中海量地形數(shù)據(jù)的處理，通常由多個(gè)地形瓦片數(shù)據(jù)的處理組合而成[14].采用單緩沖隊(duì)列的單線程處理流程效率較低，可采用單緩沖隊(duì)列的并行處理機(jī)制進(jìn)行處理，如圖1所示.

數(shù)據(jù)處理和渲染繪制分別進(jìn)行處理的設(shè)計(jì)模式區(qū)分了CPU與GPU的職責(zé)，并行處理方式也使得兩者的性能在整個(gè)海量地形數(shù)據(jù)處理的過(guò)程中都得到了充分的利用.但單一的緩沖區(qū)在面對(duì)多線程的讀寫(xiě)操作時(shí)，會(huì)出現(xiàn)線程同步的問(wèn)題，造成時(shí)間上的浪費(fèi).同時(shí)，在加載瓦片時(shí)，并未考慮瓦片加載的優(yōu)先級(jí)，也降低了用戶體驗(yàn).因此，筆者設(shè)計(jì)了一種基于雙緩沖隊(duì)列的海量地形數(shù)據(jù)處理方法，該方法具有以下特點(diǎn).

(1)根據(jù)瓦片中心點(diǎn)與視線的距離，設(shè)立瓦片加載的優(yōu)先級(jí).當(dāng)距離越近，則優(yōu)先級(jí)越高，在單個(gè)線程中優(yōu)先級(jí)越高的瓦片就越早被加載.

(2)將瓦片的繪制過(guò)程分為數(shù)據(jù)處理和渲染繪制兩個(gè)獨(dú)立的過(guò)程，并采用多線程并發(fā)的策略進(jìn)行加速.

(3)采用雙緩沖隊(duì)列的設(shè)計(jì)思路，減少了線程間同步產(chǎn)生的開(kāi)銷(xiāo).

圖1　單緩沖隊(duì)列的并行處理機(jī)制Fig.1　Parallel processing mechanism of single buffer queue

基于雙緩沖隊(duì)列的海量地形數(shù)據(jù)并行處理架構(gòu)，主要由瓦片數(shù)據(jù)選取及優(yōu)先級(jí)處理、雙緩沖隊(duì)列、數(shù)據(jù)處理以及渲染繪制4個(gè)主要模塊構(gòu)成，其整體架構(gòu)設(shè)計(jì)如圖2所示.

其中，瓦片數(shù)據(jù)選取及優(yōu)先級(jí)處理模塊主要根據(jù)當(dāng)前的視域范圍選取待加載瓦片數(shù)據(jù)；同時(shí)，根據(jù)視點(diǎn)與瓦片之間的距離，計(jì)算所有待加載瓦片數(shù)據(jù)的優(yōu)先級(jí)，生成瓦片加載優(yōu)先級(jí)隊(duì)列，并將生成的瓦片加載優(yōu)先級(jí)隊(duì)列傳遞給數(shù)據(jù)處理模塊.

緩沖隊(duì)列1和緩沖隊(duì)列2的主要功能是提供固定大小的數(shù)據(jù)緩沖空間，分別負(fù)責(zé)讀出和寫(xiě)入，使讀操作和寫(xiě)操作分別針對(duì)不同的緩沖區(qū)進(jìn)行，從而減少了線程間同步的開(kāi)銷(xiāo).當(dāng)讀隊(duì)列為空，或者寫(xiě)隊(duì)列滿時(shí)，兩個(gè)隊(duì)列會(huì)進(jìn)行交換，保證讀寫(xiě)操作能夠不間斷進(jìn)行.

數(shù)據(jù)處理模塊能夠根據(jù)瓦片的繪制優(yōu)先級(jí)為各個(gè)線程分配數(shù)據(jù)處理任務(wù)，保證每個(gè)線程中優(yōu)先級(jí)較高的瓦片數(shù)據(jù)能夠優(yōu)先被處理.數(shù)據(jù)處理任務(wù)主要有：根據(jù)地形瓦片模型網(wǎng)格的大小對(duì)高程數(shù)據(jù)進(jìn)行插值拉伸；計(jì)算網(wǎng)格頂點(diǎn)的索引值；以及確定每個(gè)頂點(diǎn)的紋理映射等.數(shù)據(jù)處理完畢后，直接存入寫(xiě)隊(duì)列中;在寫(xiě)隊(duì)列滿時(shí)，能夠控制隊(duì)列交換.

渲染繪制模塊能建立多個(gè)線程，且并行地從讀隊(duì)列中讀出數(shù)據(jù)，利用讀出的數(shù)據(jù)最終生成地形瓦片模型，加載到場(chǎng)景中.在讀隊(duì)列為空時(shí)，能夠控制隊(duì)列進(jìn)行交換.

圖2　雙緩沖隊(duì)列的并行處理機(jī)制整體架構(gòu)圖Fig.2　Parallel processing mechanism of double queue

2算法實(shí)施

筆者采用金字塔模型對(duì)海量地形數(shù)據(jù)進(jìn)行組織和存儲(chǔ)，其基本思想是自底向上生成金字塔，根據(jù)需求直接取其中某一級(jí)作為操作對(duì)象以提高整體效率.在實(shí)現(xiàn)海量地形數(shù)據(jù)處理之前，場(chǎng)景中所有待處理的高程數(shù)據(jù)以及紋理數(shù)據(jù)，均已經(jīng)按照金字塔瓦片模型的設(shè)計(jì)思路，按Google Map標(biāo)準(zhǔn)切分成瓦片，切分后的瓦片數(shù)據(jù)按照以下形式存儲(chǔ)在本地，如：“D:Root432.abc”，該路徑所代表的含義是:“磁盤(pán)根目錄數(shù)據(jù)根目錄層級(jí)行號(hào)列號(hào).后綴名”.

步驟1：計(jì)算待加載瓦片行列號(hào)的范圍.首先，根據(jù)屏幕的可視范圍，建立同屏幕視域等大的邊界盒(Bounding Box,BBOX).在Google Map標(biāo)準(zhǔn)中，可以通過(guò)公式(1)～(3)獲取任意經(jīng)緯度所在瓦片的行列號(hào)：

n=2zoom;

(1)

(2)

(3)

式中：n是當(dāng)前層級(jí)列方向或行方向上瓦片總數(shù)；zoom是層數(shù)；xtile和ytile分別表示列號(hào)和行號(hào)；lon是瓦片左上角的經(jīng)度；lat是瓦片左上角的緯度.

然后，將邊界盒的最小經(jīng)度、緯度以及最大經(jīng)度、緯度分別代入公式(1)～(3)，就能夠確定整個(gè)可視范圍內(nèi)待加載瓦片行列號(hào)的范圍.

步驟2：計(jì)算瓦片的加載優(yōu)先級(jí).確定單張瓦片加載優(yōu)先級(jí)的主要依據(jù)是：瓦片中心點(diǎn)與視點(diǎn)的距離，距離越小，繪制的優(yōu)先級(jí)就越高.依據(jù)步驟1中的公式可得到以下公式：

(4)

g(ytile)=lat=arc tan(sinh(π×(1-

(5)

假設(shè)瓦片的行號(hào)為x，列號(hào)為y，則瓦片的中心點(diǎn)坐標(biāo)經(jīng)緯度CenterLon、CenterLat分別可由以下公式求出:

(6)

(7)

求出瓦片的中心點(diǎn)經(jīng)緯度坐標(biāo)后，再轉(zhuǎn)化為三維空間坐標(biāo);根據(jù)三維空間坐標(biāo)系兩點(diǎn)間距離的運(yùn)算公式，求出瓦片中心點(diǎn)與視點(diǎn)的距離，然后將瓦片按距離大小從小到大排序，便得出了一個(gè)瓦片加載優(yōu)先級(jí)隊(duì)列.

步驟3：按照瓦片加載的優(yōu)先級(jí)進(jìn)行任務(wù)分配.將所有瓦片的數(shù)據(jù)處理任務(wù)，按照瓦片加載優(yōu)先級(jí)分配給多個(gè)線程并行處理.任務(wù)分配時(shí)，將所有待處理任務(wù)，按照瓦片加載優(yōu)先級(jí)從大到小依次分配給各個(gè)線程進(jìn)行處理.假設(shè)負(fù)責(zé)數(shù)據(jù)處理的線程總數(shù)為4，具體分配方法如圖3所示.

從步驟2得出的瓦片加載優(yōu)先級(jí)隊(duì)列中，按優(yōu)先級(jí)從高到低得到待處理瓦片，依次分配給各個(gè)線程.設(shè)Tilek為瓦片加載優(yōu)先級(jí)隊(duì)列中瓦片，則第m個(gè)線程中待處理瓦片隊(duì)列為：{Tile4k+m} (k=0,1,2,…)，這就保證了每個(gè)線程中優(yōu)先級(jí)較高的瓦片能夠優(yōu)先得到處理.

步驟4：執(zhí)行數(shù)據(jù)處理.任務(wù)分配完成后，各個(gè)線程開(kāi)始執(zhí)行數(shù)據(jù)處理任務(wù).數(shù)據(jù)處理任務(wù)除了進(jìn)行高程數(shù)據(jù)的插值拉伸、生成頂點(diǎn)、計(jì)算頂點(diǎn)索引和紋理映射之外，還需要讀取寫(xiě)隊(duì)列的狀態(tài)，控制兩個(gè)緩沖隊(duì)列進(jìn)行交換.數(shù)據(jù)在單個(gè)線程上的處理過(guò)程如下.

(1)從待處理瓦片隊(duì)列中獲取原始數(shù)據(jù)，進(jìn)行拉伸、插值等處理.

(2)判斷當(dāng)前寫(xiě)隊(duì)列是否已滿，如果隊(duì)列已滿，執(zhí)行(3)；如果隊(duì)列未滿，執(zhí)行(4).

(3)通過(guò)原子操作更改讀寫(xiě)隊(duì)列狀態(tài)標(biāo)識(shí)符，控制讀寫(xiě)隊(duì)列交換，返回(2).

(4)將處理完畢的數(shù)據(jù)寫(xiě)入寫(xiě)隊(duì)列中，并判斷待處理瓦片隊(duì)列的狀態(tài)，如果待處理瓦片隊(duì)列為空，結(jié)束；否則，返回(1).

圖3　 基于優(yōu)先級(jí)的任務(wù)分配Fig.3　Task allocation based on priority

步驟5：地形繪制.數(shù)據(jù)處理完畢后，渲染繪制模塊利用處理完畢的數(shù)據(jù)生成地形瓦片模型，并將生成地形瓦片模型繪制到主界面中，這個(gè)過(guò)程同樣采用并行的方式進(jìn)行，但由于主界面所在的主線程不能被其他線程調(diào)用，所以，在三維場(chǎng)景中加載地形瓦片模型必須采用異步的方式.筆者利用WPF中Dispatcher對(duì)象進(jìn)行異步調(diào)用.地形在單個(gè)線程上的繪制過(guò)程如下：

(1)判斷當(dāng)前讀隊(duì)列是否為空，如果讀隊(duì)列為空，則執(zhí)行(2);如果不為空，則執(zhí)行(3).

(2)通過(guò)原子操作更改讀寫(xiě)隊(duì)列狀態(tài)標(biāo)識(shí)符，控制讀寫(xiě)隊(duì)列進(jìn)行交換，返回(1).

(3)獲取處理完畢的數(shù)據(jù)，生成地形瓦片模型，并加載到場(chǎng)景中，將已加載瓦片數(shù)目加1.

(4)當(dāng)已加載的瓦片數(shù)目與待加載的瓦片總數(shù)目相同時(shí)，完成地形繪制；否則，結(jié)束當(dāng)前任務(wù).

3實(shí)驗(yàn)分析

在Visual Studio 2012的開(kāi)發(fā)環(huán)境下利用WPF實(shí)現(xiàn)目標(biāo)，并在硬件配置為Intel(R) Core(TM) i7-2600 3.40GHz(8 CPUs)，4G RAM，GeForce GT 420的計(jì)算機(jī)上進(jìn)行測(cè)試.實(shí)驗(yàn)數(shù)據(jù)為北京昌平地區(qū)的SRTM(Shuttle Radar Topography Mission)數(shù)據(jù)和SAR影像數(shù)據(jù)，其中，SRTM數(shù)據(jù)的分辨率為90 m，單個(gè)數(shù)據(jù)的像素尺寸為1 024 ×1 024.紋理圖像采用相同地區(qū)的SAR影像數(shù)據(jù)制作，圖像尺寸為19 132×15 314，原始大小為279 MB.在進(jìn)行實(shí)驗(yàn)之前，兩種數(shù)據(jù)均已按照Google Map的標(biāo)準(zhǔn)進(jìn)行了瓦片金字塔切分，單張瓦片的大小為256×256.

3.1確定最佳讀、寫(xiě)線程數(shù)

為了確定最佳讀、寫(xiě)線程數(shù)，以生成由100塊地形瓦片模型組成的三維地形場(chǎng)景為目標(biāo)，設(shè)置緩沖隊(duì)列長(zhǎng)度為100進(jìn)行實(shí)驗(yàn)，每個(gè)平均值均由15次測(cè)量得出.具體實(shí)驗(yàn)步驟如下：

步驟1：確定數(shù)據(jù)處理的最佳線程數(shù).在不同的線程數(shù)下進(jìn)行數(shù)據(jù)處理測(cè)試，記錄每個(gè)線程數(shù)目下處理時(shí)間的平均值，令渲染繪制的線程數(shù)目為1，測(cè)試結(jié)果如表1所示.從表1可以看出，在線程數(shù)目為8時(shí)數(shù)據(jù)處理的平均時(shí)間達(dá)到最小.為了得到最佳的處理速度，實(shí)驗(yàn)時(shí)采用8個(gè)線程對(duì)數(shù)據(jù)進(jìn)行處理為最佳.

表1　不同寫(xiě)線程下數(shù)據(jù)處理的平均時(shí)間

步驟2：確定渲染繪制的最佳線程數(shù).指定數(shù)據(jù)處理的線程數(shù)目為8，記錄在不同渲染繪制線程數(shù)目下處理時(shí)間的平均值，通過(guò)對(duì)比，最終確定最佳的渲染繪制線程數(shù)，實(shí)驗(yàn)結(jié)果如表2所示.

表2　不同讀線程數(shù)目下渲染繪制的平均時(shí)間

由表2可以看出：當(dāng)渲染繪制線程數(shù)目超過(guò)2個(gè)后，處理時(shí)間開(kāi)始增加,因此，將渲染繪制線程的數(shù)目設(shè)置為2.

步驟3：對(duì)比實(shí)驗(yàn).按照以上兩個(gè)步驟得到的最佳線程數(shù)目，建立雙緩沖隊(duì)列方法的實(shí)驗(yàn)場(chǎng)景，并與單線程和多線程單緩沖區(qū)兩種方法進(jìn)行對(duì)比實(shí)驗(yàn)，3個(gè)實(shí)驗(yàn)場(chǎng)景如表3所示.

場(chǎng)景1、2、3分別代表：?jiǎn)尉€程、多線程單緩沖區(qū)以及多線程雙緩沖區(qū)為對(duì)每個(gè)場(chǎng)景進(jìn)行了15次測(cè)試，獲得各個(gè)實(shí)驗(yàn)場(chǎng)景下生成三維地形所需的平均時(shí)間：場(chǎng)景1為3 374.8 s，場(chǎng)景2為790.5 s，場(chǎng)景3為432.3 s.

表3　對(duì)比實(shí)驗(yàn)場(chǎng)景

可以得出：在大規(guī)模地形繪制中，采用雙緩沖隊(duì)列方法的處理速度，約是單線程方法的7.8倍，是多線程單緩沖隊(duì)列的1.83倍.

3.2對(duì)比分析

為了驗(yàn)證本文方法在處理大規(guī)模地形數(shù)據(jù)時(shí)的效率，選擇與文獻(xiàn)[7,10]中提出的兩種傳統(tǒng)LOD方法以及Mipmap方法進(jìn)行對(duì)比.其中,文獻(xiàn)[7] 提出了一種基于四叉樹(shù)孤立分割和屏幕誤差的地形LOD算法；文獻(xiàn)[10]提出了一種3D_DP和Quad_TIN支持下的大規(guī)模地形自適應(yīng)LOD算法，實(shí)驗(yàn)結(jié)果如表4所示.

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

從表4可以看出，在一次性加載大量地形瓦片時(shí)，本文方法在繪制時(shí)間上要優(yōu)于Mipmap方法、文獻(xiàn)[7]方法和文獻(xiàn)[10]方法，這說(shuō)明本文方法能夠在保證地形模型細(xì)節(jié)的前提下，顯著提升海量地形數(shù)據(jù)的處理速度.在實(shí)際應(yīng)用中，當(dāng)對(duì)三維瓦片模型的展示細(xì)節(jié)要求較高、或需要頻繁重新構(gòu)建三維場(chǎng)景時(shí)，本文方法更有優(yōu)勢(shì).

4結(jié)論

針對(duì)在大規(guī)模地形繪制過(guò)程中硬件的性能優(yōu)勢(shì)得不到充分利用的狀況，提出了一種基于雙緩沖隊(duì)列的海量地形數(shù)據(jù)并行處理方法.該方法將瓦片的繪制過(guò)程分解為數(shù)據(jù)處理以及渲染繪制兩個(gè)過(guò)程，將讀、寫(xiě)操作分隔開(kāi)來(lái)，減少了CPU與GPU的空閑時(shí)間.在對(duì)讀、寫(xiě)兩個(gè)過(guò)程進(jìn)行并行處理的同時(shí)，設(shè)計(jì)了兩個(gè)緩沖隊(duì)列，分別負(fù)責(zé)暫存用于讀入和寫(xiě)出的數(shù)據(jù)，這不僅能夠充分發(fā)揮多核處理器的性能，而且能夠最大限度地減少線程間同步所浪費(fèi)的時(shí)間；在數(shù)據(jù)處理時(shí)也考慮了瓦片加載的優(yōu)先級(jí)，從而根據(jù)優(yōu)先級(jí)進(jìn)行任務(wù)分配，提升了用戶體驗(yàn).實(shí)驗(yàn)表明，該方法能夠顯著提升海量地形數(shù)據(jù)處理速度，為海量地形數(shù)據(jù)處理提供了新的思路.后續(xù)研究將考慮把本文的方法與傳統(tǒng)LOD的方法相結(jié)合，以達(dá)到更好效果.

參考文獻(xiàn)：

[1]姚凡凡,梁強(qiáng),許仁杰,等. 基于Vega Prime的三維虛擬戰(zhàn)場(chǎng)大地形動(dòng)態(tài)生成研究[J]. 系統(tǒng)仿真學(xué)報(bào),2012,24(9):1900-1904.

[2]閆佳,閆楓. 基于XNA的地理信息系統(tǒng)的研究與實(shí)現(xiàn)[J]. 測(cè)繪與空間地理信息,2014,37(11):152-154.

[3]龔桂榮,杜瑩,歐陽(yáng)峰. 地形金字塔中地物模型的空間劃分及層級(jí)索引研究[J]. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào),2014,31(2):198-202.

[4]李建勛,郭蓮麗,李楊,等. 面向瓦片金字塔的層深確定與投影變換方法[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(9): 2683-2686.

[5]應(yīng)申,靳鳳攢,李霖,等. 基于ArcGIS Engine的矢量數(shù)據(jù)分層分塊技術(shù)研究[J]. 測(cè)繪地理信息,2014,39(6):50-53.

[6]胡鵬昱, 王曉軍. 基于 Geometry Clipmap 算法的大規(guī)模地形可視化研究[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2012,29(7): 87-90.

[7]張俊峰,姚志宏. 基于四叉樹(shù)孤立分割和屏幕誤差的地形LOD算法[J]. 西南交通大學(xué)學(xué)報(bào),2013,48(4):666-671.

[8]HEIDRICH W, SLUSALLEK P, SEIDEL H P. Real-time generation of continuous levels of detail for height fields[C]//Proc Winter School of Computer Graphics’98.Plzen： Science Press,1998: 315-322.

[9]TURNER B.Real-time dynamic level of detail terrain rendering with roam.(2000-04-03)[2015-02-02] [EB/OL].http://www.gamasutra.com/view/feature/131596/realtime_dynamic_level_of_detail_.php.

[10]張俊峰,孫大鵬,許德合. 3D_DP和Quad_TIN支持下的大規(guī)模地形自適應(yīng)LOD算法[J]. 地理與地理信息科學(xué),2014,30(3):29-32.

[11]時(shí)鋼. 基于Mipmap的大規(guī)模地形繪制算法與仿真[J]. 計(jì)算機(jī)仿真,2015,32(2):270-274.

[12]劉浩, 曹巍, 趙文吉, 等. 面向大規(guī)模地形的瓦片調(diào)度與實(shí)時(shí)繪制算法[J]. 計(jì)算機(jī)科學(xué), 2013, 40(6A):120-124.

[13]楊秀峰,靳海亮,臧文乾. 基于GPU并行處理的地形三維重建技術(shù)研究[J]. 江西科學(xué),2014,32(1):22-25.

[14]于衛(wèi)東. 三維地理空間環(huán)境重建與繪制技術(shù)研究[D]. 鄭州: 解放軍信息工程大學(xué)地理空間信息學(xué)院, 2012.

Double-Buffered Queue-Based Parallel Processing Algorithm for Massive Terrain Dataset

CHEN Xiaopan1,QU Jiantao1,2,ZHAO Yameng2,WANG Peng1,2,CHEN Yulin1

(1.College of Computer and Information Engineering, Henan University, Kaifeng 475004,China;2.Institute of Remote Sensing and Digital Earth, Chinese Academy of Sciences， Beijing 100012, China)

Abstract:When dealing with massive terrain data, the advantage of hardware performance can’t be fully utilized. This has become a bottleneck, which restricts the speed of massive terrain tiles rendering. This paper analyzes the key factors that affect large-scale terrain rendering speed, and proposes a parallel algorithm for massive terrain data processing. The algorithm adopts double buffer queues and divides large scale terrain rendering into two parallel processing which includes data processing and rendering. The two buffer queues are responsible for data reading and writing operations in turn. The loading priority of terrain tiles is considered and tasks are allocated based on the priority. The experimental results show that this approach improves the speed of rendering massive terrain tiles greatly.

Key words:massive terrain data; double buffer queue; parallelization; large-scale terrain rendering; tile load

收稿日期:2015-09-26；

修訂日期：2015-11-19

基金項(xiàng)目:國(guó)家‘973’計(jì)劃資助項(xiàng)目(Y070072070)；國(guó)家國(guó)防科技工業(yè)局高分重大專(zhuān)項(xiàng)項(xiàng)目(Y4D0100038;Y4D00100GF)

作者簡(jiǎn)介:陳小潘(1982—)，男，河南偃師人，河南大學(xué)講師，博士研究生，主要從事空間分析優(yōu)化、圖像處理與模式識(shí)別研究，E-mail:xpchen@henu.edu.cn.

文章編號(hào):1671-6833(2016)03-0006-05

中圖分類(lèi)號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

doi:10.13705/j.issn.1671-6833.2016.03.002