直线、圆、椭圆的生成.ppt

第三章直线、圆、椭圆生成算法,图形的扫描转换（光栅化）确定一个像素集合，用于显示一个图形的过程。步骤如下：1、确定有关像素2、用图形的颜色或其它属性，对像素进行写操作。对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。,图形显示前需要：扫描转换+裁剪裁剪-扫描转换：最常用，节约计算时间。扫描转换-裁剪：算法简单；,本章内容,3.1扫描转换直线段3.1.1DDA算法3.1.2中点画线法3.1.3Bresenham画线算法3.2圆弧、椭圆弧扫描转换3.2.1中点算法3.2.2内接正多边形迫近法3.2.3等面积正多边形逼近法3.2.4生成圆弧的正负法,3.1直线段的扫描转换算法,直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。,3.1.1数值微分法（）,假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。,(Xi+1,Yi+k),(Xi,Int(Yi+0.5),(Xi,Yi),栅格交点表示象素点位置,。,。,。,。,3.1.1数值微分(DDA)法,基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。,计算yi+1=kxi+1+b=kxi+b+kx=yi+kx当x=1;yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。,数值微分(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;xx1,x+)drawpixel(x,int(y+0.5),color);y=y+k;,数值微分(DDA)法,例：画直线段P0(0,0)-P1(5,2)xint(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5,012345,3,2,1,Line:P0(0,0)-P1(5,2),实现DDA画线程序,步骤：第一步：建立一个DDALine的工程文件；第二步：添加ddaline()成员函数方法：在工作区中选择CLASSVIEW类窗口，右击CDDAlineView类，选择“addmemberfunction”，定义如下的成员函数：voidddaline(CDC*pDC,intx0,inty0,intx1,inty1,COLORREFcolor);,第三步：编写自定义的成员函数ddaline()程序,voidCDDALineView:ddaline(CDC*pDC,intx0,inty0,intx1,inty1,COLORREFcolor)intlength,i;floatx,y,dx,dy;length=abs(x1-x0);if(abs(y1-y0)length)length=abs(y1-y0);dx=(float)(x1-x0)/length;dy=(float)(y1-y0)/length;x=x0+0.5;y=y0+0.5;for(i=1;iSetPixel(int)x,(int)y,color);x=x+dx;y=y+dy;,第四步：编写OnDraw()函数,voidCDDALineView:OnDraw(CDC*pDC)CDDALineDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);/TODO:adddrawcodefornativedatahereddaline(pDC,100,100,400,100,RGB(255,0,0);ddaline(pDC,400,100,400,400,RGB(0,255,0);ddaline(pDC,400,400,100,400,RGB(0,0,255);ddaline(pDC,100,400,100,100,RGB(255,255,0);ddaline(pDC,100,100,400,400,RGB(255,0,255);ddaline(pDC,100,400,400,100,RGB(0,255,255);,数值微分(DDA)法,缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,中点画线法,原理：,假定直线斜率0取P2。M在Q的上方-P1离直线更近更近-取P1M与Q重合，P1、P2任取一点。问题：如何判断M与Q点的关系？,P=(,x,p,y,p,),Q,P2,P1,3.1.2中点画线法,假设直线方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知：欲判断中点M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,P=(,x,p,y,p,),Q,P2,P1,构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采用增量算法呢？,P=(,x,p,y,p,),Q,P2,P1,若d0-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；增量为a,P=(,x,p,y,p,),Q,P2,P1,若dM在直线下方-取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；增量为ab,P=(,x,p,y,p,),Q,P2,P1,画线从(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来摆脱小数，提高效率。,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(xy1)if(dSetPixel(x,y,color);,Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一。令k=y/x，就0k1的情况来说明Bresenham算法。由DDA算法可知：yi+1=yi+k(1)由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（xi,yir）的象素来表示直线上的点，其中yir表示最靠近yi的整数。,Bresenham画线算法,设图中xi列上已用（xi,yir）作为表示直线的点，又设B点是直线上的点，其坐标为（xi+1,yi+1），显然下一个表示直线的点（xi+1,yi+1,r）只能从图中的C或者D点中去选。设A为CD边的中点。若B在A点上面则应取D点作为（xi+1,yi+1,r），否则应取C点。,xi,Xi+1,Yi,r,Yi+1,r,C,D,B,A,(x)的几何意义,为能确定B在A点上面或下面，令(xi+1)=yi+1-yir-0.5(2)若B在A的下面，则有(xi+1)0。由图可知yi+1,r=yir+1，若(xi+1)0(3)yi+1,r=yir，若(xi+1)0,Bresenham画线算法,由式（2）和式（3）可得到(xi+2)=yi+2-yi+1,r-0.5=yi+1+k-yi+1,r-0.5（4）yi+1-yir-0.5+k-1,当(xi+1)0yi+1-yir-0.5+k,当(xi+1)0(xi+2)=(xi+1)+k-1,当(xi+1)0(xi+2)=(xi+1)+k,当(xi+1)0由式（1）和式（2）可得到(x2)=k-0.5(5),Bresenham画线算法,BresenhamLine(CDC*pDC,intx1,inty1,intx2,inty2,COLORREFcolor)intx,y,dx,dy,p;/传入端点坐标x值相等if(x1=x2)if(y1SetPixel(x1,i,color);elsefor(inti=y2;iSetPixel(x1,i,color);return;,/斜率判断，斜率绝对值大于，则m为false，否则为trueBOOLm=(fabs(y2-y1)x2)p=x1;x1=x2;x2=p;p=y1;y1=y2;y2=p;x=x1;y=y1;dx=x2-x1;dy=y2-y1;,/斜率绝对值小于等于if(m)/第一种情况，y递增if(y1SetPixel(x,y,color);if(pSetPixel(x,y,color);if(p0)x+;p=p-(dy1);elsex+;y-;p=p-(dy+dx)SetPixel(x,y,color);if(p0)y-;p=p+(dx1);elsex+;y-;p=p+(dx+dy)SetPixel(x0-x,y0+y,c);pDC-SetPixel(x0+x,y0-y,c);pDC-SetPixel(x0-x,y0-y,c);pDC-SetPixel(x0+y,y0+x,c);pDC-SetPixel(x0-y,y0+x,c);pDC-SetPixel(x0+y,y0-x,c);pDC-SetPixel(x0-y,y0-x,c);,对于圆心在（x0,y0)、半径为r的圆，先对圆心在原点，半径为r的8分圆进行扫描转换，每确定一个象素，可输出原始圆的8个点。,3.2.4中点画圆法,利用圆的对称性，只须讨论1/8圆。第二个8分圆P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp-1)。,M,P1,P2,P（Xp，Yp）,构造函数：F（X，Y）=X2+Y2-R2；则F（X，Y）=0（X，Y）在圆上；F（X，Y）0（X，Y）在圆外。设M为P1、P2间的中点，M=(Xp+1,Yp-0.5),M,P1,P2,有如下结论：F（M）M在圆内-取P1F（M）=0-M在圆外-取P2为此，可采用如下判别式：,M,P1,P2,d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若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-R,M,P1,P2,算法步骤：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更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x=y时，重复步骤3和4。否则结束。,MidpointCircle(intr,intcolor)intx,y;floatd;x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(xy)if(d0)d+=2*x+3;x+;elsed+=2*(x-y)+5;x+;y-;drawpixel(x,y,color);,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用e=d-0.25代替de0=1-R,算法优化,算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x=y时，重复步骤3和4。否则结束。,中点画圆法程序代码,MidpointCircle(intr,intcolor)intx,y;floatd;x=0;y=r;d=1-r;drawpixel(x,y,color);while(x=y)if(d0)d+=2*x+3;x+elsed+=2*(x-y)+5;x+;y-;drawpixel(x,y,color);,上述算法能否再改进呢？注意到d的增量是x,y的线性函数，每当x递增1，则d的增量递增x=2每当y递减1，则d的增量递增y=2x初始值=3；y初始值=-2r+2,x=0;y=r;d=1-r;.if(d0)d+=2*x+3;x+;elsed+=2*(x-y)+5;x+;y-;,x=0;y=r;d=1-r;d1=3;d2=-2*r+2;.if(d0)d+=d1;x+;d1+=2;elsed+=d1+d2;x+;y-;d1+=2;d2+=2,MidpointCircle(intr,intcolor)intx,y;intd;x=0;y=r;d=1-r;d1=3;d2=-2*r+2;while(xy)drawpixel(x,y,color);if(d0)d+=d1;x+;d1+=2elsed+=d1+d2;x+;y-;d1+=2;d2+=2;,程序实现步骤：,(1)建立MidPointCircle工程文件；(2)右击CMidPointCircleView类，建立成员函数voidMidpointCircle(CDC*pDC,intx0,inty0,intr,COLORREFcolor)intCirPot(CDC*pDC,intx0,inty0,intx,inty,COLORREFcolor),(3)编写成员函数代码，程序如下：,voidCMidPointCircleView:MidpointCircle(CDC*pDC,intx0,inty0,intr,COLORREFcolor)intx,y;floatd;x=0;y=r;d=1.25-r;CirPot(pDC,x0,y0,x,y,color);while(xSetPixel(x0+y),(y0+x),color);pDC-SetPixel(x0+y),(y0-x),color);pDC-SetPixel(x0+x),(y0-y),color);pDC-SetPixel(x0-x),(y0-y),color);pDC-SetPixel(x0-y),(y0-x),color);pDC-SetPixel(x0-y),(y0+x),color);pDC-SetPixel(x0-x),(y0+y),color);return0;,（4）编写OnDraw(CDC*pDC)函数，程序如下：voidCMidPointCircleView:OnDraw(CDC*pDC)CMidPointCircleDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);/TODO:adddrawcodefornativedatahereMidpointCircle(pDC,100,100,10,RGB(255,0,0);MidpointCircle(pDC,500,300,60,RGB(255,255,0);(5)编译、运行程序，查看结果。,3.2.5Bresenham画圆算法,现在从A点开始向右下方逐点来寻找弧AB要用的点。如图中点Pi-1是已选中的一个表示圆弧上的点，根据弧AB的走向，下一个点应该从Hi或者Li中选择。显然应选离AB最近的点作为显示弧AB的点。假设圆的半径为R，显然，当xhi2+yhi2-R2R2-(xli2+yli2)时，应该取Li。否则取Hi。令di=xhi2+yhi2+xli2+yli2-2R2显然，当di0时应该取Li。否则，取Hi。,Pi-1,Hi,Li,应取Hi还是取Li,剩下的问题是如何快速的计算di。设图中Pi-1的坐标为(xi-1,yi-1)，则Hi和Li的坐标为(xi,yi-1)和(xi,yi-1-1)di=xi2+yi-12+xi2+(yi-1-1)2-2R2=2xi2+2yi-12-2yi-1-2R2di+1=(xi+1)2+yi2+(xi+1)2+(yi-1)2-2R2=2xi2+4xi+2yi2-2yi-2R2+3,Pi-1,Hi,Li,应取Hi还是取Li,Bresenham画圆算法,当di取Hi-yi=yi-1，则di+1=di+4xi-1+7当di0时-取Li-yi=yi-1-1，则di+1=di+4(xi-1-yi-1)+11易知x0=0，y0=R,x1=x0+1因此d0=12+y02+12+(y0-1)2-2R2=3-2y0=3-2R,Pi-1,Hi,Li,应取Hi还是取Li,Bresenham画圆算法代码,voidCircleBres(intradius)intx=0,y=radius,p=3-2*radius;while(x向圆外Pi在圆外时-F(xi,yi)0-向下-向圆内,即求得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)的计算，能否采用增量算法？,若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+(yi1)2-R2=F(xi,yi)-2yi+13、初始值：圆弧起点(0,R),圆弧终点(R，0),3.2.7生成圆弧的多边形逼近法,圆的内接正多边形迫近法圆的等面积正多边形迫近法,圆的内接正多边形逼近法,思想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即因此，在允许的误差范围内，可以用正多边形代替圆。设内接正n边形的顶点为Pi(xi,yi),Pi的幅角为i,每一条边对应的圆心角为a，则有xi=Rcosiyi=Rsini,圆的内接正多边形逼近法,内接正n边形代替圆计算多边形各顶点的递推公式Xi+1Rcos(a+i)=Yi+1Rsin(a+i)Xi+1cosa-sinaXi=Yi+1sinacosaYi因为:a是常数，sina，cosa只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。,圆的等面积正多边形逼近法,当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。,圆的等面积正多边形逼近法,步骤：求多边形径长，从而求所有顶点坐标值由逼近误差值，确定边所对应的圆心角,3.3椭圆的扫描转换,3.3.1椭圆的特征,对于椭圆上的点，有F(x,y)=0；对于椭圆外的点，F(x,y)0；对于椭圆内的点，F(x,y)0，取Pd(xi+1,yi-1),误差项的递推d10：取Pu(xi+1,yi),增量为：b2(2xi+3),d10：取Pd(xi+1,yi-1),增量为：b2(2xi+3)+a2(-2yi+2),判别式的初始值弧起点为(0,b)，故第一个中点为(1,b-0.5),再来推导椭圆弧下半部分的绘制公式原理,请思考？,判别式和初始值,若d20，取(xi+1,yi-1)若d20，取(xi,yi-1),用上半部分计算的最后点(x，y)来计算下半部分中d的初值：d=b2(x+0.5)2+a2(y-1)2-a2b2,递推式,d0,取正下方元素（xi，yi-1）,递推式,d0,取右下方元素（xi+1，yi-1）,算法描述,(1)输入椭圆的长半轴a和短半轴b。(2)计算初始值：d=b2+a2(-b+0.25),x=0,y=b.(3)绘制点(x,y)及其在四分象限上的另外3个对称点.(4)判断d的符号。若d=0，则先将d更新为d+b2(2xi+3),再将（xi,yi）更新为（xi+1,yi）;否则先将d更新为d+b2(2xi+3)+a2(-2yi+2),再将（xi,yi）更新为（xi+1,yi-1）(5)当b2(x+1)a2(y-0.5)时，重复步骤(3)和(4)，否则转(6)(6)用上半部分计算的最后点(x，y)来计算下半部分中d的初值：d=b2(x+0.5)2+a2(y-1)2-a2b2(7)绘制点(x,y)及其在四分象限的另外3个对称点b(8)判断d的符号.若d=0，则先将d更新为d+b2(2xi+2)+a2(-2yi+3),再将(x,y)更新为(x+1,y-1);否则先将d更新为d+a2(-2yi+3),再将（x，y）更新为(x，y1).(9)当y0时，重复步骤(7)和(8)，否则结束。,程序：MidpointEllipe(a,b,color)inta,b,color;intx,y;floatd1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);putpixel(x,y,color);while(b*b*(x+1)0)if(d20)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-；elsed2+=a*a*(-2*y+3);y-;putpixel(x,y,color);,