哈尔滨工业大学计算机学院唐好选.ppt

基本图形生成算法 图元扫描转换 直线段扫描转换 圆弧扫描转换 实区域填充 图形反走样技术 光栅图形中点的表示 光栅图形中点的表示 光栅图形中点的表示 图形显示的几种方式 图形显示前需要：扫描转换+裁剪 裁剪→扫描转换：最常用，节约计算时间 扫描转换→裁剪：算法简单 直线段扫描转换 假设 像素间均匀网格，整型坐标系，直线段斜率0m1 对m＞1，x、y互换 直线段的扫描转换算法 直线的扫描转换 确定最佳逼近于该直线的一组象素 按扫描线顺序，对这些象素进行写操作 三个常用算法： - 数值微分法（DDA） - 中点画线法 - Bresenham算法 数值微分(DDA)法(1/5) 已知线段端点：P0(x0,y0), P1(x1,y1) 直线方程 y=kx+b， {(xi, yi)}, i=0,….n. 浮点数取整 : yi=round(yi)=(int)(yi+0.5) 用到浮点数的乘法、加法和取整运算 数值微分(DDA)法(2/5) 增量算法 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互换。 数值微分(DDA)法(3/5) digital differential analyzer 基本思想 用数值方法解微分方程 dx/dt = ?x dy/dt = ?y xn+1 = xn + ??x yn+1 = yn + ??y 数值微分(DDA)法(4/5) 简单的DDA 取?= 1/max(|?x |,|?y|) 使 ?|?x |, ?|?y|中必有一个是单位步长 ?x为最大时， ??x =1, ??y =k ?y为最大时， ??y =1, ??x =1/k 数值微分(DDA)法(5/5) 缺点： 浮点数运算 不易硬件实现 数值微分(DDA)法 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.5b =a+0.5b 用2d代替d后，d0=2a+b=a+a+b d的增量都是整数 优点： 只有整数运算，不含乘除法 可用硬件实现 About Bresenham E.Jack Bresenham Professor of Computer Science Ph.D., Stanford University, 1964 MSIE, Stanford University, 1960 BSEE, University of New Mexico, 1959 Retired from 27 years service at IBM as a Senior Technical Staff Member in 1987. Have taugh