二维基本图形生成2课件.ppt

第二讲 二维基本图形生成;扫描转换直线段 DDA算法 中点画线法 Bresenham算法 圆弧、椭圆弧扫描转换 中点算法 Bresenham算法 内接多边形迫近法* 等面积多边形逼近法*;1 简单的二维图形显示流程;;2 直线段的扫描转换;;; 条件： 待扫描转换的直线段： 斜率： 直线方程： 直接求交算法： 划分区间[x0,x1]: 计算纵坐标： 取整： ; 复杂度：乘法+加法+取整 DDA算法（增量算法） 复杂度：加法+取整 程序;DDA画线算法程序;举例：用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段;;改进算法（增量DDA）;DDA画线算法程序（改进）;;DDA直线绘制的C++实现void DDA直线绘制(HDC hdc){ int k; double x1=50,y1=50,  x2=300,y2=350; double x,y,deltx,delty,length; if (fabs(x2-x1)=fabs(y2-y1)) length=fabs(x2-x1); else length=fabs(y2-y1); deltx=(x2-x1)/length; delty=(y2-y1)/length;;画线中点算法;; ;;问题：判断距直线最近的下一个象素点 构造判别式：d=F(M)=F(Xp+1,Yp+0.5) 由d＞0，＜0可判定下一个象素， ;要判定再下一个象素，分两种情形考虑： 1）若d≥0，取正右方象素P1，再下一个象素判定， 由：d1=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c=d+a，d的增量是a 2）若d＜0，取右上方象素P2，再下一个象素， 由：d2=F(Xp+2,Yp+1.5)=d+a+b d的增量为a+b;d的初始值 d0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5*b 因(X0,Y0)在直线上，F(X0，Y0)=0,所以，d0=a+0.5*b d的增量都是整数，只有初始值包含小数，可以用2d代替d, 2a改写成a+a。 算法中只有整数变量，不含乘除法，可用硬件实现。 ;中点算法程序 MidPointLine(x0,y0,x1,y1,color) {int x0,y0,x1,y1,color; int a,b,d1,d2,x,y; a = y0-y1; b = x1 – x0; d = 2 * a +b; d1 = 2*a; d2 = 2*(a+b); x = x0; y = y0; SetPixel(x,y,color); while (xx1) { if (d0) { x++; y++; d +=d2;} else { x++; d +=d1;} SetPixel(x,y,color); } };举例 用中点画线方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段;画线Bresenham算法;工作原理：根据直线的斜率在x或y的方向每次都只递增一个象素单位，另一个方向的增量为0或1;;;;举例：用Bresenham方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 x y e 0 0 -0.5 1 0 -0.1? 0.3-1 2 1 -0.7 3 1 -0.3? 0.1-1 4 2 -0.9 5 2 -0.5;;扫描转换圆弧;;扫描转换圆弧;扫描转换圆弧;问题：与直线情形类似 圆弧的隐函数：F(X,Y)=X2+Y2-R2=0 切线斜率m in [-1,0] 中点 M=(Xp+1,Yp-0.5), 当F(M)＜0时，M在圆内，说明P1距离圆弧更近，取P1； 当F(M)＞0时，P取P2;构造判别式 d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1)2+(Yp-0.5)2-R2 1）若d＜0，取P1，再下一个象素的判别式为： d1=F(Xp+2,Yp-0.5)=d+2Xp+3， 沿正右方向，d的增量为2Xp+3； 2）若d≥0，取P2，再下一个象素的判别式为： d2=F(Xp+2,Yp-1.5)=d+(2Xp+3)+(-2Yp+2) 沿右下方向，d的增量为2(Xp-Yp)+5 d的初始值(在第一个象素(0,R)处), d0=F(1, R-0.5)=1.25