gjlchp03直线圆椭圆的生成.ppt

第三章直线 圆 椭圆生成算法 图形的扫描转换 光栅化 确定一个像素集合 用于显示一个图形的过程 步骤如下 1 确定有关像素2 用图形的颜色或其它属性 对像素进行写操作 对一维图形 不考虑线宽 则用一个像素宽的直线来显示图形 二维图形的光栅化 即区域的填充 确定像素集 填色或图案 任何图形的光栅化 必须显示在一个窗口内 否则不予显示 即确定一个图形的哪些部分在窗口内 哪些在窗口外 即裁剪 图形显示前需要 扫描转换 裁剪 裁剪 扫描转换 最常用 节约计算时间 扫描转换 裁剪 算法简单 本章内容 扫描转换直线段DDA算法中点画线法Bresenham画线算法 圆弧 椭圆弧扫描转换中点算法内接正多边形迫近法等面积正多边形逼近法生成圆弧的正负法 直线段的扫描转换算法 直线的扫描转换 确定最佳逼近于该直线的一组象素 并且按扫描线顺序 对这些象素进行写操作 三个常用算法 数值微分法 DDA 中点画线法Bresenham算法 数值微分法 假定直线的起点 终点分别为 x0 y0 x1 y1 且都为整数 Xi 1 Yi k Xi Int Yi 0 5 Xi Yi 栅格交点表示象素点位置 数值微分 DDA 法 基本思想已知过端点P0 x0 y0 P1 x1 y1 的直线段Ly kx b直线斜率为这种方法直观 但效率太低 因为每一步需要一次浮点乘法和一次舍入运算 数值微分 DDA 法 计算yi 1 kxi 1 b kxi b k x yi k x当 x 1 yi 1 yi k即 当x每递增1 y递增k 即直线斜率 注意上述分析的算法仅适用于 k 1的情形 在这种情况下 x每增加1 y最多增加1 当 k 1时 必须把x y地位互换 数值微分 DDA 法 增量算法 在一个迭代算法中 如果每一步的x y值是用前一步的值加上一个增量来获得 则称为增量算法 DDA算法就是一个增量算法 数值微分 DDA 法 voidDDALine intx0 inty0 intx1 inty1 intcolor intx floatdx 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 数值微分 DDA 法 例 画直线段P0 0 0 P1 5 2 xint y 0 5 y 0 5000 0 5100 4 0 5210 8 0 5311 2 0 5421 6 0 5522 0 0 5 数值微分 DDA 法 缺点 在此算法中 y k必须是float 且每一步都必须对y进行舍入取整 不利于硬件实现 中点画线法 原理 假定直线斜率0 K 1 且已确定点亮象素点P Xp Yp 则下一个与直线最接近的像素只能是P1点或P2点 设M为中点 Q为交点现需确定下一个点亮的象素 中点画线法 当M在Q的下方 P2离直线更近更近 取P2 M在Q的上方 P1离直线更近更近 取P1M与Q重合 P1 P2任取一点 问题 如何判断M与Q点的关系 中点画线法 假设直线方程为 ax by c 0其中a y0 y1 b x1 x0 c x0y1 x1y0由常识知 欲判断M点是在Q点上方还是在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 能否采用增量算法呢 中点画线法 若d 0 M在直线上方 取P1 此时再下一个象素的判别式为d1 F xp 2 yp 0 5 a xp 2 b yp 0 5 c a xp 1 b yp 0 5 c a d a 增量为a 中点画线法 若dM在直线下方 取P2 此时再下一个象素的判别式为d2 F xp 2 yp 1 5 a xp 2 b yp 1 5 c a xp 1 b yp 0 5 c a b d a b 增量为a b 中点画线法 画线从 x0 y0 开始 d的初值d0 F x0 1 y0 0 5 a x0 1 b y0 0 5 c F x0 y0 a 0 5b a 0 5b由于只用d的符号作判断 为了只包含整数运算 可以用2d代替d来摆脱小数 提高效率 中点画线法 voidMidpointLine intx0 inty0 intx1 inty1 intcolor inta b d1 d2 d x y a y0 y1 b x1 x0 d 2 a b d1 2 a d2 2 a b x x0 y y0 drawpixel x y color while x x1 if d 0 x y d d2 else x d d1 drawpixel x y color while midPointLine 中点画线法 例 用中点画线法P0 0 0 P1 5 2 a y0 y1 2b x1 x0 5d0 2a b 1d1 2a 4d2 2 a b 6ixiyid1001210 33213431 15425 Bresenham画线算法 在直线生成的算法中Bresenham算法是最有效的算法之一 令k y x 就0 k 1的情况来说明Bresenham算法 由DDA算法可知 yi 1 yi k 1 由于k不一定是整数 由此式求出的yi也不一定是整数 因此要用坐标为 xi yir 的象素来表示直线上的点 其中yir表示最靠近yi的整数 Bresenham画线算法 设图中xi列上已用 xi yir 作为表示直线的点 又设B点是直线上的点 其坐标为 xi 1 yi 1 显然下一个表示直线的点 xi 1 yi 1 r 只能从图中的C或者D点中去选 设A为CD边的中点 若B在A点上面则应取D点作为 xi 1 yi 1 r 否则应取C点 为能确定B在A点上面或下面 令 xi 1 yi 1 yir 0 5 2 若B在A的下面 则有 xi 1 0 由图可知yi 1 r yir 1 若 xi 1 0 3 yi 1 r yir 若 xi 1 0 Bresenham画线算法 由式 2 和式 3 可得到 xi 2 yi 2 yi 1 r 0 5 yi 1 k yi 1 r 0 5 4 yi 1 yir 0 5 k 1 当 xi 1 0yi 1 yir 0 5 k 当 xi 1 0 xi 2 xi 1 k 1 当 xi 1 0 xi 2 xi 1 k 当 xi 1 0由式 1 和式 2 可得到 x2 k 0 5 5 程序如下 BresenhamLine x0 y0 x1 y1 color intx0 y0 x1 y1 color intx y dx dy floatk e inte1 dx x1 x0 dy y1 y0 k dy dx e 0 5 x x0 y y0 e dx for i 0 i0 e e 1 e e 2 dx if e 0 y Bresenham画线算法 圆的扫描转换算法 下面仅以圆心在原点 半径R为整数的圆为例 讨论圆的生成算法 假设圆的方程为 X2 Y2 R2 圆弧扫描算法 X2 Y2 R2Y Sqrt R2 X2 在一定范围内 每给定一X值 可得一Y值 当X取整数时 Y须取整 缺点 浮点运算 开方 取整 不均匀 角度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 值后 即可以增量方式获得圆周上的坐标 然后取整可得象素坐标 但要采用浮点运算 乘法运算 取整运算 中点画圆法 利用圆的对称性 只须讨论1 8圆 第二个8分圆P为当前点亮象素 那么 下一个点亮的象素可能是P1 Xp 1 Yp 或P2 Xp 1 Yp 1 M P1 P2 P Xp Yp 中点画圆法 构造函数 F X Y X2 Y2 R2 则F X Y 0 X Y 在圆上 F X Y 0 X Y 在圆外 设M为P1 P2间的中点 M Xp 1 Yp 0 5 中点画圆法 有如下结论 F M M在圆内 取P1F M 0 M在圆外 取P2为此 可采用如下判别式 中点画圆法 d F M F xp 1 yp 0 5 xp 1 2 yp 0 5 2 R2若d 0 则P1为下一个象素 那么再下一个象素的判别式为 d1 F xp 2 yp 0 5 xp 2 2 yp 0 5 2 R2 d 2xp 3即d的增量为2xp 3 中点画圆法 若d 0 则P2为下一个象素 那么再下一个象素的判别式为 d1 F xp 2 yp 1 5 xp 2 2 yp 1 5 2 R2 d 2xp 3 2yp 2 即d的增量为2 xp yp 5 d的初值 d0 F 1 R 0 5 1 R 0 5 2 R2 1 25 R P1 中点画圆法 MidpointCircle intr intcolor intx y floatd x 0 y r d 1 25 r while x y drawpixel x y color if d 0 d 2 x 3 x else d 2 x y 5 x y 中点画圆法 为了进一步提高算法的效率 可以将上面的算法中的浮点数改写成整数 将乘法运算改成加法运算 即仅用整数实现中点画圆法 使用e d 0 25代替de0 1 R 中点画圆法 上述算法能否再改进呢 注意到d的增量是x y的线性函数 每当x递增1 则d的增量递增 x 2每当y递减1 则d的增量递增 y 2 x初始值 3 y初始值 2r 2算法 Bresenham画圆算法 现在从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 Pi 1 Hi Li 应取Hi还是取Li Bresenham画圆算法 剩下的问题是如何快速的计算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 2R2di 1 xi 1 2 yi2 xi 1 2 yi 1 2 2R2 2xi2 4xi 2yi2 2yi 2R2 3 Pi 1 Hi Li 应取Hi还是取Li Bresenham画圆算法 当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易知x0 0 y0 R x1 x0 1因此d0 12 y02 12 y0 1 2 2R2 3 2y0 3 2R Pi 1 Hi Li 应取Hi还是取Li 生成圆弧的正负法 原理 设圆的方程为F x y X2 Y2 R2 0 假设求得Pi的坐标为 xi yi 则当Pi在圆内时 F xi yi 向右 向圆外Pi在圆外时 F xi yi 0 向下 向圆内 生成圆弧的正负法 即求得Pi点后选择下一个象素点Pi 1的规则为 当F xi yi 0取xi 1 xi 1 yi 1 yi 当F xi yi 0取xi 1 xi yi 1 yi 1 这样用于表示圆弧的点均在圆弧附近 且使F xi yi 时正时负 故称正负法 快速计算的关键是F xi yi 的计算 能否采用增量算法 生成圆弧的正负法 若F xi yi 已知 计算F xi 1 yi 1 可分两种情况 1 F xi yi 0 xi 1 xi 1 yi 1 yi F xi 1 yi 1 xi 1 2 yi 1 2 R2 xi 1 2 yi2 R2 F xi yi 2xi 12 F xi yi 0 xi 1 xi yi 1 yi 1 F xi 1 yi 1 xi 1 2 yi 1 2 R2 xi2 yi 1 2 R2 F xi yi 2yi 13 初始值 略 生成圆弧的多边形逼近法 圆的内接正多边形迫近法 圆的等面积正多边形迫近法 圆的内接正多边形逼近法 思想 当一个正多边形的边数足够多时 该多边形可以和圆无限接近 即因此 在允许的误差范围内 可以用正多边形代替圆 设内接正n边形的顶点为Pi xi yi Pi的幅角为 i 每一条边对应的圆心角为a 则有xi Rcos iyi Rsin i 圆的内接正多边形逼近法 内接正n边形代替圆计算多边形各顶点的递推公式Xi 1Rcos a i Yi 1Rsin a i Xi 1cosa sinaXi Yi 1sinacosaYi因为 a是常数 sina cosa只在开始时计算一次所以 一个顶点只需4次乘法 共4n次乘法 外加直线段的中点算法的计算量 圆的等面积正多边形逼近法 当用内接正多边形逼近圆时 其面积要小于圆的面积 而当用圆的外切正多边形逼近圆时 其面积则要大于圆的面积 为了使近似代替圆的正多边形和圆之间在面积上相等 只有使该正多边形和圆弧相交 称之为圆的等面积正多边形 圆的等面积正多边形逼近法 步骤 求多边形径长 从而求所有顶点坐标值由逼近误差值 确定边所对应的圆心角 椭圆的扫描转换 F x y b2x2 a2y2 a2b2 0椭圆的对称性 只考虑第一象限椭圆弧生成 分上下两部分 以切线斜率为 1的点作为分界点 椭圆上一点处的法向 N x y F xi F yj 2b2xi 2a2yj 在上半部分 法向量的y分量大在下半部分 法向量的x分量大 上半部分 下半部分 法向量两分量相等 M1 M2 在当前中点处 法向量 2b2 Xp 1 2a2 Yp 0 5 的y分量比x分量大 即 b2 Xp 1 a2 Yp 0 5 而在下一中点 不等式改变方向 则说明椭圆弧从上部分转入下部分 椭圆的中点画法 与圆弧中点算法类似 确定一个象素后 接着在两个候选象素的中点计算一个判别式的值 由判别式的符号确定更近的点先讨论椭圆弧的上部分设 Xp Yp 已确定 则下一待选像素的中点是 Xp 1 Yp 0 5 d1 F Xp 1 Yp 0 5 b2 Xp 1 2 a2 Yp 0 5 2 a2b2 根据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 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 程序 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 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