基于FPGA的圆弧快速生成算法及其应用

张小永

（北京青云航空仪表有限公司 北京市 101300）

1 引言

圆弧是组成计算机图形最基本的元素之一。在机载显示系统中，常使用圆弧绘制天地球等图形。现有圆弧绘制算法大多以减少圆弧中每点坐标计算的复杂度为研究对象，以简单的方法获得离实际圆弧线段最近的光栅点[1-3]。

计算机图形学中通常采用Bresenham 算法和数字微分分析仪（digital diあerential analyzer，DDA）算法绘制圆弧。这两种算法采用逐点递推步进的方式绘制圆弧，这种递推步进的绘制方式由于绘制的各点存在严格的先后关系不易实现并行运算，因此目前多核处理器和FPGA 的并行计算能力的大幅提高，并不能有效提高绘制速度。

本算法采用逐点计算各像素到圆心距离以确定该点是否在待绘制圆弧上的方式进行圆弧绘制。该方式较DDA 和Bresenham 圆弧绘制方法增加了计算量，但解除了相邻像素点的递推关系，因为可以在FPGA 实现时通过设计多级流水线大大提高计算速度。

2 算法原理

本算法利用点P 到圆心O 的距离l 是否在圆弧范围内，判定点P 是否在半径R、宽度W 的圆弧范围内，并通过点P 到圆弧角度边界的距离d 判定点P 是否在圆弧角度边界范围内。对于在圆弧线宽边界和起止角度边界的点，利用Wu 反走样算法进行反走样处理，使绘制的圆弧更加美观。另外，利用圆的对称性，可以通过计算第一象限内的四分之一圆弧像素坐标扩展得到整个圆弧的像素坐标。

2.1 点P到圆心O的距离小l

2.2 点P到圆弧边界距离d

因此可得：

2.3 圆弧线宽边界反走样处理

计算点P 沿半径方向的线宽边界颜色系数KR。按点P 到圆心O 的距离l 与半径R 和线宽W 的关系确定KR，具体如下：

图1：圆弧生成算法原理示意图

2.4 圆弧角度边界反走样处理

计算点P 沿圆弧方向的角度边界颜色系数Kθ。按P 到圆弧角度边界的距离d 确定Kθ，具体如下：

（1）当 时，KR=0；

（3）当0＜d 时，KR=1；

2.5 计算反走样系数

根据线宽边界颜色系数KR和角度边界颜色系数Kθ，计算得到第P 的反走样系数K。

3 算法FPGA实现

本算法的实现需要依靠FPGA 强大的计算能力，计算预估圆弧所在区域内各像素点到圆心的距离和到圆弧边界弧度的距离判定该像素是否在圆弧上，从而实现圆弧的快速生成。如图2 所示，本算法在FPGA 中实现时分为四级流水线。

图2：圆弧生成算法FPGA 实现原理框图

第一级流水线实现1 象限四分圆的坐标序列生成。如图3 所示，生成坐标时在的区域内水平扫描生成圆弧像素坐标序列。在生成时利用剔除不在圆弧内的点。利用沿扫描方向像素到圆心的距离l 单调递增的规律，在扫描到时结束本行扫描。利用扫描线与圆弧内径交点随y 坐标减小增大，因此在进行新的一行扫描时，起点设置为上一行扫描线与圆弧内径交点的x 坐标。

第三级流水线依据l、d 和Color 计算各坐标的颜色值，对于在圆弧线宽边界和起止角度边界的点，利用Wu 反走样算法进行反走样处理。并依据对称性对整个圆弧进行扩展。

第四级流水线将计算得到的圆弧各点坐标和颜色值写入图像存储空间。

4 算法仿真与测试验证

图4 给出了对本算法原理利用Matlab 进行仿真的效果图，图中所绘制的圆弧准确美观，圆弧的内外径边界和两端点边界反走样效果理想。图5 给出了本算法在某机载显示设备中实现的圆弧绘制效果。

5 结论

经过上述验证，本文设计的基于FPGA 的圆弧快速生成算法，能够依靠FPGA 强大的计算能力，通过计算预估圆弧所在区域内各像素点到圆心的距离和到圆弧边界弧度的距离判定该像素是否在圆弧上，从而实现圆弧的快速生成。相较计算机图形学常用的Bresenham 圆生成算法和数字微分分析仪算法（digital diあerentialanalyzer，DDA），本方法消除了圆弧生成过程中逐点递推计算的先后关系，能够充分利用FPGA 并行计算的优势，提高圆弧绘制速度。另外通过计算像素到圆弧边界弧度的距离来处理圆弧的两个端点，使圆弧绘制更美观。仿真和实验结果表明：本圆弧生成算法绘制的圆弧视觉效果好，时间效率高，达到了工程应用的目的。

图3：四分圆的坐标序列生成示意图

图4：MATLAB 仿真效果图

图5：某机载显示设备显示效果图