新一代载人航天器显示仪表的图形加速算法研究

张庆熙，夏加高，李文新

(兰州空间技术物理研究所，兰州 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直线生成算法和基于凸多边形的种子填充算法比改进前的算法在图形绘制的效率上有明显的提升。整套算法能够准确绘制空间站仪表的操控及显示界面，相比于其它的改进算法，提高了界面图形绘制和显示的实时性，以及画面刷新率的上限，同时规避了不能使用图形加速卡带来的硬件限制问题，能够在一定程度上满足空间站航天仪表对图形加速的需求，在空间站仪表操控显示界面的绘制上具有较好的工程实用性。