有效的浮点运算消除技术与椭圆的快速生成  

Efficient floating-point operation eliminating technique and fast ellipse generating

作　　者：牛连强[1] 陈欣[2] 宋超[2] 李兆明[3] 

机构地区：[1]沈阳工业大学软件学院,沈阳110870 [2]沈阳工业大学理学院,沈阳110870 [3]长春职业技术学院网络中心,长春130033

出　　处：《沈阳工业大学学报》2014年第1期72-78,共7页Journal of Shenyang University of Technology

基　　金：沈阳市科技计划资助项目(F12-168-9-00);辽宁省科学技术计划资助项目(2007410003)

摘　　要：为了改善椭圆基本生成算法的效率和消除算法中存在的错误边界像素问题,提出了一种浮点数消除技术和标准椭圆的生成算法.与现存算法采用中间量进行浮点数先期消除方法不同,该算法直接利用曲线上相邻两点所满足的表达式的差值构造包含残差的递推关系,再通过最近准则和1/2处的残差将其转换为整数形式的决策参数.分析和实验结果表明,该算法消除了递推关系中每步迭代时的常数项,比目前普遍采用的中点椭圆算法具有更高的效率,且有着与中点法一致的简单性.该算法不会产生特殊情况的错误边界像素,由于残差与亮度具有对应关系,可以实现整数形式的反走样绘制.In order to improve the efficiency of basic generating algorithms for ellipse and eliminate the erroneous pixels at region boundaries in the algorithm, a floating-point operation eliminating technique and an algorithm for standard ellipse generating were proposed. Different from the existing algorithms where the earlier eliminating of floating-point operations was performed with the intermediate parameters, the recursion relations including the residual error were established with the differences between the expressions satisfied by two adjacent points on the curves in the proposed algorithm. Furthermore, the recursion relations were converted into the integer decision perameters according to the nearest criterion and a residual error in 1/2 position. The analysis and experimental results show that the proposed algorithm can eliminate the constant term for each iteration in the recursion relations, has the higher efficiency compared with the mid-point ellipse algorithm widely used at present, and exhibits the simplicity same as the mid-point ellipse algorithm. Meanwhile, the erroneous pixels at region boundaries will not appear in the proposed algorithm for some special cases, and the integral anti-aliasing drawing is easily realized because of the corresponding relation between residual error and brightness.

关 键 词：椭圆生成 整数运算 残差 区域转换 反走样 中点法 光栅转换 浮点运算消除 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]