張立強(qiáng)，徐翔，譚繼強(qiáng)

（1.北京師范大學(xué)遙感科學(xué)國家重點(diǎn)實(shí)驗(yàn)室，北京 100875；2.黑龍江測繪地理信息局，黑龍江 哈爾濱 150081）

0 引言

高性能計算是以并行計算的形式同時使用多種計算資源解決大型復(fù)雜的計算問題。隨著數(shù)據(jù)采集技術(shù)飛速發(fā)展，人們獲取的矢量地圖數(shù)據(jù)的精細(xì)程度日益提高，數(shù)據(jù)量越來越大，矢量地圖往往包含大量復(fù)雜地理要素，并且要素之間存在復(fù)雜的拓?fù)鋷缀侮P(guān)系，使得大規(guī)模矢量地圖的快速可視化對于高性能并行計算的需求十分迫切。

目前基于并行計算方法實(shí)現(xiàn)矢量地圖可視化的文獻(xiàn)不多，大多算法集中在數(shù)據(jù)簡化方面，通過數(shù)據(jù)簡化完成矢量地圖的快速可視化。Guibas等［1］證明了如何在避免自相交的情況下保留盡可能少的點(diǎn)是一個NP－h(huán)ard問題。Estkowski等［2］提出了一種針對平行線要素（如等高線）的綜合方法，即先采用Douglas－Peuker算法生成初步的簡化結(jié)果，然后用“繞遠(yuǎn)之路（detour）”替換交叉的地方以避免要素之間的相交，該方法的時間復(fù)雜度在最壞的情況下為O（n3）。Yang等［3］以 Visvalingam－Whyattt算法為基礎(chǔ)，在簡化時加入約束條件，可避免簡化后相交和自相交錯誤的產(chǎn)生，其時間復(fù)雜度是O（nlogn）。Mustafa等［4］提出了一種基于Voronoi圖的算法，借助于深度緩存，將每個要素的Voronoi區(qū)域渲染到模板緩存中，再利用模板測試，保證每個要素的簡化結(jié)果都位于該要素的Voronoi區(qū)域中，從而避免了要素間的相交。該方法因借助了圖形硬件可獲得較快的效率，但其簡化精度會受到幀緩存分辨率的影響，且不能避免簡化后要素的自相交。楊玲等［5］在Mustafa等研究的基礎(chǔ)上，利用幀緩存和Voronoi實(shí)現(xiàn)矢量地圖的快速簡化以及用模板緩存剔除Voronoi圖中因自相交而重疊的區(qū)域，避免了簡化后要素間錯誤相交和自相交。

為了實(shí)現(xiàn)大數(shù)據(jù)量矢量地圖實(shí)時可視化，本文提出了基于多核CPU和GPU的矢量地圖快速可視化方法。在GPU進(jìn)行并行計算的同時，利用多核CPU創(chuàng)建多線程進(jìn)行數(shù)據(jù)讀寫，隱藏數(shù)據(jù)I／O時間，提高顯示的實(shí)時性。

1 串行矢量地圖可視化

為了加快大數(shù)據(jù)量矢量地圖可視化的速度，需要基于計算機(jī)硬件的性能，采用簡化算法將矢量數(shù)據(jù)簡化成不同的細(xì)節(jié)層次，然后根據(jù)窗口縮放的尺寸采用不同層次的數(shù)據(jù)顯示。為了避免簡化后的線要素出現(xiàn)自相交及要素間相交的拓?fù)溴e誤，首先將每個線要素拆分為單調(diào)鏈；再借助于圖形硬件（模板緩存、深度緩存和顏色緩存相結(jié)合）對每個單調(diào)鏈進(jìn)行簡化；最后，連接簡化后的單調(diào)鏈以得到線要素的最終簡化結(jié)果［5，6］。該過程計算量大，數(shù)據(jù)I／O頻繁，計算耗時，需通過并行計算提高其處理速度。

2 數(shù)據(jù)讀寫

在預(yù)處理階段建立適于繪制的數(shù)據(jù)結(jié)構(gòu)，包括包圍盒層次結(jié)構(gòu)和樹狀索引結(jié)構(gòu)。對于圖1中的索引樹，不同層的數(shù)據(jù)表示不同尺度的地圖，最高層的節(jié)點(diǎn)表示國家尺度上的地圖，第二層的節(jié)點(diǎn)表示省域尺度上的地圖，第三層的節(jié)點(diǎn)表示市域尺度上的地圖。層次越低，其細(xì)節(jié)程度越高。同時對每一層次的數(shù)據(jù)進(jìn)行分塊，每塊的大小控制在5M左右為宜，為各塊計算最小包圍矩形。在數(shù)據(jù)讀寫時，自頂向下遍歷索引樹。如果一個節(jié)點(diǎn)的最小包圍矩形不在視域范圍內(nèi)，則停止遍歷；否則，根據(jù)該地圖的最小包圍矩形在近裁剪面上的投影，如果其投影面積小于閾值δ，則停止遍歷，該節(jié)點(diǎn)應(yīng)該被渲染，否則繼續(xù)遍歷。

圖1 索引樹，從頂至下細(xì)節(jié)程度逐漸增加Fig.1 Index tree，details increase from the top to the bottom

把數(shù)據(jù)文件中的索引樹信息和幾何數(shù)據(jù)分開，會大大提高場景裝載的速度。特別是對于海量數(shù)據(jù)的大場景而言，裝載時需要把整個文件順序讀入內(nèi)存，進(jìn)行文件解析，速度緩慢。而分開之后，索引樹文件非常小，這樣的讀入解析時間會大幅度減小。通過由樹根向葉子節(jié)點(diǎn)遞歸遍歷，以包圍盒或剖分信息為判據(jù)把整個子樹剔除，從而達(dá)到優(yōu)化。

但是由于裝載數(shù)據(jù)耗時較長，往往會出現(xiàn)數(shù)據(jù)已位于可見范圍內(nèi)，但由于未能及時裝載而不可見，造成用戶等待的情況。為了防止這種情況，對于數(shù)據(jù)的預(yù)取十分必要。另外，一般而言，最新的請求總是比那些老的請求更具緊迫性。為此，一個簡單、有效的實(shí)現(xiàn)是采用后入先服務(wù)方式，也就是永遠(yuǎn)優(yōu)先服務(wù)最新的數(shù)據(jù)請求，過時的請求總是被排在最后處理，或者被主動取消。當(dāng)渲染線程發(fā)出命令時，中斷對上幀預(yù)取數(shù)據(jù)的裝載，而首先裝載本幀所需數(shù)據(jù)。

在物理內(nèi)存消耗到某個臨界值時，需要選取那些不再使用的幾何數(shù)據(jù)并將其移出內(nèi)存。關(guān)于移出數(shù)據(jù)的選取，根據(jù)當(dāng)前運(yùn)動預(yù)測，結(jié)合可見性剔除算法確定在下幾幀中最不可能被訪問到的繪制體，然后把這些數(shù)據(jù)置換出物理內(nèi)存。給定視點(diǎn)和視線方向，正常情況下，連續(xù)幾幀中，場景可看做在一條直線上作相同運(yùn)動，因而下一幀目標(biāo)點(diǎn)和視點(diǎn)可以基于前一幀和當(dāng)前幀內(nèi)插。預(yù)測下一幀的視點(diǎn)位置與方向后，可將其偏離視線方向且可視域最遠(yuǎn)的數(shù)據(jù)優(yōu)先移出內(nèi)存。

3 矢量地圖簡化與渲染

矢量地圖數(shù)據(jù)的簡化采用楊玲等［5］的方法，根據(jù)閾值的大小實(shí)現(xiàn)不同細(xì)節(jié)層次的簡化。在簡化過程中，基于ε－Voronoi圖和借助于圖形硬件（幀緩存、模板緩存和深度緩存）避免矢量要素間相交和自相交。由于構(gòu)建單調(diào)鏈的Voronoi圖計算量大，可以通過并行技術(shù)加快Voronoi圖的生成［7，8］。生成每一個矢量要素的Voronoi圖時，通過GPU加速實(shí)現(xiàn)最終數(shù)據(jù)的簡化。因此，能夠同時通過CPU和GPU的并行完成矢量數(shù)據(jù)簡化，其中ε－Voronoi圖通過CPU并行計算完成，合規(guī)線段的判斷和違規(guī)線段的剔除基于CUDA語言在GPU中進(jìn)行。

根據(jù)某個地圖對最終圖像的像素貢獻(xiàn)決定需要繪制的精細(xì)程度，這種方法可以有效控制每一幀需要繪制的幾何數(shù)據(jù)的復(fù)雜度。渲染時，以每幅地圖中心為中心，生成一個半徑為ε的球體，將其投影到屏幕上，如果投影面積超過一個給定閾值，則顯示時該地圖可替代原始地圖。

4 基于并行技術(shù)的矢量地圖可視化

從硬盤將數(shù)據(jù)讀入內(nèi)存的速度較慢，在實(shí)時性要求嚴(yán)格的繪制程序中，阻塞式的數(shù)據(jù)請求顯然不可接受。所以，利用并行多線程技術(shù)，將數(shù)據(jù)繪制、數(shù)據(jù)裝載和數(shù)據(jù)簡化分離，就可使主繪制線程無需等待數(shù)據(jù)讀入過程，而是每次只繪制已經(jīng)在內(nèi)存中的簡化數(shù)據(jù)，從而保持較為穩(wěn)定的幀率。

在基于CPU和GPU的并行矢量數(shù)據(jù)簡化和可視化算法中，簡化部分的數(shù)據(jù)I／O時間相比矢量地圖可視化計算時間所占比例大幅提高，I／O瓶頸限制了并行程序運(yùn)行效率的進(jìn)一步提高。

在主線程進(jìn)行基于GPU的并行計算的同時，創(chuàng)建多個派生線程并分配給每個線程一定任務(wù)并行執(zhí)行。利用CPU多核特性，設(shè)計基于多線程的并行方法，將讀數(shù)據(jù)、簡化和可視化3個互不相關(guān)的過程分配給3個線程同時運(yùn)行，線程一從磁盤讀取未計算數(shù)據(jù)塊并存到內(nèi)存中，對內(nèi)存中已簡化數(shù)據(jù)塊的計算結(jié)果進(jìn)行寫操作，線程二調(diào)用核函數(shù)對內(nèi)存中待簡化的數(shù)據(jù)塊進(jìn)行并行簡化計算，線程三實(shí)現(xiàn)不同層次的矢量地圖的可視化。I／O與簡化、可視化并行執(zhí)行可隱藏部分I／O時間。

如圖2所示，程序中包含3個主要的線程：一個負(fù)責(zé)繪制（簡稱T1），一個負(fù)責(zé)I／O管理和數(shù)據(jù)預(yù)?。ê喎QT2），一個負(fù)責(zé)矢量要素的簡化（簡稱T3），這3個線程異步并行運(yùn)行。T1根據(jù)當(dāng)前視點(diǎn)計算當(dāng)前可見視域，并遍歷索引樹，向T3發(fā)出命令；T3根據(jù)T1返回的索引樹層次的ID，選擇合適的結(jié)點(diǎn)，并判斷哪些數(shù)據(jù)塊可見。當(dāng)T2接收到數(shù)據(jù)請求的命令后，將在當(dāng)前視域范圍內(nèi)但不在內(nèi)存中的節(jié)點(diǎn)裝載入內(nèi)存，T3即可對其進(jìn)行簡化，并將簡化后的數(shù)據(jù)傳給T1；T1對其進(jìn)行繪制和可視化，而不需等待其它數(shù)據(jù)的裝載。在T3線程中，進(jìn)一步通過CPU和GPU的并行完成矢量數(shù)據(jù)簡化。

圖2 并行處理線程Fig.2 Parallel processing threads

5 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證本文的方法，在Windows的Vistual C?2010環(huán)境下利用OpenMP、DUDA進(jìn)行了編程實(shí)現(xiàn)，研發(fā)了基于多核CPU和GPU并行的矢量地圖可視化原型系統(tǒng)，并與楊玲等［5］數(shù)據(jù)串行簡化和可視化的時間相比較。表1列出了實(shí)驗(yàn)中所用的計算機(jī)主要配置參數(shù)。

實(shí)驗(yàn)數(shù)據(jù)選取了1∶100萬的全國矢量土壤數(shù)據(jù)和美國夏威夷河流數(shù)據(jù)。這兩種數(shù)據(jù)的矢量要素分別是polygon和polyline，代表兩種不同的空間特征類型，并且要素之間存在著較為復(fù)雜的拓?fù)鋷缀侮P(guān)系。表2列出了兩種數(shù)據(jù)的主要幾何特征。

表1 CPU、GPU參數(shù)Table 1 Parameters of CPU and GPU

表2 實(shí)驗(yàn)所用矢量數(shù)據(jù)Table 2 Vector map data used in the experiments

為了驗(yàn)證采用多核CPU和GPU并行方案能有效提高矢量地圖可視化速度，基于表2中的矢量數(shù)據(jù)，分別在不同的閾值ε下，定量比較了數(shù)據(jù)簡化串行簡化［5］的時間和并行簡化時間。從表3可以看出，本文的方法能夠有效提高矢量數(shù)據(jù)簡化的效率，尤其是在ε較小時，由于需要大量的循環(huán)運(yùn)算判斷每條單調(diào)鏈Voronoi內(nèi)的合規(guī)線段，所以并行方法的效率更高。

表3 數(shù)據(jù)簡化的并行和串行時間比較Table 3 Time of parallel and serial algorithms when data is simplified

圖3展示了ε＝0.2%和ε＝0.05%時，1∶100萬的全國矢量土壤數(shù)據(jù)的可視化結(jié)果，相應(yīng)的驗(yàn)證了串行和并行兩種方法在可視化過程中的時間（表4）。矢量地圖簡化和顯示過程中，由于數(shù)據(jù)量大且存在著復(fù)雜空間關(guān)系，決定了其數(shù)據(jù)的I／O時間難以忽略，提高加速比在很大程度上取決于I／O優(yōu)化的程度，降低數(shù)據(jù)I／O在可視化計算過程中所占的比例能夠顯著提高并行可視化的效率。

圖3 矢量土壤數(shù)據(jù)可視化結(jié)果Fig.3 Visualization of vector soil data

表4 數(shù)據(jù)可視化的并行和串行時間比較Table 4 Time of parallel and serial algorithms when data is rendered

6 結(jié)論

為了加快大規(guī)模矢量地圖的可視化，本文提出了基于多核CPU和GPU的矢量地圖快速可視化方法。在并行過程中，有3個線程：一個負(fù)責(zé)繪制的線程T1，一個負(fù)責(zé)I／O管理和數(shù)據(jù)預(yù)取的線程T2，一個負(fù)責(zé)矢量要素簡化的線程T3，這3個線程異步并行運(yùn)行。T1根據(jù)當(dāng)前視點(diǎn)計算當(dāng)前可見視域，并遍歷索引樹，向T3發(fā)出命令，T3根據(jù)T1返回的索引樹層次的ID，選擇合適的節(jié)點(diǎn)，并判斷哪些數(shù)據(jù)塊可見。當(dāng)T2接收到數(shù)據(jù)請求的命令后，將在當(dāng)前視域范圍內(nèi)但不在內(nèi)存中的節(jié)點(diǎn)裝載入內(nèi)存，T3即可對其進(jìn)行簡化，并將簡化后的數(shù)據(jù)傳給T1，T1對其進(jìn)行繪制和可視化，而不需等待其它數(shù)據(jù)的裝載。在T3線程中，進(jìn)一步利用空閑的CPU并行實(shí)現(xiàn)單調(diào)鏈的ε－Voronoi的構(gòu)建，同時基于GPU加速完成最終的簡化。在GPU并行計算的同時，利用多核CPU創(chuàng)建多線程進(jìn)行數(shù)據(jù)讀寫，隱藏數(shù)據(jù)I／O時間，提高顯示的實(shí)時性。相比楊玲等［5］的串行方法，本文并行方法在大數(shù)據(jù)量矢量地圖簡化和可視化效率上有了極大提高。

未來的工作集中在優(yōu)化數(shù)據(jù)的I／O，降低數(shù)據(jù)I／O在可視化計算過程中所占的比例，進(jìn)一步提高并行大數(shù)據(jù)量復(fù)雜矢量地圖可視化的效率。

［1］ GUIBAS L J，HERSHBERGER J，MITCHELL J，et al.Approximating polygons and subdivisions with minimum link paths［J］.Lecture Notes in Computer Science，1993，3：383－415.

［2］ ESTKOWSKI R，MITCHELL J S B.Simplifying apolygonal subdivision while keeping it simple［A］.Proceedings of the 17th ACM Symposium on Computational Geometry［C］.2001.40－49.

［3］ YANG B S，PURVES R，WEIBEL R.Efficient transmission of vector data over the Internet［J］.International Journal of Geographical Information Science，2007，21（2）：215－237.

［4］ MUSTAFA N，KRISHNAN N S G，VARADHAN S.Dynamic simplification and visualization of large maps［J］.International Journal of Geographical Information Science，2006，20（3）：273－320.

［5］ 楊玲，張立強(qiáng)，何子琳，等.一種大規(guī)模矢量地圖數(shù)據(jù)實(shí)時簡化的方法［J］.中國圖象圖形學(xué)報，2009，14（6）：1007－1011.

［6］ ZHANG L Q，ZHANG L，REN Y C，et al.Transmission and visualization of large geographical maps［J］.Photogrammetry and Remote Sensing，2010，66（1）：73－80.

［7］ 李淑艷.基于多核CPU的平面Voronoi圖并行生成算法研究［D］.陜西師范大學(xué)，2010.

［8］ HOFF K E，CULVER T，KEYSER J，et al.Fast computation of generalized Voronoi diagrams using graphics hardware［A］.Computer Graphics Simplification of Large Maps 301（SIGGRAPH′99Proceedings）［C］.1999，33：277－286.