圆的像素级生成及反走样算法
Double-Step Circle Drawing Algorithm with and without Grey Scale
-
摘要: 介绍了圆的逐点生成算法的研究现状,指出被忽视了的Kuzmin逐点生成圆弧算法具有最小计算量,指出并纠正其存在的严重错误;然后,提出了一种双点生成圆弧算法该算法只用整数运算来选择距离圆弧最近的像素点,比较结果表明,该算法比现有其他算法具有更快的执行速度;最后,在文中算法的基础上提出了一个生成反走样圆弧的算法且没有增加算法的计算量该算法与惟一可比的双点生成反走样圆弧的Wu-Rokne算法进行比较的结果表明,该算法比后者多产生了4个中间灰度级,并且所生成的反走样圆弧的最大光强误差比后者减少了40%文中算法便于硬件实现.Abstract: Some existing pixel-level algorithms for drawing circles are introduced first in this paper. We further pointed out that the Kuzmin's circle drawing algorithm, a neglected algorithm in fact has least calculations, but on the other hand the algorithm carries serious mistakes. This paper corrects the mistakes in the algorithm, and then presented a double-step circle drawing algorithm. The new algorithm chooses the best approximate pixels to the circle with only integer arithmetic. The comparison results show that its speed is higher than the existing circle drawing algorithms. Finally, based on this algorithm, an algorithm for drawing anti-aliased circles is proposed without increasing the calculations. It generates four more intermediate shades of grey scale than the double-step algorithm by Wu and Rokne and the greatest error of intensity is reduced by 40%. These algorithms are easy to be realized by hardware.
下载: