第四章 基本图形生成算法 (一) 2019/4/21 Thank you for your time today. Believe I have a lot of good information to share with you today – it’s been just a little over a year since we introduced the notion of e-business on demand – know that there’s been a lot written about it … lots of competitors have begun to describe notions that sound very similar. Today I want to spend the majority of our time together moving the discussion from the what and why of becoming an on demand business to the how – to some very concrete essentials, methodologies and offerings that we’ve spent the last year developing. But before I get into specifics on the how to – I do want to spend a few minutes up front – setting a little context. 2019/4/21 IBM Confidential

基本图形生成算法 图形的扫描转换：确定象素几何与颜色，用于显示图形的过程； 本章讨论基本图形的扫描转换问题： 图形扫描转换步骤： 点、直线、圆、椭圆的扫描转换； 二维图形（多边形）的填充； 字符的表示及输入、输出； 图形的裁剪和反走样； 图形扫描转换步骤： 1）确定有关象素； 2）用图形的颜色或其它属性，对象素进行某种写操作； 图元的生成:完成图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。也称扫描转换图元。 2019/4/21

点的扫描转换 定义：将图形区域上的数学点(x,y)->(x’,y’)的象素点； 扫描转换方法： 方法一： X’=Floor(x), y’=Floor(y) 取x,y的整数部分作为x’,y’ 例：P1(1.7,0.8)->(1,0); P2(2.2,1.3),P3(2.8,1.9)->(2,1) 方法二： X’=Floor(X+0.5),Y’=Floor(Y+0.5) 即(x,y)所在的坐标系统的原点放在象素（0，0）的中心； 所有满足X’-0.5≤X<X’+0.5和Y’-0.5 ≤Y<Y’+0.5的点都映射在象素点(X’,Y’)处； 例：P1,p2->(2,1),p3->(3,2) 2019/4/21

主要内容： 直线的扫描转换 圆与椭圆的扫描算法 区域填充 线宽与线型的处理 字符 裁剪 反走样 2019/4/21

直线的扫描转换 计算机图形学中的一条直线通常指一条线段。 直线的扫描转换：确定一组有限象素，显示出来的过程； 线段表示方程：y = kx + b（斜截式方程） 斜截式方程不适合垂直线； 水平线、垂直线、对角线（∣k∣=1）作为特殊直线考虑； 直线扫描算法： 直接使用直线方程 数值微分算法 中点画线法 Bresenham画线算法 2019/4/21

缺点：浮点运算（乘法和加法）－》计算复杂； 直线的扫描转换－直接使用直线方程 最简单的方法； 步骤： 1、将P1,P2分别转换为象素坐标（x1’,y1’）,（x2’,y2’）; 2、设置k=(y2’-y1’)/(x2’-x1’)和b=y1’-kx1’; 3、如果∣k∣≤1，对(x1’,x2’)开区间的整数x代入方程得到y－》得到(x,y)； 3、如果∣k∣>1，对(y1’,y2’)开区间的整数y代入方程得到x－》得到(x,y); 优点：简单 缺点：浮点运算（乘法和加法）－》计算复杂； 2019/4/21

直线的扫描转换－数值微分算法(DDA,Digital Differential Analyzer) 2019/4/21

直线的扫描转换－数值微分算法(DDA,Digital Differential Analyzer) 复杂度：乘法 + 加法 + 取整 2019/4/21

直线的扫描转换－数值微分算法(DDA,Digital Differential Analyzer) 优点：比直接用直线方程的方法快：没有浮点乘法； 缺点：求每个连续点时，需要浮点加法；加0.5舍尾取整，不利于硬件实现；表示长直线时，由于精度限制－》累计误差； 2019/4/21

目标：消除DDA算法中的浮点运算（浮点数取整运算，不利于硬件实现；DDA算法效率低）； 原理： 直线的扫描转换－中点画线法 目标：消除DDA算法中的浮点运算（浮点数取整运算，不利于硬件实现；DDA算法效率低）； 原理： 1、确定与直线距离最近的点P； 2、利用点P确定下一个点； 条件：同DDA算法 假设斜率： 直线段的隐式方程 2019/4/21

直线的扫描转换－中点画线法 直线的正负划分性 直线上方点：F( x，y)＞0 直线下方点: F( x，y)＜0 2019/4/21

构造判别式：d=F(M)=F(Xp+1,Yp+0.5) 由d＞0，＜0可判定下一个象素. 直线的扫描转换－中点画线法 问题：判断距直线最近的下一个象素点 构造判别式：d=F(M)=F(Xp+1,Yp+0.5) 由d＞0，＜0可判定下一个象素. 如果：d = 0? 任选一个,(约定取正右方P1)； P P2 P1 2019/4/21

P2 P1 P 直线的扫描转换－中点画线法 判定再下一个象素，分两种情形考虑： 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 P2 P P1 2019/4/21

d的初始值：第一个象素应取左端点（x0,y0） d0 = F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5b 直线的扫描转换－中点画线法 d的初始值：第一个象素应取左端点（x0,y0） d0 = F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5b 因(X0,Y0)在直线上，F(X0，Y0)=0,所以，d0=a+0.5b d的增量都是整数，只有初始值包含小数，可以用2d代替d,以摆脱浮点数, 2a改写成a + a。 算法中只有整数变量，不含乘除法，可用硬件实现。 程序：见PP168 自习书中pp168的例子； 2019/4/21

直线的扫描转换－Bresenham画线算法 算法基本思想：每次迭代在增量最大方向上均走一步，其方向由增量的正负而定，另一方向上是否也走，取决于计算出来的点与直线上的点的误差，根据误差决定是否走一步。例如取X方向为最大增量方向，则有： 绘制直线时点的选取: 2019/4/21

直线的扫描转换 －Bresenham画线算法 偏差计算： 设偏差为 当 时，计算的点（实际直线上的点）在 中点的上方，取 当 < 0 时，计算的点（实际直线上的点）在 中点的下方，取 整理后，有 2019/4/21

直线的扫描转换 －Bresenham画线算法 偏差的递推关系： 误差 因为 有 2019/4/21

直线的扫描转换 －Bresenham画线算法 算法优点： 快速增量算法； 要获得准确的数学结果，只需通过整数的加、减法和乘2运算； 计算机中乘2可以容易的通过算术移位实现； 直线的扫描转换－小结 前面介绍的数值微分法、中点画线法以及Bresenham算法，它们各有优缺点。因此在使用不同的图形输设备时要选用最适合于该设备的方法。 2019/4/21

直线的扫描转换 －Bresenham画线算法 习题： 给出使用中点画线算法画斜率介于0到45度之间的直线所需的步骤。 解答： 1、计算初始值：dx=x2-x1; dy = y2 – y1; lnc1=2dy; lnc2 = 2(dy – dx)；d = lnc1-dx 2、设置左下方的端点坐标为（x,y）,同时将Xend设为x的最大值。如果dx<0,则x=x2,y=y2,Xend=x1. 如果dx>0，则x=x1,y=y1,Xend=x2; 3、在当前（x，y）坐标画一个点； 4、判断整条线段是否已经画完，如果x=Xend，则停止； 5、计算下一个象素的位置，如果d<0，那么d=d+lnc1，如果d>=0,则d=d+lnc2,且y=y+1; 6、增加x:x=x+1; 7、在当前的(x,y)坐标画一个点； 8、转到步骤4； 2019/4/21

主要内容： 直线的扫描转换 圆与椭圆的扫描算法 多边形的扫描转换 区域填充 线宽与线型的处理 字符 裁剪 反走样 2019/4/21

圆的扫描转换 处理对象：圆心在原点的圆弧 圆的八路对称性：每隔45度对称计算圆上的点； 2019/4/21

圆的扫描转换 两种直接离散方法： 离散点: 离散角度: 开根，三角函数运算，计算量大，不可取。 2019/4/21

圆的扫描转换 高效画圆方法：避免三角计算和乘方计算，计算只涉及整数的加减法和乘2运算：中点法和Bresenham算法； 圆弧的正负划分性 圆弧外的点：F(X，Y)＞0 圆弧内的点：F(X，Y)＜0 2019/4/21

圆的扫描转换(中点算法) 生成圆弧的中点算法:利用圆的对称性，只须讨论1/8圆 考虑对象：第二个八分圆， 第一象限的八分之一圆弧 P P1 2019/4/21

圆的扫描转换(中点算法) 问题：与直线情形类似; 圆弧的隐函数： F(X,Y)=X2+Y2-R2=0 切线斜率k为[-1,0] 中点M=(Xp+1,Yp - 0.5), 当F(M)＜0时，M在圆内，说明P1距离圆弧更近，取P1； 当F(M)＞0时，P取P2 P2 P1 P 2019/4/21

圆的扫描转换(中点算法) 构造判别式 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)=(0+1)×(0+1)+(R-0.5)×(R-0.5)-R×R=1.25-R 算法中有浮点数：用e=d-0.25代替d0：少0.25不改变d的符号，也不影响以后的扫描转换过程：d只在后面计算中整数递增； 2019/4/21

圆的扫描转换(中点算法) 初始化运算d0 = 1.25 – R 对应于 e0= 1- R 判别式 d < 0 对应于 e < -0.25 又因为：e的初值e0为整数，运算过程中的分量也为整数， 故e始终为整数 所以： e < -0.25 等价于 e < 0 程序见pp170（完全用整数实现） 2019/4/21

圆的扫描转换(Bresenham 算法) 为讨论方便，仅考虑圆心在原点，半径为R的第一象限上的一段圆弧。且取（0，R）为起点，按顺时针方向(+x, -y方向)绘制该1/4圆弧（如图1）。 算法原理 ：如图2所示，从当前点亮象素（x,y）出发，按顺时针方向生成圆时，最佳逼近该圆的下一个象素只可能为H、D、V三象素之一。H、D、V中距圆周边界距离最小者，即为所求的象素点； (0,R) 图1 （x，y） H（x+1，y） D（x+1，y-1） V（x，y-1） 图2 2019/4/21

圆的扫描转换(Bresenham 算法) H D V (x,y) 1 2 3 4 5 图3 具体算法： H、D、V三点到圆心的距离平方与圆的半径平方差，即为H、D、V到圆弧距离的一种度量： H = (x+1) 2 + y2 - R2; D = (x+1) 2 + (y-1) 2 - R2; （式1） V = x2 + (y-1) 2 - R2; 为根据这些度量值可确定最佳象素点，首先，将H、D、V与理想圆弧的关系进行分类。如下图所示，存在以下五种情况： H D V (x,y) 1 2 3 4 5 图3 2019/4/21

圆的扫描转换(Bresenham 算法) （见上图） 1）H、D、V全在圆内； 2）H在圆外，D、V在圆内； 3）D在圆上，H在圆外，V在圆内； 4）H、D在圆外，V在圆内； 5）H、D、V全在圆外。 同Bresenham画线算法，按照不同类型，找出误差度量的递推公式，判别它的正、负性即可确定最佳逼近的象素点。 当D < 0,只能为1或2种情况。为确定是H还是D，用如下判别： δHD = |H| - |D| δHD ≤ 0 则应选H，否则选D。 2019/4/21

圆的扫描转换(Bresenham 算法) 对于第2种情况： δHD = H + D = (x+1)2 + y2 - R2 + (x+1)2 + (y-1)2 - R2 =2 D + 2y - 1 对于第1种情况： ∵　y是x的单调递减函数 　　∴　H为下一点亮象素。（见图3） 另，此时H < 0 和 D < 0 H + D = 2D + 2y - 1 < 0 综上两种情况可得如下结论： 在D＜0时，若2（D + y) - 1≤0，则取H，否则取D 2019/4/21

圆的扫描转换(Bresenham 算法) 当D＞0,有4、5两种情况，且最佳象素点为D或V，用如下判别： δDV = | D |- | V | δDV ≤　0 则应选D，否则选V。（见图3） 对于第4种情况： δDV = D + V （ D ＞0，V ＜0） = (x+1)2 + (y-1)2 - R2 + (x)2 + (y-1)2 - R2 = 2(D - x) - 1 对于第5种情况： D,V都在圆外，显然V为所选象素。 注意：∵ D ＞0， V＞0 ∴ D + V = 2(D - x) - 1 ＞ 0 2019/4/21

圆的扫描转换(Bresenham 算法) 综上两种情况可得如下结论： 在 D＞ 0时，若2（ D -x) - 1 ≤0，则取D，否则取V 总结上述分析结果：（见图3） 当D ＞ 0， 若 2(D - x) - 1 ＞ 0，取D，否则取V 当D ＜ 0，若 2 ( D +y) - 1 ≤0，取H，否则取D 当D = 0， 取D。 关键的问题就是计算 D （见 D的计算公式：式1） 采用增量法，获得D的计算公式： 2019/4/21

圆的扫描转换(Bresenham 算法) 分三种情况：（见图3） 下一象素为H时 H=(x’, y’)=(x+1,y) D=((x+1)+1)2 +(y-1)2 - R2 =(x+1)2 + (y-1)2 -R2 + 2(x+1) + 1 = D +2(x+1) + 1 下一象素为D时 D=(x’, y’)=(x+1,y-1) D=((x+1)+1)2 +((y-1)-1)2 - R2 =(x+1)2 + (y-1)2-R2 + 2(x+1) - 2(y-1) + 1 = D +2(x+1) - 2(y-1) + 2 2019/4/21

圆的扫描转换(Bresenham 算法) 下一象素为V时 （见图3） V=(x’,y’)=(x,y-1) D=(x+1)2 +((y-1)-1)2 - R2 =(x+1)2 + (y-1)2 -R2 - 2(y-1) + 1 = D - 2(y-1) + 1 有了上述 D的递推计算公式，还需计算出D的初值。 ∵ 圆弧的起点为（0，R） ∴ D的初值为： D = (0+1)2 +(R-1)2-R2 = 2 (1-R) 程序见pp175 2019/4/21

圆的扫描转换(任意圆心位置的圆) 上述算法假设圆的圆心在坐标系的原点； 若圆的圆心在（Xc,Yc）点，则扫描转换算法将SetPixel(x,y)改为SetPixel(x+Xc,y+Yc); 这样，就能够实现任意圆心位置圆的扫描转换算法； 2019/4/21

圆的扫描转换 1、设置初始变量(h,k)=圆心坐标；x=0;y=圆的半径r；d=3-2r; 习题：使用Bresenham算法扫描转换圆的步骤是什么？ 解答： 1、设置初始变量(h,k)=圆心坐标；x=0;y=圆的半径r；d=3-2r; 2、测试整个圆是否已经扫描转换完。如果x>y则停止； 3、以中心（h,k）为对称点，对当前的(x,y)坐标画8个圆上的点： Plot(x+h,y+k); plot(-x+h,-y+k);plot(y+h,x+k);plot(-y+h,-x+k) Plot(-y+h,x+k);plot(y+h,-x+k);plot(-x+h,y+k);plot(x+h,-y+k); 4、计算下一个象素的位置，如果d<0,则d=d+4x+6,和x=x+1.如果d>=0,则d=d+4(x-y)+10、x=x+1、y=y-1. 5、转到步骤2； 2019/4/21

圆的扫描转换 习题：当使用8路对称方法从0度到45度或90度到45度的8分圆中生成整个圆时，有些象素被设置或画了两次，这种现象称为重击。请说明如何判断重击发生？ 解答： 在初始坐标为（r,0)或(0,r)时的位置。因为（0,r）= （-0,r）, （0,-r）= （-0,-r）, （r,0）= （r,-0）, （-r,0）= （-r,-0）; 如果最后生成的象素在对角线上，坐标为（ar,ar），其中a约为0.7071,则在(ar,ar)、(-ar,ar)、(ar,-ar)、(-ar,-ar)处会发生重击； 习题：重击除了浪费时间外还有其它坏处吗？ 通常不会有问题； 但是如果直接操纵输出设备，可能有问题； 2019/4/21

椭圆的扫描转换 四路对称； 数学上定义椭圆的两种方法： 旋转椭圆轴 多项式定义： 其中（h,k）为椭圆中心点；a为长轴长；b为短轴长； 极坐标定义： 旋转椭圆轴 90度旋转： 其它角度旋转： 2019/4/21

椭圆的扫描转换(中点法) 中点法：增量算法 椭圆的特征：a, b均为整数 由于对称性－》讨论第一象限 2019/4/21

椭圆的扫描转换(中点法) 椭圆方程： 对于椭圆上的点，有F(x,y)=0； 对于椭圆外的点，F(x,y)>0； 2019/4/21

椭圆的扫描转换(中点法) 椭圆的特征： 以弧上斜率为－1的点作为分界将第一象限椭圆弧分为上下两部分。如图所示： 上部分：y分量大 下部分：x分量大 2019/4/21

椭圆的扫描转换(中点法) 椭圆的特征： 法向量： 若在当前中点，法向量的y分量比x分量大，即 在下一个中点，不等号改变方向，说明椭圆弧从上部分转入下部分。 2019/4/21

椭圆的扫描转换(中点法) 椭圆的中点算法 算法原理 1、上半部分： M（Xi+1，Yi-0.5) 2、下半部分： 2019/4/21

椭圆的扫描转换(中点法) 先推导上半部分的椭圆绘制公式 2019/4/21

椭圆的扫描转换(中点法) 判别式 若d1≤0，取Pu(xi+1,yi) 若d1>0，取Pd(xi+1,yi-1) Pxi,yi Puxi+1,yi M(xi+1,yi-0.5) Pd(xi+1,yi-1) 上半部分椭圆弧的绘制原理 2019/4/21

椭圆的扫描转换(中点法) 误差项的递推 d1≤0： 2019/4/21

椭圆的扫描转换(中点法) 误差项的递推 d1> 0： 2019/4/21

椭圆的扫描转换(中点法) 判别式的初始值P0(0,b) M0(1，b-0.5) 2019/4/21

椭圆的扫描转换(中点法) 再推导椭圆弧下半部分的绘制公式: 原理: 2019/4/21

椭圆的扫描转换(中点法) 判别式 : 若d2>0，取Pl(xi,yi-1) 若d2≤0，取Pr(xi+1,yi-1) 2019/4/21

椭圆的扫描转换(中点法) 误差项的递推: d2>0： 2019/4/21

椭圆的扫描转换(中点法) 误差项的递推: D2 ≤ 0： 2019/4/21

椭圆的扫描转换(中点法) 注意： 上半部分的终止判别; 下半部分误差项的初值; 算法步骤 (1/3): 1.输入椭圆的长半轴a和短半轴b; 2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b; 3.绘制点(x,y)及其在四分象限上的另外三个对称点; 2019/4/21

椭圆的扫描转换(中点法) 算法步骤 (2/3): 4.判断d的符号。若d≤0，先将d更新为d+b2(2x+3)，再将(x, y)更新为(x+1,y)；否则将d更新为d+b2(2x+3)+a2(-2y+2)，再将(x,y)更新为(x+1,y-1); 5.当b2(x+1)<a2(y-0.5)时，重复步骤3和4。否则转到步骤6; 6.用上半部分计算的最后点(x,y)来计算下半部分中d的初值： 2019/4/21

椭圆的扫描转换(中点法) 算法步骤 (3/3): 7.绘制点(x,y)及其在四分象限上的另外三个对称点; 8.判断d的符号: 若d≤0，则先将d更新为b2(2xi+2)+a2(-2yi+3)，再将(x,y)更新为(x+1,y-1)； 否则先将d更新为d+a2(-2yi+3)，再将(x,y)更新为(x,y-1); 9.当y>0时，重复步骤7和8。否则结束; 程序：见pp178 2019/4/21

弧、扇形弧的扫描转换 弧 可以用多项式或极坐标表示； 用极坐标，始角和终角分别设为 其余步骤与圆的扫描转换类似，只是不能使用对称性； 多项式表示：x的值在(X1,X2)间变化，y的值可以利用 从编程角度：弧仅是圆的一部分，但是Bresenham画圆算法画弧有问题： 算法中，弧端点必须用X,Y坐标表示； 若要确定端点，必须在每个45度弧的增量上判断其是否为端点； 由对称产生的8个端点也要进行判断，确定这些点是否在指定弧的两端点间； 所以，必须化时间计算和判断圆周上的每个点； 还可能引发端点丢失－》程序进入死循环； 原公式的执行效率降低。 2019/4/21

弧、扇形弧的扫描转换 扇形 可以通过生成的弧加上两条连接弧心和端点的直线生成； 2019/4/21

Thank you! Best Wishes! 谢谢! 2019/4/21