第3章 基本图形生成算法.ppt

《第3章 基本图形生成算法.ppt》由会员分享，可在线阅读，更多相关《第3章 基本图形生成算法.ppt（53页珍藏版）》请在三一办公上搜索。

1、第3章 基本图形生成算法,3.1 图元扫描转换直线段扫描转换圆弧扫描转换椭圆弧扫描转换3.2 实区域填充3.3 图形反走样,3.1图元扫描转换,直线段扫描转换圆弧扫描转换 椭圆弧扫描转换,直线段的扫描转换算法,直线的扫描转换确定最佳逼近于该直线的一组象素按扫描线顺序，对这些象素进行写操作三个常用算法数值微分(DDA)算法中点画线法Bresenham画线算法,数值微分(DDA)法,假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。,(X i+1,Yi+k),(X i,Int(Yi+0.5),(X i,Yi),栅格交点表示象素点位置,。,。,。,。,数值微分(DDA)法,基本

2、思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。,数值微分(DDA)法,计算yi+1=kxi+1+b=kxi+b+kx=yi+kx 当x=1;yi+1=yi+k 即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1,y最多增加1。当 k 1时，必须把x，y地位互换,数值微分(DDA)法,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。,数值微分(DDA)法,vo

3、id DDALine(HDC hdc,int x0,int y0,int x1,int y1,int color)int x；float dx,dy,y,k;dx=x1-x0;dy=y1-y0;k=dy/dx;y=y0;for(x=x0;x=x1;x+)SetPixel(hdc,x,int(y+0.5),color);y=y+k;,数值微分(DDA)法,例：画直线段P0(0,0)-P1(5,2)x int(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5,数值微分(DDA)法,缺点：在此算法中，y、k必须是float

4、，且每一步都必须对y进行舍入取整，不利于硬件实现。,中点画线法,原理：,假定直线斜率0K1，且已确定点亮象素点P（Xp,Yp）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点现需确定下一个点亮的象素。,中点画线法,当M在Q的下方-P2离直线更近-取P2。M在Q的上方-P1离直线更近-取P1M与Q重合，P1、P2任取一点。问题：如何判断M与Q点的关系？,中点画线法,假设直线方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知：欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,中点画线法,构造判别式：d=

5、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；能否采用增量算法呢？,中点画线法,若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,中点画线法,若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；增量为a

6、b,中点画线法,画线从(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来摆脱小数，提高效率。优点：只有整数运算，不含乘除法可用硬件实现,中点画线法,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,c

7、olor);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=5d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6ixiyid1001210-33213431-154256 5 2,Bresenham画线算法,使用最广泛与中点画线法的思想类似由误差项符号决定下一个象素取正右方像素还是右上方像素,Bresenham画线算法,现就0k1的情况来说明Bresenham算法

8、。由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点。,为能确定B在A点上面或下面，令(xi+1)=yi+1-yir-0.5(2)若B在A的下面，则有(xi+1)0。

9、由图可知 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)0 yi+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 由式（2）可得到的初值(x2)=y2-yr-0.5=d-0.5=-0.5(5),程序如下：BresenhamLine(x0,y0,x1,y1,color)int

10、x0,y0,x1,y1,color;int x,y,dx,dy;float k,e;dx=x1-x0;dy=y1-y0;k=dy/dx;e=-0.5;x=x0;y=y0;for(i=0;i=0)y+;e=e-1;,Bresenham画线算法,Bresenham画线算法,上述Bresenham算法在计算斜率时用到除法，在计算误差项时用到小数。由于算法中只用到误差项的符号来判断，因此，如下替换不会改变算法性质。e=2*e*dx优点整数运算，速度快精度高乘2运算可用移位实现，适于硬件实现,程序如下：BresenhamLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,col

11、or;int x,y,dx,dy;float k,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;(e=-0.5)for(i=0;i=0)y+;e=e-2*dx;(e=e-1),Bresenham画线算法,3.1图元扫描转换,直线段扫描转换圆弧扫描转换 椭圆弧扫描转换,圆弧扫描转换算法,圆弧的扫描转换确定最佳逼近于该圆弧的一组象素按扫描线顺序，对这些象素进行写操作四个常用算法中点画圆法Bresenham画圆算法生成圆弧的正负法圆的内接正多边形逼近法,下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。假设圆的方程为：X2+Y2=R2,圆弧扫描算法,圆弧扫描算法,

12、X2+Y2=R2Y=Sqrt(R2-X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须取整。缺点：浮点运算，开方，取整，不均匀。,中点画圆法,利用圆的对称性，只须讨论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在圆内-取P1 F（M）=0-M

13、在圆外-取P2为此，可采用如下判别式：,M,P1,P2,中点画圆法,d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2 若d0,则P1 为下一个象素，那么再下一个象素的判别式为：d2=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3 即d 的增量为 2xp+3.,M,P1,P2,中点画圆法,若d=0,则P2 为下一个象素，那么再下一个象素的判别式为：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+（2xp+3）+（-2 yp+2）即d 的增量为 2(xp-yp)+5.d的初值:d0=F(1

14、,R-0.5)=1+(R-0.5)2-R2=1.25-R,M,P1,P2,中点画圆法,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+elsed+=2*(x-y)+5;x+;y-;drawpixel(x,y,color);,中点画圆法,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用e=d-0.25代替de0=1-R,Bresenham画圆算法,现在从A

15、点开始向右下方逐点来寻找弧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。,Bresenham画圆算法,剩下的问题是如何快速的计算di。设图中Pi-1的坐标为(xi-1,yi-1)，则Hi和Li的坐标为(xi,yi-1)和(xi,yi-1-1)di=xi2+yi-12+xi2+(yi-

16、1-1)2-2R2=2xi2+2yi-12-2yi-1-2R2 Hi+1和Li+1的坐标为(xi+1,yi)和(xi+1,yi-1)di+1=(xi+1)2+yi2+(xi+1)2+(yi-1)2-2R2=2xi2+4xi+2yi2-2yi-2R2+3,Bresenham画圆算法,当di取Hi-yi=yi-1，则 di+1=di+4xi-1+7当di 0时-取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,生成圆弧的正负法,原理：(xi,yi),

17、设圆的方程为F(x,y)=X2+Y2-R2=0;假设求得Pi的坐标为(xi,yi)；则当Pi在圆内时-F(xi,yi)向右-向圆外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,y

18、i)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、初始值：略,圆的内接正多边形逼近法,思想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即因此，在允许的误差范围内，可以用正多边形代替圆。设内接正n边形的顶点为Pi(xi,yi),Pi的幅角为i,每一条边对应的圆心角为，则有xi=

19、Rcos i yi=Rsin i,圆的内接正多边形逼近法,内接正n边形代替圆计算多边形各顶点的递推公式 Xi+1 Rcos(+i)=Yi+1 Rsin(+i)Xi+1 cos-sin Xi=Yi+1 sin cos Yi因为:是常数，sin，cos 只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。,3.1图元扫描转换,直线段扫描转换圆弧扫描转换 椭圆弧扫描转换,椭圆的扫描转换,F(x,y)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。椭圆上一点处的法向：N(x,y)=(Fx)i+

20、(Fy)j=2b2 xi+2a2 yj i 和j分别为沿x轴和y轴方向的单位向量,在上半部分,法向量的y分量大在下半部分,法向量的x分量大,上半部分,下半部分,法向量两分量相等,M1,M2,若在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5)的y分量比x分量大,即：b2(Xp+1)a2(Yp-0.5),若在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分,椭圆的中点画法,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点先讨论椭圆弧的上部分设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5)d1=

21、F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b2,根据d1的符号来决定下一像素是取正右方的那个，还是右下方的那个。若d10，中点在椭圆内，取正右方象素，判别式更新为：d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)d1的增量为b2(2Xp+3)当d10，中点在椭圆外，取右下方象素，更新判别式：d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)d1的增量为b2(2Xp+3)+a2(-2Yp+2),d1的初始条件：椭圆弧起点为(0，b)；第一个中点为(1,b-0.5)初始判别式：d1=F(1,b-0.5)=b*b+a*a

22、(-b+0.25)转入下一部分，下一象素可能是正下方或右下方，此时判别式要初始化。d2=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若d2=0,取正下方像素，则d2=F(Xp+0.5,Yp-2)=d2+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)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);,作业,(1)采用Bresenham画线法绘出起点（1，3），终点为（9，18）的直线段。(2)用中点画圆法生成圆心在（3，-2），半径为12的上半个半圆。(3)编写程序完成画整个圆的算法。,