有效的混合圆弧扫描转换算法

张胜男， 牛连强， 陈 欣

（1. 沈阳工业大学信息科学与工程学院，辽宁 沈阳 110870；2. 沈阳工业大学理学院，辽宁 沈阳 110870）

图形基元的生成算法对整个图形系统的效率和质量具有重要影响。因此，从20世纪70年代起，这些基元的光栅转换算法的研究就已开始[1]，至今仍受到关注[2-4]。目前，直线的光栅转换算法已得到了充分的研究，并发展了2步算法、多步算法、行程算法以及多级行程算法等[2,5-7]，利用很少的几次基本运算即可绘制多个像素。但由于圆弧等曲线的非线性性，其进行光栅转换算法的设计远比处理直线复杂，进展也非常缓慢。

作为经典圆弧绘制算法，Bresenham算法[8]和中点法[9]分别采用两点的距离平方差和中点误差作为决策参数，确定每次每步时的坐标位置，算法简单，容易实现。文献[10]提出了基于中点法的快速算法，该算法先将中点法的迭代关系除以系数 2，再利用奇、偶次迭代来分别处理关系式中的常数1/2，从而消除了系数2所带来的位移运算。本文作者于文献[11]提出了一种直接利用残差实现的另一种有别于前述两种算法的基本圆弧生成算法。由于这些算法的共同点是每步选择一个像素，故被称为基于像素（pixel-based）的算法。

为了提高圆弧的生成速度，目前的研究工作主要集中在以下两个方面：

1）尽量减少每次步进消耗的运算次数；

2）尽量减少输出(I/O)的次数。

很难从理论上说明，每次步进至少需要多少次运算，但由于单步选择像素法的运算量已经难以减小，改进的目标将是多步法。……