计算机图形学教学PPT2 基本图形生成算法(直线、圆).ppt

第4章 扫描转换 鲁萍 第四章 基本图形生成算法 4.1 直线段的扫描转换 4.2 圆弧的扫描转换 4.7 反走样 直线段扫描转换 假设 像素间均匀网格，整型坐标系，直线段斜率0m1 对m＞1，x、y互换 数值微分(DDA)法（1/5） 基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b 直线斜率为 数值微分(DDA)法（2/5） 计算yi+1= kxi+1+b = kxi+b+k?x = yi+k?x 当?x =1;yi+1 = yi+k 当x每递增1，y递增k(即直线斜率) ,y最多增加1 增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。 DDA算法就是一个增量算法。 数值微分(DDA)法（3/5） /* 算法2.1*/ void DDALine(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++) ? drawpixel (x, int(y+0.5), color); y=y+k; ? ? 数值微分(DDA)法（4/5） 例2.1：画直线段P0(0,0)--P1(5,2) x int(y+0.5) y+0.5 0 0 0+0.5 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5 中点画线法（1/6） 原理： 中点画线法（2/6） 问题：判断距离理想直线最近的下一个象素点 已知：线段两端点(x0,y0)，(x1,y1) 直线方程：F(x,y)=ax+by+c=0 a=y0-y1 b=x1-x0 c=x0y1-x1y0 中点画线法（3/6） 构造判别式： M(xp+1,yp+0.5) d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 中点画线法（4/6） 分两种情形考虑再一下个象素的判定： 若d≥0，中点M在直线上方，取正右方象素P1 (Xp+1,Yp) 再下一个象素的判别式为 M(xp+2,yp+0.5)： d’=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c =F(Xp,Yp)+a+0.5b+a= d+a d的增量为a 若d＜0，中点M在直线下方，取右上方象素P2 (Xp+1,Yp+1) 再下一个象素的判别式为 M(xp+2,yp+1.5) ： d’’=F((Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c =F(Xp,Yp)+a+0.5b+a+b =d+a+b d的增量为a+b 中点画线法（7/7） 例2.2：画直线段P0(0,0)--P1(5,2) a=y0-y1=-2, b=x1-x0=5, d=a+0.5b=0.5 d1=a=-2, d2=a+b=3 x y d 0 0 0.5 1 0 -1.5 2 1 1.5 3 1 -0.5 4 2 2.5 中点画线法（5/6） d的初始值 d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5 =a+0.5b 用2d代替d后，d0=2a+b d的增量都是整数 优点： 只有整数运算，不含乘除法 可用硬件实现 中点画线法（6/6） /* 算法2.2*/ 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