第三章 二维基本图形元素生成算法.ppt

第三章二维基本图形元素生成算法 1 基本概念 所谓图元的生成 是指完成图元的参数表示形式 由图形软件包的使用者指定 到点阵表示形式 光栅显示系统刷新时所需的表示形式 的转换 通常也称扫描转换图元 2 课程内容 3 1简单的二维图形显示流程 3 2直线段的扫描转换 3 3圆弧的扫描转换 3 4易画曲线的正负法 3 5线画图元的属性控制 3 3 1简单的二维图形显示流程 图3 1 1二维图形显示流程 裁剪和扫描 图形显示前需要进行扫描转换 裁剪 这一过程有三种方法 裁剪 扫描转换 最常用 节约计算时间 扫描转换 裁剪 算法简单 扫描转换到画布 位块拷贝 算法简单 但耗时耗内存 常用于字符显示 5 3 2直线段的扫描转换 目标 求与直线段充分接近的像素集两点假设1 直线段的宽度为12 直线段的斜率 像素间均匀网格整型坐标系 图3 2 1 6 描绘线条图形的要求直线段要显得笔直线段端点位置要准确线段的亮度要均匀转换算法速度要快 7 3 2 1DDA digitaldifferentialanalyzer 算法 条件 待扫描转换的直线段 斜率 其中直线方程 8 3 2 1DDA算法 直接求交算法 划分区间 x x1 计算纵坐标 取整 复杂度 乘法 加法 取整 图3 2 2 9 3 2 1DDA算法 DDA算法 增量算法 复杂度 加法 取整算法 图3 2 3 10 3 2 1DDA算法 DDA算法程序 voidLineDDA intx0 inty0 intx1 inty1 intcolor 假定x0 x1 1 k 1 intx y floatdx dy k dx float x1 x0 dy float y1 y0 k dy dx y y0 for x x0 x x1 x Putpixel x int y 0 5 color y k 11 3 2 1DDA算法 举例 用DDA方法扫描转换连接两点P0 0 0 和P1 5 2 的直线段xint y 0 5 y 0 5000100 4 0 5210 8 0 5311 2 0 5421 6 0 5 图3 2 4 12 3 2 1DDA算法 特点1注意上述分析的算法仅适用于 k 1的情形 在这种情况下 x每增加1 y最多增加1 当 k 1时 必须把x y地位互换 y每增加1 x相应增加1 k 特点2在这个算法中 y与k必须用浮点数表示 而且每一步都要对y进行四舍五入后取整 这使得它不利于硬件实现 13 3 2 1DDA算法 改进算法 增量DDA 优化点 增加斜率判断并改变循环参数 14 3 2 1DDA算法 DDA画线算法程序 改进 voidLineDDA intx0 inty0 intx1 inty1 intcolor intx y floatdx dy k l m dx float x1 x0 dy float y1 y0 k dy dx if abs k x1怎么办 15 3 2 2画线中点算法 目标 消除DDA算法中的浮点运算 浮点数取整运算 不利于硬件实现 DDA算法 效率低 条件 同DDA算法斜率 直线段的隐式方程 x0 y0 x1 y1 两端点 F x y ax by c 0式中a y0 y1 b x1 x0 c x0y1 x1y0 16 基本原理 画直线段的过程中 当前象素点为 xp yp 一个象素点有两种可选择点p1 xp 1 yp 或p2 xp 1 yp 1 若M xp 1 yp 0 5 为p1与p2之中点 Q为理想直线与x xp 1垂线的交点 当M在Q的下方 则P2应为下一个象素点 M在Q的上方 应取P1为下一点 图3 2 5 17 3 2 2画线中点算法 3 2 2画线中点算法 点与直线的关系 on F x y 0 up F x y 0 down F x y 0 图3 2 6 直线的正负划分性 18 3 2 2画线中点算法 欲判断中M在Q点的上方还是下方 只要把M代F x y 并判断它的符号 构造判别式 d F M F xp 1 yp 0 5 a xp 1 b yp 0 5 c当d0 M在Q点上方 取P1为下一个象素 当d 0 选P1或P2均可 约定取P1为下一个象素 19 问题 判断距直线最近的下一个象素点构造判别式 d F M F xp 1 yp 0 5 由d 0 d 0可判定下一个象素 P P2 P1 图3 2 7 20 3 2 2画线中点算法 要判定再下一个象素 分两种情形考虑 1 若d 0 取正右方象素P1 再下一个象素判定 由d1 F xp 2 yp 0 5 a xp 2 b yp 0 5 c d a d的增量是a2 若d 0 取右上方象素P2 再下一个象素 由 d2 F xp 2 yp 1 5 d a bd的增量为a b P2 P P1 图3 2 8 21 3 2 2画线中点算法 d的初始值d0 F x0 1 y0 0 5 F z0 y0 a 0 5 b因 x0 y0 在直线上 F x0 y0 0 所以 d0 a 0 5 bd的增量都是整数 只有初始值包含小数 可以用2d代替d 2a改写成a a 算法中只有整数变量 不含乘除法 可用硬件实现 22 3 2 2画线中点算法 中点算法程序MidPointLine x0 y0 x1 y1 color intx0 y0 x1 y1 color inta b d1 d2 x y a y0 y1 b x1 x0 d 2 a b d1 2 a d2 2 a b x x0 y y0 PutPixel x y color while x x1 if d 0 x y d d2 else x d d1 PutPixel x y color 23 3 2 2画线中点算法 举例用中点画线方法扫描转换连接两点P0 0 0 和P1 5 2 的直线段 a y0 y1 2 b x1 x0 5 d0 2 a b 1 d1 2 a 4 d2 2 a b 6xyd00110 3d1213d231 1d1425d2521 图3 2 9 24 3 2 2画线中点算法 3 2 3画线Bresenham算法 Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法 该方法类似于中点法 由误差项符号决定下一个象素取右边点还是右上点 算法原理如下 过各行各列象素中心构造一组虚拟网格线 按直线从起点到终点的顺序计算直线与各垂直网格线的交点 然后确定该列象素中与此交点最近的象素 该算法的巧妙之处在于采用增量计算 使得对于每一列 只要检查一个误差项的符号 就可以确定该列的所求象素 25 如下图所示 设直线方程为 其中k dy dx 假设x列的象素已经确定为xi 其行坐标为yi 那么下一个象素的列坐标为xi 1 而行坐标要么不变为yi 要么递增1为yi 1 图3 2 10 26 3 2 3画线Bresenham算法 是否增1取决于如图所示误差项d的值 因为直线的起始点在象素中心 所以误差项d的初值d0 0 x下标每增加1 d的值相应递增直线的斜率值k 即d d k 一旦d 1 就把它减去1 这样保证d在0和1之间 当d 0 5时 直线与xi 1列垂直网格交点最接近于当前象素 xi yi 的右上方象素 xi 1 yi 1 而当d 0 5时 更接近于右方象素 xi 1 yi 图3 2 10 27 3 2 3画线Bresenham算法 为方便计算 令e d 0 5 e的初值为 0 5 增量为k 当e 0时 取当前象素 xi yi 的右上方象素 xi 1 yi 1 而当e 0时 更接近于右方象素 xi 1 yi 28 3 2 3画线Bresenham算法 Bresenham画线算法程序voidBresenhamline intx0 inty0 intx1 inty1 intcolor intx y dx dy floatk e dx x1 x0 dy y1 y0 k dy dx e 0 5 x x0 y y0 for i 0 i 0 y e e 1 29 3 2 3画线Bresenham算法 举例 用Bresenham方法扫描转换连接两点P0 0 0 和P1 5 2 的直线段 xye00 0 510 0 10 3 121 0 731 0 30 1 142 0 952 0 5 图3 2 11 30 3 2 3画线Bresenham算法 上述bresenham算法在计算直线斜率与误差项时用到小数与除法 可以改用整数以避免除法 由于算法中只用到误差项的符号 因此可作如下替换 e e 2dx改进的Bresenham画线算法程序 voidInterBresenhamline intx0 inty0 intx1 inty1 intcolor dx x1 x0 dy y1 y0 e dx x x0 y y0 for i 0 i 0 y e e 2 dx 31 3 2 3画线Bresenham算法 3 3圆弧的扫描转换 处理对象 圆心在原点的圆弧圆的八对称性 图3 3 1 32 两种直接离散方法 离散点 离散角度 缺点 开根 三角函数运算 计算量大 不可取 33 3 3圆弧的扫描转换 3 3 1角度DDA法转换圆弧 x x0 Rcos y y0 Rsin dx Rsin d dy Rcos d xn 1 xn dxyn 1 yn dyxn 1 xn dx xn Rsin d xn yn y0 d yn 1 yn dy yn Rcos d yn xn x0 d 显然 确定x y的初值及d 值后 即可以增量方式获得圆周上的坐标 然后取整可得象素坐标 但要采用浮点运算 乘法运算 取整运算 34 圆弧的正负划分性 圆弧外的点 F x y 0圆弧内的点 F x y 0 3 3 1角度DDA法转换圆弧 图3 3 2 35 生成圆弧的中点算法考虑对象 第二个八分圆 第一象限的八分之一圆弧 3 3 1角度DDA法转换圆弧 图3 3 3 36 问题 与直线情形类似圆弧的隐函数 F x y x2 y2 R2 0切线斜率min 1 0 中点M xp 1 yp 0 5 当F M 0时 M在圆内 说明P1距离圆弧更近 取P1 当F M 0时 P取P2 3 3 1角度DDA法转换圆弧 37 构造判别式d F M F xp 1 yp 0 5 xp 1 2 yp 0 5 2 R21 若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 5d的初始值 在第一个象素 0 R 处 d0 F 1 R 0 5 1 25 R 算法中有浮点数 用e d 0 25代替 3 3 1角度DDA法转换圆弧 38 所以 初始化运算d0 1 25 R对应于e0 1 R判别式d 0对应于e 0 25又因为 e的初值e0为整数 运算过程中的分量也为整数 故e始终为整数所以 e 0 25等价于e 0程序如下 完全用整数实现 MidpointCircle r color Intr color intx y d x 0 y r d 1 r putpixcel x y color while x y if d 0 d 2 x 3 x else d 2 x y 5 x y putpixcel x y color 39 3 3 2Bresenham画圆算法 现在从A点开始向右下方逐点来寻找弧AB要用的点 如图中点Pi 1是已选中的一个表示圆弧上的点 根据弧AB的走向 下一个点应该从Hi或者Li中选择 显然应选离AB最近的点作为显示弧AB的点 假设圆的半径为R 显然 当xHi2 yHi2 R2 R2 xLi2 yLi2 时 应该取Li 否则取Hi 令di xHi2 yHi2 xli2 yli2 2R2显然 当di 0时应该取Li 否则取Hi 图3 3 4 40 剩下的问题是如何快速的计算di 设图中Pi 1的坐标为 xi 1 yi 1 则Hi和Li的坐标为 xi yi 1 和 xi yi 1 1 di xi2 yi 12 xi2 yi 1 1 2 2R2 2xi2 2yi 12 2yi 1 1 2R2 3 3 2Bresenham画圆算法 di 1 xi 1 2 yi2 xi 1 2 yi 1 2 2R2 2xi2 4xi 2yi2 2yi 2R2 3 41 当di取Hi yi yi 1 则di 1 di 4xi 1 6当di 0时 取Li yi yi 1 1 则di 1 di 4 xi 1 yi 1 10 3 3 2Bresenham画圆算法 易知x0 0 y0 R x1 x0 1因此d0 1 12 y02 12 y0 1 2 2R2 3 2y0 3 2R 42 1 求误差初值 p1 3 2R i 1 画点 0 r 2 求下一个光栅位置 x i 1 x i 1 如果pi 0则y i 1 y i 否则y i 1 y i 1 3 画点 x i 1 y i 1 4 计算下一个误差 ifp i 0则p i 1 p i 4x i 6 否则p i 1 p i 4 x i y i 10 5 i i 1 ifx y则end 否则返2 3 3 2Bresenham画圆算法 43 3 3 2Bresenham画圆算法 44 3 3 3椭圆的扫描转换 F x y b2x2 a2y2 a2b 0椭圆的对称2性 只考虑第一象限椭圆弧生成 分上下两部分 以切线斜率为 1的点作为分界点 椭圆上一点处的法向 N x y F xi F yj 2b2xi 2a2yj 图3 3 5 45 M2 在当前中点处 法向量 2b2 xp 1 2a2 yp 0 5 的y分量比x分量大 即 b2 xp 1 a2 yp 0 5 而在下一中点 不等式改变方向 则说明椭圆弧从上部分转入下部分 3 3 3椭圆的扫描转换 46 椭圆的中点算法与圆弧中点算法类似 确定一个象素后 接着在两个候选象素的中点计算一个判别式的值 由判别式的符号确定更近的点 先讨论椭圆弧的上部分 xp yp 中点 xp 1 yp 0 5 d1 F xp 1 yp 0 5 b2 xp 1 2 a2 yp 0 5 2 a2b2 3 3 3椭圆的扫描转换 47 根据d1的符号来决定下一像素是取正右方的那个 还是右下方的那个 若d1 0 中点在椭圆内 取正右方象素 判别式更新为 d1 F xp 2 yp 0 5 d1 b2 2xp 3 d1的增量为b2 2xp 3 当d1 0 中点在椭圆外 取右下方象素 更新判别式 d1 F xp 2 yp 1 5 d1 b2 2xp 3 a2 2yp 2 d1的增量为b2 2xp 3 a2 2yp 2 3 3 3椭圆的扫描转换 48 d1的初始条件 椭圆弧起点为 0 b 第一个中点为 1 b 0 5 初始判别式 d10 F 1 b 0 5 b b a a b 0 25 转入下一部分 下一象素可能是一正下方或右下方 此时判别式要初始化 d2 F Xp 0 5 Yp 1 b2 Xp 0 5 2 a2 Yp 1 2 a2b2若d2 0 则d2 F Xp 0 5 Yp 2 d2 a2 2Yp 3 下半部分弧的终止条件为y 0 3 3 3椭圆的扫描转换 49 程序 MidpointEllipe a b color inta b color intx y floatd1 d2 x 0 y b d1 b b a a b 0 25 putpixel x y color while b b x 1 a a y 0 5 if d1 0 d1 b b 2 x 3 x else d1 b b 2 x 3 a a 2 y 2 x y putpixel x y color 上部分 50 3 3 3椭圆的扫描转换 d2 sqr b x 0 5 sqr a y 1 sqr a b while y 0 if d2 0 d2 b b 2 x 2 a a 2 y 3 x y else d2 a a 2 y 3 y putpixel x y color 51 3 3 3椭圆的扫描转换 3 3 4生成圆弧的多边形逼近法 用正多边形近似代替圆 显示多边形的边可用扫描转换直线段的中点算法来实现 圆的正内接多边形迫近法圆的等面积正多边形迫近法 52 圆的正内接多边形迫近法原理计算多边形各顶点的递推公式Xi 1cosa sinaXi Yi 1sinacosaYi因为 a是常数 sina cosa只在开始时计算一次所以 一个顶点只需4次乘法 共4n次乘法 外加直线段的中点算法的计算量 3 3 4生成圆弧的多边形逼近法 图3 3 7 53 图3 3 8 问题 给定最大逼近误差 最大距离 DELTA 如何确定多边形的边数n或a 另外 用矢量运算可以简化计算 推出求顶点的逆推公式 p60 d R Rcos a 2 R DELTA Ra 2arccos R DELTA R amax 2arccos R DELTA Rn 360 a 54 3 3 4生成圆弧的多边形逼近法 图3 3 10 圆的等面积正多边形迫近法 步骤 求多边形径长 从而求所有顶点生标值由逼近误差值 确定边所对应的圆心