计算机图形学课件(C版)-4

第3章3.1直线生成算法3.2圆与椭圆的生成算法主要教学内容3.3实区域的扫描转换3.4区域填充3.5图形反走样基础DD-line(x1,y1,x2,y2,color)intx1,y1,x2,y2,color;{intlength;floatx,y,x,y;length=abs(x2-x1);if(abs(y2-y1)length)length=abs(y2-y1);x=(x2-x1)/length;y=(y2-y1)/length;x=x1+0.5*sign(x);y=y1+0.5*sign(y);for(i=1;i=length;i++){putpixel(Int(x),Int(y),color);x=x+x;y=y+y;}}sign(x)=1,当x0时0,当x=0时-1,当x0时putpixel(30,50,2);在(30,50)处用2号色显示一点。它将像素的亮度存储到帧缓存的对应位置。简单DDA算法Int(x)：不大于X的最大整数P132例:起点(0,0),终点(-8,-4)显示(-1,-1)，(-2,-1)，(-3,-2)，(-4,-2)，(-5,-3)，(-6,-3)，(-7,-4)，(-8,-4)-1-2-3-4-8-7-6-5-4-3-2-1简单DDA算法应用举例(2)对称DDA法:取△t=2-n,有:2n-1=max(|△X|,|△Y|)2n思考题:用对称DDA法来处理上例,请写出各轨迹点的坐标。DDA法比直接使用直线方程的方法快，为什么？——没有浮点乘法，但仍有浮点数的加法DDA中取整操作和浮点运算仍然十分耗时。3.1.2Bresenham画线算法类似简单DDA法,每次在增量最大方向上均走一步,由e的值决定另一方向是否走步。设直线的起点(xs,ys),终点(xe,ye),斜率m=△y/△x=(ye-ys)/(xe-xs)判断e(xi+1)=yi+1-yi,r-0.50=m1的第1象限直线,x方向为增量最大方向yi,r是当前像素P的纵坐标,yi+1,r是下一个像素的纵坐标，xi+1=xi+1A是C和D的中点,当前像素P,下一步在C或D中选择一个若e(xi+1)=0,表示B在A之上,下一个将是D,yi+1,r=yi,r+1若e(xi+1)0,表示B在A之下,下一个将是C,yi+1,r=yi,ryi,r+1DB(xi+1,yi+1)ACXYP(xi,yi)O(0,0)yi,re(xi+1)=yi+1-yi,r-0.5e(x2)=y2-y1,r-0.5=y2-y1-0.5=y1+m-y1-0.5=m-0.5e(xi+2)=yi+2–yi+1,r-0.5yi+1+m-yi,r-1-0.5=e(xi+1)+m-1,当e(xi+1)=0时=yi+1+m-yi,r-0.5=e(xi+1)+m,当e(xi+1)0时即e(xi+1)=e(xi)+m-1,当e(xi)=0时,将选D点(xi+1,yi,r+1)e(xi)+m,当e(xi)0时,将选C点(xi+1,yi,r)e的初值？Bresenham-line(x1,y1,x2,y2,color)intx1,y1,x2,y2,color;{intx,y,△x,△y;floate,m;x=x1;y=y1;△x=x2-x1;△y=y2-y1;m=△y/△x;e=m-0.5;for(i=1;i=△x;i++){putpixel(x,y,color);ife=0{y=y+1;e=e-1;}x=x+1;e=e+m;}}适合0=m1的第1象限直线的Bresenham算法P134例:用Bresenham画直线算法生成(0,0)到(8,3)的直线段。显示(0,0),(1,0),(2,1),(3,1),(4,2),(5,2),(6,2),(7,3)当e(xi)0时,(即f(xi)0)f(xi+1)=2*e(xi+1)*△x=2*(e(xi)+△y/△x))*△x=f(xi)+2△y适合0=m1的第1象限直线的整数Bresenham算法为便于硬件实现,需去掉除法运算:令f=2*e*△x当e(xi)=0时,(即f(xi)=0)f(xi+1)=2*e(xi+1)*△x=2*(e(xi)+△y/△x-1)*△x=f(xi)+2△y-2△xf(x2)=2*e(x2)*△x=2*(△y/△x-0.5)*△x=2△y-△x则f(xi+1)与f(xi)有何关系？f的初值？Inter.bresenham-Line(x1,y1,x2,y2,color)intx1,y1,x2,y2,color;{intx,y,△x,△y,e;x=x1;y=y1;△x=x2-x1;△y=y2-y1;e=2*△y-△x;for(i=1;i=△x;i++){putpixel(x,y,color);if(e=0){y=y+1;e=e-2*△x;}x=x+1;e=e+2*△y;}}(适合0=m1的第1象限直线)整数Bresenham画直线算法算法只用到整数的加法、减法和乘2（算术移位）运算。是一种转换直线的快速增量算法。Generalized-Integer-Bresenham-Line(x1,y1,x2,y2,color);intx1,y1,x2,y2,color;{intx,y,△x,△y,s1,s2,temp,interchange;x=x1;y=y1;△x=abs(x2-x1);△y=abs(y2-y1);s1=sign(x2-x1);s2=sign(y2-y1);if(△y△x){temp=△x;△x=△y;△y=temp;interchange=1;}elseinterchange=0;e=2*△y-△x;for(i=1;i=△x;i++){putpixel(x,y,color);if(e=0){if(interchange=1)x=x+s1;elsey=y+s2;e=e-2*△x;}if(interchange=1)y=y+s2;elsex=x+s1;e=e+2*△y;}}适合各种象限及各种斜率直线的一般Bresenham算法P136例:用一般Bresenham画线算法生成AB线段,起点A(0,0),终点B(-8,-4),请写出轨迹点的坐标。适合各种象限及各种斜率直线的一般Bresenham算法显示(0,0),(-1,-1)，(-2,-1)，(-3,-2)，(-4,-2)，(-5,-3)，(-6,-3)，(-7,-4)如何生成指定宽度的直线?（1）最简单的一种方法是利用“线刷子”.若直线斜率|m|=1,用垂直方向的线刷子;若直线斜率|m|1,用水平方向的线刷子.直线段的基本属性有线型、宽度和颜色。线型包括实线、虚线、点线等。如何生成不同线型的直线？putpixel(x,y-1,RED);putpixel(x,y,RED);putpixel(x,y+1,RED);用垂直刷子生成宽度为3的直线段putpixel(x-1,y,RED);putpixel(x,y,RED);putpixel(x+1,y,RED);用水平刷子生成宽度为3的直线段采用“线刷子”的优点:简单、容易实现。提高分辨率•把显示器分辨率提高一倍（硬件方法）–直线经过两倍的象素，锯齿也增加一倍，–但同时每个阶梯的宽度也减小了一倍，–所以显示出的直线段看起来就平直光滑了一些。例：如何用线刷子生成宽度为3的直线？（3）区域填充（2）正方形刷子也可以用上述方法生成粗曲线。如生成半径为16，线宽为4的圆，可生成半径为14和17的两个同心圆，然后填充两个圆之间的区域。Y.(-Y,X).(Y,X).(-X,Y).(X,Y)(0,0)X.(-X,-Y).(X,-Y).(-Y,-X).(Y,-X)在生成封闭的圆周时,只要生成第一象限的1/8圆弧,其余部分可利用对称点得到。圆弧的扫描转换：确定最佳逼近于该圆弧的一组象素；按扫描线顺序，对这些象素进行写操作。方法1:利用圆的方程y2=r2-x2,x从0递增到r/2,利用方程求出y值,效率很低,用到平方、减法、开平方根。x=r.cosØ,y=r.sinØ,Ø从0变化到/4,计算相应的x和y值,但计算正弦和余弦值花时间比前一种更多。方法2：利用bersenham画圆算法、中点法、正负法、逐点插补法，……..设圆心在原点,半径为R(顺时针画圆)。只考虑第1象限的1/8圆周的情况,其余部分可根据对称得出。圆的方程为:X2+Y2-R2=0yx.Pi-1.Li.Hi(0,0)RBA3.2.1圆弧的bresenham算法P1373.2圆与椭圆的生成算法若D(Si)=XSi2+YSi2-R20,Si在圆外；D(Ti)=XTi2+YTi2-R20,Ti在圆内令di=D(Si)+D(Ti)若di0,Ti离圆近,选Ti(从Pi-1的右下角)di=0,选两点均可di0,Si离圆周近,选Si(Pi-1的正右方)yx.Pi-1.Ti.Si(0,0)RBA现在从A点开始向右下方逐点来寻找弧AB要显示的点。如图中点Pi-1是已选中的一个表示圆弧上的点，根据弧AB的走向，下个点应该从Si或者Ti中选择。显然应选Si和Ti中离AB最近的一点。在起点A(0,R)处,S1(1,R),T1(1,R-1)d1=1+R2-R2+1+(R-1)2-R2=3-2R在起点处，d1的值是多少呢？如何快速的计算di？下面推导di+1与di之间的关系。di=D(Si)+D(Ti)=(Xi-1+1)2+Yi-12-R2+(Xi-1+1)2+(Yi-1-1)2-R2(1)若di0,选Si,Xi+1=Xi-1+1,Yi+1=Yi-1.Pi-1(Xi-1,Yi-1).Si(Xi-1+1,Yi-1).Si+1(Xi-1+2,Yi-1).Ti(Xi-1+1,Yi-1-1).Ti+1(Xi-1+2,Yi-1-1)di+1=D(Si+1)+D(Ti+1)=(Xi-1+2)2+Yi-12-R2+(Xi-1+2)2+(Yi-1-1)2-R2=di+4Xi-1+6P138(2)若di=0,选Ti,Xi+1=Xi-1+1,Yi+1=Yi-1-1.Pi-1(Xi-1,Yi-1).Si(Xi-1+1,Yi-1).Ti(Xi-1+1,Yi-1-1).Si+1(Xi-1+2,Yi-1-1).Ti+1(Xi-1+2,Yi-1-2)di+1=D(Si+1)+D(Ti+1)=(Xi-1+2)2+(Yi-1-1)2-R2+(Xi-1+2)2+(Yi-1-2)2-R2=di+4(Xi-1-Yi-1)+10BresenhamCircle(r,color)intr,color;{intx,y,d;x=0;y=r;d=3-2*r;while(xy){putpixel(x,y,color);if(d=0){d=d+4*(x-y)+10;y=y-1;}elsed=d+4*x+6;x=x+1;}}圆弧的bresenham算法XY01234567899876543210P139例子：用Bresenham画圆算法生成X2+Y2-64=0第1象限的1/4圆弧。同理可以推导出圆心不在原点的第1象限圆弧的di的递推公式(di+1与di之间的关系)。圆方程为:(X–Xc)2+(Y–Yc)2-R2=0BresenhamCircle(xc,yc,r,color)intxc,yc,r,color;{intx,y,d;x=0;y=r;d=3-2*r;while(xy){circle-pointS(x,y,color);if(d=0){d=d+4*(x-y)+10;y=y-1;}elsed=d+4*x+6;x=x+1;}if(x=y)circle-pointS(x,y,color);}适合圆心在（xc,yc)的Bresenham画圆周算法其中circle-pointS(x,y,color){putpixel(x+xc,y+yc,color);putpixel(y+xc,x+yc,color);putpixel(y+xc,-x+yc,color);putpixel(x+