圆及圆弧生成算法市公开课金奖市赛课一等奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.2 圆弧扫描转换,对称性,x,y,0,（8，2）,（x，y）,（8，2）,（x，y）,（8，2）,（x，y）,（8，2）,（x，y）,（2，8）,（y，x）,（2，8）,（y，x）,（2，8）,（y，x）,（2，8）,（y，x）,P,1,=(x,y)P,5,=(-x,-y),P,2,=(y,x)P,6,=(-y,-x),P,3,=(-y,x)P,7,=(y,-x),P,4,=(-x,y)P,8,=(x,-y),第1页,第1页,3.2.1,圆弧扫描法,已知圆圆心坐标为（x,c,y,c,），半径为R,圆直角坐标方程表示为 (x-x,c,),2,+(y-y,c,),2,=R,2,x,0,=x,c,-R,y,0,=,y,c,x,i+1,=x,i,+1,y,i+1,(x,i,+1,Round,(y,i+1,),缺点,:,(1)运算速度慢,(2)显示质量不好,(x,c,y,c,),(x,c,-R,y,c,),角度DDA算法,圆弧扫描法,正负法、圆弧Bresenham算法、中点画圆法等,3.2圆生成算法,第2页,第2页,由圆参数方程,推导出圆弧增量算法表示式:,缺点：所产生圆是不封闭，且该圆半径有不断增大趋势。,取微分,令,x,0,=R,y,0,=0,起点(x,0,y,0,),=02,为所画圆弧圆心角,单位为弧度,d 2,-m,角度增量，m 为整数。,已知圆圆心坐标为（0,0），半径为R,(0,0),(R,0),3.2.2角度DDA算法(近似法),第3页,第3页,P,i,P,i+1,原因：,P,i+1,是在P,i,上加一个小矢量而得到，这个矢量垂直于位置矢量P,i。,因此新半径经常比前一个半径大，从而得到曲线是一条螺线。,将第二式中,x,i,用,x,i+1,代替,则有:,y,i+1,=y,i,+x,i+1,d,=,y,i,+(x,i,-y,i,d,),d,=,d,x,i,+(1-d,2,),y,i,x,i+1,=x,i,-y,i,d,为椭圆,d2,-m,，当m=4时，此椭圆与准确圆之间误差E16,3.2.3椭圆差分法,第4页,第4页,10/10/hjy-5,d,P,i+1,P,i,O,X,Y,1 pixel=R,sin d,d,=arc sin,-1,1/R,令：,3.2.4旋转法(正多边形迫近),第5页,第5页,3.2.4旋转法(正多边形迫近),设圆圆心为,c,(0,0),半径为,R,。,假设圆弧起始角和终止角分,别为,0,和,1,，,把圆弧分割为,n,份，则两个顶点之间夹角为,=（,1,-,0,）/n,。,设内接正多边形一个顶点为,P,i,(,x,i,y,i,),，,cP,i,幅角为,i,，,则,x,i,=,R,cos,i,y,i,=,R,sin,i,顶点,P,i,+1,坐标为,x,i,+1,=,R,cos(,i,+,),=,x,i,cos,-,y,i,sin,y,i,+1,=,R,sin(,i,+,),=,x,i,sin,+,y,i,cos,用正多边形迫近圆弧法,由此决定了,一系列顶点，两个定点拟定一条直线，n条直线迫近了个整个圆。,第6页,第6页,表示为矩阵形式，则内接正多边形递推公式,计算一个点（,x,i,+1,y,i,+1,）只要作四次乘法。,x,i,+1,=,R,cos(,i,+,),=,x,i,cos,-,y,i,sin,y,i,+1,=,R,sin(,i,+,),=,x,i,sin,+,y,i,cos,第7页,第7页,x,y,(x,c,y,c,),方程,若F(x,y),0,点(x,y)在圆,外,若F(x,y),=,0,点(x,y)在圆,上,2.F(x,y)=0 是二阶光滑,F,F,F,F,1.F(x,y)=0 划分平面域为3个点集,函数特点：,F,F,圆方程为：,3.每一个点曲率半径步长 (1 pixel),3.2.5正负法（隐函数曲线),第8页,第8页,(0,R),若点P,i,在圆内或圆上，,即 F(x,i,y,i,)0,若点P,i,在圆外，,即,F(x,i,y,i,),0,以第一个1/4圆弧为例，取圆弧最上方点为起始点(x,0,y,0,)，,x,0,=0 y,0,=R,点P,i+1,取R点，即x,i+1,=x,i,+1,y,i+1,=y,i,点P,i+1,取,B点，即,x,i+1,=x,i,y,i+1,=y,i,-1,由当前点,P,i,(x,i,y,i,),选择下一点,P,i+1,(x,i+1,y,i+1,),规则是：,x,y,o,第9页,第9页,则,当x,i+1,=x,i,+1,y,i+1,=y,i,时,，,当x,i+1,=x,i,y,i+1,=y,i,-1时,，,第10页,第10页,结论第一个1/4圆弧正负法算法：,若F(x,i,y,i,)0（点在内侧，下一点选外侧）,若F(x,i,y,i,)0（点在外侧，下一点选内侧）,x,i+1,=x,i,+1,y,i+1,=y,i,x,i+1,=x,i,y,i+1,=y,i,-1已知圆心坐标为（x,c,y,c,），半径为R，,起始点(x,0,y,0,)x,0,=x,c,y,0,=y,c,+R,第11页,第11页,存在问题：,考虑过极限点转向，即换向规则。,x,y,o,极限点,极限点,当,时，有x向极值。,当,时，有y向极值。,第12页,第12页,以坐标原点为圆心第一象限1/4圆为例,X,Y,O,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),(0,R),(R,0),起点为(0,R)，按顺时针方向生成圆,则y为x单调递减函数,设P(x,i,y,i,)点为当前点圆上亮点,下一个该显示象素有三种也许:,右方象素H、,右下方D、,下方象素V,决定一象素使其与真正圆距离平方最小,2,2,2,),1,(,R,y,x,m,i,i,V,-,-,+,=,2,2,2,),1,(,),1,(,R,y,x,m,i,i,D,-,-,+,+,=,2,2,2,),1,(,R,y,x,m,i,i,H,-,+,+,=,圆在与点P(x,i,y,i,)附近光栅网格相交关系只有5种,1,2,3,4,5,1.基本思想,3.2.6圆弧Bresenham算法,第13页,第13页,五种情况分解图：,H,D,V全在圆内,H在圆外，D,V在圆内,D在圆上，H在圆外，V在圆内,D,H在圆外，V在圆内,D,V,H 全在圆外,3,H,D,V,5H,D,V,4,H,D,V,2,D,V,H,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),1,2,3,4,5,1,H,D,V,取D点,取H点或D点,取D点或V点,取H点,取V点,第14页,第14页,首先计算圆心到右下角象素D距离平方与圆心到圆弧上点距离平方之差,假如,i,0,阐明D点在圆内,只能是1,2情况，可选D点或H点,设,为圆到象素H距离平方与圆到象素D距离平方之差。,|(x,i,+1),2,+(y,i,),2,-R,2,|-|(x,i,+1),2,+(y,i,-1),2,-R,2,|,Mh Md,假如,0,应选D(x,i+1,y,i,-1),假如,=0,要求选D(x,i+1,y,i,-1),V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),1,2,3,第15页,第15页,对于情况2，左下角D总是位于圆内，而H点总是位于圆外,(x,i,+1),2,+(y,i,-1),2,-R,2,0,=2(,i,+,y,i,)-1,对于情况1,由于y为一单调递减函数，只能选取H点,由于：,(x,i,+1),2,+(y,i,),2,-R,2,0,(x,i,+1),2,+(y,i,-1),2,-R,2,0,=,(y,i,-1),2,-(y,i,),2,=0,Vx,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),1,2,3,|(x,i,+1),2,+(y,i,),2,-R,2,|-|(x,i,+1),2,+(y,i,-1),2,-R,2,|,第16页,第16页,假如,i,0,阐明D点在圆外,只能是4,5情况，可选V点或D点,设,为圆到象素D距离平方与圆到象素V距离平方之差。,|(x,i,+1),2,+(y,i,-1),2,-R,2,|-|(x,i,),2,+(y,i,-1),2,-R,2,|,假如,0,假如,=0,要求选D(x,i+1,y,i,-1),阐明圆到D点距离大,应选V(x,i,yi,-1),情况4:,由于D在圆外，而V在圆内:,(x,i,+1),2,+(y,i,-1),2,-R,2,=0,(x,i,),2,+(y,i,-1),2,-R,2,0,结论与情况4是一致,对于情况3,应选D点,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),4,5,第17页,第17页,归纳总结：,当,i,0时，,0,取D,(x,i,+1,y,i,-1)点,当,i,0时，,0,取V,(x,i,y,i,-1)点,当,i,=0时，,取D,(x,i,+1,y,i,-1)点,由上面分析,增量算法递推公式:,水平移动到,H,(x,i,+1,y,i,)点,X,i+1,=,x,i,+1,y,i+1,=,y,i,i+1,=,(x,i+1,+1),2,+(y,i+1,-1),2,-R,2,(x,i,+1),2,+(y,i,-1),2,-R,2,i,+2x,i+1,+1,对角移动到,D,点,X,i+1,=,x,i,+1,y,i+1,=,y,i,-1,i+1,=,i,+2x,i+1,-2y,i+1,+2,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),第18页,第18页,移动到,V,点,X,i+1,=,x,i,y,i+1,=,y,i,-1,i+1,=,i,-2y,i+11,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),圆弧Bresenham算法长处:,起点和终点准确，分布均匀，计算简朴。,正负法绘制圆,Bresenham法绘制圆,第19页,第19页,举例:,画圆心为(0,0),半径R=8四分之一圆弧,初始条件,:x,1,=0;y,1,=8;R=8,1,=(x,1,+1),2,+(y,1,-1),2,-R,2,=1+49-64=-140;,HD,=2(,1,+y,1,)-1=2(-14+8)-1=-130,取H点,2,=,1,+2x,2,+1=-14+2*1+1=-110,HD,=2(,2,+y,2,)-1,=2(-11+8)-1=-70,取D点,取H点,点亮点(0,8),也许点亮H或D点,x,2,=1,y,2,=8,3,=,2,+2x,3,+1=-11+2*2+1=-60,x,3,=2,y,3,=8,x,4,=3,y,4,=7,4,=,3,+2x,4,-2y,4,+2=-6+2*3-2*7+2=-120,HD,=2(,3,+y,4,)-1,=,2(-12+7)-1=-110,取H点,x,4,=4,y,4,=7,5,=,4,+2x,5,+1=-12+2*4+1=-30,取D点,x,5,=5,y,5,=6,6,=,5,+2x,5,-2y,5,+2=-3+2*5-2*6+2=-30,取D点,x,6,=6,y,6,=5,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),第20页,第20页,7,=,6,+2x,6,-2y,6,+2=-3+2*6-2*5+2=10,取D点,x,7,=7,y,7,=4,DV,=2(,6,-x,6,)-1=2(1-6)-1=-110,DV,=2(,7,-x,7,)-1=2(9-7)-1=30,取V点,x,8,=7,y,8,=3,9,=,8,-2y,8,+1=9-2*3+1=40,DV,=2(,9,-x,8,)-1=2(4-7)-1=-70,DV,=2(,10,-x,9,)-1=218-8)-1=190,取V点,x,10,=8,y,10,=1,11,=,10,-2y,10,+1=19-2*2+1=160,DV,=2(,11,-x,10,)-1=2(16-8)-1=150,取V点,x,11,=8,y,11,=0,第21页,第21页,Y,y=0,Y,N,结束,起点x=0,y=R,D,0,Y,N,Y,N,1/4圆程序流程图,第22页,第22页,只须讨论1/8圆，普通采用第二个8分圆,P为当前点亮象素，那么，下一个选择象素也许是P1（Xp+1，Yp）或P2（Xp+1，Yp1)。,3.2.7中点画圆算法（利用圆对称性）,第23页,第23页,结构函数：F（X，Y）=X,2,+Y,2,-R,2,；则,F（X，Y）=0 （X，Y）在圆上；,F（X，Y）0 （X，Y）在圆外。,设M为P1、P2间中点，M=(X,p,+1,Y,p,-0.5),M,P1,P2,3.2.7中点画圆算法（利用圆对称性）,第24页,第24页,有下列结论：,F（M）=0，在圆外，则取P2,为此，可采用下列判别式：,d=F(M)=F(x,p,+1,y,p,-0.5),=(x,p,+1),2,+(y,p,-0.5),2,-R,2,M,P1,P2,第25页,第25页,d=F(M)=F(x,p,+1,y,p,-0.5),=(x,p,+1),2,+(y,p,-0.5),2,-R,2,若d=0,则P2 为下一个象素那么再下一个象素判别式为：,d1=F(x,p,+2,y,p,-1.5),=(x,p,+2),2,+(y,p,-1.5),2,-R,2,=d+（2x,p,+3）+（-2 y,p,+2）,即d 增量为 2(x,p,-y,p,)+5.,d,初值:,d0=F(1,R-0.5),=1+(R-0.5),2,-R,2,=1.25-R,M,P1,P2,第27页,第27页,算法环节：,1.输入圆半径R。,2.计算初始值d=1.25-R、x=0、y=R。,3.绘制点(x,y)及其在八分圆中另外七个对称点。,4.判断d符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；不然先将d更新为d2(x-y)+5，再将(x,y)更新为(x+1,y-1)。,5.当xy时，重复环节3和4。不然结束。,第28页,第28页,MidpointCircle(int r),int x,y;,float d;,x=0;y=r;d=1.25-r;,while(xy),Setpixel(x,y);,if(d=0,d 增量为:,2(x,p,-y,p,)+5.,若d0,d 增量为:,2x,p,+3.,第i个象素 d P,i,(x,y),1 d0=1.25-10=-8.750 P1(0,10)2 d1=-8.75+3=-5.750 P1(1,10),3 d2=-5.75+5=-0.750 P1(3,9),5 d4=6.25-7=-0.750 P1(5,8),7 d6=10.25-1=9.250 P1(6,7),8 d7=9.25+3=12.250 P1(7,6),例子：设圆半径R=10,第30页,第30页,为了进一步提升算法效率，能够将上面算法中浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。,使用e=d-0.25代替d，(d=1.25 R),则 e0=1-R,第31页,第31页,void MidpointCircle1(int R),int x,y,d;,x=0;y=R;,d=1-R,;,SetPixel(x,y);,while(xy),if(,d0,),d+=2*x+3,;x+;,else,d+=2*(x-y)+5;,x+;y-;,SetPixel(x,y);,第32页,第32页,上述算法能否再改进呢？,注意到,d,增量是,x,y,线性函数，,每当,x,递增1，则,d,增量递增,x,=2,每当,y,递减1，则,d,增量递增,y,=2,x,初始值=3；,y,初始值=-2,r,+2,第33页,第33页,void MidpointCircle2(int R),int x,y,deltax,deltay,d;,x=0;y=R;d=1-R;,deltax=3;,deltay=2-R-R;,SetPixel(x,y);,while(xy),if(d0；,对于椭圆内点，F(xy)0。,处理问题：沿x轴或y轴取单位距离都有斜率绝对值不小于1或小于1曲线，怎么办？,第36页,第36页,在上半部分,法向量y分量大,在下半部分,法向量x分量大,上半部分,下半部分,法向量,两分量相等,M1,M2,在当前中点处，,法向量,（,2,b,2,(Xp+1),，2,a,2,(Yp-0.5)y分量比x分量大,即：b,2,(Xp+1)a,2,(Yp-0.5),而在下一中点，不等式改变方向，则阐明椭圆弧从上部分转入下部分。,法向量斜率绝对值小于1 在y轴取单位步长,法向量斜率绝对值不小于1 在x轴取单位步长,第37页,第37页,F(x,y)=b,2,x,2,+a,2,y,2,-a,2,b2,=0,椭圆上一点处法向量,第38页,第38页,中点椭圆算法,与圆中点算法类似：拟定一个象素后，接着在两个候选象素中点计算一个判别式值，由判别式符号拟定更近点,先讨论椭圆弧上部分,设(X,p,，Y,p,)已拟定，则下一待选像素中点是(X,p,+1,Y,p,-0.5),d1=F(X,p,+1,Y,p,-0.5)=b,2(,X,p,+1),2,+a,2(,Y,p,-0.5),2,-a,2,b,2,第39页,第39页,依据d1符号来决定下一像素是取正右方那个，还是右下方那个。,若d10，中点在椭圆内，取正右方象素，判别式更新为：,d1=F(X,p,+2,Y,p,-0.5)=d1+b,2,(2X,p,+3),d1增量为b,2,(2X,p,+3),第40页,第40页,依据d1符号来决定下一像素是取正右方那个，还是右下方那个。,当d10，中点在椭圆外，取右下方象素，更新判别式：,d1=F(X,p,+2,Y,p,-1.5)=d1+b,2,(2X,p,+3)+a,2,(-2Y,p,+2),d1增量为b,2,(2X,p,+3)+a,2,(-2Y,p,+2),第41页,第41页,d1初始条件：椭圆弧起点为(0，b)；,第一个中点为(1,b-0.5),初始判别式：,d1=F(1,b-0.5)=b*b+a*a(-b+0.25),第42页,第42页,转入下一部分，下一象素也许是正下方或右下方，此时判别式要初始化。,d2=F(X,p,+0.5,Y,p,-1)=b,2(,X,p,+0.5),2,+a,2(,Y,p,-1),2,-a,2,b,2,若d2=0,取正下方像素，则d2=F(X,p,+0.5,Y,p,-2)=d2+a,2,(-2Y,p,+3),下半部分弧终止条件为 y=0,第44页,第44页,椭圆算法环节：,1、d1初始条件：椭圆弧起点为(0，b)；,2、第一个中点为(1,b-0.5),初始递推式：d1=F(1,b-0.5)=b*b+a*a(-b+0.25),3、进入上半部分，下一象素也许是正右方或右下方，此时递推式要初始化。,d1=F(Xp+0.5,Yp-1)=b,2,(Xp+0.5),2,+a,2,(Yp-1),2,-a,2,b,2,a、若d1=0,取右下方像素，则,d1=F(Xp+2,Yp-1.5)=d,2,+b,2,(2Xp+3)+a,2,(-2Yp+2),4、直到a,2,Ypb,2,Xp,5、进入下半部分,6、下半部分弧终止条件为y=0,注意：,上半部分终止判别,下半部分递推式初值,第45页,第45页,程序：MidpointEllipe(int a,int b),int x,y;float d1,d2;,x=0;y=b;,d1=b*b+a*a*(-b+0.25);,SetPixel(x,y);,while(b*b*(x+1)a*a*(y-0.5),if(d10),if(d2 0)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-；,else d2+=a*a*(-2*y+3);y-;,SetPixel(x,y);,第46页,第46页,上机：,1.编制直线Bresenham算法程序；,（下次上机时完毕）,2.读懂并上机调试、运营圆弧,中点画圆算法程序；,手工：,画圆心为(0,0),半径R=10四分之一圆弧用圆弧,Bresenham算法和中点画圆算法计算各个,象,素点坐标值,减少取整;避免浮点运算;双向计算.,1.更加好办法,思考:,第47页,第47页,