ch03直线、圆、椭圆的生成2008.ppt

1 扫描转换直线段 DDA算法 中点画线法 Bresenham画线算法 2 圆弧 椭圆弧扫描转换 中点画圆算法 Bresenham画圆算法 中点画椭圆算法 本章内容 扫描转换原理 第三章直线 圆 椭圆生成算法 1 输出图元 OutputPrimitive 图形生成的基本构造单元称为输出图元 输出图元包括字符串和几何成分 如 点 直线 二次曲线 填充区域 多边形 圆 及由彩色阵列定义的形状 2 扫描转换 图形的两种表示方法 点阵表示 矢量表示 反映了图形的外表 反映了图形的内在联系 对光栅扫描器而言 矢量表示不能直接用于显示 将矢量表示的图形对象的转换为点阵表示称为扫描转换 任何图形的光栅化 必须显示在一个窗口内 否则不予显示 即确定一个图形的哪些部分在窗口内 哪些在窗口外 即裁剪 第三章直线 圆 椭圆生成算法 图形的扫描转换 光栅化 确定一个像素集合 用于显示一个图形的过程 步骤如下 1 确定有关像素 2 用图形的颜色或其它属性 对像素进行写操作 对一维图形 不考虑线宽 则用一个像素宽的直线来显示图形 二维图形的光栅化 即区域的填充 确定像素集 填色或图案 图形显示前需要 扫描转换 裁剪 裁剪 扫描转换 最常用 节约计算时间 扫描转换 裁剪 算法简单 第三章直线 圆 椭圆生成算法 屏幕坐标定义 由扫描转换原理知 数字设备通过绘制两端点间的离散点来显示直线段 线段上离散坐标位置是从线段方程中计算出来的 其所表示的对象用精确的坐标描述 其每一位置是数学上的无限小的点 而在光栅扫描显示器中的点用一个像素表示 其为一有限的屏幕区域 屏幕的位置用整数值 所以屏幕上绘制的点仅是实际坐标中点位置的近似 要显示坐标系中指定几何形状就需要调整数学输入点到有限像素区域的映射 数学输入点到有限像素区域的映射方法有两种 1 对象与像素中心对齐 2 物体边界与像素边界对齐 见下图 第三章直线 圆 椭圆生成算法 像素中心对准编址方式 像素边界对准编址方式 两种屏幕坐标的编址方法 注 在后面学习中使用像素中心对准编址方式 第三章直线 圆 椭圆生成算法 直线段的扫描转换算法 直线的扫描转换 确定最佳逼近于该直线的一组象素 并且按扫描线顺序 对这些象素进行写操作 三个常用算法 数值微分法 DDA 中点画线法 Bresenham算法 假定直线的起点 终点分别为 x0 y0 x1 y1 且都为整数 记直线的斜率为k 数值微分 DDA 法 虚线交叉点为像素中心点 基本思想 已知过端点P0 x0 y0 P1 x1 y1 的直线段L y kx b 直线斜率为 这种方法直观 但效率太低 因为每一步需要一次浮点乘法和一次舍入运算 数值微分 DDA 法 即 当x每递增1 y递增k 即直线斜率 先考虑 k 1的情形 当 k 1时 必须把x y地位互换 数值微分 DDA 法 在这种情况下 x每增加1 y最多增加1 在这种情况下 y每增加1 x最多增加1 即 当y每递增1 x递增1 k 即直线斜率倒数 数值微分 DDA 法 增量算法 在一个迭代算法中 如果每一步的x y值是用前一步的值加上一个增量来获得 则称为增量算法 DDA算法就是一个增量算法 上面是从左端点开始计算的 若以右端点作为起始点 当 k 1时 取 x 1 yi 1 yi k 当 k 1时 取 y 1 xi 1 xi 1 k 下面为一般DDA算法的一段伪代码 数值微分 DDA 法 if abs x1 x0 abs y1 y0 thenLength abs x1 x0 elseLength abs y1 y0 endif 选取 x和 y大者作为步长 x x1 x0 Length y y1 y0 Lengthx x0 0 5y y0 0 5 开始主循环i 1while i Length Setpixel int x int y x x xy y yi i 1endwhile DDA算法的伪代码 include includeinlineintround constfloata returnint a 0 5 voidlineDDA intx0 inty0 intxEnd intyEnd intdx xEnd x0 dy yEnd y0 steps k floatxIncrement yIncrement x x0 y y0 if fabs dx fabs dy steps fabs dx elsesteps fabs dy xIncrement float dx float steps yIncrement float dy float steps setPixel round x round y for k 0 k steps k x xIncrement y yIncrement setPixel round x round y 数值微分 DDA 法 例 画直线段P0 0 0 P1 5 2 缺点 在此算法中 y k必须是float 且每一步都必须对y进行舍入取整 不利于硬件实现 数值微分 DDA 法 dx 5 dy 3 steps 5 x 1 y 2 5 0 4 假定直线斜率0 k 1 且已确定点亮象素点P xp yp 则下一个与直线最接近的像素只能是P1点或P2点 设M为中点 Q为交点 原理 现需确定下一个点亮的象素 中点画线法 当M在Q的下方 P2离直线更近更近 取P2 M在Q的上方 P1离直线更近更近 取P1 M与Q重合 P1 P2任取一点 中点画线法 问题 如何判断M与Q点的关系 假设直线方程为 ax by c 0 其中a y0 y1 b x1 x0 c x0y1 x1y0 令F x y ax by c 由常识知 欲判断M点是在Q点上方还是在Q点下方 只需把M代入F x y 并检查它的符号 中点画线法 dp F M F xp 1 yp 0 5 a xp 1 b yp 0 5 c 构造判别式 当dp 0 M在直线 Q点 下方 取右上方P2 xp 1 yp 1 当dp 0 M在直线 Q点 上方 取右下方P1 xp 1 yp 当dp 0 选P1或P2均可 约定取P1 能否采用增量算法呢 dp称为画线算法中第p步决策参数 中点画线法 若dp 0 M在直线上方 xp 1 yp 1 取P1 xp 1 yp 此时再求下一个象素的判别式为 dp 1 F xp 2 yp 0 5 a xp 2 b yp 0 5 c a xp 1 b yp 0 5 c a dp a 增量为a 中点画线法 若dp 0 M在直线下方 xp 1 yp 1 取P2 xp 1 yp 1 此时再求下一个象素的判别式为 dp 1 F xp 2 yp 1 5 a xp 2 b yp 1 5 c a xp 1 b yp 0 5 c a b dp 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 由于只用dp的符号作判断 为了只包含整数运算 可以用2dp代替dp来摆脱小数 提高效率 此时d0 2a b 增量分别为2a和2 a b 中点画线法 k 1时直线中点画线算法 1 输入线段的两个端点 并将左端点储存在 x0 y0 中 2 将 x0 y0 装入帧缓存中 画出第一个点 3 计算常量a y0 y1 b x1 x0 d1 2a d2 2 a b 并得到决策参数的第一个值d0 2a b 4 从p 0开始 在沿路径的每个xp处 进行下列检测 如果dp 0 下一个绘制的点为 xp 1 yp 1 并且dp 1 dp d2 否则 下一个绘制的点为 xp 1 yp 并且dp 1 dp d1 5 重复步骤4 直到xp x1为止 中点画线法 voidMidpoint Line 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 2 b x1 x0 5 d0 2a b 1 d1 2a 4 d2 2 a b 6 ixiyid 1001 210 3 3213 431 1 5425 Bresenham画线算法 在直线生成的算法中Bresenham算法是最有效的算法之一 令k y x 就0 k 1的情况来说明Bresenham算法 假设已确定要显示的像素 xi yi 下一步要确定在列xi 1上绘制在位置 xi 1 yi 像素 还是在位置 xi 1 yi 1 像素 设直线方程为y kx b 其与x xi 1的交点为 x y 设d1 d2分别为交点 x y 到y yi和y yi 1的距离 显然 又 令pi x d1 d2 所以pi x d1 d2 2 yxi 2 xyi c 其中c 2 y x 2b 1 由于 x 0 所以pi与 d1 d2 同号 pi称为画线算法中第i步决策参数 Bresenham画线算法 pi的增量算法 pi 1 2 yxi 1 2 xyi 1 c pi 1 pi 2 y xi 1 xi 2 x yi 1 yi 因为xi 1 xi 1 所以有 pi 1 pi 2 y 2 x yi 1 yi 显然p0 x 2k 1 2 y x Bresenham画线算法 k 1时直线Bresenham算法 1 输入线段的两个端点 并将左端点储存在 x0 y0 中 2 将 x0 y0 装入帧缓存中 画出第一个点 3 计算常量 x y 2 y和2 y 2 x 并得到决策参数的第一个值p0 2 y x 4 从i 0开始 在沿路径的每个xi处 进行下列检测 如果pi 0 下一个绘制的点为 xi 1 yi 并且pi 1 pi 2 y 否则 下一个绘制的点为 xi 1 yi 1 并且pi 1 pi 2 y x Bresenham画线算法 5 重复步骤4 共 x次 Bresenham画线算法 例 求过端点为 20 10 和 30 18 直线各像素点 x 10 y 8 d1 2 y 16 d2 2 y 2 x 4 p0 2 y x 6 kpkxk 1yk 1 062111 122212 2 22312 3142413 4102514 562615 622716 7 22816 8142917 9103018 k y x 4 5 1 include include m xEnd x xEnd y yEnd xEnd x0 else x x0 y y0 setPixel x y while x xEnd x if p 0 p twoDy else y p twoDyMinusDx setPixel x y BresenhamLine x0 y0 x1 y1 color intx0 y0 x1 y1 color intx y dx dy e dx x1 x0 dy y1 y0 d dx x x0 y y0 for i 0 i 0 y d d 2 dx Bresenham画线算法 圆的扫描转换算法 仅以圆心在原点 半径R为整数的圆为例 讨论圆的生成算法 假设圆的方程为 x2 y2 R2 在一定范围内 每给定一x值 可得一y值 当x取整数时 y须取整 浮点运算 开方 取整 不均匀 缺点 角度DDA法 x x0 Rcos y y0 Rsin dx Rsin d dy Rcos d xn 1 xn dxyn 1 yn dy xn 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 中点画圆法 中点画圆法 构造函数 F x y x2 y2 R2 则 F x y 0 x y 在圆上 F x y 0 x y 在圆内 F x y 0 x y 在圆外 设M为P1 P2间的中点 M xp 1 yp 0 5 中点画圆法 有如下结论 F M 0 F M 0 为此 可采用如下判别式 M在圆内 取P1 xp 1 yp M在圆外 取P2 xp 1 yp 1 dp F M F xp 1 yp 0 5 xp 1 2 yp 0 5 2 R2 中点画圆法 若dp 0 则P1为下一个象素 那么再下一个象素的判别式为 dp 1 F xp 1 1 yp 1 0 5 xp 2 2 yp 0 5 2 R2 dp 2xp 3 即 d的增量为2xp 3 若dp 0 则P2为下一个象素 那么再下一个象素的判别式为 dp 1 F xp 1 1 yp 1 0 5 xp 2 2 yp 1 5 2 R2 dp 2xp 3 2yp 2 即d的增量为2 xp yp 5 dp 2 xp yp 5 中点画圆法 中点画圆法 初始决策参数 计算的起始位置为 x0 y0 0 R d0 F x0 1 y0 0 5 F 1 R 0 5 即 d0 5 4 R 1 R 1 2 2 R2 假定将半径R指定为整数 则可以对d0进行简单取整 d0 1 R R为整数 因为所有的增量为整数 中点画圆算法的步骤总结 1 输入圆半径R和圆心 xc yc 并得到圆周 圆心在原点 上的第一个点 x0 y0 0 R 2 计算出初始决策参数值 d0 5 4 R 或d0 1 R 3 从k 0开始 在每个xk位置 完成以下测试 若dk 0 圆心在 0 0 的圆的下一点坐标 xk 1 yk 1 xk 1 yk 并且dk 1 dk 2xk 3 否则 圆的下一点坐标 xk 1 yk 1 xk 1 yk 1 并且dk 1 dk 2 xk yk 5 中点画圆法 中点画圆法 5 将每个计算出来的像素位置 xk yk 移到圆心在 xc yc 圆的对应位置上 即 xk xk xc yk yk xc 并画出坐标值 6 重复步骤3到步骤5 直到x y为止 4 确定在其它七个八分圆中的对称点 例 使用中点画圆法画圆心在原点 半径为10的图 初始决策参数d0 1 R 9 初始点 x0 y0 0 10 kdkxkyk 0 9010 1 6110 2 1210 36310 4 349 5859 6568 中点画圆法 7 77 中点画圆法 MidpointCircle intR intcolor intx y floatd x 0 y R d 1 25 R drawpixel x y color while x y if d 0 d 2 x 3 x else d 2 x y 5 x y 算法 中点画圆法 MidpointCircle intR intcolor intx y d x 0 y R d 1 R drawpixel x y color while x y if d 0 d 2 x 3 x else d 2 x y 5 x y 算法 drawpixel x y color Bresenham画圆算法 现在从A点开始向右下方逐点来寻找弧AB要用的点 如图中点Pi是已选中的一个表示圆弧上的点 根据弧AB的走向 下一个点应该从Hi或者Li中选择 显然应选离AB最近的点作为显示弧AB的点 假设圆的半径为R 显然 当 应该取Li 否则取Hi 显然 当di 0时应该取Li 否则取Hi Bresenham画圆算法 剩下的问题是如何快速的计算di 设图中Pi的坐标为 xi yi 则Hi和Li的坐标为 xi 1 yi 和 xi 1 yi 1 当di 0时 取Hi yi 1 yi 则di 1 di 4xi 6 当di 0时 取Li yi yi 1 则di 1 di 4 xi yi 10 易知x1 0 y1 R x2 x1 1 因此d0 12 y12 12 y1 1 2 2R2 3 2y1 3 2R Bresenham画圆算法 intx 0 y r d 3 2 r while x y drawpixel x y if d 0 d d 4 x 6 else d d 4 x y 10 y x 例 使用Bresenham画圆法画圆心在原点 半径为10的图 初始决策参数d0 3 2R 17 初始点 x0 y0 0 10 kxkykdk 0010 17 1110 11 2210 1 331013 449 5 55917 66811 77713 F x y b2x2 a2y2 a2b2 0 椭圆的对称性 只考虑第一象限椭圆弧生成 分上下两部分 以切线斜率为 1的点作为分界点 椭圆上一点处的法向 N x y Fx i Fy j 2b2xi 2a2yj 椭圆的扫描转换 在上半部分 法向量的y分量大 即 b2x a2y 在当前中点处 法向量 2b2 xp 1 2a2 yp 0 5 的y分量比x分量大 即 b2 xp 1 a2 yp 0 5 而在下一中点 不等式改变方向 则说明椭圆弧从上部分转入下部分 在下半部分 法向量的x分量大 椭圆的扫描转换 即 b2x a2y 与圆弧中点算法类似 确定一个象素后 接着在两个候选象素的中点计算一个判别式的值 由判别式的符号确定更近的点 椭圆的中点画法 先讨论椭圆弧的上部分 设 xp yp 已确定 则下一待选像素的中点是 xp 1 yp 0 5 dp F xp 1 yp 0 5 b2 xp 1 2 a2 yp 0 5 2 a2b2 根据dp的符号来决定下一像素是取正右方的那个 还是右下方的那个 若d1p 0 中点在椭圆内 取正右方像素 判别式更新为 d1p 1 F xp 2 yp 0 5 d1p b2 2xp 3 d1p的增量为b2 2xp 3 当d1p 0 中点在椭圆外 取右下方像素 更新判别式 d1p 1 F xp 2 yp 1 5 d1p b2 2xp 3 a2 2yp 2 d1p的增量为b2 2xp 3 a2 2yp 2 椭圆的中点画法 d1p的初始条件 椭圆弧起点为 0 b 第一个中点为 1 b 0 5 初始判别式 d10 F 1 b 0 5 b2 a2b 0 25a2 转入下一部分 下一象素可能是正下方或右下方 此时判别式要初始化 d2p F xp 0 5 yp 1 b2 xp 0 5 2 a2 yp 1 2 a2b2 若d2p 0 取右下方像素 则 d2p 1 F xp 1 5 yp 2 d2p b2 2xp 2 a2 2yp 3 若d2p 0 取正下方像素 则 d2p 1 F xp 0 5 yp 2 d2p 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 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 上部分d2 sqr b x 0 5 sqr a y 1 sqr a b while y 0 i