椭圆的扫描转换.ppt

第三章基本图形生成算法 授课人 张勇 回顾 直线扫描算法 数值微分法DDA中点画线法Bresenham画线法 确定当前点的下一点的产生方法 确定判别式 实现增量计算 第三节圆与椭圆的扫描转换 圆的扫描转换中点画圆算法Bresenham画圆算法内接正多边形迫近法椭圆的扫描转换中点画法若干相关问题 圆的表示 原始定义 等价定义 代数离散法 效率低 圆的属性分析 对称性 正负划分性 圆的扫描转换的数学模型 找到逼近如下圆弧线的像素点集合 切线斜率范围 取x为自变量 中点画圆算法的原理 判别量定义 续 续 设 可替代的高效算法 则判别量的初值为 结论 二阶差分方法 任意多项式均可使用该方法实现增量计算 类似地 中点画圆算法伪代码 VoidMidPointCircle intr intcolor intx y d x 0 y r d 1 r delta1 3 delta2 5 2r drawpixel x y color while y x if d 0 d delta1 delta2 2 else d delta2 delta2 4 y delta1 2 x drawpixel x y color while end Bresenham画圆算法 1 原理 选择与圆心距离与半径之差较小的一点 圆弧上可选点情况 Bresenham画圆算法 2 Bresenham画圆算法 3 以最高点为初始点 计算判别量初值再根据判别量的正负确定递推关系递推关系的确定需根据右图分别不同情况进行讨论 去掉绝对值符号 并进行化简 Bresenham画圆算法 4 初始值的计算 利用增量计算方法加速判别参数的计算 圆的内接正多边形迫近法 圆的内接正多边形迫近法 1 内接正n边形顶点 圆的多边形迫近 圆的内接正多边形迫近法 2 使用增量计算确定多边形顶点 同理 圆的内接正多边形迫近法 3 上述递推公式可用矩阵形式表示为 可以证明 该递推公式关于误差稳定 圆的内接正多边形迫近法 4 改进的增量计算 使用两个初始点 该递推公式关于误差稳定 圆的内接正多边形迫近法 5 圆的等面积正多边形迫近法 原理 圆的等面积正多边形迫近法示意图 椭圆的扫描转换算法 椭圆弧的几何特点 1 定义 到两个定点的距离之和为定长的点的集合 假设 椭圆中心在坐标原点 椭圆弧的几何特点 2 椭圆弧上一点处的切线 切线斜率 椭圆弧的几何特点 3 具有与圆弧类似的属性 对称性空间的正负划分性 椭圆的扫描转换 问题 绘制第一象限内椭圆弧对应的像素点 解决方案 中点扫描转换算法算法原理与圆弧的中点扫描转换算法相同注意 第一象限内椭圆弧切线斜率跨两范围 1 0 以及 1 切线斜率k 1的点为扫描转换分割点 第一象限内椭圆弧的划分 割点位置计算 切线斜率为 1的点 椭圆弧上部的扫描转换 1 椭圆弧上部对应的决策参数 根据决策参数的取值 成立 椭圆弧上部的扫描转换 2 决策参数的递推计算 初始条件 椭圆弧上部的扫描转换 3 椭圆弧上部的扫描转换 4 椭圆弧上部的扫描转换 5 递推计算过程 椭圆弧下部的扫描转换 1 同理对椭圆弧的下部进行扫描转换 椭圆弧下部的扫描转换 2 判别参数的递推计算 椭圆弧的扫描转换 从 0 ry 开始 绘制椭圆弧的上部 采用判别参数为d1i 当绘制当前点满足切线斜率大于 1时 椭圆弧上部绘制完成 从 rx 0 开始 绘制椭圆弧的下部 采用判别参数为d2i 当绘制当前点的坐标与椭圆弧上部的最后一点交叉时 椭圆弧下部绘制完成 根据椭圆的对称性完成整个椭圆的绘制 0 ry rx 0 若干相关问题 1 曲线的扫描转换 一般方法 直线段逼近注意象素点的等距 为此可使用曲线的参数表示 或按照曲线斜率选择自变量 而从显式表示中生成等距位置点 正负法 尤其适合易画曲线 具有正负划分性 平坦性 连续性初始定向 起始点切线方向 前进规则 正负划分性确定 若干相关问题 2 直线绘制算法的并行实现 任何线生成算法都可以通过线段分割而适用于并行实现 有足够多的处理器时 按照屏幕的不同区域分配处理器 若干相关问题 3 图元几何尺寸的保留 在扫描转换过程中注意象素集合的实际尺寸 如线段的始末点坐标的定义 不同图元的尺寸变化不同 若干相关问题 4 线宽控制标准线宽的直线被扫描转换为一个象素宽的直线段 其它线宽的实现可以采用笔或刷的方式 通过沿相邻平行线路径画额外的象素可以定义标准线宽的正整数倍的其它线宽 线刷子方法实现的线宽控制 分水平和垂直两种 垂直线刷子 一般地 对于任意线段 当某点切矢斜率在 1 1 之间时 扫描转换过程是 给定x以固定步长 确定y方向的增量 所以可用垂直线刷子扫过象素 即得到所要求的线段 水平线刷子 对于其切矢斜率在 1 1 之外的线段 可用水平线刷子扫过即可 线刷子的设计简单高效 但它存在如图所示的缺陷 线刷子方案的缺陷 采用矩形刷子可以避免第一个缺陷需设计新的数据结构以避免象素的重复绘制 采用画轮廓线再填充的方法可以避免上述三种缺陷 解决方案 线型控制线型属性 实线 虚线和点划线等 线型的实现方式 通过设置沿线路径显示的实线段的长度和间距来修改画线算法得到不同类型的线 例如 用布尔数组定义出指定的类型 如间距为5的虚线 1111100000 1表示绘制点 0表示不绘制点 并使其在直线段的有效定义范围内不断重复 即扫描转换后得到的象素点依序与线型定义数组一一对应 并根据线型定义数组决定该象素点的绘制与否 若干相关问题 5 采用上述固定划线长度的实现方法会在直线方向定义不同时产生出不等长的划线段 原因在于相同个数的象素沿不同方向将生成不同长度的线段 为实现精确的线型定义 应按照线的斜率调整线型定义数组中实线段和空白段的象素数目 线型的精确控制 另一种精确定义线型的方法是 将线上的每一段实划线作为一段单独的线段 定位其始末端点坐标 再调用直线的扫描转换算法实现绘制 线型的精确控制 小结 圆的扫描转换