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

1、扫描转换直线段,DDA算法,中点画线法,Bresenham画线算法,2、圆弧、椭圆弧扫描转换,中点画圆算法,Bresenham画圆算法,中点画椭圆算法,本章内容,扫描转换原理,第三章 直线、圆、椭圆生成算法,1、输出图元(Output Primitive),图形生成的基本构造单元称为输出图元。,输出图元包括字符串和几何成分，如：点、直线，二次曲线、填充区域（多边形，圆）及由彩色阵列定义的形状。,2、扫描转换,图形的两种表示方法,点阵表示,矢量表示,反映了图形的外表,反映了图形的内在联系,对光栅扫描器而言，矢量表示不能直接用于显示,将矢量表示的图形对象的转换为点阵表示称为扫描转换,任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。,第三章 直线、圆、椭圆生成算法,图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下：,1、确定有关像素,2、用图形的颜色或其它属性，对像素进行写操作。,对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。,图形显示前需要：扫描转换+裁剪,裁剪扫描转换：最常用，节约计算时间。,扫描转换裁剪：算法简单；,第三章 直线、圆、椭圆生成算法,屏幕坐标定义,由扫描转换原理知：数字设备通过绘制两端点间的离散点来显示直线段，线段上离散坐标位置是从线段方程中计算出来的，其所表示的对象用精确的坐标描述，其每一位置是数学上的无限小的点；,而在光栅扫描显示器中的点用一个像素表示。其为一有限的屏幕区域，屏幕的位置用整数值，所以屏幕上绘制的点仅是实际坐标中点位置的近似。,要显示坐标系中指定几何形状就需要调整数学输入点到有限像素区域的映射,数学输入点到有限像素区域的映射方法有两种,1、对象与像素中心对齐,2、物体边界与像素边界对齐,见下图,第三章 直线、圆、椭圆生成算法,像素中心对准编址方式,像素边界对准编址方式,两种屏幕坐标的编址方法,注：在后面学习中使用像素中心对准编址方式,第三章 直线、圆、椭圆生成算法,直线段的扫描转换算法,直线的扫描转换:,确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。,三个常用算法：,数值微分法（DDA）；,中点画线法；,Bresenham算法。,假定直线的起点、终点分别为：(x0,y0), (x1,y1)，且都为整数。记直线的斜率为k。,数值微分(DDA)法,虚线交叉点为像素中心点,基本思想,已知过端点P0 (x0, y0), P1(x1, y1)的直线段L:y=kx+b,直线斜率为,这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。,数值微分(DDA)法,即：当x每递增1，y递增k(即直线斜率)；,先考虑k 1的情形。,当 k 1时，必须把x，y地位互换,数值微分(DDA)法,在这种情况下，x每增加1，y最多增加1。,在这种情况下，y每增加1，x最多增加1。,即：当y每递增1，x递增1/k(即直线斜率倒数)；,数值微分(DDA)法,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。,DDA算法就是一个增量算法。,上面是从左端点开始计算的，若以右端点作为起始点,当k 1时：取x=-1, yi+1=yi-k,当k 1时：取y=-1, xi+1=xi-1/k,下面为一般DDA算法的一段伪代码,数值微分(DDA)法,if( abs(x1-x0)=abs(y1-y0) then Length= abs(x1-x0) else Length= abs(y1-y0) end if %选取x和y大者作为步长 x=(x1-x0)/Length y=(y1-y0)/Length x=x0+0.5 y=y0+0.5,%开始主循环 i=1 while(i=Length) Setpixel(int(x),int(y) x=x+ x y=y+ y i=i+1 end while,DDA算法的伪代码,#include #include inline int round (const float a) return int (a + 0.5); void lineDDA (int x0, int y0, int xEnd, int yEnd) int dx = xEnd - x0, dy = yEnd - y0, steps, k; float xIncrement, yIncrement, x = x0, y = y0; if (fabs (dx) fabs (dy) steps = fabs (dx); else steps = fabs (dy); xIncrement = float (dx) / float (steps); yIncrement = float (dy) / float (steps); setPixel (round (x), round (y); for (k = 0; k steps; k+) x += xIncrement; y += yIncrement; setPixel (round (x), round (y); ,数值微分(DDA)法,例：画直线段P0(0,0)-P1(5,2),缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,数值微分(DDA)法,dx =5,dy =3 steps =5,x =1, y =2/5=0.4,假定直线斜率0k1，且已确定点亮象素点P(xp ,yp )，则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点,原理：,现需确定下一个点亮的象素。,中点画线法,当M在Q的下方 P2离直线更近更近取P2 。,M在Q的上方 P1离直线更近更近取P1,M与Q重合， P1、P2任取一点。,中点画线法,问题：如何判断M与Q点的关系？,假设直线方程为：ax+by+c=0, 其中a=y0-y1, b=x1-x0 , c=x0y1-x1y0。,令F(x,y)=ax+by+c，由常识知：,欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y)，并检查它的符号。,中点画线法,dp=F(M) =F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c,构造判别式：,当dp0, M在直线(Q点)下方,取右上方P2(xp+1,yp+1);,当dp 0,M在直线(Q点)上方,取右下方P1(xp+1,yp);,当dp=0，选P1或P2均可，约定取P1。,能否采用增量算法呢？,dp称为画线算法中第p步决策参数,中点画线法,若dp0M在直线上方(xp+1,yp+1)取P1(xp+1,yp);,此时再求下一个象素的判别式为,dp+1 =F(xp+2, yp+0.5) =a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =dp+a；,增量为a,中点画线法,若dp0M在直线下方(xp+1,yp+1)取P2(xp+1,yp+1);,此时再求下一个象素的判别式为,dp+1= F(xp+2, yp+1.5) =a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =dp+a+b ；,增量为ab,中点画线法,画线从(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,由于只用dp 的符号作判断，为了只包含整数运算, 可以用2dp代替dp来摆脱小数，提高效率。,此时d0= 2a+b，增量分别为2a和2(a+b)。,中点画线法,|k|1时直线中点画线算法,1、输入线段的两个端点，并将左端点储存在(x0,y0)中.,2、将(x0,y0)装入帧缓存中，画出第一个点。,3、计算常量a=y0-y1, b=x1-x0, d1=2a, d2=2 (a+b); 并得到决策参数的第一个值d0=2a+b 。,4、从p=0开始,在沿路径的每个xp处,进行下列检测：,如果dp0,下一个绘制的点为(xp+1,yp+1)，并且dp+1=dp+d2；,否则，下一个绘制的点为(xp+1,yp)，并且dp+1=dp+d1。,5、重复步骤4，直到xpx1为止。,中点画线法,void Midpoint_Line (int x0,int y0,int x1, int y1,int color), int a, 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 (xx1) if (d0) x+; y+; d+=d2; else x+; d+=d1; drawpixel(x, y, color); /* while */ /* mid PointLine */,中点画线法,例：用中点画线法P0(0,0) P1(5,2),a=y0-y1=-2 , b=x1-x0=5,d0=2a+b=1, d1=2a=-4 ,d2=2(a+b)=6,i xi yi d,1 0 0 1,2 1 0 -3,3 2 1 3,4 3 1 -1,5 4 2 5,Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一,令 k= y/x，就0k1的情况来说明Bresenham算法,假设已确定要显示的像素(xi,yi)，下一步要确定在列xi+1上绘制在位置(xi+1,yi)像素，还是在位置(xi+1,yi+1)像素,设直线方程为 y=kx+b,其与x=xi+1的交点为(x,y),设d1,d2分别为交点(x,y)到y=yi和y=yi+1的距离,显然,又,令pi=x(d1-d2),所以pi=x(d1-d2)= 2yxi-2xyi+c,其中c= 2y+x(2b-1),由于x0，所以pi 与(d1-d2)同号,pi称为画线算法中第i步决策参数,Bresenham画线算法,pi 的增量算法,pi+1=2yxi+1-2xyi+1+c,pi+1-pi=2y(xi+1-xi)-2x(yi+1-yi),因为xi+1=xi+1, 所以有,pi+1=pi+2y-2x(yi+1-yi),显然 p0= x(2k-1)=2y-x,Bresenham画线算法,|k|1时直线Bresenham算法,1、输入线段的两个端点，并将左端点储存在(x0,y0)中.,2、将(x0,y0)装入帧缓存中，画出第一个点。,3、计算常量x、y、2y和2y-2x ，并得到决策参数的第一个值p0=2y- x 。,4、从i=0开始，在沿路径的每个xi处，进行下列检测：,如果pi0,下一个绘制的点为(xi+1,yi)，并且pi+1=pi+2y,否则，下一个绘制的点为(xi+1,yi+1)，并且pi+1=pi+2(y-x),Bresenham画线算法,5、重复步骤4，共x次。,Bresenham画线算法,【例】求过端点为(20,10)和(30,18)直线各像素点,x=10, y=8, d1=2y=16, d2=2y-2x=-4,p0=2y-x=6,k pk xk+1 yk+1,0 6 21 11,1 2 22 12,2 -2 23 12,3 14 24 13,4 10 25 14,5 6 26 15,6 2 27 16,7 -2 28 16,8 14 29 17,9 10 30 18,|k|=|y/x|=4/51,#include #include /* |m| xEnd) x = xEnd; y = yEnd; xEnd = x0; else x = x0; y = y0; setPixel (x, y);,while (x xEnd) x+; if (p 0) p += twoDy; else y+; p += twoDyMinusDx; setPixel (x, y); ,BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; int x,y,dx,dy,e; dx = x1-x0; dy = y1-y0; d= -dx; x=x0; y=y0; for( i=0; i=0) y+; d=d2*dx; ,Bresenham画线算法,圆的扫描转换算法,仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。,假设圆的方程为： x2 + y2 = R2,在一定范围内，每给定一x值，可得一y值。,当x取整数时，y须取整.,浮点运算，开方，取整，不均匀。,缺点,角度DDA法,x=x0+Rcos y=y0+Rsin,dx=-Rsind dy=Rcosd,xn+1=xn+dx yn+1=yn+dy,xn+1=xn+dx=xn-Rsind =xn-(yn-y0)d yn+1=yn+dy=yn+Rcosd =yn+(xn-x0)d,显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。,利用圆的对称性，只须讨论1/8圆。第二个8分圆,P为当前点亮象素，那么，下一个点亮的象素可能是P1(xp+1,yp)或P2(xp+1,yp-1)。,中点画圆法,中点画圆法,构造函数：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),中点画圆法,有如下结论,F(M) 0,F(M) 0,为此，可采用如下判别式,M在圆内,取P1(xp+1,yp),M在圆外,取P2(xp+1,yp-1),dp=F(M) =F(xp+1, yp-0.5) =(xp+1)2+(yp-0.5) 2-R2,中点画圆法,若dp0, 则P1为下一个象素，那么再下一个象素的判别式为：,dp+1 = F(xp+1+1, yp+1- 0.5),= (xp + 2)2 + (yp - 0.5)2- R2,= dp + 2xp +3,即: d 的增量为 2xp+3,若dp 0, 则P2 为下一个象素，那么再下一个象素的判别式为：,dp+1 = F(xp+1+1,yp+1-0.5),= (xp+2)2+ (yp-1.5)2-R2,= dp+(2xp+3)+(-2yp+2),即d 的增量为 2 (xp-yp)+5,= dp+2(xp-yp) +5,中点画圆法,中点画圆法,初始决策参数,计算的起始位置为(x0,y0)=(0,R),d0=F(x0+1,y0-0.5),=F(1,R-0.5),即：d0=5/4-R,=1+(R-1/2)2-R2,假定将半径R指定为整数，则可以对d0进行简单取整,d0=1-R (R 为整数）,因为所有的增量为整数,中点画圆算法的步骤总结,1、输入圆半径R和圆心(xc,yc)，并得到圆周（圆心在原点）上的第一个点,(x0,y0)=(0,R),2、计算出初始决策参数值：d0=5/4-R(或 d0=1-R),3、从k=0开始，在每个xk位置，完成以下测试：,若dk0，圆心在 (0,0)的圆的下一点坐标(xk+1,yk+1)=(xk+1,yk)，并且dk+1= dk + 2xk +3,否则，圆的下一点坐标(xk+1,yk+1)=(xk+1,yk-1)，并且dk+1= dk + 2(xkyk)+5,中点画圆法,中点画圆法,5、将每个计算出来的像素位置 (xk,yk)移到圆心在(xc,yc)圆的对应位置上，即：,xk=xk+xc，yk=yk+xc,并画出坐标值。,6、重复步骤3到步骤5，直到xy为止,4、确定在其它七个八分圆中的对称点,【例】使用中点画圆法画圆心在原点，半径为10的图,初始决策参数d0=1-R=-9,初始点(x0,y0)=(0,10),k dk xk yk,0 -9 0 10,1 -6 1 10,2 -1 2 10,3 6 3 10,4 -3 4 9,5 8 5 9,6 5 6 8,中点画圆法,7 7 7,中点画圆法,MidpointCircle(int R, int color),int x,y;,float d;,x=0; y=R; d=1.25-R;,drawpixel(x,y,color);,while(xy),if(d0) d+ = 2*x+3; x+ ,else d+ = 2*(x-y) + 5; x+;y-; ,算法,中点画圆法,MidpointCircle(int R, int color),int x,y,d;,x=0; y=R; d=1-R;,drawpixel(x,y,color);,while(xy),if(d0) d+ = 2*x+3; x+ ,else d+ = 2*(x-y) + 5; x+;y-; ,算法,drawpixel(x,y,color);,Bresenham画圆算法,现在从A点开始向右下方逐点来寻找弧AB要用的点。,如图中点Pi是已选中的一个表示圆弧上的点，根据弧AB的走向，下一个点应该从Hi或者Li中选择。,显然应选离AB最近的点作为显示弧AB的点。,假设圆的半径为R，显然，当,应该取Li 。否则取Hi。,显然，当di 0 时应该取Li。 否则取Hi。,Bresenham画圆算法,剩下的问题是如何快速的计算di,设图中Pi的坐标为(xi,yi)，则Hi和Li的坐标为(xi+1,yi)和(xi+1,yi-1 ),当di0时取Hi yi+1=yi,则 di+1= di+4xi+6,当di0时取Li yi=yi-1,则 di+1= di+4(xi-yi)+10,易知 x1=0，y1=R, x2=x1+1,因此 d0=12 + y12 + 12 +(y1 - 1)2 - 2R2,= 3 - 2y1 = 3 - 2R,Bresenham画圆算法,int x=0,y=r,d=3-2*r;,while(xy) ,drawpixel(x,y);,if (d0),d=d+4*x+6;,else ,d=d+4*(x-y)+10;,y-;,x+;,【例】使用Bresenham画圆法画圆心在原点，半径为10的图,初始决策参数d0=3-2R=-17,初始点(x0,y0)=(0,10).,k xk yk dk,0 0 10 -17,1 1 10 -11,2 2 10 -1,3 3 10 13,4 4 9 -5,5 5 9 17,6 6 8 11,7 7 7 13,F(x,y)=b2x2+a2y2-a2b2=0,椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。,椭圆上一点处的法向：,N(x,y) = Fx i + Fy j,= 2b2 x i + 2a2 y j,椭圆的扫描转换,在上半部分,法向量的y分量大.,即: b2 x a2 y,在当前中点处，法向量( 2b2 (xp+1) , 2a2 (yp-0.5)的y分量比x分量大,即: b2 (xp+1) a2 (yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分,在下半部分,法向量的x分量大,椭圆的扫描转换,即: b2 x a2 y,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点,椭圆的中点画法,先讨论椭圆弧的上部分,设(xp,yp)已确定，则下一待选像素的中点是(xp+1,yp-0.5),dp= F(xp+1,yp-0.5),= b2(xp+1)2+a2(yp-0.5)2-a2b2,根据dp的符号来决定下一像素是取正右方的那个，还是右下方的那个。,若d1p0，中点在椭圆内，取正右方像素，判别式更新为：,d1p+1=F(xp+2,yp-0.5)=d1p+b2(2xp+3),d1p的增量为b2(2xp+3),当d1p0，中点在椭圆外，取右下方像素，更新判别式：,d1p+1=F(xp+2,yp-1.5)=d1p+b2(2xp+3)+a2(-2yp+2),d1p的增量为b2(2xp+3)+a2(-2yp+2),椭圆的中点画法,d1p的初始条件：椭圆弧起点为(0,b)；,第一个中点为(1,b-0.5),初始判别式：d10=F(1,b-0.5)=b2-a2b+0.25a2,转入下一部分，下一象素可能是正下方或右下方，此时判别式要初始化。,d2p=F(xp+0.5,yp-1) = b2(xp+0.5)2+a2(yp-1)2-a2b2,若d2p0,取右下方像素，则,d2p+1 = F(xp+1.5,yp-2)=d2p + b2(2xp+2)+a2(-2yp+3),若d2p0,取正下方像素，则,d2p+1 = F(xp+0.5,yp-2) = d2p + a2(-2yp+3),下半部分弧的终止条件为 y = 0,椭圆的中点画法,MidpointEllipe(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) d1 +=b*b*(2*x+3); x+; else d1 +=(b*b*(2*x+3)+a*a*(-2*y+2) x+; y-; ,putpixel(x,y,color); /上部分 d2 = sqr(b*(x+0.5)+sqr(a*(y-1)-sqr(a*b); while(y 0) 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); ,椭圆的中点画法程序伪码,inline int round (const float a) return int (a + 0.5); /* 下列程序接受椭圆的