《图形显示软件》PPT课件.ppt

计算机图形显示技术 2 第十一讲图形软件 Bresenham画线算法圆的生成算法Bresenham画圆法中点画圆法区域填充算法扫描线填充算法边界填充算法 3 图形软件 Bresenham画线算法 AboutBresenhamE JackBresenham ProfessorofComputerSciencePh D StanfordUniversity 1964MSIE StanfordUniversity 1960BSEE UniversityofNewMexico 1959Retiredfrom27yearsserviceatIBMasaSeniorTechnicalStaffMemberin1987 Havetaught10yearsatWinthrop Holderoffivepatents 4 图形软件 Bresenham画线算法 Bresenham算法该算法由Bresenham在1965年提出 是目前使用较为广泛的一种扫描转换算法 可用于直线 圆弧等图元的扫描转换 5 图形软件 Bresenham画线算法 Bresenham画线算法基本思想过各行各列像素中心构造一组假想的栅格按直线从起点到终点的顺序计算直线与各垂直网格线的交点 然后根据误差项的符号确定该列象素中与此交点最近的象素 6 图形软件 Bresenham画线算法 Bresenham画线算法设直线从起点 x1 y1 到终点 x2 y2 设直线方程为 y kx b其中b y1 k x1 7 图形软件 Bresenham画线算法 Bresenham画线算法若直线斜率k 0 1 且x2 x1的情况 1a象限 根据即 DDA算法的讨论有 xi 1 xi 1 1 yi 1 yi k 2 在1a象限里 当直线光栅化时 x每次都增加1个单元 xi 1 xi 1 8 图形软件 Bresenham画线算法 Bresenham画线算法由于k不一定是整数 因此由 2 式求出的y也不一定是整数 所以要用最靠近y的整数yi来代替y假设直线上第i个像素坐标为 xi yi 那么 它的下一个点的像素点的可能位置为 xi 1 yi 或 xi 1 yi 1 如图 9 图形软件 Bresenham画线算法 Bresenham画线算法若直线斜率k 0 1 且x2 x1的情况 1a象限 如上图在x xi 1处 直线上y的值y k xi 1 b该点距离点 xi 1 yi 和点 xi 1 yi 1 的距离分别为d1和d2 d1 y yi k xi 1 b yid2 yi 1 y yi 1 k xi 1 b因此 这两个距离的差为 d1 d2 2k xi 1 2yi 2b 1 1 10 图形软件 Bresenham画线算法 Bresenham画线算法根据 1 式 作如下讨论分析 当d1 d2 0时 说明直线上的理论点距离 xi 1 yi 1 较近 因此下一个直线像素点应取 xi 1 yi 1 当d1 d2 0时 说明直线上的理论点距离 xi 1 yi 较近 因此下一个直线像素点应取 xi 1 yi 当d1 d2 0时 说明直线上的理论点距离上 下两个像素点的距离相等 因此规定取 xi 1 yi 1 作为下一个直线像素点 11 图形软件 Bresenham画线算法 Bresenham画线算法若直线斜率k 0 1 且x2 x1的情况 1a象限 因此 利用 d1 d2 的符号就可以决定下一个像素点的选择然而含有 变量xi yi 不利于计算 为此 我们构造一个新的判别式 pi x d1 d2 2xi y 2yi x c 2 其中 x x2 x1 0 因此pi与 d1 d2 符号相同 y y2 y1 c 2 y x 2b 1 12 图形软件 Bresenham画线算法 Bresenham画线算法若直线斜率k 0 1 且x2 x1的情况 1a象限 以i 1代入式 2 中的i 得 pi 1 x d1 d2 2xi 1 y 2yi 1 x c 3 将式 3 减去式 2 并由xi 1 xi 1可得 pi 1 pi 2 y 2 x yi 1 yi 4 假设直线上的初始端点恰好是其像素点的坐标 则将x1 y1和b代入式 2 中的xi yi可到pi的初始值p1 2x1 y 2y1 x 2 y x 2 y1 kx1 1 2 y x 5 13 图形软件 Bresenham画线算法 Bresenham画线算法若直线斜率k 0 1 且x2 x1的情况 1a象限 利用上面构造的误差判别变量 可得第1a象限内的直线Bresenham算法 p1 2 y xxi 1 xi 1yi 1 yi 1 pi 1 pi 2 y x 当pi 0时yi 1 yi pi 1 pi 2 y当pi 0时 14 图形软件 Bresenham画线算法 Bresenham画线算法若直线斜率k 0 1 且x2 x1的情况 1a象限 从算法可以看出 第i 1步的判别变量pi 1仅与第i步的判别变量pi 直线的两个端点分量差 x y有关 只用整数相加和乘2运算 没有四舍五入处理 而乘2可利用左移一位来实现因此该算法速度快且易于硬件实现 15 图形软件 Bresenham画线算法 Bresenham画线算法描述若直线斜率k 0 1 且x2 x1的情况 1a象限 1 输入两端点 x1 y1 x2 y2 并以第一点作为起始点2 分别计算 x x2 x1 y y2 y1 计算误差初值p1 2 y x i 1 3 求直线的下一点位置 xi 1 xi 1 ifpi 0则yi 1 yi 1 否则yi 1 yi 16 图形软件 Bresenham画线算法 Bresenham画线算法描述若直线斜率k 0 1 且x2 x1的情况 1a象限 4 画点 xi 1 yi 1 5 求下一个误差pi 1 ifpi 0则pi 1 pi 2 y 2 x 否则pi 1 pi 2 y 6 i i 1 ifi x 1则转3 否则end 17 图形软件 Bresenham画线算法 Bresenham画线算法现在讨论如何让该算法实现任何方向线段的绘制如图所示 线段的方向可分为8种 从原点出发射向8个区当直线斜率的绝对值大于1时 让y坐标每次增加1 再用Bresenham的误差判别式确定x坐标是否需要增加1 18 图形软件 Bresenham画线算法 Bresenham画线算法如果能充分利用x y平面各种八分和四分区域间的对称性就可减少运算量 19 图形软件 Bresenham画线算法 Bresenham画线算法 FLASH演示 例 分析从 0 0 到 5 2 的直线段 原始直线 Bresenham画出直线 20 图形软件 圆的生成算法 给出圆心坐标 xc yc 和半径r 逐点画出一个圆周的公式有下列两种 1 直角坐标法由上式导出 直角坐标法当x xc从 r到r作加1递增时 就可以求出对应的圆周点的y坐标但由于有乘方和平方根运算 且都是浮点运算 算法效率不高 同时 这样求出的圆周上的点是不均匀的 x xc 接近R时 由于圆的斜率趋向于无穷大 使得圆周上有较大的间隙 21 图形软件 圆的生成算法 22 图形软件 圆的生成算法 极坐标法假设圆周上一点 x y 处的半径与x轴的夹角为 则圆的极坐标方程为 x xc r cos y yc r sin 利用圆周上点的对称性 我们可求出圆上各点 此时自变量 的取值范围是 0 45 度 以固定角度为步长来变化 可得到沿圆周等距离分布的一系列光点 但运算量大 也不被采用 A B 极坐标法对称性 x y y x y x x y x y y x y x x y 45 23 图形软件 圆的生成算法 Bresenham画圆算法与Bresenham直线生成算法一样 其基本思想 利用判别变量来判断选择最近的像素 判别变量仅用加减和移位就可计算出来为讨论方便 仅考虑圆心在原点 半径为R的第一象限上的一段圆弧取 0 R 为起点 按顺时针方向绘制该1 4圆弧 24 Bresenham画圆算法如图所示 从当前点亮像素出发 按顺时针方向生成圆时 最佳逼近该圆的下一个像素只可能为H D V三像素之一 H D V中距圆周边界距离最小者 即为所求的像素点 图形软件 圆的生成算法 25 Bresenham画圆算法H D V三点到圆心的距离平方与圆的半径平方差 即为H D V到圆弧距离的一种度量 H x 1 2 y2 R2 D x 1 2 y 1 2 R2 V x2 y 1 2 R2 为了根据这些度量值可确定最佳像素点 首先 将H D V与理想圆弧的关系进行分类 图形软件 圆的生成算法 26 Bresenham画圆算法如图存在以下五种情况 1 H D V全在圆内2 H在圆外 D V在圆内3 D在圆上 H在圆外 V在圆内4 H D在圆外 V在圆内5 H D V全在圆外 图形软件 圆的生成算法 27 Bresenham画圆算法与Bresenham画线算法一样 按照上述不同类型 找出误差度量的递推公式 然后判别它的正 负性即可确定最佳逼近的像素点当 D 0 只可能为1或2的情况 为了确定是H还是D 可用如下判别式 HD H D HD 0则应选H 否则选D 图形软件 圆的生成算法 28 Bresenham画圆算法对于第2种情况 HD H D x 1 2 y2 R2 x 1 2 y 1 2 R2 2 D 2y 1因为 H 0 D0 否则2 D 2y 1 0 对于第1种情况 y是x的单调递减函数 H为下一点亮像素 另 此时 H 0和 D 0 H D 2 D 2y 1 0综上两种情况可得如下结论 在 D 0时 若2 D y 1 0 则取H 否则取D 图形软件 圆的生成算法 29 Bresenham画圆算法当 D 0 只可能有4 5两种情况 且最佳像素点为D或V 可用如下判别式 DV D V 当 DV 0则应选D 否则选V 对于第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若2 D x 1 0 则选V 否则选D 图形软件 圆的生成算法 30 Bresenham画圆算法对于第5种情况 D V都在圆外 显然V为所选像素 注意 D 0 V 0 D V 2 D x 1 0综上两种情况可得如下结论 在 D 0时 若2 D x 1 0 则取D 否则取V当 D 0此时D是最佳像素 图形软件 圆的生成算法 Bresenham画圆算法总结上述分析结果 当 D 0 若2 D x 1 0 取D 否则取V当 D 0 若2 D y 1 0 取H 否则取D当 D 0 取D关键的问题就是计算 D D x 1 2 y 1 2 R2 采用增量法 获得 D的计算公式 图形软件 圆的生成算法 32 Bresenham画圆算法分三种情况 下一像素为H时H x y x 1 y Dk 1 x 1 1 2 y 1 2 R2 x 1 2 y 1 2 R2 2 x 1 1 Dk 2 x 1 1 图形软件 圆的生成算法 33 Bresenham画圆算法下一像素为D时D x y x 1 y 1 Dk 1 x 1 1 2 y 1 1 2 R2 x 1 2 y 1 2 R2 2 x 1 2 y 1 1 Dk 2 x 1 2 y 1 2 图形软件 圆的生成算法 34 Bresenham画圆算法下一像素为V时V x y x y 1 Dk 1 x 1 2 y 1 1 2 R2 x 1 2 y 1 2 R2 2 y 1 1 Dk 2 y 1 1 图形软件 圆的生成算法 35 Bresenham画圆算法有了上述 D的递推计算公式 还需计算出 D的初值 圆弧的起点为 0 R D的初值为 D 0 1 2 R 1 2 R2 2 1 R 图形软件 圆的生成算法 36 图形软件 圆的生成算法 中点画圆算法与Bresenham画圆算法一样 以单位间隔取样并在每个步长中确定离指定圆最近的像素位置对于给定半径r和圆心 xc yc 可先给出计算中心在原点 0 0 的像素位置的算法 然后通过平移使每个计算出的 x y 移动到其适当的屏幕位置利用圆的对称性 只须讨论1 8圆 37 图形软件 圆的生成算法 中点画圆算法为了应用中点圆算法 定义一个圆函数 fcircle x y x2 y2 r2则任何点 x y 的相对位置可由对圆函数符合的检测来决定 0 x y 位于圆边界外 38 图形软件 圆的生成算法 中点画圆算法假设用该算法计算出第k个点P xk yk 下一步需要决定像素位置是A xk 1 yk B xk 1 yk 1 其中xk 1 xk 1A B的中点M xk 1 yk 0 5 M A B P Xk Yk 39 图形软件 圆的生成算法 中点画圆算法在M处决策参数 pk fcircle xk 1 yk 0 5 xk 12 yk 0 5 2 r2则 当pk 0 这个中点M在圆内 扫描线yk上的像素 xk 1 yk 更接近于圆边界 则下一点应取右边的点A xk 1 yk 否则 中点M位于圆外或在边界上 我们选择扫描线yk 1上的像素B xk 1 yk 1 pk 1 xk 1 1 2 yk 1 0 5 2 r2 40 图形软件 圆的生成算法 中点画圆算法递归表达式 pk 1 pk 2xk 1 y2k 1 y2k yk 1 yk 1其中 yk 1是yk pk 0 或是yk 1 pk 0 这取决于pk的符号圆在起始位置 x0 y0 0 r 处求值就可得到初始决策参数 p0 fcircle 1 r 0 5 5 4 r 41 图形软件 圆的生成算法 中点画圆算法中点圆算法的算法表示 p0 5 4 rxk 1 xk 1yk 1 yk pk 1 pk 2xk 1 1当pk 0yk 1 yk 1 pk 1 pk 2xk 1 1 2yk 1当pk 0 42 图形软件 圆的生成算法 中点画圆算法对于2xk 1和2yk 1本身又是一个增量表达式2xk 1增量始终为2而2yk 1增量为0 当pk 0 或 2 当pk 0 在起始位置 x0 y0 0 r 2xk 1和2yk 1的初始值分别为0和2r 43 图形软件 圆的生成算法 中点画圆算法步骤1 输入圆半径r和圆心 xc yc 并得到圆心在原点的圆周上的第一点为 x0 y0 0 r 2 计算决策参数的初始值 p0 5 4 r3 在每个xk位置处 从k 0开始 完成下列检测 假如pk 0 中心在 0 0 的圆的下一个点为 xk 1 yk 且pk 1 pk 2xk 1 1否则 圆的下一个点为 xk 1 yk 1 且pk 1 pk 2xk 1 1 2yk 1其中 2xk 1 2xk 1 2yk 1 2yk 2 44 图形软件 圆的生成算法 中点画圆算法 FLASH演示 4 确定在其它7个8分圆中的对称点5 将每个计算出的像素位置 x y 移动到