原创 画圆算法

2009-5-8 22:48 4200 0 分类: MCU/ 嵌入式

 本项目在嵌入式软件开发过程中,涉及到在嵌入式TFT LCD上实现画圆,下面先简要介绍常用的画圆算法(Bresenham算法),然后再具体阐述笔者对该算法的改进。<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />


    一个圆,如果画出了圆上的某一点,那么可以利用对称性计算余下的七段圆弧:Plot(xy)Plot(yx)Plot(y-x)Plot(x-y)Plot(-x-y)Plot(-y-x)Plot(-yx)Plot(-xy)


    1Bresenham 画圆算法。Bresenham算法的主要思想是:以坐标原点(00)为圆心的圆可以通过0度到45°的弧计算得到,即x0增加到半径,然后利用对称性计算余下的七段圆弧。当x0增加到时,yR递减到。


    设圆的半径为R,则圆的方程为:


    f(xy)(x+1)2+y2-R20                                   (1)


    假设当前列(x=xi列)中最接近圆弧的像素已经取为P(xiyi),根据第二卦限1/8圆的走向,下一列(x=xi+1列)中最接近圆弧的像素只能在P的正右方点H(xi+1yi)或右下方点L(xi+1yi-1)中选择,如图1所示。Bresenham画圆算法采用点T(xy)到圆心的距离平方与半径平方之差D(T)作为选择标准,即


    D(T)=(x+1)2+y2-R2                                         (2)


    通过比较HL两点各自对实圆弧上点的距离大小,即根据误差大小来选取,具有最小误差的点为绘制点。根据公式(2)得:


    H(xi+1yi)点有:D(H)=(xi+1)2+yi2-R2


    L(xi+1yi-1)点有:D(L)=(xi+1)2+(yi-1)2-R2


    根据Bresenham画圆算法,则选择的标准是:


    如果|D(H)|<|D(L)|,那么下一点选取H(xi+1yi)


    如果|D(H)|>|D(L)|,那么下一点选取L(xi+1yi-1)


    如果|D(H)|=|D(L)|,那么下一点可以取L(xi+1yi-1),也可以选取H(xi+1yi),我们约定选取H(xi+1yi)


 


    1  Bresenham画圆算法点的选取


    综合上述情况,得:


    |D(H)|>|D(L)|时,选取L(xi+1yi-1)为绘制点坐标;


    |D(H)|<|D(L)|时,选取H(xi+1yi)为绘制点坐标。


    然后将选取的点坐标作为当前坐标,重复上述过程直至xi=或者yi=为止,(xiyi)的初始值为(0R)。


    以上便是Bresenham算法的主要思想,但是上述算法是在一个假设下:以坐标原点(00)为圆心。该假设实际上只是为了方便算法的研究。但在实际嵌入式LCD显示设备中,往往圆心坐标不是(00)点,而是以左上角为(00)点,这样就使得在实际运用中,需要对这个算法做很大的改进。


    另外,如果完全按照Bresenham画圆算法,那么就会涉及到浮点运算,这使得嵌入式编程十分烦琐,因为本系统中所有数据都是整型的,因此在这方面也要作一定的改进。下面根据本系统中嵌入式硬件特点和数据结构得特点,对这个算法进行改进。


    2、改进的Bresenham画圆算法。先假设起始点为(R0),令Pi=(xiyi)为当前的一点,那么我们就需要在Ti=(xiyi+1)Si=(xi-1yi+1)中选取一点,如图2所示。


 


    2 嵌入式LCD画圆时点的选取


    (xi-1/2+eyi+1)ST之间圆上的点,eST中点到圆上点的误差,带入圆的方程(1)得:


    f(xi-1/2+eyi+1)=(xi-1/2+e)2+(yi+1)2-R2=f(xi-1/2yi+1)+2(xi-1/2)e+e2=0   (3)


    在式(3)中,令


    di="f"(xi-1/2yi+1)=-2(xi-1/2)e-e2                                    (4)


    如果e<0,那么di>0,因此选择S=(xi-1yi+1),根据(3)(4)得:


    di+1=f(xi-1-1/2yi+1+1)=di-2(xi-1)+2(yi+1)+1=di+2(yi+1-xi+1)+1         (5)


    如果e30,那么di0,因此选择T=(xiyi+1),根据(3)(4)得:


    di+1=f(xi-1/2yi+1+1)=di+2yi+1+1                                  (6)


    起始点是(R0)的时候,根据(4)di的初始值d0就是:


    d0=f(R-1/20+1)=(R-1/2)2+1-R2=5/4-R=1-R(由于编程中所用数据类型均为整型,故取1-R)。


    综合上述情况,得:


    当选取S=(xi-1yi+1)时,那么di+1di+2(yi+1-xi+1)+1


    当选取T=(xiyi+1)时,那么di+1=di+2yi+1+1


    然后将选取的点坐标作为当前坐标,重复上述过程直至x=y,而不是xi=或者yi=,这样就可以不用作浮点数计算了。


    本项目中的LCD像素为640×480点阵,并且数据是八位的,当横坐标和纵坐标超过255时,那么数据就不能一次传送成功,因此需要通过字节操作来设定高字节,然后再传送低字节。因此,每次画圆上的点时要传送的参数至少是六个,圆心坐标是四个(因为要考虑圆心坐标可能大于255,因此要对其圆心坐标设置高、低字节),另外两个是圆上的点相对于圆心的坐标,但是最后要画一个点,需要四个参数,即改进的画圆算法为六个参数输入,四个参数输出。


    C语言在嵌入式LCD上实现改进的Bresenham画圆算法的部分代码如下:


    void MidBresenhamcircle(int R)  /*改进的Bresenham算法画圆程序*/


    {


    int x,y,d;


    x="0";y=R;d=1-R;        /* 计算初始值 */


    while(x<y)


    { circlePoint(x,y);   /*绘制点(xy)及其在八分圆中的另外7个对称点*/


     if(d<0)  d+=2*x+3;  


     /*根据误差项d的判断,决定非最大位移方向上是走还是不走*/


       else


            { d+=2*(x-y)+5;


              y--;


             }


              x++;


     delay(900000);


     }  /* while */

广告

文章评论 0条评论)

登录后参与讨论
相关推荐阅读
lcjoys12 2009-05-24 16:26
滤波电路
 电容滤波电路<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />★滤波原理◆当u2为正...
lcjoys12 2009-05-08 22:51
RS-232、RS-422与RS-485标准及应用
RS-232、RS-422与RS-485都是串行数据接口标准,最初都是由电子工业协会(EIA)制订并发布的,RS-232在1962年发布,命名为EIA-232-E,作为工业标准,以保证不同厂家产品之间...
lcjoys12 2009-05-08 22:46
单片机AT89S52中文资料
AT89S521 主要性能l 与MCS-51单片机产品兼容l 8K字节在系统可编程Flash存储器l 1000次擦写周期l 全静态操作:0Hz~33MHzl 三级加密程序存储器l 32个可编程I/O口...
lcjoys12 2009-05-08 22:41
基于89C2051的4位显示万年历时钟
基于89C2051的4位显示万年历时钟.C*//*备注:按键一为功能键,按一下调年,按两下调月,按三下调日,按四下调时,按五下调分*//*         按六下退出,或者在任何时候按键四退出设定状态...
我要评论
0
0
广告
关闭 热点推荐上一条 /1 下一条