張慶熙，夏加高，李文新

(蘭州空間技術(shù)物理研究所，蘭州 730000)

0 引言

隨著我國載人航天事業(yè)的不斷發(fā)展，航天顯示儀表作為空間站與航天員之間的數(shù)據(jù)窗口，如何高質(zhì)高效地進(jìn)行數(shù)據(jù)顯示一直是一個(gè)不可回避的問題。航天顯示儀表的存在是為了便于航天員觀察空間站當(dāng)前各系統(tǒng)的各種狀態(tài)數(shù)據(jù)，而人眼在感知事物時(shí)，當(dāng)畫面切換頻率高于40幀/秒，人眼才不會(huì)察覺到畫面的閃爍，為保證儀表的畫面質(zhì)量，每幅圖像從解析到顯現(xiàn)保持必須小于25毫秒[1]?？臻g站在運(yùn)行過程中，各種系統(tǒng)需要傳遞給宇航員的信息量極大，為了能夠及時(shí)展現(xiàn)空間站狀態(tài)，當(dāng)數(shù)據(jù)信息發(fā)生變化時(shí)儀表圖像的切換速度就必須要快，而顯示圖像的切換不同于幻燈片，每一幀二維圖像都需要從點(diǎn)、線、圓、多邊形開始繪制并進(jìn)行圖形填充[2]。

新一代航天顯示儀表采用了DSP/CPU+FPGA的高速處理器架構(gòu)。相比于民用的顯示儀表，空間站中不適合使用體積更大、能耗更高的圖形加速卡(graphics processing unit，GPU)，無法使用民用領(lǐng)域一些利用GPU進(jìn)行圖形加速的新算法，所以必須選擇適合于當(dāng)前儀表硬件平臺(tái)的圖形顯示算法，對(duì)其進(jìn)行改進(jìn)，減少運(yùn)算時(shí)間，提高運(yùn)算效率。此外，受嵌入式平臺(tái)自身的計(jì)算資源總量的限制，圖形顯示算法應(yīng)選擇在保證不過多占用資源基礎(chǔ)上提高處理速度的處理算法。航天儀表控件主要使用二維繪圖算法進(jìn)行繪制，所以改進(jìn)二維繪圖算法，減少繪制所需的計(jì)算量，提高儀表人機(jī)界面的繪制效率。每一點(diǎn)圖像繪制效率的提高，積累到儀表顯示上都會(huì)使儀表的單位時(shí)間顯示信息量得到提升、使得儀表的實(shí)時(shí)性得到加強(qiáng)，使航天員對(duì)空間站的運(yùn)行狀態(tài)把握更為精準(zhǔn)。

1 二維繪圖算法研究內(nèi)容

二維圖形繪制是儀表顯示系統(tǒng)的基礎(chǔ)，圖形算法是一個(gè)專門的研究方向。每當(dāng)圖形算法運(yùn)行速度有微小的提升，對(duì)于整個(gè)系統(tǒng)的運(yùn)行都能夠有節(jié)約大量時(shí)間資源的增益。一般地，二維圖形算法研究內(nèi)容方向可以分為兩大類：圖元(點(diǎn)、線、圓、多邊形)算法研究和圖形填充算法研究。

直線的繪制算法，主要有數(shù)值微分法、中點(diǎn)畫線法、Bresenham等幾種經(jīng)典的算法，近年來也提出一些新的算法，如多像素行直線生成算法[3]，雙步算法進(jìn)行直線繪制[4]。這些新算法在特殊的應(yīng)用場(chǎng)景有較好的效果，但是程序?qū)崿F(xiàn)有些難度。因此，本文在經(jīng)典的直線繪制算法基礎(chǔ)上進(jìn)行研究。

圓的繪制算法較多，內(nèi)接正多邊形逼近算法、圓正交正多邊形逼近算法和8分圓生成算法，也有人提出橢圓離散直線位移加速法[5]，圓弧快速繪制的方法[6]。這些算法的主要思想是利用圓的對(duì)稱進(jìn)行圖形加速。

多邊形算法的基礎(chǔ)是直線算法，各種多邊形的快速生成算法本質(zhì)是直線算法的延伸[7]。

圖形填充算法研究方向較多，經(jīng)典有種子算法、邊界掃描法等。張毅等人提出基于邊界跟蹤的任意區(qū)域填充算法[8];邱國清提出了基于種子算法的環(huán)形掃描填充法[9]。通過對(duì)比分析，這幾種填充算法的效率提高并不明顯，主要是依靠硬件水平的提升來實(shí)現(xiàn)快速填充，所以本文在經(jīng)典的種子算法上進(jìn)行研究。

繪制到屏幕的圖形需要有位置信息，離不開屏幕坐標(biāo)系的設(shè)定[11]。坐標(biāo)系的設(shè)置主要有兩個(gè)方面內(nèi)容，即原點(diǎn)位置和坐標(biāo)軸方向。本文采用如圖1的屏幕坐標(biāo)系，屏幕的左上角為原點(diǎn)，向右為X軸正方向，向下為Y軸正方向。

圖1 屏幕坐標(biāo)系

2 圖元加速算法研究

圖形繪制過程中，由于圖元(點(diǎn)、線、圓、多邊形)的不同，因而需要采取相應(yīng)不同的算法，本節(jié)主要就不同圖元的繪制算法進(jìn)行闡述，并提出可行的加速改進(jìn)算法。

2.1 直線加速算法研究

直線繪圖是2D繪圖中最基本的繪圖功能，是繪制其它圖形的基礎(chǔ)，如果直線繪制的效率高，則會(huì)提高整個(gè)儀表顯示系統(tǒng)的運(yùn)行速度。

繪制直線一般有三種函數(shù)，橫線、豎線和斜直線[12-14]。橫線、豎線的算法比較簡單，但斜直線的算法比較多，時(shí)間和空間復(fù)雜度各不相同。其中最常見的算法有Bresenham直線生成算法[15]，在工程上應(yīng)用廣泛。

經(jīng)典Bresenham直線生成算法的算法步驟如下：首先通過線段的起點(diǎn)(x0,y0)和終點(diǎn)(x1,y1)得出繪制直線的參考坐標(biāo)軸，如果x坐標(biāo)差值絕對(duì)值大于y坐標(biāo)差值絕對(duì)值，則直線沿著X軸繪制，反之則沿著Y軸繪制；第二步，根據(jù)起始點(diǎn)坐標(biāo)差值的正負(fù)號(hào)，決定坐標(biāo)軸的繪制方向；第三步，得出直線斜率；第四步，沿某個(gè)坐標(biāo)軸方向步進(jìn)，計(jì)算另一坐標(biāo)軸的坐標(biāo)的誤差項(xiàng)；第五步，修正誤差項(xiàng)d：

d=kxi+1+b-yi

(1)

如果誤差項(xiàng)大于0.5，則另一坐標(biāo)值加1并繪點(diǎn)，同時(shí)修正誤差項(xiàng)，反之誤差項(xiàng)則保持原值。算法的流程圖如圖2所示。

圖2 Bresenham直線生成算法流程圖

為了更好地滿足需求，對(duì)Bresenham直線生成算法進(jìn)行了改進(jìn)，具體步驟如下：1)通過線段的起始點(diǎn)判斷線段繪制的參考坐標(biāo)軸；2)得出繪制線段的坐標(biāo)方向；3)得出繪制線段的斜率；4)得出線段沿繪制坐標(biāo)方向的中點(diǎn)坐標(biāo)；5)沿繪制坐標(biāo)軸方向得出誤差項(xiàng)；6)修正誤差項(xiàng)d，同式(1)。如果誤差項(xiàng)大于0.5，則另一坐標(biāo)值加1并繪點(diǎn)，同時(shí)向繪制的另一端點(diǎn)減1并繪點(diǎn)，即計(jì)算出兩個(gè)坐標(biāo)值，然后修正誤差項(xiàng)，反之誤差項(xiàng)保持原值。

算法流程圖如圖3所示。

圖3 改進(jìn)的Bresenham直線生成算法流程圖

通過算法流程圖可以看出，改進(jìn)的Bresenham直線生成算法每次循環(huán)可以繪制出兩個(gè)點(diǎn)，比Bresenham直線生成算法節(jié)省循環(huán)次數(shù)，運(yùn)行效率和直線的長度相關(guān)，在200像素點(diǎn)的條件下，減少了100次循環(huán)，減少了100個(gè)計(jì)算步驟，減少了約30%的計(jì)算次數(shù)。

2.2 圓的繪制算法研究

圓是2D幾何繪圖中的基本圖形，其生成算法主要有內(nèi)接正多邊形逼近算法、圓正交正多邊形逼近算法和8分圓生成算法。前兩種算法主要是利用線段逼近圓弧的方法生成圓，其逼近的正N邊形，只有N足夠大，才能更加逼近圓。

零具有對(duì)稱性，只計(jì)算圓上一部分的值，再通過對(duì)稱性將值變換到其他象限可以極大的減少計(jì)算量。目前工程上常用的是八分圓生成算法和中心圓生成法。所謂八分法，只需要計(jì)算八分之一的圖形坐標(biāo)，其它部分通過映射即可以得出坐標(biāo)，從而減少運(yùn)算量。

對(duì)于第一象限內(nèi)，靠近Y軸的八分之一圓弧(弧上點(diǎn)滿足0≤x≤y)如圖4，采用Bresenham直線算法的思想，其基本的方法是利用判別變量來判斷選擇最近的像素點(diǎn)，判別變量的數(shù)值僅僅用一些加、減和移位運(yùn)算就可以計(jì)算出來。Bresenham畫八分圓算法也是用一系列離散的點(diǎn)來近似描述一個(gè)圓弧。

圖4 八分圓示意圖

畫圓時(shí)，第一個(gè)點(diǎn)取(0,R)，設(shè)第i步已經(jīng)確定點(diǎn)(xi,yi)，下一步需要確定A(xi+1,yi+1)位置，這個(gè)點(diǎn)只可能是B(xi+1,yi)或者C(xi+1,yi-1)，由B和C到A的距離之差d大小決定。將d進(jìn)行近似計(jì)算：

(2)

將(0,R)代入上式可得到d=3-2R。

當(dāng)d≥0時(shí)，下一點(diǎn)就選為C點(diǎn)，將yi+1=yi-1代入式(2)得到:

di+1=4(xi-yi)+10

(3)

反之，選D點(diǎn)，將yi+1=yi代入式(2):

di+1=4xi+6

(4)

在計(jì)算每個(gè)(xi,yi)時(shí)，都利用對(duì)稱性將區(qū)域外的其他7個(gè)點(diǎn)同時(shí)得到。

依次迭代，直到x≥y停止計(jì)算。

Bresenham八分圓算法的流程圖如圖5。

圖5 Bresenham八分圓算法流程圖

2.3 多邊形繪制

在儀表顯示系統(tǒng)中，規(guī)則圖形只是圖形的一部分，還有大量的圖形是不規(guī)則圖形，很多不規(guī)則圖形可以通過多邊形顯示。

多邊形繪制是以直線繪制為基礎(chǔ)得到的。其主要思路為將多邊形的頂點(diǎn)通過直線的繪制方法連接起來。直線的繪制算法采用改進(jìn)的Bresenham直線生成算法。

多邊形其主要算法如圖6所示。

圖6 多邊形繪制算法流程圖

3 圖形填充算法研究

圖形填充是在完成圖形繪制之后，對(duì)于具有相同色彩或灰度值的一定區(qū)域進(jìn)行填充，以完成由線成面的過程[16]。本節(jié)主要就經(jīng)典填充算法進(jìn)行分析，并提出改進(jìn)的填充算法。

3.1 種子填充算法介紹

圖形填充的算法有很多種[17-18]，其中較為有名的是種子填充算法，該算法思想簡單，比較易于實(shí)現(xiàn)。

如圖7，種子填充圖形算法的主要思想是在一個(gè)封閉的幾何圖形中找到一點(diǎn)，稱之為種子，種子按照水平掃描，分別從兩個(gè)方向掃描，即向左和向右掃描，掃描的終止條件為圖形的邊界。本行掃描完畢后，再向上或向下尋找新的種子，尋找到的種子條件是必須在圖形邊界內(nèi)。

圖7 種子圖形填充算法

種子圖形填充算法主要有以下幾個(gè)步驟：1)要計(jì)算種子數(shù)組的長度，數(shù)組的大小為Y軸坐標(biāo)相減，然后種子數(shù)組置零；2)根據(jù)給定的首個(gè)種子按左、右兩個(gè)方向進(jìn)行水平掃描，分別掃到兩個(gè)邊界為止；3)種子掃描結(jié)束后，在相對(duì)應(yīng)的位置(Y)上記錄為1，表明本行已經(jīng)掃描結(jié)束；4)尋找新的種子，新種子可以向上尋找也可以向下尋找，向上尋找到了邊界后，再由最下部向上尋找，種子尋找的條件是必須在封閉圖形的范圍內(nèi)，種子可以沿6個(gè)方向?qū)ふ遥?)判斷種子數(shù)組是否已經(jīng)滿了，即種子數(shù)據(jù)的各個(gè)元素均為1時(shí)，說明填充完畢。種子填充算法的具體流程如圖8所示。

圖8 種子圖形填充算法流程圖

種子圖形填充算法可以適用于任意圖形的填充，但是種子的尋找以及掃描邊界的確定都需要耗費(fèi)時(shí)間資源，所以種子圖形填充算法的效率較低[19]。

3.2 基于凸多邊形的種子填充算法

在航天儀表顯示系統(tǒng)中要經(jīng)常使用圖形填充算法，如果能提高圖形填充的繪圖效率，則可以提高屏幕的圖像刷新率上限[20]，為了實(shí)現(xiàn)這一目標(biāo)，本文提出了基于凸多邊形的種子填充算法。

基于凸多邊形的種子填充算法繼承了種子填充算法的核心思想，根據(jù)凸多邊形的幾何特點(diǎn)，以凸多邊形的一條“邊”確定填充種子，記為填充起點(diǎn)；以余下的“邊”作為圖形填充邊界，記為填充終點(diǎn)。將所有起點(diǎn)和終點(diǎn)進(jìn)行對(duì)應(yīng)劃線，則將圖形填充完成。

基于凸多邊形的種子填充算法(以X軸為掃描方向)的步驟如下：

1)要根據(jù)凸多邊形的頂點(diǎn)確定掃描種子的數(shù)量，即X方向掃描線的數(shù)量。根據(jù)凸多邊形頂點(diǎn)的Y軸坐標(biāo)找出最大值和最小值，種子數(shù)量為最大值和最小值之差加1，設(shè)種子數(shù)量為N。同時(shí)定義兩個(gè)坐標(biāo)數(shù)組，掃描起點(diǎn)數(shù)組和終點(diǎn)數(shù)組，數(shù)組的大小均為N，即POINT_START[N]和POINT_END[N]。

2)從凸多邊形的Y軸坐標(biāo)的最小值頂點(diǎn)，沿其左側(cè)到Y(jié)軸坐標(biāo)的最大值頂點(diǎn)進(jìn)行“畫線”操作?！爱嬀€”是指調(diào)用直線繪制程序，將線的點(diǎn)坐標(biāo)放置在POINT_START[N]數(shù)組中。

3)從凸多邊形的Y軸坐標(biāo)的最大值頂點(diǎn)，沿其右側(cè)到Y(jié)軸坐標(biāo)的最小值頂點(diǎn)進(jìn)行“畫線”操作?！爱嬀€”是指調(diào)用直線繪制程序，將線的點(diǎn)坐標(biāo)放置在POINT_ END[N]數(shù)組中，繪點(diǎn)的順序從N-1開始，到0結(jié)束，點(diǎn)的填充順序與第二步相反。

4)繪線填充。根據(jù)POINT_START[N]和POINT_END[N]，從0到N-1依次進(jìn)行繪線操作，則填充完畢。

對(duì)種子圖形填充算法和基于凸多邊形的填充算法復(fù)雜度進(jìn)行比較。設(shè)如圖9所示圖形，分別利用種子圖形填充算法和基于凸多邊形的填充算法進(jìn)行填充。

圖9 等腰三角形填充

表1是兩種填充算法的計(jì)算步驟比較，表中的填充算法只計(jì)算坐標(biāo)點(diǎn)的計(jì)算步驟，不將坐標(biāo)點(diǎn)輸出到屏幕的時(shí)間統(tǒng)計(jì)在內(nèi)。從表1中可以看出，圖8的圖形利用基于凸多邊形的填充算法比種子填充計(jì)算步驟少了398步，減少了幾乎一半的計(jì)算復(fù)雜度。

表1 填充算法復(fù)雜度比較

工程實(shí)踐中，凹多邊形也可以分解為若干個(gè)凸多邊形，利用基于凸多邊形的填充算法進(jìn)行圖形填充，從而減少填充的計(jì)算步驟。

另一方面，有些特殊的凹多邊形也可以利用基于凸多邊形的填充算法進(jìn)行圖形填充，如圖10所示。

圖10 X(Y)軸有序多邊形

圖10中的多邊形Polygon_01雖然不是凸多邊形，但是仍然可以在X軸方向利用基于凸多邊形的填充算法進(jìn)行圖形填充；而多邊形Polygon_02則不可以利用該算法在X軸方向進(jìn)行填充，但是可以利用該算法在Y軸方向進(jìn)行填充，從而提高圖形填充速度。為此，這類特殊的多邊形進(jìn)行了如下定義，稱之為X軸方向有序多邊形或Y軸方向有序多邊形。

定義：在一個(gè)平面上，一個(gè)多邊形與X軸任意掃描線相交有且只有兩個(gè)交點(diǎn)，這個(gè)多邊形稱之為X軸方向有序多邊形。

定義：在一個(gè)平面上，一個(gè)多邊形與Y軸任意掃描線相交有且只有兩個(gè)交點(diǎn)，這個(gè)多邊形稱之為Y軸方向有序多邊形。

X軸方向有序多邊形可以利用基于凸多邊形的填充算法在X軸方向進(jìn)行圖形填充；Y軸方向有序多邊形可以利用基于凸多邊形的填充算法在Y軸方向進(jìn)行圖形填充。

另外圓是特殊的凸多邊形，可以基于凸多邊形的填充算法進(jìn)行圖形填充。

4 圖形加速算法驗(yàn)證

本文算法的驗(yàn)證平臺(tái)采用DSP+FPGA平臺(tái)，該平臺(tái)為新一代航天顯控儀表的通用架構(gòu)，DSP為國產(chǎn)DSP6713，主頻為400 MHz，圖形算法均在DSP處理器中完成，F(xiàn)PGA選用國產(chǎn)的BM3803，由FPGA完成對(duì)顯存的控制輸出。

儀表界面一般由若干儀表控制組成，提高復(fù)雜儀表控件繪圖速度，即可保證整個(gè)航天儀表顯示系統(tǒng)的顯示效率。本文采用了較為復(fù)雜的角度儀表控件和電源加載控件進(jìn)行對(duì)比驗(yàn)證。

用經(jīng)典繪圖算法和本文的圖形加速算法完成角度儀的圖形繪制。圖11的角度儀表圖像，其繪圖用時(shí)對(duì)比如表2。

圖11 角度儀表控件

表2 算法效率比較

繪圖算法和本文的圖形加速算法分別生成如圖12的電源加載控件，其繪圖用時(shí)對(duì)比見如表3。

圖12 電源加載控件

表3 算法效率比較

通過比較用時(shí)，本文的圖形加速算法比經(jīng)典算法有比較明顯的速度優(yōu)勢(shì)，圖形繪制效率有較大的提升，可以滿足新一代航天器顯示儀表的顯示要求，已經(jīng)成功地應(yīng)用在載人航天器上。

如圖13所示，該菜單指令界面為利用本文算法渲染生成的空間站某儀表操作交互界面，整個(gè)界面包括文字都是利用圖形加速算法完成繪制填充，繪制圖形精確，色彩填充完整。在繪制不同界面時(shí)，在不使用圖形加速卡情況下，本算法平均刷新頻率比其他圖形繪制算法提高15 Hz，本算法有明顯的速度優(yōu)勢(shì)，占用計(jì)算資源量更少，更適合于空間站顯示儀表的圖形繪制。

圖13 某儀表操控交互界面

5 結(jié)束語

本文基于空間站對(duì)提高儀表顯示質(zhì)量、效率的需求提出了完整的改進(jìn)的航天儀表2D圖形繪制方法。改進(jìn)的Bresenham直線生成算法和基于凸多邊形的種子填充算法比改進(jìn)前的算法在圖形繪制的效率上有明顯的提升。整套算法能夠準(zhǔn)確繪制空間站儀表的操控及顯示界面，相比于其它的改進(jìn)算法，提高了界面圖形繪制和顯示的實(shí)時(shí)性，以及畫面刷新率的上限，同時(shí)規(guī)避了不能使用圖形加速卡帶來的硬件限制問題，能夠在一定程度上滿足空間站航天儀表對(duì)圖形加速的需求，在空間站儀表操控顯示界面的繪制上具有較好的工程實(shí)用性。