计算机图形学课件之第3章_基本图形生成算法1.ppt

第三章 基本图形生成算法 基本图形生成算法 图元扫描转换 直线段扫描转换 圆弧扫描转换 实区域填充 图形反走样 光栅图形中点的表示 光栅图形中点的表示 光栅图形中点的表示 直线段扫描转换 假设 像素间均匀网格，整型坐标系，直线段斜率0m1 对m＞1，x、y互换 直线段的扫描转换算法 直线的扫描转换 确定最佳逼近于该直线的一组象素 按扫描线顺序，对这些象素进行写操作 三个常用算法： 1数值微分法（DDA） 2中点画线法 3Bresenham算法。 数值微分(DDA)法 已知线段端点：P0(x0,y0), P1(x1,y1) 直线方程 y=kx+b {(xi, yi)}, i=0,….n. 浮点数取整 : yi=round(yi)=(int)(yi+0.5) 用到浮点数的乘法、加法和取整运算 数值微分(DDA)法 增量算法 yi+1=kxi+1+b=k(xi+1)+b=yi+k (xi,yi)→(xi+1,yi+k) 缺点： 有浮点数取整运算 不利于硬件实现 效率低 仅适用于?k? ≤1的情形:x每增加1,y最多增加1。当 ?k? ?1时，必须把x，y互换。 例：画直线段P0(0,0)--P1(5,2) x int(y+0.5) y+0.5 0 0 0 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 注：网格点表示象素 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； ? ? 中点画线法（1/4） 问题：判断距离理想直线最近的下一个象素点 已知：线段两端点(x0,y0)，(x1,y1) 直线方程：F(x,y)=ax+by+c=0 a=y0-y1 b=x1-x0 c=x0y1-x1y0 中点画线法（2/4） 直线上方点： F(x,y)＞0 直线下方点: F(x,y)＜0 构造判别式： d=F(M)=F(Xp+1,Yp+0.5) 由d＞0，d＜0可判定下一个象素 分两种情形考虑再一下个象素的判定： 若d≥0，中点M在直线上方，取正右方象素P1 (Xp+1,Yp) 再下一个象素的判别式为： d1=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a d的增量为a 若d＜0，中点M在直线下方，取右上方象素P2 (Xp+1,Yp+1) 再下一个象素的判别式为： d2=F((Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c =d+a+b d的增量为a+b 中点画线法（4/4） d的初始值 d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5 =a+0.5b 用2d代替d后，d0=2a+b d的增量都是整数 优点： 只有整数运算，不含乘除法 可用硬件实现 例：用中点画线法P0（0,0) P1（5,2) a = y0-y1=-2, b = x1-x0 = 5 d0 = 2a+b = 1, d1= 2a = - 4, d2 = 2(a+b)=6 i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5 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 {x++； d+=d1;} drawpixel (x, y, co