王家潤(rùn)，孫禹楠，尹 輝，楊志龍

華北計(jì)算技術(shù)研究所 基礎(chǔ)三部，北京100083

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，國(guó)家及軍隊(duì)的網(wǎng)絡(luò)安全日益重要，網(wǎng)絡(luò)態(tài)勢(shì)可視化也成為研究熱點(diǎn)[1-2]。不僅如此，在軍事作戰(zhàn)戰(zhàn)場(chǎng)綜合態(tài)勢(shì)中，軍事目標(biāo)之間內(nèi)部復(fù)雜抽象的邏輯關(guān)系（通信、指揮、作戰(zhàn)編隊(duì)、目標(biāo)跟蹤等）可視化，已成為戰(zhàn)場(chǎng)態(tài)勢(shì)感知的關(guān)鍵，也已成為戰(zhàn)場(chǎng)態(tài)勢(shì)可視化的重點(diǎn)研究?jī)?nèi)容，深度揭示敵方的作戰(zhàn)意圖，從而整體提升軍事作戰(zhàn)的決策水平。

網(wǎng)絡(luò)可視化一般轉(zhuǎn)換成圖的node-link 表達(dá)[3]，重點(diǎn)是自動(dòng)布局算法[4]及圖的繪制美學(xué)標(biāo)準(zhǔn)研究[4]，在軍事場(chǎng)景中，還需要考慮目標(biāo)的三維空間真實(shí)位置約束。文獻(xiàn)[5]中，通過(guò)建立IP與經(jīng)緯度的映射，以互聯(lián)網(wǎng)目標(biāo)的分層層次作為邏輯高度，建立賽博空間與三維地理空間的一一映射，但缺失真實(shí)的高度信息。文獻(xiàn)[6]中，對(duì)互聯(lián)網(wǎng)節(jié)點(diǎn)基于節(jié)點(diǎn)的地理位置約束進(jìn)行了網(wǎng)絡(luò)拓?fù)淇梢暬?，并在三維數(shù)字地球上進(jìn)行可視，地面上節(jié)點(diǎn)之間采用近似拋物線表達(dá)連接關(guān)系，但沒(méi)有考慮地面的起伏對(duì)連線的影響。文獻(xiàn)[7]中，美軍軍用編輯工具M(jìn)OLE 中對(duì)軍事目標(biāo)進(jìn)行了視覺(jué)上的重排，實(shí)際的地理位置采用錨點(diǎn)，顯示位置與真實(shí)位置通過(guò)虛線相連，地理范圍采用包絡(luò)輔助顯示，如圖1 所示，但沒(méi)有討論三維顯示。

圖1 MOLE：錨點(diǎn)、地理范圍凸包線等效果

在軍事地形顯示中，文獻(xiàn)[8]對(duì)線貼地采用LOD 及道格拉斯-普克算法化簡(jiǎn)曲線等進(jìn)行了處理，并對(duì)zfighting 閃爍現(xiàn)象進(jìn)行深度偏移減弱，高程采樣計(jì)算量較大，而且針對(duì)地形起伏變化劇烈的區(qū)域，完全貼地會(huì)引起視覺(jué)上的抖動(dòng)感及破碎感。文獻(xiàn)[9]中，采用經(jīng)典的陰影錐技術(shù)，實(shí)現(xiàn)線面與地面的像素級(jí)融合，而且只能處理單色。文獻(xiàn)[10]中，對(duì)交通道路網(wǎng)的繪制采用高度增加偏移量及垂直墻的顯示策略，避免了考慮地形起伏的影響，但顯示位置發(fā)生了變化。文獻(xiàn)[11]中，在三維球上，對(duì)航空飛行路線的繪制采用B 樣條邊綁定、BumpMapping 技術(shù)、GPU Shade 等繪制，效果較好，但對(duì)地理位置的高度信息沒(méi)有考慮。文獻(xiàn)[12]采用濾波策略，可提取出地形起伏特征，一定程度上可消除地形劇烈起伏的影響。文獻(xiàn)[13]采用梯度提取高程采樣點(diǎn)的方法，可提取出地形起伏特征，消除地形劇烈起伏的影響。文獻(xiàn)[14]將高程采樣，提取地形起伏關(guān)鍵點(diǎn)，并采用B樣條曲線擬合，實(shí)現(xiàn)標(biāo)號(hào)的跨掠式顯示。

目前網(wǎng)絡(luò)可視化軟件ECharts、Gephi、D3、FireEye、FORG3D、Pajek、Cytoscape[15]等，網(wǎng)絡(luò)可視化布局算法及動(dòng)態(tài)效果等較好，但是在三維顯示中，沒(méi)有考慮地形影響。軍事標(biāo)號(hào)的貼地繪制方法主要為在提取地勢(shì)的基礎(chǔ)上，對(duì)點(diǎn)集進(jìn)行一定的處理，消除地形劇烈變化的影響，得到貼合地勢(shì)的標(biāo)號(hào)繪制，但是保留了地勢(shì)的不斷起伏變化。

本文面向軍事作戰(zhàn)領(lǐng)域，重點(diǎn)考慮三維虛擬戰(zhàn)場(chǎng)中地形起伏的影響，并借鑒圖的美學(xué)標(biāo)準(zhǔn)原則，提出了軍事目標(biāo)關(guān)系的保凸三維可視化。主要?jiǎng)?chuàng)新點(diǎn)：

（1）設(shè)計(jì)了融合、替換及剔除策略，采用凸包算法[16-17]，優(yōu)選出保凸特征點(diǎn)集，抽取出地形起伏主體趨勢(shì)特征，消除了隨地勢(shì)的不斷起伏變化。

（2）設(shè)計(jì)了保凸的Bézier 控制點(diǎn)[18-22]的幾何構(gòu)造方法，通過(guò)逐段連續(xù)插值光滑，實(shí)現(xiàn)整條曲線的保凸可視化。

2 軍事雙目標(biāo)單一關(guān)系的保凸可視化

2.1 基本說(shuō)明

研究?jī)蓚€(gè)目標(biāo)之間的單一關(guān)系的三維可視化，軍事目標(biāo)群體的多重關(guān)系三維可視化可分解為兩個(gè)目標(biāo)之間的單一關(guān)系可視化。

定義（保凸特征點(diǎn)集）指兩個(gè)目標(biāo)之間繪制的連接曲線上的點(diǎn)集（含兩個(gè)端點(diǎn)），是兩目標(biāo)之間連接曲線可視化的幾何構(gòu)建要素點(diǎn)集。通過(guò)保凸特征點(diǎn)集，依次連接各點(diǎn)，實(shí)現(xiàn)兩個(gè)目標(biāo)之間關(guān)系的三維可視化。

2.2 算法流程圖

雙目標(biāo)單一關(guān)系可視化流程圖如圖2。

2.3 算法描述

三維坐標(biāo)采用WGS-84地心坐標(biāo)系，地球質(zhì)心為坐標(biāo)原點(diǎn)，位置描述：經(jīng)度、緯度、高度。

輸入：

大范圍判定閾值Delta；高程采樣率Rate；曲線光滑采樣數(shù)Num ；球面弧最大高度Height ；視覺(jué)偏移調(diào)整量Modify；兩個(gè)目標(biāo)點(diǎn)AO、BO 的地理位置信息。

過(guò)程：

步驟1 構(gòu)建兩目標(biāo)虛擬參考線。

將地球中心點(diǎn)EC 與目標(biāo)點(diǎn)AO 相連，形成線段ECAO；將地球中心點(diǎn)EC 與目標(biāo)點(diǎn)BO 相連，形成線段ECBO ，參見(jiàn)圖3（AS 、BS 對(duì)應(yīng)的海平面點(diǎn)；AG 、BG 對(duì)應(yīng)的真實(shí)地面點(diǎn)；AN 、BN 對(duì)應(yīng)的新點(diǎn)）。該步主要是建立與兩個(gè)目標(biāo)點(diǎn)AO、BO 對(duì)應(yīng)的海平面點(diǎn)、地面點(diǎn)等參考信息。

步驟2 虛擬參考線夾角計(jì)算。

計(jì)算線段ECAO 與線段ECBO 的夾角angle，如果angle ＞Delta，則AO 與BO 兩目標(biāo)相距較遠(yuǎn)（默認(rèn)大于1 000 km，短程彈道導(dǎo)彈的射程范圍上限），采用大范圍繪制算法，轉(zhuǎn)到步驟3；否則，轉(zhuǎn)到步驟4。

圖2 雙目標(biāo)單一關(guān)系可視化流程圖

圖3 大范圍球面弧保凸特征點(diǎn)集示意圖

步驟3 構(gòu)建大范圍球面弧型保凸特征點(diǎn)集（第III類保凸特征點(diǎn)集）。

沿線段ECAO 延伸至AN ；沿線段ECBO 延伸至BN 。點(diǎn)AN 與BN 的高度統(tǒng)一采用輸入?yún)?shù)：Height 。最后形成的折線段：AO 點(diǎn)、AN 與BN 之間的球面弧線各點(diǎn)、BO 點(diǎn)，構(gòu)成保凸特征點(diǎn)集，即為目標(biāo)AO 與目標(biāo)BO 之間最終的連接曲線點(diǎn)集，參見(jiàn)圖3 中上部綠色折線上的點(diǎn)集。轉(zhuǎn)步驟8。

步驟4 兩目標(biāo)剖面分析，獲取高程采樣。

使用高程采樣率參數(shù)Rate，采用GIS 兩點(diǎn)之間的剖面分析功能，沿球面插值采樣，計(jì)算目標(biāo)AO 、目標(biāo)BO 對(duì)應(yīng)的經(jīng)緯位置點(diǎn)之間的剖面高程點(diǎn)集，參見(jiàn)圖3中AG、BG 兩點(diǎn)及兩點(diǎn)之間黑色折線上的點(diǎn)。

步驟5 融合、替換、剔除及凸包處理。

采用目標(biāo)點(diǎn)AO 替換點(diǎn)AG ；采用目標(biāo)點(diǎn)BO 替換點(diǎn)BG ；基于點(diǎn)集：EC、AO、AO 與BO 之間的剖面點(diǎn)集、BO ，進(jìn)行凸包（Graham 凸包算法）處理，得到凸包點(diǎn)集，再剔除點(diǎn)EC，形成新的凸點(diǎn)集。如果返回兩點(diǎn)點(diǎn)集，則轉(zhuǎn)到步驟6，否則轉(zhuǎn)到步驟7。

步驟6 構(gòu)建小范圍兩點(diǎn)型保凸特征點(diǎn)集（第I類保凸特征點(diǎn)集）。

由AO 、BO 兩目標(biāo)點(diǎn)之間連線與三維地形無(wú)交點(diǎn)，該兩點(diǎn)直接構(gòu)成保凸特征點(diǎn)集（此處為統(tǒng)一描述，將線段兩點(diǎn)統(tǒng)一描述為保凸特征點(diǎn)集），線段AOBO 即為AO、BO 兩目標(biāo)之間的連接線段。轉(zhuǎn)步驟8。

步驟7 構(gòu)建小范圍曲線型保凸特征點(diǎn)集（第II類保凸特征點(diǎn)集）。

針對(duì)新的凸點(diǎn)集，采用逐段連續(xù)的光滑插值算法進(jìn)行光滑處理[19]，獲得保凸特征點(diǎn)集，參見(jiàn)圖4 中AO 與BO 之間上部綠色曲線點(diǎn)集。轉(zhuǎn)步驟8。

圖4 小范圍Bézier曲線保凸特征點(diǎn)集示意圖

步驟8 可視化繪制。

針對(duì)第I、II、III 各類保凸特征點(diǎn)集，采用幾何線段依次相連，基于VBO技術(shù)繪制出曲線，實(shí)現(xiàn)可視化。

2.4 算法補(bǔ)充

2.4.1 保凸可視化曲線（或點(diǎn)集）分類設(shè)計(jì)

算法產(chǎn)生的保凸特征點(diǎn)集共分為三種類型：小范圍兩點(diǎn)型（第I 類保凸特征點(diǎn)集）、小范圍曲線型（第II類保凸特征點(diǎn)集）、大范圍球面圓弧型（第III 類保凸特征點(diǎn)集）。

（1）小范圍兩點(diǎn)型（第I類保凸特征點(diǎn)集）

當(dāng)在小范圍時(shí)，兩目標(biāo)之間連線與三維地形無(wú)交點(diǎn)時(shí)，此時(shí)從視覺(jué)感知方面看，線段距離最短、最簡(jiǎn)潔，因此此時(shí)采用兩點(diǎn)線段進(jìn)行可視表達(dá)，視覺(jué)效果較好。

（2）小范圍曲線型（第II類保凸特征點(diǎn)集）

當(dāng)在小范圍時(shí)，兩目標(biāo)之間連線與三維地形有交點(diǎn)時(shí)，地面高山等的起伏影響將會(huì)占據(jù)視覺(jué)主導(dǎo)，所以此時(shí)要精細(xì)處理。獲得兩點(diǎn)之間球面弧上的高程采樣點(diǎn)集，獲取高程信息（地形起伏變化）；采用凸包算法，優(yōu)選獲取地形的整體起伏趨勢(shì)；再經(jīng)過(guò)保凸光滑插值處理，獲得保凸特征點(diǎn)集，最后生成的整條曲線基本擬合地勢(shì)、整體保凸等，視覺(jué)效果較好。

剖面分析中會(huì)使用對(duì)應(yīng)金字塔級(jí)別的高程數(shù)據(jù)，GIS剖面分析接口中會(huì)設(shè)置相應(yīng)的金字塔級(jí)別，算法中設(shè)置高程采樣率Rate 參數(shù)，主要也是考慮高程數(shù)據(jù)采樣級(jí)別影響，在實(shí)際中可根據(jù)實(shí)際對(duì)應(yīng)調(diào)整該參數(shù)。

算法中曲線光滑采樣數(shù)參數(shù)Num，主要是調(diào)整曲線的光滑度，根據(jù)實(shí)際要求做調(diào)整。

（3）大范圍球面圓弧型（第III類保凸特征點(diǎn)集）

在較大范圍內(nèi)，大球面弧線成為視覺(jué)感知的主體，尤其是在三維場(chǎng)景中，目標(biāo)之間相距較遠(yuǎn)時(shí)，視覺(jué)主體主要是兩者之間的連線關(guān)系，此時(shí)可主要考慮地球曲率的影響，忽略地表地形起伏的變化影響。同時(shí)也考慮：GIS 中的剖面分析，針對(duì)大范圍時(shí)，會(huì)存在一定的性能問(wèn)題，所以針對(duì)大范圍情景，采用更高效、更簡(jiǎn)潔的算法進(jìn)行簡(jiǎn)化處理，采用較粗略的地球球面弧繪制簡(jiǎn)單，直接的球面插值采樣計(jì)算方面也更為簡(jiǎn)單。算法中設(shè)置球面弧最大高度參數(shù)Height ，一般可設(shè)珠穆朗瑪峰高度8 848 m（或稍高些：10 000 m）。為保證在兩端處連接的光滑性，可進(jìn)行局部中點(diǎn)逐次光滑逼近。較好的可采用基于視點(diǎn)的自動(dòng)光滑，結(jié)合GPU 細(xì)分著色器進(jìn)行實(shí)時(shí)光滑處理。

2.4.2 凸包算法前后的融合、替換及剔除策略設(shè)計(jì)

（1）采用目標(biāo)AO 位置替換AG 位置；采用目標(biāo)BO 位置替換BG 位置。即將目標(biāo)位置點(diǎn)與剖面分析的高程點(diǎn)進(jìn)行融合及替換。

設(shè)計(jì)思路：因?yàn)榭梢暬抢L制目標(biāo)AO 、目標(biāo)BO的連接曲線，希望這兩點(diǎn)能是最終曲線上的首末點(diǎn)，所以將該兩目標(biāo)點(diǎn)提前參與。特別注意：在本文中，為討論方便，限定軍事目標(biāo)位置不能低于地面點(diǎn)以下，AO只能在AG 的外側(cè)（上部或該點(diǎn)），同理，BO 只能在BG 的外側(cè)（上部或該點(diǎn)）。

（2）凸包計(jì)算前，將地球中心點(diǎn)EC 加入，構(gòu)建新點(diǎn)集：EC、AO、AO 與BO 之間的剖面點(diǎn)集、BO，基于該點(diǎn)集，采用凸包處理后，再?gòu)漠a(chǎn)生的點(diǎn)集中剔除地球中心點(diǎn)EC。

設(shè)計(jì)思路：點(diǎn)EC 參與凸包計(jì)算，主要是保證整個(gè)凸包點(diǎn)集向外凸出（從地球內(nèi)部往外看），以便保證最后兩目標(biāo)之間的連接曲線向外凸出（即向上凸出）；凸包處理后，再剔除地球中心點(diǎn)，主要是保證最后繪制的曲線起點(diǎn)與終點(diǎn)恰好是目標(biāo)AO、BO 兩點(diǎn)。

經(jīng)過(guò)上述策略處理，構(gòu)建出的凸包點(diǎn)集，具有良好的整體外凸性，表現(xiàn)為特征點(diǎn)從地心向外分布，將地形高程采樣點(diǎn)集簡(jiǎn)化為較少的保凸特征點(diǎn)集，優(yōu)選出地勢(shì)的主體變化特征點(diǎn)，在一定程度上屏蔽地形的起伏[12-14]，為后面的可視化奠定了關(guān)鍵基礎(chǔ)。

2.4.3 保凸Bézier控制點(diǎn)的幾何構(gòu)造

參照?qǐng)D5，輸入凸點(diǎn)集ABCDE。以CD 為例：在該段上再插入兩個(gè)新控制點(diǎn)，然后以C、D 端點(diǎn)及這兩個(gè)新控制點(diǎn)，構(gòu)造一段三次Bézier曲線。以下標(biāo)表示新插入的控制點(diǎn)，例如：D 的左右兩側(cè)D1及D2。

（1）內(nèi)部新增控制點(diǎn)的幾何構(gòu)建過(guò)程

以點(diǎn)C 為例，在三角形BCD 中：

①計(jì)算中線GH 。

②記a=CG 與CH 的長(zhǎng)度比值，在GH 上取點(diǎn)F，使得GF 與FH 的長(zhǎng)度比值為：

a=CG/CH=GF/FH

③過(guò)C 點(diǎn)作GH 的平行線C1C2，使得CC1=GF，CC2=FH 。

④過(guò)C2作CD 的垂線L1；過(guò)D1作CD 的垂線L2，比較兩條垂線長(zhǎng)度，取較小者（例如L2）對(duì)應(yīng)的點(diǎn)D1，則過(guò)D1作CD 的平行線，交C1C2于點(diǎn)C3，則C3、D1即為CD 內(nèi)部所求的兩個(gè)新控制點(diǎn)。

依據(jù)上述過(guò)程，依次逐個(gè)處理非端點(diǎn)的各點(diǎn)。在端點(diǎn)處，進(jìn)行特殊處理：開(kāi)始端點(diǎn)A 的右側(cè)控制點(diǎn)A2，使得A2=A，左側(cè)控制點(diǎn)A1忽略；結(jié)束端點(diǎn)E 的左側(cè)點(diǎn)E1，使得E1=E，右側(cè)控制點(diǎn)E2忽略。

（2）保凸Bézier曲線幾何設(shè)計(jì)思路

①四個(gè)控制點(diǎn)下的Bézier曲線形狀變化

參看圖6，在不同的控制點(diǎn)下，Bézier 曲線（中間曲線）形狀會(huì)有較大變化。圓形點(diǎn)表示開(kāi)始與結(jié)束兩個(gè)控制點(diǎn)，中間方形點(diǎn)表示內(nèi)部?jī)蓚€(gè)控制點(diǎn)?？煽闯?，如果Bézier 曲線需要保凸，則內(nèi)部?jī)蓚€(gè)控制點(diǎn)需要保證同側(cè)、不交錯(cuò)，關(guān)鍵是保證四個(gè)控制點(diǎn)（特征多邊形）是凸點(diǎn)列[18-19]。

②整條Bézier曲線的連續(xù)保凸光滑

圖5 Bézier曲線保凸控制點(diǎn)構(gòu)造示意圖

圖5 中，在線段AB 上，基于A、A2、B1、B 四個(gè)控制點(diǎn)，構(gòu)造三次Bézier 曲線；在線段CD 上，基于C、C3、D1、D 四個(gè)控制點(diǎn)，構(gòu)造三次Bézier 曲線，其余各段類似處理。將各段Bézier曲線依此相連，合成出整條的Bézier曲線，即為最終所求的曲線。整條曲線具有如下幾何特點(diǎn)：連續(xù)光滑；整體保凸。

圖6 內(nèi)部控制點(diǎn)不同分布生成曲線示意圖

在每個(gè)輸入點(diǎn)的兩側(cè)生成的控制點(diǎn)共線，例如C 點(diǎn)的兩側(cè)控制點(diǎn)C1、C3，保證了各段Bézier 曲線在連接處的光滑[18]；輸入點(diǎn)列ABCDE 是凸點(diǎn)列，并且在每一小段上的Bézier新插入的兩個(gè)控制點(diǎn)處于同一外側(cè)（C點(diǎn)的兩側(cè)控制點(diǎn)C1、C3），四個(gè)控制點(diǎn)（C、C3、D1、D）組成的特征多邊形是梯形，保證了是凸點(diǎn)列，從而保證了該段上的Bézier曲線外凸[22]。綜合上述兩個(gè)階段的保凸處理，最后合成的整體Bézier曲線保凸[19-20]、連續(xù)光滑。

③兩個(gè)新控制點(diǎn)無(wú)交錯(cuò)的證明

下面證明：在每個(gè)輸入點(diǎn)兩側(cè)插入的新控制點(diǎn)，長(zhǎng)度小于所投影所在邊長(zhǎng)的1/2。該處理主要是保證新插入的兩個(gè)控制點(diǎn)不會(huì)出現(xiàn)相互交錯(cuò)，從而避免該小段上的Bézier曲線出現(xiàn)扭曲等現(xiàn)象，參見(jiàn)圖6（c）。

由構(gòu)建過(guò)程知a=CG/CH=GF/FH，即GF=aFH，CG=aCH 。在三角形GCH 中，GH ＜GC+CH，GH=GF+FH，得出GF+FH ＜GC+CH，即有aFH+FH ＜aCH+CH，即FH ＜CH ，由構(gòu)建過(guò)程知CC2=FH ，H是CD 中點(diǎn)，可知：CC2＜1/2CD。因?yàn)镃3處于C、C2之間，所以CC3＜1/2CD，類似可證明DD1＜1/2CD，即C3與D1位于CD 的垂直平分線PQ 兩側(cè)。

④平行截取處理的保凸及視覺(jué)設(shè)計(jì)

“過(guò)D1作CD 的平行線，交C1C2于點(diǎn)C3”，使得C3D1∥CD，通過(guò)這種平行截?cái)啵瑯?gòu)建了一個(gè)梯形，保證了四個(gè)控制點(diǎn)組成的特征多邊形CC3D1D 是凸點(diǎn)列，由Bézier曲線的保凸性可知：特征多邊形是凸多邊形時(shí)Bézier曲線是凸的，而且較好地抑制了每小段（CD）上構(gòu)建的Bézier曲線可能出現(xiàn)的單側(cè)較高凸起的現(xiàn)象[18]，延伸到空中的空間緊湊感也更好，曲線的局部對(duì)稱性也得到較大的改善。在C3D1與CD 之間，任意平行線與兩側(cè)的交點(diǎn)，都能滿足凸點(diǎn)列要求，但是與CD 太接近，導(dǎo)致該段上的Bézier曲線過(guò)度接近CD 線段，視覺(jué)上無(wú)法感覺(jué)出光滑的效果。也可不用平行線段，只將C2朝C1回移，找到保凸的新點(diǎn)，構(gòu)成凸點(diǎn)列，但是中間兩個(gè)控制點(diǎn)的高度可能不同，曲線可能會(huì)出現(xiàn)單側(cè)凸起現(xiàn)象，曲線的對(duì)稱性會(huì)較差。綜合考慮，平行截取方法構(gòu)建的Bézier曲線貼近凸包線、連續(xù)光滑、近似對(duì)稱、空間占有較少等，視覺(jué)上的美感較好。

2.4.4 算法時(shí)間復(fù)雜度分析

整個(gè)過(guò)程主要包含三個(gè)階段：剖面分析、凸包提取、Bézier插值光滑。剖面分析主要是依據(jù)高程網(wǎng)格數(shù)據(jù)，線性查詢出采樣點(diǎn)的高程數(shù)據(jù)，時(shí)間復(fù)雜度O(N)；Graham掃描算法時(shí)間復(fù)雜度為O(N×lb N)[17]；Bézier光滑處理時(shí)間復(fù)雜度為O(N)。整體時(shí)間復(fù)雜度為O(N×lb N)，其中N 為點(diǎn)集中點(diǎn)的個(gè)數(shù)。

2.4.5 視覺(jué)偏移調(diào)整量Modify參數(shù)

在三維疊加矢量顯示時(shí)會(huì)出現(xiàn)z-fighting 閃爍現(xiàn)象[8]，一般需要做一定的處理，保證無(wú)閃爍的視覺(jué)效果。在構(gòu)造凸包點(diǎn)集前，針對(duì)高程采集的中間點(diǎn)可增加一定的視覺(jué)偏移量（兩個(gè)目標(biāo)點(diǎn)不增加該偏移量，保證首末位置的準(zhǔn)確性），進(jìn)行適當(dāng)升高，算法中的視覺(jué)偏移調(diào)整量Modify 主要是考慮此處，可根據(jù)實(shí)際進(jìn)行調(diào)整。本文可視化算法中已保證整條曲線外凸，所以增加稍許偏移量，不會(huì)影響整條曲線的整體外凸趨勢(shì)，視覺(jué)效果上影響較小。

2.4.6 視覺(jué)美學(xué)原則的符合性分析

圖的繪制美學(xué)原則[4]主要包含直線邊原則、區(qū)域最小化原則、凸多邊形原則等，本文算法依據(jù)這些原則實(shí)現(xiàn)連線的繪制。

（1）直線邊原則

人類視覺(jué)感知最直接的方式，是最直觀的展示網(wǎng)絡(luò)連接的方式。在兩點(diǎn)之間不會(huì)穿山的時(shí)候，優(yōu)先選用直線段繪制連線，即小范圍兩點(diǎn)型。

（2）區(qū)域最小化原則

網(wǎng)絡(luò)拓?fù)鋱D的繪制應(yīng)該盡量節(jié)省屏幕空間。本文算法中小范圍曲線型依地勢(shì)進(jìn)行繪制，大范圍球面圓弧型以珠穆朗瑪峰高度進(jìn)行約束，與文獻(xiàn)[6]中的直接采用拋物線繪制相比，三維空間占用較少，屏幕占用空間也會(huì)較少。

（3）凸多邊形原則

與凹多邊形相比，凸多邊形具有視覺(jué)上的完美感，視覺(jué)美感較好。本文算法中小范圍曲線型由凸包和保凸的Bézier 插值得到，大范圍球面圓弧型擬合地球球面，整條曲線外凸，和球心可以構(gòu)成完整的凸多邊形，并且由此能消除視覺(jué)上的抖動(dòng)現(xiàn)象。

圖7 保凸特征點(diǎn)集不同類型的多重繪制示意圖

3 軍事目標(biāo)群體多重關(guān)系的保凸可視化

針對(duì)軍事目標(biāo)群體多重關(guān)系的可視化，可通過(guò)分解為兩目標(biāo)之間單一關(guān)系的三維可視化進(jìn)行處理。

3.1 可視化數(shù)據(jù)模型

基于圖論，建立數(shù)據(jù)模型M=(V,E)，V ：目標(biāo)（或頂點(diǎn)）集合（含位置信息，顯示樣式：包圍球、顏色等）；E：關(guān)系（或邊）集合（含連線樣式：顏色、粗細(xì)、動(dòng)態(tài)、方向性、繪制偏移量等基本顯示屬性）。

3.2 構(gòu)建性能優(yōu)化

目標(biāo)群體包含的關(guān)系較多時(shí)，顯示連線的構(gòu)建，整體來(lái)說(shuō)計(jì)算量將會(huì)比較大?？紤]到每條連線的構(gòu)建過(guò)程相互獨(dú)立，可采用OpenMP或CUDA等高性能并行計(jì)算API[23]，進(jìn)行性能優(yōu)化。

3.3 顯示性能優(yōu)化

繪制時(shí)可采用GPU Shader進(jìn)行高性能等繪制[11]。

3.4 多重關(guān)系的偏移繪制

兩目標(biāo)之間，如果存在多種關(guān)系時(shí)，需要考慮不同連線的偏移，避免兩目標(biāo)之間不同連線的空間顯示重疊，需要符合圖的美學(xué)一般原則：邊交叉數(shù)量盡量少。針對(duì)三種保凸特征點(diǎn)集類型，進(jìn)行不同的多重偏移處理：

（1）小范圍兩點(diǎn)型

作中垂線，在中垂線上向外（從地球球心向外看；如果線段垂直地面，可考慮以指北針?lè)较驗(yàn)榛鶞?zhǔn)，增加旋轉(zhuǎn)偏移）取一點(diǎn)，采用最大值拋物線法或最大值Bézier曲線法構(gòu)建，結(jié)果見(jiàn)圖7（a）中最上部的綠色及藍(lán)色曲線，可依次向外追加繪制偏移量向空中擴(kuò)張。

（2）大范圍球面圓弧型

將兩線段分別向外旋轉(zhuǎn)一個(gè)繪制偏移角度，并分別延長(zhǎng)一個(gè)繪制偏移長(zhǎng)度，再整體繪制，參看圖7（b）中最上部的全部藍(lán)色折線部分。

（3）小范圍曲線型

將高程剖面分析中（不含兩個(gè)端點(diǎn)）各點(diǎn)高度增加一個(gè)繪制偏移量，再采用凸包擬合光滑法（簡(jiǎn)稱：凸包擬合法）進(jìn)一步處理，參見(jiàn)圖7（c）最上部的藍(lán)色弧線部分。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)條件

Win7 64位操作系統(tǒng)，i7-3770，3.4 GHz CPU，4 GB內(nèi)存，GTX 650ti顯卡。三維開(kāi)源圖形引擎Open Scene Graph（OSG）[24]版本為3.0.1。采用1∶25 萬(wàn)DEM 高程數(shù)據(jù)，地理范圍：北京香山附近。

4.2 結(jié)果及分析

4.2.1 作戰(zhàn)態(tài)勢(shì)圖繪制效果

分別使用本文算法、貼地繪制和直線繪制一張作戰(zhàn)態(tài)勢(shì)圖，包含目標(biāo)13個(gè)（其中空中目標(biāo)2個(gè)，地面目標(biāo)11個(gè)），連線20條，如圖8、圖9、圖10所示。

圖8 本文算法繪制效果

圖9 貼地繪制效果

比較圖8和圖9可看出：圖9中貼地連線，部分連線凹凸變化，出現(xiàn)視覺(jué)上的抖動(dòng)感，其中5 條具有明顯抖動(dòng)，2條有一定的彎曲，都是由于下方空中目標(biāo)產(chǎn)生，共占比35%。產(chǎn)生抖動(dòng)和扭曲的連線不符合圖的凸多邊形原則，視覺(jué)美感較差。圖8 中采用本文算法繪制，連線保證外凸（從球心方向往外看），符合圖的凸多邊形原則，視覺(jué)美感較好。

圖10 直線繪制效果

比較圖8 和圖10 可看出：圖10 中直線繪制，部分連線出現(xiàn)“穿山入地”現(xiàn)象，其中5 條比較明顯，1 條輕微被地形遮蓋，共占比30%?！按┥饺氲亍睂?dǎo)致連線在視覺(jué)上出現(xiàn)“破碎”感，視覺(jué)效果較差。圖8 中采用本文算法繪制，連線外凸，較好地對(duì)“穿山入地”的連線進(jìn)行了校正，已基本沒(méi)有穿山入地現(xiàn)象，驗(yàn)證了本文算法的有效性。

整體上看，本文算法繪制的效果，比貼地繪制和直線繪制的效果要好，綜合來(lái)看，該態(tài)勢(shì)圖中有7 條連線得到了改善，效果改善提升約為35%。

4.2.2 局部連線繪制效果與分析

圖11中高程采樣后，經(jīng)過(guò)凸包處理，共有凸包點(diǎn)六個(gè)，其中右側(cè)除端點(diǎn)外還有兩個(gè)凸點(diǎn)。

圖11 跨越多山峰：凸包擬合曲線效果

比較圖11～圖13，可看出：（1）凸包擬合曲線能提取多個(gè)山峰的主要趨勢(shì)，無(wú)“穿山”現(xiàn)象，保凸、光滑。（2）貼地曲線，每點(diǎn)取自實(shí)際的地面高程點(diǎn)，與凸包擬合曲線相比，視覺(jué)感知波動(dòng)較大，不符合圖繪制美學(xué)中的凸多邊形原則；從不同的視點(diǎn)看，中間山坳部分的曲線可能會(huì)被附近的山引起前后遮擋，造成視覺(jué)上對(duì)整條曲線的“間斷感”及“破碎”感[12]，而凸包擬合曲線則有較好的抗“破碎”能力。（3）最大值Bézier 曲線使用首末凸包點(diǎn)及最高凸包點(diǎn)三點(diǎn)生成。只在最高點(diǎn)附近擬合較好，在右側(cè)較低山峰附近，與凸包擬合曲線在該處差距較大，因?yàn)橹皇褂昧俗髠?cè)的最高凸包點(diǎn)，缺失了中間右側(cè)的凸點(diǎn)，忽略了這些凸包點(diǎn)處的地形高度信息，導(dǎo)致擬合地勢(shì)不足，在較低處附近出現(xiàn)了部分曲線的“穿山”現(xiàn)象。

圖12 跨越多山峰：貼地曲線效果

圖13 跨越多山峰：最大值Bézier曲線效果

圖14 曲線局部幾何特征綜合分析（隱去高程后）

圖14中的下部細(xì)折線為凸包線，中間曲線為Bézier曲線，上部粗線段為控制點(diǎn)連線，向上的垂線為凸包邊的垂直平分線。從該圖可看出：（1）新插入的控制點(diǎn)在垂直平分線兩側(cè)，不會(huì)越界與交錯(cuò)；（2）每一小段上的Bézier 曲線保凸且處于外側(cè)，與凸包線的凸性一致；（3）兩個(gè)新控制點(diǎn)連線與該段基本平行，特征多邊形構(gòu)成凸點(diǎn)列；（4）每一小段上的Bézier曲線近似對(duì)稱，沒(méi)有明顯的單側(cè)凸出現(xiàn)象；（5）整條曲線（中間曲線）保凸，貼近凸包線，與文獻(xiàn)[6]中的拋物線效果相比，空間占用更少；（6）整條曲線連續(xù)、光滑。

4.2.3 算法性能與結(jié)果分析

對(duì)算法中的時(shí)間及中間數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，最大值Bézier 曲線（簡(jiǎn)稱最大值曲線），凸包擬合光滑線（簡(jiǎn)稱凸包擬合線）。表1 是繪制不同數(shù)目曲線的時(shí)間統(tǒng)計(jì)，表2是不同精度時(shí)各類曲線生成的時(shí)間統(tǒng)計(jì)，圖15是與之對(duì)應(yīng)的曲線圖，表3是與表2對(duì)應(yīng)的高程采樣點(diǎn)、凸包采樣點(diǎn)等的點(diǎn)數(shù)統(tǒng)計(jì)，圖16是與表3對(duì)應(yīng)的高程采樣點(diǎn)數(shù)與凸包點(diǎn)數(shù)比較曲線圖。精度系數(shù)越大，高程采樣點(diǎn)數(shù)越多，曲線越精確，默認(rèn)精度系數(shù)取0.1。

表1 不同數(shù)目曲線的生成時(shí)間 ms

表2 不同精度曲線的生成時(shí)間 ms

圖15 不同采樣點(diǎn)數(shù)生成時(shí)間

表3 不同精度曲線的點(diǎn)數(shù) 個(gè)

從表1 可知，隨著曲線條數(shù)的增加，凸包擬合線生成時(shí)間與最大值曲線生成時(shí)間都呈線性增長(zhǎng)，兩者時(shí)間基本近似。

表2是不同精度下，凸包擬合線生成時(shí)間與最大值曲線生成時(shí)間都呈線性增長(zhǎng)，兩者時(shí)間也基本接近。結(jié)合表3，參看圖15，可看出：隨高程采樣點(diǎn)數(shù)的增加（即精度增加），凸包擬合線生成時(shí)間與最大值曲線生成時(shí)間都呈線性增長(zhǎng)。

從表3 看出，高程采樣點(diǎn)數(shù)變化范圍：9～129，而對(duì)應(yīng)的凸包擬合線（光滑前）的凸包點(diǎn)數(shù)已得到極大的優(yōu)化，點(diǎn)數(shù)范圍降低到：4～7。參看對(duì)應(yīng)的圖16可知：在高程采樣點(diǎn)數(shù)不斷增加（即精度增加）的情況下，凸包點(diǎn)數(shù)基本趨于穩(wěn)定，這表明了凸包在抽取地勢(shì)整體變化趨勢(shì)方面，具有很強(qiáng)的簡(jiǎn)化能力。

圖16 凸包點(diǎn)數(shù)和高程采集點(diǎn)數(shù)對(duì)比

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

綜合上述實(shí)驗(yàn)結(jié)果，結(jié)論如下：保凸可視化算法生成的目標(biāo)連接曲線具有較好的特點(diǎn)：整體保凸、光滑、擬合地勢(shì)較好、無(wú)“穿山入地”現(xiàn)象、符合圖的美學(xué)原則等。算法中的凸包對(duì)地勢(shì)整體變化趨勢(shì)的抽取具有較強(qiáng)的能力。

5 結(jié)束語(yǔ)

通過(guò)在目標(biāo)之間進(jìn)行剖面分析，獲得三維地勢(shì)的起伏變化信息；通過(guò)與目標(biāo)位置等進(jìn)行保凸融合，采用Graham 掃描算法，優(yōu)選出了反映整體地勢(shì)變化趨勢(shì)的保凸特征點(diǎn)集；通過(guò)設(shè)計(jì)保凸的Bézier曲線控制點(diǎn)幾何構(gòu)造方法，實(shí)現(xiàn)整條曲線的保凸光滑，而且整體空間占有較少。實(shí)驗(yàn)結(jié)果顯示：目標(biāo)連接曲線擬合地形變化整體趨勢(shì)，具有優(yōu)良的保凸性，較好地保證了目標(biāo)之間連接曲線的整體單凸性，整體單一向下彎曲，形成了空中分布的視覺(jué)感知，在一定程度上減弱了高山前后遮擋的影響，避免了視覺(jué)上的“S”型扭曲現(xiàn)象等，較好地消除了地形起伏引起的“穿山入地”，極大減輕了視覺(jué)感知上的間斷性“破碎”感[12]及抖動(dòng)感等，視覺(jué)感知較好。

進(jìn)一步：（1）研究STK、ECharts、FireEye等軟件中的動(dòng)態(tài)特效及光照效果[11]，完善可視化動(dòng)態(tài)效果。（2）針對(duì)網(wǎng)絡(luò)作戰(zhàn)領(lǐng)域，探索虛擬網(wǎng)絡(luò)空間與地理空間的混合顯示，深入研究地理因素約束下的網(wǎng)絡(luò)態(tài)勢(shì)可視化。（3）針對(duì)軍事中作戰(zhàn)編隊(duì)這種特殊群體，借鑒復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的思想進(jìn)行挖掘[25]，并進(jìn)一步探索更好的群體關(guān)系可視化。（4）針對(duì)小范圍兩點(diǎn)型，可考慮采用邊集束[10]技術(shù)進(jìn)一步改善效果等。（5）針對(duì)拓?fù)浣Y(jié)構(gòu)復(fù)雜混亂的問(wèn)題，考慮地形約束，進(jìn)行布局算法，從而減少邊交叉數(shù)量，提升視覺(jué)美感，需要下一步深入研究。