快速绘制圆弧的行程算法

A run-length algorithm for fast circle drawing

为了提高圆弧的生成效率,给出一种快速圆弧绘制的简单算法.该算法将圆弧离散轨迹看成是由一系列水平线段和斜线段构成,逐段找出并绘制这些线段,可减少圆弧绘制过程中所需的输出操作.与现存的行程类算法不同,新算法对斜线段的定义更合理,并直接对传统Bresenham算法的决策参数进行迭代和检测,圆弧的不同区段无需重新构造初始值,节约了运算量且算法结构非常简单.2步加速计算线段长度措施的提出进一步提高了计算效率,且每执行一次输出操作可生成2个或多个像素点.与Bresenham算法相比,新算法的圆弧平均绘制速度提高近1倍,并可以推广到椭圆或其他二次曲线的绘制中.

In order to improve the efficiency of circle drawing,a simple algorithm for fast circle drawing was proposed. In the present algorithm,the discrete locus of a circular arc was thought to be composed of a series of horizontal lines and diagonal lines. By locating and drawing these lines one by one,the output operation in the circle drawing process can be reduced. Different from the conventional run-length algorithms,the new algorithm defines diagonal lines more reasonably,and iteration and inspection are realized directly with the decision parameters of Bresenham algorithm. It is unnecessary to recalculate the initial values in different segments of circle,and thus the operation amount gets reduced and the algorithm structure is quite simple. The proposed 2-step accelaration calculation of line length increases the calculation efficiency further. Every output operation can generate two or more pixels. New algorithm almost doubles the circle drawing speed,compared with Bresenham algorithm. Furthermore,new algorithm can be generalized to the production of ellipse and other conics in computer graphics.