直线、圆、椭圆的生成省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件

第三章直线、圆、椭圆生成算法图形扫描转换（光栅化）：确定一个像素集合，用于显示一个图形过程。步骤以下：1、确定相关像素2、用图形颜色或其它属性，对像素进行写操作。对一维图形，不考虑线宽，则用一个像素宽直线来显示图形。二维图形光栅化，即区域填充：确定像素集，填色或图案。任何图形光栅化，必须显示在一个窗口内，不然不予显示。即确定一个图形哪些部分在窗口内，哪些在窗口外，即裁剪。 1/899/12/20231西安工程大学计算机图形学图形显示前需要：扫描转换+裁剪●裁剪---〉扫描转换：最惯用，节约计算时间。●扫描转换---〉裁剪：算法简单；2/899/12/20232西安工程大学计算机图形学本章内容扫描转换直线段

DDA算法中点画线法Bresenham画线算法圆弧、椭圆弧扫描转换

中点算法内接正多边形迫近法等面积正多边形迫近法生成圆弧正负法

3/899/12/20233西安工程大学计算机图形学

在数学上，理想直线是没有宽度，是由无数个在它上面点组成集合。直线能够向一个方向及其相反方向无限延长。在图形学中研究对象是直线段，它是一条含有一个Pixel或多个Pixel宽直线段。图形显示器是由一个个排列有序像素组成，划分像素点越多分辨率就越高。比如640X480显示器，分成640X480个网格，网格单元视为像素，一条线段就是由一些连续可见像素所组成，以下列图所表示：直线段扫描转换算法4/899/12/20234西安工程大学计算机图形学由上图可知：画一条直线实际上就是依据一系列计算出来并与该直线靠近像素绘制。Line:P0(0,0)——P1(5,2)0143215234各行各列像素中心组成一组虚拟网格线像素单元5/899/12/20235西安工程大学计算机图形学直线扫描转换:确定最正确迫近于该直线一组象素，而且按扫描线次序，对这些象素进行写操作。直线段是最基本图形，所以直线段生成质量好坏与速度快慢将直接影响整个图形生成质量和速度。三个惯用算法：数值微分法（DDA）中点画线法Bresenham算法。6/899/12/20236西安工程大学计算机图形学数值微分法（ＤＤＡ）

假定直线起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。

栅格交点表示象素点位置(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)。。。。7/899/12/20237西安工程大学计算机图形学数值微分(DDA)法基本思想已知过端点P0(x0,y0),P1(x1,y1)直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。

8/899/12/20238西安工程大学计算机图形学数值微分(DDA)法计算yi+1=kxi+1+b

=kxi+b+k

x =yi+k

x

当

x=1;

yi+1=

yi+k

即：当x每递增1，y递增k(即直线斜率)；注意上述分析算法仅适合用于

k

≤1情形。在这种情况下，x每增加1,y最多增加1。9/899/12/20239西安工程大学计算机图形学注：当时，必须把x,y位置交换，即利用递推式，y每增加1，x对应增加。所以取和中较大者为步进方向，以下列图自然明白。，，x为步进方向y为步进方向10/899/12/202310西安工程大学计算机图形学数值微分(DDA)法增量算法：在一个迭代算法中，假如每一步x、y值是用前一步值加上一个增量来取得，则称为增量算法。DDA算法就是一个增量算法。11/899/12/202311西安工程大学计算机图形学数值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)

intx； floatdx,dy,y,k; dx,=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;x

x1,x++)

drawpixel(x,int(y+0.5),color); y=y+k;

12/899/12/202312西安工程大学计算机图形学数值微分(DDA)法例：画直线段P0(0,0)--P1(5,2)xint(y+0.5) y+0.50 0 0+0.51 0 0.4+0.52 1 0.8+0.5 3 1 1.2+0.54 2 1.6+0.55 2 2.0+0.5012345321Line:P0(0,0)--P1(5,2)13/899/12/202313西安工程大学计算机图形学数值微分(DDA)法该算法优点是绘制实数直线效果好，误差小。缺点是实现较复杂，不利于硬件实现。该算法包括到实数乘除法运算，y与k必须用浮点数表示，而且每一步都要对y进行四舍五入后取整。14/899/12/202314西安工程大学计算机图形学中点画线法原理：假定直线斜率0<K<1，且已确定点亮象素点P（Xp

,Yp

）,则下一个与直线最靠近像素只能是P1点或P2点。设M为中点，Q为交点现需确定下一个点亮象素。P=(xp,yp)QP2P115/899/12/202315西安工程大学计算机图形学中点画线法当M在Q下方->P2离直线更近更近->取P2。M在Q上方->P1离直线更近更近->取P1M与Q重合，P1、P2任取一点。问题：怎样判断M与Q点关系？P=(xp,yp)QP2P1M16/899/12/202316西安工程大学计算机图形学中点画线法假设直线方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知：∴欲判断中点M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检验它符号。P=(xp,yp)QP2P1M17/899/12/202317西安工程大学计算机图形学中点画线法结构判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d<0，M在直线(Q点)下方，取右上方P2；当d>0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采取增量算法呢？P=(xp,yp)QP2P118/899/12/202318西安工程大学计算机图形学中点画线法若d

0->M在直线上方->取P1;此时再下一个象素判别式为d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a；增量为aP=(xp,yp)QP2P119/899/12/202319西安工程大学计算机图形学中点画线法若d<0->M在直线下方->取P2;此时再下一个象素判别式为d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b；增量为a＋bP=(xp,yp)QP2P120/899/12/202320西安工程大学计算机图形学中点画线法画线从(x0,y0)开始，d初值 d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b因为只用d符号作判断，为了只包含整数运算,能够用2d代替d来摆脱小数，提升效率。21/899/12/202321西安工程大学计算机图形学中点画线法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x<x1){if(d<0){x++;y++;d+=d2;}else{x++;d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/22/899/12/202322西安工程大学计算机图形学中点画线法例：用中点画线法P0(0,0)P1(5,2)a=y0-y1=-2b=x1-x0=5d0=2a+b=1d1=2a=-4d2=2(a+b)=6i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5

01234532123/899/12/202323西安工程大学计算机图形学本算法由Bresenham在1965年提出，Bresenham算法是计算机图形学领域使用最广泛直线扫描转换算法。该方法类似于中点法，由误差项符号决定下一个象素取右边点还是右上点。算法原理：过各行各列象素中心结构一组虚拟网格线。按直线从起点到终点次序计算直线与各垂直网格线交点，然后确定该列象素中与此交点最近象素。该算法巧妙之处于于采取增量计算，使得对于每一列，只要检验一个误差项符号，就能够确定该列所求象素。

}dy}dx}d直线Bresenham算法

24/899/12/202324西安工程大学计算机图形学1.Bresenham算法实现为了讨论方便，我们先以第一个八分圆直线为例，即假定直线斜率在0~1之间，其它情况类似处理。如右图-1所表示，设直线方程为其中k=dy/dx。

假设x列象素已经确定为xi，其行坐标为yi。那么下一个象素列坐标为xi＋1，而行坐标要么不变为yi，要么递增1为yi＋1。

}dy}d}d

x}d图-125/899/12/202325西安工程大学计算机图形学是否增1取决于如图所表示误差项d值。因为直线起始点在象素中心，所以误差项d初值d0＝0

因为X下标每增加1，d值对应递增直线斜率值k，即d＝d＋k。一旦d≥1，就把它减去1，这么确保d在0、1之间。

1.

当d≥0.5时，直线与xi＋1列垂直网格交点最靠近于当前象素（xi，yi）右上方象素（xi+1，yi＋1）；2.

当d<0.5时，更靠近于正右方象素（xi＋1，yi）。

图-1

Bresenham算法误差项几何含义}dy}d}d

x}d26/899/12/202326西安工程大学计算机图形学为方便计算，令e＝d－0.5，e初值为－0.5，增量为k。1.当e≥0时，取当前象素（xi，yi）右上方象素点（xi＋1，yi＋1）；结论：1.

d初值d0＝0，d＝d＋k；2.当d≥0.5时，下一个像素取为右上方象素（xi+1，yi＋1）；3.当d<0.5时，下一个像素取为正右方象素（xi＋1，yi）。

2.当e<0时，更靠近于正右方象素点（xi＋1，yi）。

图-1

Bresenham算法误差项几何含义}dy}d}d

x}d27/899/12/202327西安工程大学计算机图形学Bresenham画线算法参考程序(0<k<1)：voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,i;floatdx,dy,k,e;dx=x1-x0,dy=y1-y0,k=dy/dx;e=-0.5,x=x0,y=y0;

for(i=0;i<=dx;i++)

{putpixel(x,y,color);

x=x+1，e=e+k;

if(e>=0){y++,e=e-1;}

}}因为一旦d≥1，就减去1，一样一旦e≥0，也减去1。28/899/12/202328西安工程大学计算机图形学

举例1:用Bresenham方法扫描转换连接两点P0（0,0）和P1（5,2）直线段。0.5-0.552-0.90.142-0.3-0.331-0.70.321-0.1-0.110-0.5-0.500

e判断前判断后

xy斜率K=2/5=0.4e0=-0.5e=d-0.5,d=d+k,k=dy/dx当e≥0时，取当前像素右上方像素为下一个像素当e<0时，取当前像素正右方像素为下一个像素0143215234Line:P0(0,0)—P1(5,2)29/899/12/202329西安工程大学计算机图形学

举例2：用Bresenham方法扫描转换连接从点P0（0,0）到Pi（ix100,100）(i=1,2,3,4,5)直线段。程序：

#include"graphics.h"#include"stdio.h"#include"conio.h"main(){intBresenham_line();intgdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"D:\\TC");Bresenham_line(0,0,100,100,4);Bresenham_line(0,0,200,100,4);Bresenham_line(0,0,300,100,4);30/899/12/202330西安工程大学计算机图形学Bresenham_line(0,0,400,100,4);Bresenham_line(0,0,500,100,4);getch();closegraph();}Bresenham_line(intx0,inty0,intx1,inty1,intcolor){intx,i,y;floatdx,dy,k,e;dx=x1-x0;dy=y1-y0;31/899/12/202331西安工程大学计算机图形学

k=dy/dx;e=-0.5;x=x0;y=y0;for(i=0;i<=dx;i++){putpixel(x,y,color);x=x+1;e=e+k;if(e>=0){y=y+1;e=e-1;}}}运行效果图32/899/12/202332西安工程大学计算机图形学voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy,e0;dx=x1-x0;dy=y1-y0;

e0=-dx;

x=x0;y=y0;

e=-0.5；e0=-dx上述bresenham算法在计算误差项与直线斜率时用到小数与除法。能够改用整数以防止去法。因为算法中只用到误差项符号，所以可作以下替换：

4.改进Bresenham画线算法程序：33/899/12/202333西安工程大学计算机图形学Bresenham算法优点是：1、无须计算直线之斜率，所以不做除法；2、不用浮点数，只用整数；3、只做整数加减法和乘2运算，而乘2运算能够用硬件移位实现。Bresenham算法速度很快，并适于用硬件实现。for(i=0;i<=dx;i++)

{putpixel(x,y,color);

x++;e0=e0+2*dy;

if(e0>=0){y++;e0=e0-2*dx;}

}}说明：1.因为e0=2*e*dx且e=e+k,2*e*dx=2*e*dx+2*dx*k所以e0=e0+2*dy；2.同理有e=e-1改为:e0=e0-2*dx34/899/12/202334西安工程大学计算机图形学(1)上述算法只对斜率在0~1之间直线段生成适合，当直线斜率大于1时，算法应该怎样改进?

图-1屏幕坐标系，逆时针旋转90度MaxxMaxy(0,0)(50,20)图-2直角坐标系MaxyMaxx(0,0)(50,20)}d

}d

}d

}d

注意：此时d或e增量为5.几点讨论和思索35/899/12/202335西安工程大学计算机图形学for(i=0;i<=dy;i++){putpixel(x,y,color);y=y+1;e=e+k1;if(e>=0){x=x+1;e=e-1;}}}(2)Bresenham画线算法参考程序(k>1)：Bresenham_line(intx0,inty0,intx1,inty1,intcolor){intx,i,y;floatdx,dy,k,k1,e;dx=x1-x0;dy=y1-y0;k=dy/dx;k1=1/k;e=-0.5;x=x0;y=y0;36/899/12/202336西安工程大学计算机图形学

举例：用Bresenham方法扫描转换连接从点P0（0,0）到Pi（100,ix100）(i=1,2,3,4,5)直线段。直线斜率K>1运行效果图37/899/12/202337西安工程大学计算机图形学(3)依据上述思想，我们怎样将算法扩展到，任一八分圆坐标空间图，从而形成普通Bresenham算法？以下列图：普通Bresenham算法判别条件x=x+1y=y+1x=x+1y=y-1x=x-1y=y-1x=x-1y=y+1y增1y增1y减1y减1x增1x增1x减1x减1x1,y138/899/12/202338西安工程大学计算机图形学(4)适合用于全部八个方向Bresenham直线生成算法#include"graphics.h"#include"stdio.h"#include"conio.h"main(){intbresenham_line();intgdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"D:\\TC");bresenham_line(0,0,100,300,4);getch();closegraph();}39/899/12/202339西安工程大学计算机图形学bresenham_line(x1,y1,x2,y2,c)intx1,y1,x2,y2,c;{intdx,dy;intx,y,p;intconst1,const2;intinc;inttmp;dx=x2-x1;dy=y2-y1;if(dx*dy>=0)/*准备x或y单位递变值。*/inc=1;elseinc=-1;40/899/12/202340西安工程大学计算机图形学if(abs(dx)>abs(dy)){if(dx<0){tmp=x1;/*将2a,3a象限方向*/x1=x2;/*直线变换到1a,4a*/x2=tmp;tmp=y1;/*象限方向去*/y1=y2;dx=-dy;dy=-dy;}p=2*dy-dx;const1=2*dy;/*注意此时误差*/const2=2*(dy-dy);/*改变参数取值.*/41/899/12/202341西安工程大学计算机图形学x=x1;y=y1;putpixel(x,y,c);while(x<x2){x++;if(p<0)p+=const1;else{y+=inc;p+=const2;} putpixel(x,y,c);}}42/899/12/202342西安工程大学计算机图形学else{if(dy<0){tmp=x1;/*将3b,4b象限方向*/x1=x2;/*直线变换到2b,1b*/x2=tmp;/*象限方向去.*/tmp=y1;y1=y2;dx=-dy;dy=-dy;}p=2*dx-dy;/*注意此时误差*/const1=2*dx;/*改变参数取值.*/const2=2*(dx-dy);43/899/12/202343西安工程大学计算机图形学x=x1;y=y1;putpixel(x,y,c);while(y<y2){y++;if(p<0)p+=const1;else{x+=inc;p+=const2; putpixel(x,y,c);} }}}44/899/12/202344西安工程大学计算机图形学圆扫描转换算法下面仅以圆心在原点、半径R为整数圆为例，讨论圆生成算法。假设圆方程为：X2+Y2=R245/899/12/202345西安工程大学计算机图形学圆弧扫描算法X2+Y2=R2Y=Sqrt(R2-X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须取整。缺点：浮点运算，开方，取整，不均匀。yx46/899/12/202346西安工程大学计算机图形学角度DDA法x=x0+Rcosy=y0+Rsindx=-Rsinddy=Rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn+dx=xn-Rsind=xn-(yn-y0)d

yn+1=yn+dy=yn+Rcosd=yn+(xn-x0)d

显然，确定x,y初值及d

值后，即能够增量方式取得圆周上坐标，然后取整可得象素坐标。但要采取浮点运算、乘法运算、取整运算。47/899/12/202347西安工程大学计算机图形学中点画圆法利用圆对称性，只须讨论1/8圆。第二个8分圆P为当前点亮象素，那么，下一个点亮象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp－1)。MP1P2P（Xp，Yp）48/899/12/202348西安工程大学计算机图形学中点画圆法结构函数：F（X，Y）=X2+Y2-R2；则F（X，Y）=0（X，Y）在圆上；F（X，Y）<0（X，Y）在圆内；F（X，Y）>0（X，Y）在圆外。设M为P1、P2间中点，M=(Xp+1,Yp-0.5)MP1P249/899/12/202349西安工程大学计算机图形学中点画圆法有以下结论：F（M）<0->M在圆内->取P1F（M）>=0->M在圆外->取P2为此，可采取以下判别式：

MP1P250/899/12/202350西安工程大学计算机图形学中点画圆法d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,则P1为下一个象素，那么再下一个象素判别式为：

d1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3即d增量为2xp+3.P1MP251/899/12/202351西安工程大学计算机图形学中点画圆法若d>=0,则P2为下一个象素，那么再下一个象素判别式为：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+（2xp+3）+（-2yp+2）即d增量为2(xp-yp)+5.d初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-RMP1P252/899/12/202352西安工程大学计算机图形学中点画圆法MidpointCircle(intr,intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(x<y){if(d<0){d+=2*x+3;x++}else{d+=2*(x-y)+5;x++;y--;}}}53/899/12/202353西安工程大学计算机图形学中点画圆法为了深入提升算法效率，能够将上面算法中浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用e=d-0.25代替de0=1-R54/899/12/202354西安工程大学计算机图形学中点画圆法上述算法能否再改进呢？注意到d增量是x,y线性函数，每当x递增1，则d增量递增Δx=2每当y递减1，则d增量递增Δy=2Δx初始值=3；Δy初始值=-2r+255/899/12/202355西安工程大学计算机图形学本节介绍另一个惯用画圆算法：Bresenham算法。不失普通性，考虑圆心在原点，半径为R第一4分圆。取（0，R）为起点，按顺时针方向生成圆。以下列图所表示：（0，R）YXOR第一个4分圆3.3.3圆Bresenham算法

56/899/12/202356西安工程大学计算机图形学从这段圆弧任意一点出发，按顺时针方向生成圆时，为了最正确迫近该圆，下一个像素取法只有三种可能选择：正右方像素，右下方像素和正下方像素。分别记为H、D和V。以下列图所表示：（0，R）YXOR第一个4分圆(x,y)H(x+1,y)V(x,y-1)D(x+1,y-1)第一个4分圆下一像素三个候选者57/899/12/202357西安工程大学计算机图形学这三个像素中，与理想圆弧最近者为所求像素。理想圆弧与这三个候选点之间关系只有以下五种情形：1.H、D、V全在圆内；2.H在圆外,D、V在圆内；3.D在圆上,H在圆外,V在圆内;4.H、D、在圆外，V在圆内；5.H、D、V全在圆外； 58/899/12/202358西安工程大学计算机图形学上述三点到圆心距离平方与圆弧上一点到圆心距离平方之差分别为：与Bresenham直线扫描算法一样，在选最正确迫近该圆像素时，我们希望只判别误差项符号。59/899/12/202359西安工程大学计算机图形学情况（一）：假如,那么右下方像素D在圆内，圆弧与候选点关系只可能是1与2情形。则这是最正确迫近圆弧像素只可能是H或D两个像素之一。为了确定H和D哪个更靠近于圆弧,令60/899/12/202360西安工程大学计算机图形学1.

若,则圆到正右方像素H距离小于圆到右下方像素D距离,此时应取H为下一个像素。2.

若,则圆到右下方像素D距离较小,故应取D为下一个像素。3.若,二者均可取，约定取正右方像素H。对于情形2，H总在圆外，D总在圆内，所以所以能够简化为故能够依据符号，在情形2下判断应取H或D61/899/12/202361西安工程大学计算机图形学由上述讨论可知：当时，若，即,则取H不然取D

对于情形1，H、D都在圆内，而在这段圆弧上，y是x单调递减函数，所以只能取H为下一个像素。且这时，所以有

与情形2判别条件一致。可见在情况下，若，则应取H为下一像素，不然应取D为下一像素62/899/12/202362西安工程大学计算机图形学情况（二）：假如,那么右下方像素D在圆外，圆弧与候选点关系只可能是4与5情形。则这是最正确迫近圆弧像素只可能是D或V两个像素之一。为了确定D和V哪个更靠近于圆弧,令63/899/12/202363西安工程大学计算机图形学1当，即时，应取右下方像素D；2当，即时，应取正下方像素V；3当时，二者均可取，我们约定取右下方像素DDVO64/899/12/202364西安工程大学计算机图形学对于情形4，因为D在圆外，V在圆内,所以则能够简化为故能够依据符号，在情形4下判断应取D或V从而时,取D;当时取V先考虑情形465/899/12/202365西安工程大学计算机图形学再考虑情形5对于情形5，D、V都在圆外，显然取V为下一个像素。且此时，所以

可见,在时，当时,取D为下一像素，不然应取V为下一像素。由上述讨论可知：情况（三）：此时D恰好在圆上，故应取D作为下一像素。66/899/12/202366西安工程大学计算机图形学归纳上述3种情况讨论，可得计算下一个像素算法：1当时，若，则取D，不然取V；2当时，若，则取H，不然取D；3当时，取D。

67/899/12/202367西安工程大学计算机图形学下面我们讨论怎样简化计算。与直线扫描算法类似，采取增量算法。1.首先考虑下一个像素为H情况。对于像素H:其坐标为其误差项为68/899/12/202368西安工程大学计算机图形学2.再考虑下一个像素为D情况。其坐标与误差项分别为69/899/12/202369西安工程大学计算机图形学3.当下一个像素为V情况。其坐标与误差项分别为70/899/12/202370西安工程大学计算机图形学Bresenham画圆算法参考程序（0，R）YXOR第一个4分圆Bresenham_Ciecle(intr,intcolor){intx,y,delta,delta1,delta2,direction;x=0;y=r;delta=2*(1-r);

△D初始值while(y>=0){putpixel(x,y,color);if(delta<0){delta1=2*(delta+y)－1;if(delta1<=0)direction=1;

elsedirection=2;

即选D}71/899/12/202371西安工程大学计算机图形学elseif(delta>0){delta2=2*(delta-x)-1;if(delta2<=0)direction=2;elsedirection=3;}elsedirection=2;switch(direction){case1:x++;delta+=2*x+1;break;case2:x++;y--;delta+=2*(x-y+1);break;case3:y--;delta+=(-2*y+1);break;}/*switch*/}/*while*/}/*Bresenham_Ciecle*/72/899/12/202372西安工程大学计算机图形学Bresenham画圆算法现在从A点开始向右下方逐点来寻找弧AB要用点。如图中点Pi-1是已选中一个表示圆弧上点，依据弧AB走向，下一个点应该从Hi或者Li中选择。显然应选离AB最近点作为显示弧AB点。假设圆半径为R，显然，当xhi2+yhi2-R2≥R2-(xli2+yli2)时，应该取Li。不然取Hi。令di=xhi2+yhi2+xli2+yli2-2R2显然，当di≥0时应该取Li。不然，取Hi。Pi-1HiLi应取Hi还是取Li73/899/12/202373西安工程大学计算机图形学Bresenham画圆算法剩下问题是怎样快速计算di。设图中Pi坐标为(xi,yi)，则Hi和Li坐标为(xi+1,yi)和(xi＋1,yi-1)di=(xi+1)2+yi2+(xi+1)2+(yi-1)2

-2R2=2(xi+1)2+2yi2-2yi+1-2R2当di<0时->取Hi(xi+1,yi)

，则di+1=(xi+1+1)2+yi2+(xi+1+1)2+(yi-1)2-2R2=2(xi+1)2+2yi2-2yi+1-2R2+4xi

+6=di+4xi+6PiHiLi应取Hi还是取Li74/899/12/202374西安工程大学计算机图形学Bresenham画圆算法当di≥0时->取Li(xi＋1,yi-1)，则di+1=(xi+1+1)2+(yi-1)2+(xi+1+1)2+(yi–1-1)2-2R2=di+4(xi-yi)+10易知x0=0，y0=R,x1=x0+1所以d0=12+y02+12+(y0-1)2-2R2=3-2y0=3-2RPi-1HiLi应取Hi还是取Li75/899/12/202375西安工程大学计算机图形学生成圆弧正负法原理：

设圆方程为F(x,y)=X2+Y2-R2=0;假设求得Pi坐标为(xi,yi)；则当Pi在圆内时->F(xi,yi)<0->向右->向圆外Pi在圆外时->F(xi,yi)>0->向下->向圆内76/899/12/202376西安工程大学计算机图形学生成圆弧正负法即求得Pi点后选择下一个象素点Pi+1规则为：当F(xi,yi)≤0取xi+1=xi+1，yi+1=yi;当F(xi,yi)＞0取xi+1=xi，yi+1=yi-1;这么用于表示圆弧点均在圆弧附近，且使F(xi,yi)时正时负，故称正负法。快速计算关键是F(xi,yi)计算，能否采取增量算法？77/899/12/202377西安工程大学计算机图形学生成圆弧正负法若F(xi,yi)已知，计算F(xi+1,yi+1)可分两种情况：1、F(xi,yi)≤0->xi+1=xi+1，yi+1=yi;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2

->=(xi+1)2+yi2

-R2=F(xi,yi)+2xi

+12、F(xi,yi)＞0->xi+1=xi，yi+1=yi-1;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2

->=xi2+(yi–1)2-R2=F(xi,yi)-2yi

+13、初始值：略78/899/12/202378西安工程大学计算机图形学生成圆弧多边形迫近法圆内接正多边形迫近法圆等面积正多边形迫近法79/899/12/202379西安工程大学计算机图形学圆内接正多边形迫近法思想：当一个正多边形边数足够多时，该多边形能够和圆无限靠近。即所以，在允许误差范围内，能够用正多边形代替圆。设内接正n边形顶点为Pi(xi,yi),Pi幅角为

i,每一条边对应圆心角为a，则有xi=Rcos

iyi=Rsin

i80/899/12/202380西安工程大学计算机图形学圆内接正多边形迫近法内接正n边形代替圆计算多边形各顶点递推公式Xi+1 Rcos(a+

i)

=Yi+1 Rsin(a+

i) Xi+1 cosa-sinaXi =Yi+1 sinacosaYi因为:a是常数，