图形学讲义.ppt

第二章 基本图形生成算法 　本章将主要研究在光栅显示器上的直线、圆的生成算法。 　 一、直线的生成算法 　即是找出逼近直线的一组象素，按扫描线顺序，对这些象素进行写操作。 1. 数值微分法（ＤＤＡ） 假定直线的起点、终点分别为：（X0,Y0), (X1,Y1)，且都为整数。　 直线的斜率： 　　　k = (Y1-Y0)/(X1-X0) 为讨论方便，假定 |k|=1 直线方程： 　　　Ｙ= k*X+B 设Ｘ的增量为Ｄx=１，可得如下Ｙ的增量方程： Yi+1 = k Xi+1 + B = k (Xi + Dx) + B = kXi + B + k Dx = Yi + k Dx = Yi + k 程序实现： DDALine(X0,Y0,X0,Y0,Color) int X0,Y0,X1,Y1,Color; { int X float dx,dy,k,y dx=x1-x0; dy=y1-y0; k=dy/dx; y=Y0; for(x=X0;x=X1;x++){ drawpixel(x,int(y+0.5),Color); y=y+k; } } 2. 中点画线法 原理： 算法实现： 假设直线的起点、终点分别为：（X0,Y0),(X1,Y1) 该直线方程可表示为： F(x,y)=a*x+b*y+c （1） 其中： a=Y0-Y1, b=X1-X0, c=X0*Y1-X1*Y0 当： F(Xt,Yt) = 0 ++ (Xt,Yt) 在直线上 F(Xt,Yt) 0 ++ (Xt,Yt) 在直线下方 F(Xt,Yt) 0 ++ (Xt,Yt) 在直线上方 因此：将中点M坐标代入（1）式，并判断其符号即可确定象素点的选取。构造如下判别式： d = F(M)=F(Xp+1,Yp+0.5)=a(Xp+1)+b(Yp+0.5)+c 由上式可看出，d是x,y线性函数，可推导d的增量公式。 当d= 0时，取象素P1，此时再下一个象素的判别式为： d’ = 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; 当d 0 时， 取象素P2，此时再下一个象素的判别式为： d’ = 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; 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，这样可得如下中点算法程序： MidpointLine(X0,Y0,X1,Y1,Color) int X0,Y0,X1,Y1,Color; { int a,b,d1,d2,d,x,y; a=Y0-Y1; b=X1-X0; d=a+a+b; d1=a+a; d2=a+b+a+b; x=X0; y=Y0; drawpixle(x,y,Color);