《图形显示软件》PPT课件.ppt

计算机图形显示技术计算机图形显示技术2 2第十一讲第十一讲 图形软件图形软件Bresenham画线算法画线算法圆的生成算法圆的生成算法Bresenham画圆法画圆法中点画圆法中点画圆法区域填充算法区域填充算法扫描线填充算法扫描线填充算法边界填充算法边界填充算法3 3 图形软件图形软件 Bresenham画线算法画线算法 About BresenhamAbout BresenhamE.Jack Bresenham Professor of Computer SciencePh.D.,Stanford University,1964 Ph.D.,Stanford University,1964 MSIE,Stanford University,1960 MSIE,Stanford University,1960 BSEE,University of New Mexico,1959 BSEE,University of New Mexico,1959Retired from 27 years service at IBM as a Senior Retired from 27 years service at IBM as a Senior Technical Staff Member in 1987.Have taught 10 Technical Staff Member in 1987.Have taught 10 years at Winthrop.Holder of five patents.years at Winthrop.Holder of five patents.4 4 图形软件图形软件 Bresenham画线算法画线算法Bresenham算法算法该算法由该算法由该算法由该算法由BresenhamBresenham在在在在1965年提出，是目前使用较为年提出，是目前使用较为年提出，是目前使用较为年提出，是目前使用较为广泛的一种扫描转换算法，可用于直线、圆弧等图元广泛的一种扫描转换算法，可用于直线、圆弧等图元广泛的一种扫描转换算法，可用于直线、圆弧等图元广泛的一种扫描转换算法，可用于直线、圆弧等图元的扫描转换。的扫描转换。的扫描转换。的扫描转换。5 5 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法基本思想画线算法基本思想过各行各列像素中心构造一组假想的栅格过各行各列像素中心构造一组假想的栅格过各行各列像素中心构造一组假想的栅格过各行各列像素中心构造一组假想的栅格按直线从起点到终点的顺序计算直线与各垂直网格按直线从起点到终点的顺序计算直线与各垂直网格按直线从起点到终点的顺序计算直线与各垂直网格按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中线的交点，然后根据误差项的符号确定该列象素中线的交点，然后根据误差项的符号确定该列象素中线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素与此交点最近的象素与此交点最近的象素与此交点最近的象素6 6 图形软件图形软件 Bresenham画线算法画线算法BresenhamBresenham画线算法画线算法画线算法画线算法设直线从起点设直线从起点设直线从起点设直线从起点（x1,y1x1,y1）到终点到终点到终点到终点（x2,y2x2,y2）设直线方程为：设直线方程为：设直线方程为：设直线方程为：y=kx+by=kx+b 其中其中其中其中b=y1-k*x1b=y1-k*x17 7 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法画线算法若直线斜率若直线斜率若直线斜率若直线斜率k k 0,10,1且且且且x2x1x2x1的情况（的情况（的情况（的情况（1a1a象限）象限）象限）象限）根据根据即即 DDA算法的讨论有：算法的讨论有：xi+1=xi+1 (1)yi+1=yi+k (2)在在1a象限里，当直线光栅化时，象限里，当直线光栅化时，x每次都增每次都增加加1个单元：个单元：xi+1=xi+18 8 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法画线算法由于由于由于由于k k不一定是整数，因此由不一定是整数，因此由不一定是整数，因此由不一定是整数，因此由(2)(2)式求出的式求出的式求出的式求出的y y也不一定是整数。所也不一定是整数。所也不一定是整数。所也不一定是整数。所以要用最靠近以要用最靠近以要用最靠近以要用最靠近y y的整数的整数的整数的整数y yi i来代替来代替来代替来代替y y假设假设假设假设直线上第直线上第直线上第直线上第i i个像素坐标个像素坐标个像素坐标个像素坐标为为为为(x(xi i,y,yi i)，那么，它的下一，那么，它的下一，那么，它的下一，那么，它的下一个点的像素点的可能位置为个点的像素点的可能位置为个点的像素点的可能位置为个点的像素点的可能位置为(x(xi i+1,y+1,yi i)或或或或(x(xi i+1,y+1,yi i+1)+1)。如图：如图：如图：如图：9 9 图形软件图形软件 Bresenham画线算法画线算法BresenhamBresenham画线算法画线算法画线算法画线算法若直线斜率若直线斜率若直线斜率若直线斜率k k 0,10,1且且且且x2x1x2x1的情况（的情况（的情况（的情况（1a1a象限）象限）象限）象限）如上图如上图如上图如上图在在在在x=xx=xi i+1+1处，直线上处，直线上处，直线上处，直线上y y的值的值的值的值y=k(xy=k(xi i+1)+b+1)+b该点该点该点该点距离点距离点距离点距离点(x(xi i+1,y+1,yi i)和点和点和点和点(x(xi i+1,y+1,yi i+1)+1)的距离分别为的距离分别为的距离分别为的距离分别为d d1 1和和和和d d2 2：d d1 1=y-y=y-yi i=k(x=k(xi i+1)+b-y+1)+b-yi i d d2 2=y=yi i+1-y=y+1-y=yi i+1-k(x+1-k(xi i+1)-b+1)-b 因此因此因此因此，这两个距离的差为：，这两个距离的差为：，这两个距离的差为：，这两个距离的差为：d d1 1-d-d2 2=2k(x=2k(xi i+1)-2y+1)-2yi i+2b-1(1)+2b-1(1)1010 图形软件图形软件 Bresenham画线算法画线算法BresenhamBresenham画线算法画线算法画线算法画线算法根据根据根据根据（1 1）式，作如下讨论分析：式，作如下讨论分析：式，作如下讨论分析：式，作如下讨论分析：l l当当当当d d1 1-d-d2 200时，说明直线上的理论点距离时，说明直线上的理论点距离时，说明直线上的理论点距离时，说明直线上的理论点距离(x(xi i+1,y+1,yi i+1)+1)较近，因此下一较近，因此下一较近，因此下一较近，因此下一个直线像素点应取个直线像素点应取个直线像素点应取个直线像素点应取(x(xi i+1,y+1,yi i+1)+1)。l l当当当当d d1 1-d-d2 20 x1x2x1的情况（的情况（的情况（的情况（1a1a象限）象限）象限）象限）因此，利用因此，利用因此，利用因此，利用（d d1 1-d-d2 2）的符号就可以决定下一个像素点的符号就可以决定下一个像素点的符号就可以决定下一个像素点的符号就可以决定下一个像素点的选择的选择的选择的选择然而含有然而含有然而含有然而含有 变量变量变量变量x xi i、y yi i，不利于计算。为此，我们构造一，不利于计算。为此，我们构造一，不利于计算。为此，我们构造一，不利于计算。为此，我们构造一个新的判别式：个新的判别式：个新的判别式：个新的判别式：p pi i=x*(dx*(d1 1-d-d2 2)=2 x)=2 xi i y-2yy-2yi i x+c x+c （2 2）其中：其中：其中：其中：x=(x2-x1)0 x=(x2-x1)0，因此，因此，因此，因此p pi i与与与与(d(d1 1-d-d2 2)符号相同；符号相同；符号相同；符号相同；y=y2-y1y=y2-y1；c=2c=2 y+y+x(2b-1)x(2b-1)1212 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法画线算法若直线斜率若直线斜率若直线斜率若直线斜率k k 0,10,1且且且且x2x1x2x1的情况（的情况（的情况（的情况（1a1a象限）象限）象限）象限）以以以以i+1i+1代代代代 入入入入 式式式式(2)(2)中的中的中的中的i i，得得得得：p pi+1i+1=x*(dx*(d1 1-d-d2 2)=2 x)=2 xi+1i+1 y-2yy-2yi+1i+1 x+c x+c （3 3）将式将式将式将式(3)(3)减去式减去式减去式减去式(2)(2)，并由并由并由并由x xi+1i+1=x=xi i+1+1可得可得可得可得：p pi+1i+1=p=pi i+2+2 y-2y-2 x(yx(yi+1i+1-y-yi i)（4 4）假设直线上的初始端点恰好是其像素点的坐标，则将假设直线上的初始端点恰好是其像素点的坐标，则将假设直线上的初始端点恰好是其像素点的坐标，则将假设直线上的初始端点恰好是其像素点的坐标，则将x1,x1,y1y1和和和和b b代代代代 入入入入 式式式式（2 2）中的中的中的中的x xi i,y,yi i可可可可 到到到到 p pi i的初始值的初始值的初始值的初始值p p1 1=2x=2x1 1 y-2yy-2y1 1 x+2x+2 y+y+x2(yx2(y1 1-kx-kx1 1)-1)-1 =2 =2 y-y-x x （5 5）1313 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法画线算法若直线斜率若直线斜率若直线斜率若直线斜率k k 0,10,1且且且且x2x1x2x1的情况（的情况（的情况（的情况（1a1a象限）象限）象限）象限）利用上面构造的误差判别变量，可得第利用上面构造的误差判别变量，可得第利用上面构造的误差判别变量，可得第利用上面构造的误差判别变量，可得第1a1a象限内的直象限内的直象限内的直象限内的直线线线线BresenhamBresenham算法算法：p p1 1=2=2 y-y-x x x xi+1i+1=x=xi i+1+1 y yi+1i+1=y=yi i+1,p+1,pi+1i+1=p=pi i+2(+2(y-y-x)x)当当当当p pi i 0 0时时时时 y yi+1i+1=y=yi i,p,pi+1i+1=p=pi i+2+2 y y 当当当当p pi i 0 x1x2x1的情况（的情况（的情况（的情况（1a1a象限）象限）象限）象限）从算法可以看出，第从算法可以看出，第从算法可以看出，第从算法可以看出，第i+1i+1步的判别变量步的判别变量步的判别变量步的判别变量p pi+1i+1仅与第仅与第仅与第仅与第i i步的步的步的步的判别变量判别变量判别变量判别变量p pi i、直线的两个端点分量差、直线的两个端点分量差、直线的两个端点分量差、直线的两个端点分量差 x x、y y有关，有关，有关，有关，只用整数相加和乘只用整数相加和乘只用整数相加和乘只用整数相加和乘2 2运算，没有四舍五运算，没有四舍五运算，没有四舍五运算，没有四舍五 入处理，而乘入处理，而乘入处理，而乘入处理，而乘2 2可利用左移一位来实现可利用左移一位来实现可利用左移一位来实现可利用左移一位来实现因此该算法速度快且易于硬件实现因此该算法速度快且易于硬件实现因此该算法速度快且易于硬件实现因此该算法速度快且易于硬件实现1515 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法描述画线算法描述若直线斜率若直线斜率若直线斜率若直线斜率k k 0,10,1且且且且x2x1x2x1的情况（的情况（的情况（的情况（1a1a象限）象限）象限）象限）1 1、输入两端点、输入两端点、输入两端点、输入两端点(x1,y1),(x2,y2)(x1,y1),(x2,y2)，并以第一点作为起，并以第一点作为起，并以第一点作为起，并以第一点作为起始点始点始点始点 2 2、分别计算、分别计算、分别计算、分别计算 x=x2-x1;x=x2-x1;y=y2-y1y=y2-y1；计算误差初值计算误差初值计算误差初值计算误差初值p p1 1=2=2 y-y-x x；i=1i=1；3 3、求直线的下一点位置：、求直线的下一点位置：、求直线的下一点位置：、求直线的下一点位置：x xi+1i+1=x=xi i+1+1；if pif pi i 0 0 则则则则 y yi+1i+1=y=yi i+1+1；否则否则否则否则 y yi+1i+1=y=yi i；1616 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法描述画线算法描述若直线斜率若直线斜率若直线斜率若直线斜率k k 0,10,1且且且且x2x1x2x1的情况（的情况（的情况（的情况（1a1a象限）象限）象限）象限）4、画点画点（xi+1,yi+1）；5、求下一个误差、求下一个误差pi+1；if pi 0 则则 pi+1=pi+2y-2x；否则否则 pi+1=pi+2y；6、i=i+1；if ix+1则转则转3；否则；否则end1717 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法画线算法现在讨论如何让该算法实现任何方向线段的绘制现在讨论如何让该算法实现任何方向线段的绘制现在讨论如何让该算法实现任何方向线段的绘制现在讨论如何让该算法实现任何方向线段的绘制如图所示，线段的方向可分为如图所示，线段的方向可分为如图所示，线段的方向可分为如图所示，线段的方向可分为8 8种，从原点出发射向种，从原点出发射向种，从原点出发射向种，从原点出发射向8 8个区个区个区个区当直线斜率的绝对值大于当直线斜率的绝对值大于当直线斜率的绝对值大于当直线斜率的绝对值大于1 1时，时，时，时，让让让让y y坐标每次增加坐标每次增加坐标每次增加坐标每次增加1 1，再用，再用，再用，再用 BresenhamBresenham的误差判别式确定的误差判别式确定的误差判别式确定的误差判别式确定 x x坐标是否需要增加坐标是否需要增加坐标是否需要增加坐标是否需要增加1 1。1818 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法画线算法 如果能充分利用如果能充分利用如果能充分利用如果能充分利用x xy y 平面各种八分和四分区域间的平面各种八分和四分区域间的平面各种八分和四分区域间的平面各种八分和四分区域间的对称性就可减少运算量。对称性就可减少运算量。对称性就可减少运算量。对称性就可减少运算量。象限象限取取值值1a、2ayi+1=yi 或 yi+13a、4ayi+1=yi 或 yi-11b、2bxi+1=xi 或 xi+13b、4bxi+1=xi 或 xi-11919 图形软件图形软件 Bresenham画线算法画线算法Bresenham画线算法（画线算法（FLASH演示演示）例例:分析从分析从(0,0)(0,0)到到(5,2)(5,2)的直线段的直线段原始直线Bresenham画出直线2020 图形软件图形软件 圆的生成算法给出圆心坐标(xc,yc)和半径r，逐点画出一个圆周的公式有下列两种：1.直角坐标法由上式导出：直角坐标法直角坐标法当当x x x xc c从从 r r到到r r作加作加1 1递增时，就可以求出对应的递增时，就可以求出对应的圆周点的圆周点的y y坐标坐标 但但由于有乘方和平方根运算，且都是浮点运算，由于有乘方和平方根运算，且都是浮点运算，算法效率不高。算法效率不高。同时同时，这样求出的圆周上的点是不均匀的，这样求出的圆周上的点是不均匀的 x x x xc c 接接近近R R时，由于圆的斜率趋向于无穷大，使得圆周上时，由于圆的斜率趋向于无穷大，使得圆周上有较大的间隙有较大的间隙2121 图形软件图形软件 圆的生成算法2222 图形软件图形软件 圆的生成算法 极坐标法极坐标法假设假设圆周上一点圆周上一点(x,y)(x,y)处的半径与处的半径与x x轴的夹角为轴的夹角为,则圆的极坐标方程为：则圆的极坐标方程为：x x x x=x x x xc c c c+r r r r cos cos cos cos y y y y=y y y yc c c c+r r r r sin sin sin sin 利用利用利用利用圆周上点的对称性，我们可求出圆圆周上点的对称性，我们可求出圆圆周上点的对称性，我们可求出圆圆周上点的对称性，我们可求出圆上各点，此时自变量上各点，此时自变量上各点，此时自变量上各点，此时自变量的取值范围是的取值范围是的取值范围是的取值范围是0,450,450,450,45度，以固定角度为步长来变化，可得到沿圆度，以固定角度为步长来变化，可得到沿圆度，以固定角度为步长来变化，可得到沿圆度，以固定角度为步长来变化，可得到沿圆周等距离分布的一系列光点，但运算量大，周等距离分布的一系列光点，但运算量大，周等距离分布的一系列光点，但运算量大，周等距离分布的一系列光点，但运算量大，也不被采用。也不被采用。也不被采用。也不被采用。A AB B极坐标法对称性极坐标法对称性（x,y）（y,x）（y,-x）（x,-y）（-x,y）（-y,x）（-y,-x）（-x,-y）452323 图形软件图形软件 圆的生成算法BresenhamBresenham画圆算法画圆算法与与与与BresenhamBresenham直线生成算法一样，其直线生成算法一样，其直线生成算法一样，其直线生成算法一样，其基本思想基本思想基本思想基本思想：利：利：利：利用判别变量来判断选择最近的像素，判别变量仅用用判别变量来判断选择最近的像素，判别变量仅用用判别变量来判断选择最近的像素，判别变量仅用用判别变量来判断选择最近的像素，判别变量仅用加减和移位就可计算出来加减和移位就可计算出来加减和移位就可计算出来加减和移位就可计算出来 为讨论方便，仅考虑圆心在原点，半径为为讨论方便，仅考虑圆心在原点，半径为为讨论方便，仅考虑圆心在原点，半径为为讨论方便，仅考虑圆心在原点，半径为R R的第一象的第一象的第一象的第一象限上的一段圆弧限上的一段圆弧限上的一段圆弧限上的一段圆弧取（取（取（取（0 0，R R）为起点，按顺时针方向）为起点，按顺时针方向）为起点，按顺时针方向）为起点，按顺时针方向绘制该绘制该绘制该绘制该1/1/4 4圆弧圆弧圆弧圆弧2424BresenhamBresenhamBresenhamBresenham画圆算法画圆算法画圆算法画圆算法如图所示，从当前点亮如图所示，从当前点亮如图所示，从当前点亮如图所示，从当前点亮像素像素像素像素出出出出发，按顺时针方向生成圆时，发，按顺时针方向生成圆时，发，按顺时针方向生成圆时，发，按顺时针方向生成圆时，最佳逼近该圆的下一个最佳逼近该圆的下一个最佳逼近该圆的下一个最佳逼近该圆的下一个像素像素像素像素只只只只可能为可能为可能为可能为H H、D D、V V三三三三像素像素像素像素之一之一之一之一。H H、D D、V V中距圆周边界距中距圆周边界距中距圆周边界距中距圆周边界距离最小者，即为所求的离最小者，即为所求的离最小者，即为所求的离最小者，即为所求的像素像素像素像素点点点点。图形软件图形软件 圆的生成算法2525BresenhamBresenham画圆算法画圆算法H H、D D、V V三点到圆心的距离平方与圆的半径平方差，即为三点到圆心的距离平方与圆的半径平方差，即为三点到圆心的距离平方与圆的半径平方差，即为三点到圆心的距离平方与圆的半径平方差，即为H H、D D、V V到圆弧距离的一种度量：到圆弧距离的一种度量：到圆弧距离的一种度量：到圆弧距离的一种度量：H H=(x+1)=(x+1)2 2+y+y2 2-R-R2 2；D D=(x+1)=(x+1)2 2+(y-1)+(y-1)2 2-R-R2 2；V V=x=x2 2+(y-1)+(y-1)2 2-R-R2 2；为了根据这些度量值可确定最佳为了根据这些度量值可确定最佳为了根据这些度量值可确定最佳为了根据这些度量值可确定最佳像素点，首先，将像素点，首先，将像素点，首先，将像素点，首先，将H H、D D、V V与理与理与理与理想圆弧的关系进行分类想圆弧的关系进行分类想圆弧的关系进行分类想圆弧的关系进行分类 图形软件 圆的生成算法2626BresenhamBresenham画圆算法画圆算法如图如图存在以下五种情况：存在以下五种情况：存在以下五种情况：存在以下五种情况：1 1）H H、D D、V V全在圆内全在圆内全在圆内全在圆内2 2）H H在圆外在圆外在圆外在圆外，D D、V V在圆内在圆内在圆内在圆内3 3）D D在圆上在圆上在圆上在圆上，H H在圆外在圆外在圆外在圆外，V V在圆内在圆内在圆内在圆内4 4）H H、D D在圆外在圆外在圆外在圆外，V V在圆内在圆内在圆内在圆内5 5）H H、D D、V V全在圆外全在圆外全在圆外全在圆外 图形软件图形软件 圆的生成算法圆的生成算法HDV(x,y)123452727Bresenham画圆算法画圆算法 与与与与BresenhamBresenham画线算法一样，按照上述画线算法一样，按照上述画线算法一样，按照上述画线算法一样，按照上述不同类型，找出误差度量的递推公式，然后不同类型，找出误差度量的递推公式，然后不同类型，找出误差度量的递推公式，然后不同类型，找出误差度量的递推公式，然后判别它的正、负性即可确定最佳逼近的像素判别它的正、负性即可确定最佳逼近的像素判别它的正、负性即可确定最佳逼近的像素判别它的正、负性即可确定最佳逼近的像素点点点点 当当当当 D D 0 0 0，DD 0 0+2y-1 0，否则否则否则否则2 2 DD+2y-1 +2y-1 0 0。对于第对于第对于第对于第1 1种情况：种情况：种情况：种情况：y y是是是是x x的单调递减函数的单调递减函数的单调递减函数的单调递减函数 HH为下一点亮像素。为下一点亮像素。为下一点亮像素。为下一点亮像素。另，此时另，此时另，此时另，此时 HH 0 0 和和和和 DD 0 0 HH +D D =2=2 DD+2+2y y-1 0 -1 0 综上两种情况可得如下结论：综上两种情况可得如下结论：综上两种情况可得如下结论：综上两种情况可得如下结论：在在在在 DD 0 0时，若时，若时，若时，若2 2（D D+y)-1 0+y)-1 0，则取，则取，则取，则取HH，否则取，否则取，否则取，否则取DD 图形软件图形软件 圆的生成算法圆的生成算法2929BresenhamBresenhamBresenhamBresenham画圆算法画圆算法画圆算法画圆算法当当当当 D D 0,0,只可能有只可能有只可能有只可能有4 4、5 5两种情况。两种情况。两种情况。两种情况。且最佳像素点为且最佳像素点为且最佳像素点为且最佳像素点为D D或或或或V V，可用如下判别式：，可用如下判别式：，可用如下判别式：，可用如下判别式：DV DV=|=|DD|-|-|V V|当当当当 DV DV 0 0 则应选则应选则应选则应选D D，否则选，否则选，否则选，否则选V V。对于第对于第对于第对于第4 4种情况：种情况：种情况：种情况：DV DV=DD+V V （DD 0 0，V V 0 0）=(x+1)(x+1)2 2+(y-1)+(y-1)2 2-R-R2 2 +(x)+(x)2 2+(y-1)+(y-1)2 2-R-R2 2 =2(=2(DD-x)1-x)1 若若若若2(2(DD-x)1-x)1 0 0，则选，则选，则选，则选V V，否则选，否则选，否则选，否则选D D。图形软件图形软件 圆的生成算法圆的生成算法3030 BresenhamBresenham画圆算法画圆算法对于第对于第对于第对于第5 5种情况：种情况：种情况：种情况：D D，V V都在圆外，显然都在圆外，显然都在圆外，显然都在圆外，显然V V为所选为所选为所选为所选像素像素像素像素。注意：注意：注意：注意：D D 0 0，V V0 0 DD+V V=2(2(DD-x)-1 -x)-1 0 0 综上两种情况可得如下结论：综上两种情况可得如下结论：综上两种情况可得如下结论：综上两种情况可得如下结论：在在在在 DD 0 0时，若时，若时，若时，若2 2（D D-x)-1 0-x)-1 0，则取，则取，则取，则取D D，否则取，否则取，否则取，否则取V V 当当当当 D D =0 =0 此时此时此时此时D D是最佳像素是最佳像素是最佳像素是最佳像素 图形软件图形软件 圆的生成算法圆的生成算法Bresenham画圆算法画圆算法总结上述分析结果：总结上述分析结果：总结上述分析结果：总结上述分析结果：当当 D D 0 0，若，若，若，若 2(2(D D-x)-1 -x)-1 0 0，取，取D D，否则取，否则取V V 当当 D D 0 0，若，若，若，若 2 2(D D+y)-1 0+y)-1 0，取，取H H，否则取，否则取D D 当当 D D =0=0，取，取，取，取D D关键的问题就是计算关键的问题就是计算关键的问题就是计算关键的问题就是计算 DD D D=(x+1)=(x+1)2 2+(y-1)+(y-1)2 2-R-R2 2；采用增量法，获得采用增量法，获得采用增量法，获得采用增量法，获得 DD的计算公式的计算公式的计算公式的计算公式 图形软件图形软件 圆的生成算法圆的生成算法3232Bresenham画圆算法画圆算法分三种情况：分三种情况：分三种情况：分三种情况：下一像素为下一像素为下一像素为下一像素为HH时时时时 H=(xH=(x,y,y)=(x+1,y)=(x+1,y)D Dk+1k+1=(x+1)+1)=(x+1)+1)2 2+(y-1)+(y-1)2 2-R-R2 2 =(x+1)=(x+1)2 2+(y-1)+(y-1)2 2-R-R2 2+2(x+1)+1+2(x+1)+1 =D D k k+2(x+1)+1+2(x+1)+1 图形软件图形软件 圆的生成算法圆的生成算法3333Bresenham画圆算法画圆算法下一像素为下一像素为下一像素为下一像素为D D时时时时 D=(x D=(x,y,y)=(x+1,y-1)=(x+1,y-1)D Dk+1k+1=(x+1)+1)=(x+1)+1)2 2+(y-1)-1)(y-1)-1)2 2-R-R2 2=(x+1)=(x+1)2 2+(y-1)+(y-1)2 2-R-R2 2+2(x+1)-2(y-1)+1+2(x+1)-2(y-1)+1=D D k k+2(x+1)-2(y-1)+2+2(x+1)-2(y-1)+2 图形软件图形软件 圆的生成算法圆的生成算法3434Bresenham画圆算法画圆算法下一像素为下一像素为下一像素为下一像素为V V时时时时 V=(xV=(x,y,y)=(x,y-1)=(x,y-1)D Dk+1k+1=(x+1)=(x+1)2 2+(y-1)-1)+(y-1)-1)2 2-R-R2 2 =(x+1)=(x+1)2 2+(y-1)+(y-1)2 2-R-R2 2-2(y-1)+1-2(y-1)+1 =D D k k-2(y-1)+1-2(y-1)+1 图形软件图形软件 圆的生成算法圆的生成算法3535Bresenham画圆算法画圆算法有了上述有了上述有了上述有了上述 DD的递推计算公式，还需计算出的递推计算公式，还需计算出的递推计算公式，还需计算出的递推计算公式，还需计算出 DD的初值的初值的初值的初值 圆弧的起点为（圆弧的起点为（圆弧的起点为（圆弧的起点为（0 0，R R）DD的初值为：的初值为：的初值为：的初值为：D D=(0+1)=(0+1)2 2+(R-1)+(R-1)2 2-R-R2 2 =2(1-R)=2(1-R)图形软件图形软件 圆的生成算法圆的生成算法3636 图形软件图形软件 圆的生成算法中点画圆算法中点画圆算法与与与与BresenhamBresenham画圆算法一样，以单位间隔取样并在画圆算法一样，以单位间隔取样并在画圆算法一样，以单位间隔取样并在画圆算法一样，以单位间隔取样并在每个步长中确定离指定圆最近的像素位置每个步长中确定离指定圆最近的像素位置每个步长中确定离指定圆最近的像素位置每个步长中确定离指定圆最近的像素位置对于给定半径对于给定半径对于给定半径对于给定半径r r和圆心（和圆心（和圆心（和圆心（x xc c，y yc c），可先给出计算中心），可先给出计算中心），可先给出计算中心），可先给出计算中心在原点（在原点（在原点（在原点（0,00,0）的像素位置的算法，然后通过平移使）的像素位置的算法，然后通过平移使）的像素位置的算法，然后通过平移使）的像素位置的算法，然后通过平移使每个计算出的（每个计算出的（每个计算出的（每个计算出的（x x，y y）移动到其适当的屏幕位置）移动到其适当的屏幕位置）移动到其适当的屏幕位置）移动到其适当的屏幕位置利用圆的对称性，只须讨论利用圆的对称性，只须讨论利用圆的对称性，只须讨论利用圆的对称性，只须讨论1/81/8圆圆圆圆3737 图形软件图形软件 圆的生成算法中点画圆算法中点画圆算法为了应用中点圆算法，定义一个圆函数：为了应用中点圆算法，定义一个圆函数：为了应用中点圆算法，定义一个圆函数：为了应用中点圆算法，定义一个圆函数：f fcirclecircle(x,y)=x(x,y)=x2 2+y+y2 2-r-r2 2则任何点则任何点则任何点则任何点(x,y)(x,y)的相对位置可由对圆函数符合的检测的相对位置可由对圆函数符合的检测的相对位置可由对圆函数符合的检测的相对位置可由对圆函数符合的检测来决定来决定来决定来决定 :0 (x,y)0 (x,y)0 (x,y)位于圆边界外位于圆边界外位于圆边界外位于圆边界外3838 图形软件图形软件 圆的生成算法中点画圆算法中点画圆算法假设用该算法计算出第假设用该算法计算出第假设用该算法计算出第假设用该算法计算出第k k个点个点个点个点P P(x(xk k,y,yk k)，下一步需要决，下一步需要决，下一步需要决，下一步需要决定像素位置是定像素位置是定像素位置是定像素位置是A(xA(xk+1k+1,y,yk k)，B(xB(xk+1k+1,y,yk k-1)-1)其中其中其中其中x xk+1k+1=x=xk k+1+1A A，B B的中点的中点的中点的中点 M(xM(xk+1k+1,y,yk k-0.5)-0.5)MABP（Xk，Yk）3939 图形软件图形软件 圆的生成算法中点画圆算法中点画圆算法中点画圆算法中点画圆算法在在在在MM处决策参数：处决策参数：处决策参数：处决策参数：p pk k=f=fcirclecircle(x(xk+1k+1,y,yk k-0.5)=x-0.5)=xk+1k+12 2+(y+(yk k-0.5)-0.5)2 2-r-r2 2则则则则:当当当当p pk k 0 0，这个中点，这个中点，这个中点，这个中点MM在圆内，扫描线在圆内，扫描线在圆内，扫描线在圆内，扫描线y yk k上的像素上的像素上的像素上的像素(x(xk+1k+1,y,yk k)更接近于圆边界，则下一点应取右边的点更接近于圆边界，则下一点应取右边的点更接近于圆边界，则下一点应取右边的点更接近于圆边界，则下一点应取右边的点A(xA(xk+1k+1,y,yk k)否则，中点否则，中点否则，中点否则，中点MM位于圆外或在边界上，我们选择扫描线位于圆外或在边界上，我们选择扫描线位于圆外或在边界上，我们选择扫描线位于圆外或在边界上，我们选择扫描线y yk k-1-1上的上的上的上的像素像素像素像素B(xB(xk+1k+1,y,yk k-1)-1)p pk+1k+1=(x=(xk+1k+1+1)+1)2 2+(y+(yk+1k+1-0.5)-0.5)2 2-r-r2 23939MABP（Xk，Yk）4040 图形软件图形软件 圆的生成算法中点画圆算法中点画圆算法递归表达式：递归表达式：递归表达式：递归表达式：p pk+1k+1=p=pk k+2x+2xk+1k+1+(y+(y2 2k+1k+1-y-y2 2k k)-(y)-(yk+1k+1-y-yk k)+1)+1 其中其中其中其中:y yk+1k+1是是是是y yk k(p(pk k 0)0)或是或是或是或是y yk k-1(p-1(pk k 0)0)，这取决于，这取决于，这取决于，这取决于p pk k的符号的符号的符号的符号圆在起始位置圆在起始位置圆在起始位置圆在起始位置(x(x0 0,y,y0 0)=(0,r)=(0,r)处求值就可得到初始决策处求值就可得到初始决策处求值就可得到初始决策处求值就可得到初始决策参数：参数：参数：参数：p p0 0=f=fcirclecircle(1,r-0.5)=5/4(1,r-0.5)=5/4 r r4141 图形软件图形软件 圆的生成算法中点画圆算法中点画圆算法中点圆算法的算法表示：中点圆算法的算法表示：p0=5/4 r xk+1=xk+1 yk+1=yk，pk+1=pk+2xk+1+1 当pk0 yk+1=yk-1，pk+1=pk+2xk+1+1-2yk+1 当pk04141MABP（Xk，Yk）4242 图形软件图形软件 圆的生成算法中点画圆算法中点画圆算法对于对于2xk+1和和2yk+1本身又是一个增量表达式本身又是一个增量表达式2xk+1增量始终为增量始终为2而而2yk+1增量为增量为0(当当pk0)或或-2(当当pk0)，在起始位置在起始位置(x0,y0)=(0,r)，2xk+1和和2yk+1的初始的初始值分别为值分别为0和和2r4343 图形软件图形软件 圆的生成算法中点画圆算法步骤中点画圆算法步骤 1.1.输入圆半径输入圆半径输入圆半径输入圆半径r r和圆心和圆心和圆心和圆心(x(xc c,y,yc c),),并得到圆心在原点的圆周上的第并得到圆心在原点的圆周上的第并得到圆心在原点的圆周上的第并得到圆心在原点的圆周上的第一点为一点为一点为一点为:(x:(x0 0,y,y0 0)=(0,r)=(0,r)2.2.计算决策参数的初始值：计算决策参数的初始值：计算决策参数的初始值：计算决策参数的初始值：p p0 0=5/4=5/4 r r 3.3.在每个在每个在每个在每个x xk k位置处，从位置处，从位置处，从位置处，从k=0k=0开始，完成下列检测：开始，完成下列检测：开始，完成下列检测：开始，完成下列检测：假如假如假如假如p pk k 0 0，中心在，中心在，中心在，中心在(0,0)(0,0)的圆的下一个点为的圆的下一个点为的圆的下一个点为的圆的下一个点为(x(xk+1k+1,y,yk k)，且，且，且，且 p pk+1k+1=p=pk k+2x+2xk+1k+1+1+1否则，圆的下一个点为否则，圆的下一个点为否则，圆的下一个点为否则，圆的下一个点为(x(xk+1k+1,y,yk k-1)-1)，且，且，且，且 p pk+1k+1=p=pk k+2x+2xk+1k+1+1-2y+1-2yk+1k+1其中：其中：其中：其中：2x2xk+1k+1=2x=2xk k+1+1，2y2yk+1k+1=2y=2yk k-2-2 4444 图形软件图形软件 圆的生成算法中点画圆算法中点画圆算法(FLASHFLASH演示演示）4.4.确定在其它确定在其它确定在其它确定在其它7 7个个个个8 8分圆中的对称点分圆中的对称点分圆中的对称点分圆中的对称点 5.5.将每个计算出的像素位置将每个计算出的像素位置将每个计算出的像素位置将每个计算出的像素位置(x,y)(x,y)移动到中心在移动到中心在移动