《图形学教材课件第3章基本图形生成算法1章节》由会员分享，可在线阅读，更多相关《图形学教材课件第3章基本图形生成算法1章节（39页珍藏版）》请在金锄头文库上搜索。
1、第三章 基本图形生成算法,计算机学院 苏小红,图形的扫描转换,基本图形生成算法,图元扫描转换 直线段扫描转换 圆弧扫描转换 实区域填充 图形反走样,光栅图形中点的表示,像素由其左下角坐标表示,光栅图形中点的表示,地址 = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址,每行像素点数,行数,行中位置,光栅图形中点的表示,Address(x,y) = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址 = k1 + k2y + x,Address(x1,y) = k1 + k2y + (x1) = Address(x,y) 1,Addre
2、ss(x,y1) = k1 + k2(y 1) + x = Address(x,y) k2,Address(x1,y1) = k1 + k2(y 1) + (x1) = Address(x,y) k2 1,对像素连续寻址时，如何减少计算量？,增量法的优点？,图形显示的几种方式,图形显示前需要：扫描转换+裁剪 裁剪扫描转换：最常用，节约计算时间 扫描转换裁剪：算法简单,直线段扫描转换,假设 像素间均匀网格，整型坐标系，直线段斜率0m1 对m1，x、y互换,直线段的扫描转换算法,直线的扫描转换 确定最佳逼近于该直线的一组象素 按扫描线顺序，对这些象素进行写操作 三个常用算法： 1数值微分法（DDA
3、） 2中点画线法 3Bresenham算法。,数值微分(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),d
4、igital differential analyzer 基本思想 用数值方法解微分方程 dy/dt = x dy/dt = y xn+1 = xn + x yn+1 = yn + y,如何选取？,选取的原则：使0.5|x|,|y|1,数值微分(DDA)法(4/5),对称的DDA 取=2-n 使 2n-1max(|x |,|y|)2n 简单的DDA 取= 1/max(|x |,|y|) 使 |x |, |y|中必有一个是单位步长 x为最大时， x =1, x =k y为最大时， y =1, y =1/k,数值微分(DDA)法(5/5),缺点： 浮点数运算 不易硬件实现,中点画线法（1/4）,问
5、题：判断距离理想直线最近的下一个象素点 已知：线段两端点(x0,y0)，(x1,y1) 直线方程：F(x,y)=ax+by+c=0 a=y0-y1 b=x1-x0 c=x0y1-x1y0,M,如何判断M点在Q点上方还是在Q点下方？,M,P1,P2,P,直线上方点： F(x,y)0 直线下方点: F(x,y)0 构造判别式： d=F(M)=F(Xp+1,Yp+0.5) 由d0，d0可判定下一个象素,(Xp+1,Yp+0.5),中点画线法（2/4）,分两种情形考虑再一下个象素的判定： 若d0，中点M在直线上方，取正右方象素P1 (Xp+1,Yp) 再下一个象素的判别式为： d1=F(Xp+1)+1
6、,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a d的增量为a 若d0，中点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,d的初始值 d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5 =a+0.5b 用2d代替d后，d0=2a+b d的增量都是整数 优点： 只有整数运算，不含乘除法 可用硬件实现,因(X0,Y0)在直线上，所以F(X0,Y0)=0,中点画线法（4/4）,Bresenham画线算法（1
7、/7）,使用最广泛 与中点画线法的思想类似 由误差项符号决定下一个象素取正右方像素还是右上方像素,Bresenham画线算法（2/7）,基本思想 比较从理想直线到位于直线上方的像素的距离d1和相邻的位于直线下方的像素的距离d2 根据距离误差项的符号确定与理想直线最近的象素,Bresenham画线算法（3/7）,最大位移方向每次走一步 k1时，x为最大位移方向 y方向走步与否 取决于误差e值的大小 误差计算 初值：e0= y/ x 当e0.5时，最接近P2(xi+1,yi+1) y方向走一步 当e0.5时，最接近P1(xi+1,yi) y方向不走步,Bresenham画线算法（4/7）,为方便与
8、0比较，设e=e-0.5 e0=y/ x-0.5 当e0时，最接近P2(xi+1,yi+1) y方向走一步 当e0时，最接近P1(xi+1,yi) y方向不走步 有除法，不宜硬件实现,Bresenham画线算法（5/7）,设e=e2x，不影响判断的准确性 e0=2y - x 当e0时，最接近P2(xi+1,yi+1) y方向走一步 当e0时，最接近P1(xi+1,yi) y方向不走步,Bresenham画线算法（6/7）,下一步误差的计算 当e0时，y方向走一步 e=2y/ x - 1 =e + y/ x - 1 e=e + 2y - 2x 当e0时，y方向不走步 e=2y/ x=e + y/
9、 x e=e + 2y,Bresenham画线算法（7/7）,优点 整数运算，速度快 精度高 乘2运算可用移位实现，适于硬件实现,圆弧的扫描转换,圆的八对称性 只考虑第二个八分圆 假设圆心在原点 x2+y2=R2,圆弧的扫描转换,两种直接离散生成方法 离散点 开方运算 离散角度 三角函数运算 缺点： 计算量大 所画像素位置间的间距不一致,中点画圆法（1/2）,F(X,Y)=X2+Y2-R2=0 中点 M=(Xp+1,Yp-0.5) 当F(M)0时，M在圆内，P1距离圆弧近，取P1 当F(M)0时，M在圆外，P2距离圆弧近，取P2,中点画圆法（2/2）,若 d=0, 取P1为下一象素，再下一象素
10、的判别式为 初始象素是（0,R），判别式d的初值为,P1(Xp+1,Yp),P2(Xp+1,Yp-1),使用e=d-0.25代替d e0=1-R,DDA画圆法（1/3）,圆的方程：f(x,y)=x2+y2-R2=0 全微分：df(x,y)=2xdx+2ydy=0 微分方程：dy/dx=-x/y 递推方程: (yn+1-yn)/ (xn+1-xn)=-xn/ yn xn+1 - xn = yn yn+1 - yn = -xn,实际画出的曲线不是圆，而是螺旋线，为什么？,DDA画圆法（2/3）,将递推公式写成矢量形式： 构造一个行列式值为1的矩阵 对应的圆方程递推关系为 xn+1 = xn + y
11、n yn+1 = -xn +(1-2)yn= yn- xn+1,DDA画圆法（3/3）,针对不同象限及顺逆时针画圆，赋给适当的符号 不同，圆形状不同， 大近似椭圆,Bresenham画圆算法（1/7）,顺时针画第一四分圆，下一步选择哪个点？ 基本思想： 通过比较像素与圆的距离平方来避免开方运算 下一像素有3种可能的选择 mH=|(xi+1)2+yi2-R2| mD=|(xi+1)2+(yi-1)2-R2| mV=|xi2 +(yi-1)2-R2 | 选择像素的原则 使其与实际圆弧的距离平方达到最小,Bresenham画圆算法（2/7）,圆弧与点(xi,yi)附近光栅网格的相交关系有5种 右下角
12、像素D (xi,yi)与实际圆弧的近似程度 i=(xi+1)2+(yi-1)2-R2 当i0时，D在圆外， 当i=0时，D在圆上，,Bresenham画圆算法（3/7）,当i0，则选D 若d=0，则选H,情形也适用,Bresenham画圆算法（4/7）,当i0时，D在圆外， 情形，选mv ，mD 中最小者 d=mD - mV =|(xi+1)2+(yi-1)2-R2 | - |xi2+(yi-1)2-R2| =(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2 =2 (i-xi)-1 若d0，则选V 若d=0，则选D,情形也适用,Bresenham画圆算法（5/7）,当i=
13、0时，D在圆上， 按d判别，有d0，应选D 按d判别，有d0，应选D,Bresenham画圆算法（6/7）,当i0，选D 当i0时, 若d 0，选D 若d0，选V 当i=0时，选D,Bresenham画圆算法（7/7）,判别式的递推关系 当取H(xi+1,yi)时 i+1=(xi+1+1)2+(yi-1)2-R2= i+2(xi+1)+1 当取V(xi,yi-1)时 i+1=(xi+1)2+(yi-1-1)2-R2= i-2(yi-1)+1 当取D(xi+1,yi-1)时 i+1=(xi+1+1)2+(yi-1-1)2-R2= i+2(xi+1)-2(yi-1)+2,多边形逼近法,当圆的正内接多边形边数足够多时，可以用画该多边形近似代替画圆 “以直代曲”的代表方法之一 内接正n边形顶点为Pi(xi, yi) 每条边对应的圆心角为，则有,
