新一代載人航天器顯示儀表的圖形加速算法研究

張慶熙，夏加高，李文新

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

0 引言

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

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

1 二維繪圖算法研究內容

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

直線的繪制算法，主要有數值微分法、中點畫線法、Bresenham等幾種經典的算法，近年來也提出一些新的算法，如多像素行直線生成算法[3]，雙步算法進行直線繪制[4]。這些新算法在特殊的應用場景有較好的效果，但是程序實現有些難度。因此，本文在經典的直線繪制算法基礎上進行研究。

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

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

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

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

圖1 屏幕坐標系

2 圖元加速算法研究

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

2.1 直線加速算法研究

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

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

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

d=kxi+1+b-yi

(1)

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

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

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

算法流程圖如圖3所示。

圖3 改進的Bresenham直線生成算法流程圖

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

2.2 圓的繪制算法研究

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

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

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

圖4 八分圓示意圖

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

(2)

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

當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)時，都利用對稱性將區域外的其他7個點同時得到。

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

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

圖5 Bresenham八分圓算法流程圖

2.3 多邊形繪制

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

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

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

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

3 圖形填充算法研究

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

3.1 種子填充算法介紹

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

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

圖7 種子圖形填充算法

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

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

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

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

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

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

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

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

2)從凸多邊形的Y軸坐標的最小值頂點，沿其左側到Y軸坐標的最大值頂點進行“畫線”操作。“畫線”是指調用直線繪制程序，將線的點坐標放置在POINT_START[N]數組中。

3)從凸多邊形的Y軸坐標的最大值頂點，沿其右側到Y軸坐標的最小值頂點進行“畫線”操作。“畫線”是指調用直線繪制程序，將線的點坐標放置在POINT_ END[N]數組中，繪點的順序從N-1開始，到0結束，點的填充順序與第二步相反。

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

對種子圖形填充算法和基于凸多邊形的填充算法復雜度進行比較。設如圖9所示圖形，分別利用種子圖形填充算法和基于凸多邊形的填充算法進行填充。

圖9 等腰三角形填充

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

表1 填充算法復雜度比較

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

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

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

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

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

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

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

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

4 圖形加速算法驗證

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

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

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

圖11 角度儀表控件

表2 算法效率比較

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

圖12 電源加載控件

表3 算法效率比較

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

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

圖13 某儀表操控交互界面

5 結束語

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