第2章 基本图形的生成与计算--直线、圆、椭圆的生成.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,浙江师范大学数理与信息工程学院,计算机图形学,第二章 直线、圆、椭圆生成算法,图形的扫描转换,(,光栅化,),：确定像素、显示图形的过程。步骤如下,：,确定像素,用图形属性，对像素进行写操作,一维图形，用一个像素宽的直线来显示图形,二维图形的光栅化，即区域的填充：确定像素，填色或图案。,图形的光栅化，必须显示在窗口内，否则不予显示。确定图形的哪些部分在窗口内，哪些在窗口外，即裁剪,浙江师范大学数理与信息工程学院,计算机图形学,图形显示前需要：扫描转换,+,裁剪,裁剪,-,扫描转换：最常用，节约计算时间。,扫描转换,-,裁剪：算法简单；,浙江师范大学数理与信息工程学院,计算机图形学,本章内容,直线的生成算法,圆的生成算法,区域填充算法,字符的生成,图形求交,图形裁剪,浙江师范大学数理与信息工程学院,计算机图形学,直线的生成算法,确定最佳逼近该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作,三个常用算法：,数字微分法,(DDA),中点画线法,Bresenham,算法,浙江师范大学数理与信息工程学院,计算机图形学,数字微分法,(,),假定直线的起点、终点分别为：（,x,a,y,a,),(,x,b,y,b,),，,则斜率,m,为：,m=(,y,b,-y,a,)/(x,b,-x,a,)=,dy/dx,x,i,y,i,),(x,i,+1,y,i,+k),(x,i,int(y,i,+0.5),栅格交点表示象素点位置,。,。,。,。,浙江师范大学数理与信息工程学院,计算机图形学,数值微分,(DDA),法,基本思想,直线的起点和终点分别为,(,x,a,y,a,),(,x,b,y,b,),，,斜率,m,为：,m=(,y,b,-y,a,)/(x,b,-x,a,)=,dy/dx,直线中每个点坐标由前一点坐标加增量,(,Dx,Dy,),而得到,x,i+1,=,x,i,+Dx,其中,x,1,=,x,a,y,i+1,=,y,i,+Dy,y,1,=,y,a,并且,Dy,=,mDx,浙江师范大学数理与信息工程学院,计算机图形学,数值微分,(DDA),法,直线方向的,8,个象限,在,1a,取,Dx,=1,Dy=m;,在,1b,取,Dx,=1/m,Dy=1;,得到,象限,|,dx,|,dy,|?,Dx,Dy,象限,|,dx,|,dy,|?,Dx,Dy,1a true 1 m 3a true -1 -m,1b false 1/m 1 3b false -1/m -1,2a true -1 m 4a true 1 -m,2b false -1/m 1 4b true 1/m -1,浙江师范大学数理与信息工程学院,计算机图形学,数值微分,(DDA),法,二个规律,(1),|,dx,|,dy,|,时，,|,Dx1,|,Dy,|=m,|,dx|,|dy,|,时，,|,Dx,|=1/m,|,Dy,|=1,(2),Dx,、,Dy,的符号与,dx,、,dy,的符号相同,增量算法：在迭代算法中，如果每一步的,x,、,y,值是用前一步的值加上增量来获得，则称为增量算法,DDA,算法就是一个增量算法,浙江师范大学数理与信息工程学院,计算机图形学,数值微分,(DDA),法,#include,stdio.h,#include graphics.h,void,dda_line(int,xa,int,ya,int,xb,int,yb,int,c);,void main(),int,driver=,DETECT,mode,;,int,x0,y0,x1,y1,background=WHITE,color=RED;,scanf(%d,%d,%d,%d,initgraph(&driver,&mode,d:tc,);,setbkcolor(backround,);,dda_line(x0,y0,x1,y1,color);,getch,();,closegraph,();,浙江师范大学数理与信息工程学院,计算机图形学,数值微分,(DDA),法,void,dda_line(int,xa,int,ya,int,xb,int,yb,int,c),float delta_x,delta_y,x,y;,int,dx,dy,steps,k,;,dx,=,xb-xa,;,dy,=,yb-ya,;,if(,abs(dx,),abs(dy,)steps=,abs(dx,);,else steps=,abs(dy,);,delta_x=(,float)dx/(float)steps,;delta_y=(,float)dy/(float)steps,;,x=,xa,;y=,ya,;,putpixel(x,y,c,);,for(k=1;k0,y,i+1,取,D(y,i,+1),，,否则取,C(y,i,),。,因此算法的关键在于求出,d,1,-d,2,的符号。,d,1,-d,2,=(y-y,i,)-(y,i,+1-y)=2y-2y,i,-1,=2dy/dx(x,i,+1)-2y,i,+2b,1,A,d,1,d,2,浙江师范大学数理与信息工程学院,计算机图形学,Bresenham,画线算法,取,P,i,=(d,1,-d,2,)dx,经,整理，得,P,i,=2x,i,dy-2y,i,dx+2dy+(2b-1)dx,由于在,1a,象限，有,dx,0,，故,P,i,仍可以用来判断符号,求递推公式,P,i+1,=2x,i+1,dy-2y,i+1,dx+2dy+(2b-1)dx,=2x,i,dy+2dy-2y,i+1,dx+2y,i,dx-2y,i,dx+2dy+(2b-1)dx,=P,i,+2dy-2(y,i+1,-y,i,)dx,即,求得,P,i+1,=P,i,+2dy-2(y,i+1,-y,i,)dx,求初值,P,i,中代入,x,1,和,y,1,，,得初值,P,1,=2dy-dx,浙江师范大学数理与信息工程学院,计算机图形学,Bresenham,画线算法,算法思想,1.,画点,(x,1,y,1,),dx=,x,b,-x,a,dy,=,y,b,-y,a,计算,P,1,=2dy-dx,i=1;,2.x,i+1,=,x,i,+1,如果,P,i,0,，则,y,i+1,=,y,i,P,i+1,=P,i,+2dy,；,否则,y,i+1,=,y,i,+1,，,P,i+1,=P,i,+2dy-2dx,；,3.,画点,(x,i+1,y,i+1,);,4.i=i+1,如果,idx+1,转,2,；否则结束,优点,1.,不必计算斜率，无除法,2.,不用浮点数，只用整数,3.,只做,整数加,/,减运算，乘,2,运算可用移位实现,浙江师范大学数理与信息工程学院,计算机图形学,程序如下：,BresenhamLine(int,x,a,int,y,a,int,x,b,int,y,b,int,color),int,x,y,dx,dy,p,i,;,putpixel(x,a,y,a,color,);,dx,=,x,b,-x,a,;,dy,=,y,b,-y,a,;,p=2*,dy-dx,;x=,x,a,;y=,y,a,;,putpixel(x,y,color,);,for(i=2;i=,dx,;i+),if(p0),y+;,p=p+2*,dy,;,else p=p+2*dy-2*,dx,;,x+;,putpixel(x,y,color,);,Bresenham,画线算法,浙江师范大学数理与信息工程学院,计算机图形学,直角坐标法,给定圆心坐标,(,x,c,y,c,),和半径,r,则,当,x-x,c,从,-r,到,r,加,1,递增时，,可得相应的,y,值。,缺点：浮点运算、开方、,取整、不均匀,y,x,浙江师范大学数理与信息工程学院,计算机图形学,极坐标法,x=x,0,+,Rcos,y=y,0,+,Rsin,dx,=-,Rsin,ddy,=,Rcos,d,x,n+1,=x,n,+,dx,=x,n,-,Rsin,d,x,n,-(y,n,-y,0,)d,y,n+1,=y,n,+,dy,=y,n,+,Rcos,d,y,n,+(x,n,-x,0,)d,显然，确定,x,y,的初值及,d,值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标,缺点：浮点运算、乘法运算、取整运算,浙江师范大学数理与信息工程学院,计算机图形学,Bresenham,画圆算法,下面仅以圆心为,(,x,c,y,c,),、半径,R,为整数的圆为例，讨论圆的生成算法,设圆的半径为,r,，,考虑圆心在,(0,0),，并从,x=0,、,y=r,开始的顺时针方向的,1/8,圆周的生成过程,如图中的点,P,i,是已选中的一个表示圆弧上的点，根据弧,AB,的走向，下一个点应该选择,H,或者,L,。,显然应选离,AB,最近的点作为显示弧,AB,的点,P,i,H,L,A,B,x,i,x,i+1,y,i,y,y,i,-1,浙江师范大学数理与信息工程学院,计算机图形学,Bresenham,画圆算法,y,2,=r,2,-(x,i,+1),2,d,1,=y,i,2,-y,2,=y,i,2,-r,2,+(x,i,+1),2,d,2,=y,2,-(y,i,-1),2,=r,2,-(x,i,+1),2,-(y,i,-1),2,令,判别式为,p,i,=d,1,-d,2,，,并代入,d,1,、,d,2,，,则有,p,i,=2(x,i,+1),2,+y,i,2,+(y,i,-1),2,-2r,2,p,i,的递归式为,p,i+1,=2(x,i+1,+1),2,+y,i+1,2,+(y,i+1,-1),2,-2r,2,=2(x,i,+1+1),2,+y,i+1,2,+(y,i+1,-1),2,-2r,2,=p,i,+4x,i,+6+2(y,i+1,2,-y,i,2,),2(y,i+1,-y,i,),P,i,H,L,y,i,y,y,i,-1,x,i,x,i+1,A,B,浙江师范大学数理与信息工程学院,计算机图形学,Bresenham,画圆算法,p,i+1,=p,i,+4xi,+6+2(y,i+1,2,-y,i,2,),2(y,i+1,-y,i,),如果,p,i,0,则,p,i+1,=p,i,+4x,i,+6,x,i+1,=x,i,+1,y,i+1,=,y,i,如果,p,i,0,则,p,i+1,=p,i,+4x,i,+6+2(y,i+1,-y,i,)(y,i+1,+y,i,-1),=p,i,+4x,i,+6,-,2(2y,i,-2),=p,i,+4(x,i,-y,i,),+10,x,i+1,=,x,i,+1,y,i+1,=y,i,-1,在,p,i,中代入,x,i,=0,，,y,i,=r,，,得到,p,i,的初值,p,0,p,0,=2(0+1),2,+r,2,+r-1),2,-2r,2,=3-2r,P,i,H,i,L,i,浙江师范大学数理与信息工程学院,计算机图形学,Bresenham,画圆算法,circle(int,xc,int,yc,int,r,int,c),int,x,y,p,;,x=0;,y=r;,p=3 2*r;,while(xy),plot-circle-,point(xc,yc,x,y,c);,if(p,F(x,i,y,i,),向右,-,向圆外,P,i,在圆外时,-,F(x,i,y,i,)0-,向下,-,向圆内,生成圆弧的正负法,浙江师范大学数理与信息工程学院,计算机图形学,生成圆弧的正负法,即求得,P,i,点后选择下一个象素点,P,i+1,的规则为：,当,F(x,i,y,i,)0,取,x,i+1,=,x,i,+1,，,y,i+1,=,y,i,;,当,F(x,i,y,i,),0,取,x,i+1,=x,i,，,y,i+1,=,y,i,-1;,这样用于表示圆弧的点均在圆弧附近，且使,F(x,i,y,i,),时正时负，故称正负法。,快速计算的关键是,F(x,i,y,i,),的计算，能否采用增量算法？,浙江师范大学数理与信息工程学院,计算机图形学,生成圆弧的正负法,若,F(x,i,y,i,),已知，计算,F(x,i+1,y,i+1,),可分,两种情况：,1,、,F(x,i,y,i,)0,x,i+1,=,x,i,+1,，,y,i+1y,i,;,F(x,i+1,y,i+1,)=(x,i+1,),2,+(y,i+1,),2,-R,2,=(x,i,+1),2,+y,i,2,-R,2,=,F(x,i,y,i,)+2x,i,+1,2,、,F(x,i,y,i,),0,x,i+1,=x,i,，,y,i+1,=,y,i,-1;,F(x,i+1,y,i+1,)=(x,i+1,),2,+(y,i+1,),2,-R,2,=x,i,2,+(y,i,1),2,-R,2,=,F(x,i,y,i,)-2y,i,+1,3,、,初始值,：,F(0,r)=0,2,+r,2,-r,2,=0,浙江师范大学数理与信息工程学院,计算机图形学,生成圆弧的多边形逼近法,?,圆的内接正多边形迫近法,?,圆的等面积正多边形迫近法,浙江师范大学数理与信息工程学院,计算机图形学,圆的内接正多边形逼近法,思想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即,因此，在允许的误差范围内，可以用正多边形代替圆。,设内接正,n,边形的顶点为,P,i,(x,i,y,i,),P,i,的幅角为,i,每一条边对应的圆心角为,，则,有,x,i,=,Rcos,i,y,i,=,Rsin,i,浙江师范大学数理与信息工程学院,计算机图形学,圆的内接正多边形,逼近,法,内接正,n,边形代替圆,计算多边形各顶点的递推公式,x,i+1,R,cos,(,+,i,),=,y,i,+1R,sin,(,+,i,),x,i+1,cos,-sin,x,i,=,y,i,+1,sin,cos,y,i,因为,:,是常数，,sin,，,cos,只在开始时计算一次所以，,一个顶点只需,4,次乘法，共,4n,次乘法，外加直线段的中点算法的计算量。,浙江师范大学数理与信息工程学院,计算机图形学,圆的等面积正多边形,逼近法,当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。,浙江师范大学数理与信息工程学院,计算机图形学,圆的等面积正多边形,逼近法,步骤：,求多边形径长，从而求所有顶点坐标值,由逼近误差值，确定边所对应的圆心角,浙江师范大学数理与信息工程学院,计算机图形学,椭圆的扫描转换,椭圆方程,x,2,/a,2,+y,2,/b,2,=1,F(x,y)=b,2,x,2,+a,2,y,2,-a,2,b,2,椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为,-1,的点作为分界点,椭圆上一点,(x,y),处的法向：,N(x,y)=(F),x +(F),y,=2,b,2,x,+2,a,2,y,浙江师范大学数理与信息工程学院,计算机图形学,在上半部分,法向量的,y,分量大,在下半部分,法向量的,x,分量大,上半部分,下半部分,法向量,两分量相等,M,1,M,2,在上半部分的当前中点，法向量,(,2,b,2,(,x,p,+1,),，,2,a,2,(y,p,-0.5,),的,y,分量比,x,分量大，即：,b,2,(x,p,+1),a,2,(y,p,-0.5),而在下一个中点，不等式改变方向，则说明椭圆弧从上部分转入下部分,浙江师范大学数理与信息工程学院,计算机图形学,椭圆的中点画法,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算判别式的值，由判别式的符号确定更近的点,先讨论椭圆弧的上部分,设,(,x,p,y,p,),已确定，则下一待选像素的中点是,(x,p,+1,y,p,-0.5),，,其相应的判别式为,d,1,=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,浙江师范大学数理与信息工程学院,计算机图形学,根据,d,1,的符号来决定下一像素是取正右方的那个，还是右下方的那个。,若,d,1,0,，,中点在椭圆内，取正右方象素，判别式更新为：,d,1,=F(x,p,+2,y,p,-0.5)=d,1,+b,2,(2x,p,+3),d,1,的增量为,b,2,(2x,p,+3),当,d,1,0,，,中点在椭圆外，取右下方象素，更新判别式：,d,1,=F(x,p,+2,y,p,-1.5)=d,1,+b,2,(2x,p,+3)+a,2,(-2y,p,+2),d,1,的增量为,b,2,(2x,p,+3)+a,2,(-2y,p,+2),d,1,的初始条件：椭圆弧起点为,(0,，,b),；,第一个中点为,(1,b-0.5),，,初始判别式：,d,1,=F(1,b-0.5)=b*b+a*a(-b+0.25),浙江师范大学数理与信息工程学院,计算机图形学,转入下一部分。下一象素是正下方或右下方。,下部分的中点判别式及其初始化,d,2,d,2,=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,若,d,2,=0,中点在椭圆外，,取正下方像素，,d,2,F(x,p,+0.5,y,p,-2)=d,2,+,a,2,(-2y,p,+3),下半部分弧的终止条件为,y=0,浙江师范大学数理与信息工程学院,计算机图形学,程序：,MidpointEllipse(a,b,color),int,a,b,color;,int,x,y;float d1,d2;,x=0;y=b;,d1=b*b+a*a*(-b+0.25);,putpixel(x,y,color,);,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-;,putpixel(x,y,color,);/,上部分,浙江师范大学数理与信息工程学院,计算机图形学,