張慶熙，夏加高，李文新

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

0 引言

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

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

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

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

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

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

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

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

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

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

2 圖元加速算法研究

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

2.1 直線加速算法研究

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

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

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

d=kxi+1+b-yi

(1)

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

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

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

算法流程圖如圖3所示。

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

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

2.2 圓的繪制算法研究

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

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

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

圖4 八分圓示意圖

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

(2)

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

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

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

(3)

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

di+1=4xi+6

(4)

在計算每個(xi,yi)時，都利用對稱性將區(qū)域外的其他7個點同時得到。

依次迭代，直到x≥y停止計算。

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

圖5 Bresenham八分圓算法流程圖

2.3 多邊形繪制

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

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

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

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

3 圖形填充算法研究

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

3.1 種子填充算法介紹

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

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

圖7 種子圖形填充算法

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

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

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

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

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

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

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

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

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

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

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

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

圖9 等腰三角形填充

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

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

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

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

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

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

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

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

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

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

4 圖形加速算法驗證

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

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

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

圖11 角度儀表控件

表2 算法效率比較

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

圖12 電源加載控件

表3 算法效率比較

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

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

圖13 某儀表操控交互界面

5 結(jié)束語

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