CG07-线画图形生成.ppt

线画图元生成 输出图元生成 通常 图形软件包提供使用称为图形输出图元的基本几何结构来描述场景和利用这些输出图元 或输出原语 组合成更复杂结构的功能 并通过设置影响图元显示方法的参数 属性 来控制图元的输出形态 图形的基本构造块称为输出图元 outputprimitive 包括 字符串和几何成分 如点 直线 曲线 填充区域 多边形 圆 及由彩色阵列定义的形状 生成输出图元的子程序为构造图形提供了基本工具 输出图元有两大类 线画图元 用矢量表示的二维图形 其核心是将表示图形的数学方程离散化为适于光栅扫描显示的点的表示 其过程就是扫描转换过程 填充图元 用点阵表示的二维图元 其核心是如何确定给定区域内构成图形的内部的点的表示 输出图元的生成属于图形输出设备级算法 输出图元生成 基本操作 生成思想 像素编址 像素坐标 屏幕坐标 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 画点是将由应用程序提供的单个坐标位置转换成所使用输出设备的合适操作 随机扫描系统 在显示表中储存画点指令 并在每个刷新循环中 将这些指令中的坐标值转换成偏转电压 以将电子束定位于屏幕指定位置 黑白 彩色光栅系统 通过将帧缓冲器中对应于指定屏幕位置的位设置颜色码 以表示屏幕像素位置上将要显示的颜色 电子束进行扫描时 根据帧缓冲器中位的值发射电子脉冲 画出一点 画线是通过计算沿线路径上两指定端点位置间的中间位置来完成的 输出设备则直接按指令在端点间的这些位置填充 向量式笔绘图机或随机 光栅扫描显示器这类模拟设备都通过按x和y方向所需的量线性地改变水平和垂直偏转电压来实现 输出图元基本操作 输出图元生成 基本操作 生成思想 像素编址 像素坐标 屏幕坐标 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 线画图元生成思想 线画图元生成指的是 从图元的数学 参数表示形式 由用户按需要指定 转换成适于光栅系统显示所需要的点阵表示形式 即 实现扫描转换 线画图元生成的基本思想是 根据直线的数学 参数方程计算出落在直线段上或充分靠近它的一串像素 并以此像素集近似替代原来直线段 在屏幕上显示 也就是说 线段通过像素绘制 会产生台阶状 水平和垂直方向的台阶大小受像素的间隔 或分辨率 大小限制 具体实现时 在离散位置上对线段取样 并在每个取样位置上决定距线段最近的像素 输出图元生成 基本原理 生成思想 像素编址 像素坐标 屏幕坐标 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 图元像素编址 数字式设备通过绘制两端点间的离散点来显示直线段要在屏幕上显示世界坐标系中指定对象的几何形状 需要调整数学输入点到有限像素区域的映射 线路径上离散坐标位置是从线段方程中计算出来的 其采用精确的世界坐标描述 其每一位置是数学上的一个无限小的点 屏幕像素坐标参考有限的屏幕区域 屏幕位置使用整数值 所以 绘制的位置仅是在两指定端点间的实际线段位置的近似 图元像素编址 数学输入点到有限像素区域的映射 按对象边界与像素区域的覆盖量来调整显示物体的尺寸 即 对象与像素中心对准 将对象映射到像素间的屏幕位置 以使物体边界与像素边界对准 输出图元生成 基本操作 生成思想 像素编址 像素坐标 屏幕坐标 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 像素网格坐标 这个编址策略是依照像素中心给显示位置定址扫描线从屏幕底部从零开始顺序编号 像素列则沿每条扫描线从左至右从零开始编号 其每个点的坐标位置在像素点的中心处 占据具有屏幕坐标位置 x y 的一个像素的区域标识为中点位置在 x y 处的单位面积 输出图元生成 基本原理 生成思想 像素编址 像素坐标 屏幕坐标 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 屏幕网格坐标 参考由相距为单位长的水平和垂直像素边界线组成网格的屏幕坐标 这样屏幕坐标位置是一对标定两像素间网格相交位置的整数值 假如坐标原点位于屏幕左下方 那么每个像素区域就可由左下角的整数网格坐标来指定 通常 将占据具有屏幕坐标位置 x y 的一个像素的区域标识为对角位置在 x y 和 x 1 y 1 处的单位面积 这种像素编址方案有很多优点 它避免了半整数像素边界 实现了精确的对象表示 并简化了包含在许多扫描转换算法和其它光栅程序的处理 输出图元生成 基本原理 生成思想 像素编址 像素坐标 屏幕坐标 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 线画图元生成原理 直线的笛卡尔斜率截距方程为 y mx b m表示线的斜率 b是y轴截距 给定线段的两个端点 x1 y1 和 x2 y2 可计算斜率m和截距b m y2 y1 x2 x1 b y1 mx1 显示直线的算法可以上述直线方程和m b算式为基础 对任何沿直线给定的x增量 x 可从方程中计算出对应的y增量 y y m x 同样 可得出对应于 y的x增量 x x y m 上述方程形成了模拟设备决定偏转电压的基础 具有斜率绝对值 m 1的线段 可设置一个小的水平偏转电压 x 垂直偏转电压则可用计算出的 y来设定 斜率值 m 1的线 则设置一个小的垂直偏转电压 y 水平偏转电压则由计算出来的 x来设定 斜率 m 1的线 x y 水平和垂直偏转电压相等 这样 在指定端点间就可生成一条斜率为m的光滑线段 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 线生成DDA算法 DDA digitaldifferentialanalyzer 方法 直接利用计算 x或 y的线段扫描转换算法在一个坐标轴上以单位间隔对线段取样 而决定另一个坐标轴上最靠近线段路径的对应整数值 先考虑具有正斜率 从左端点到右端点处理的线段 若斜率m 1 则在单位x间隔 x 1 取样 并计算每个顺序的y值 yk 1 yk m 1 下标k取整数值从第一个点1开始递增 直至最后端点 若m 1 则将x和y的规则交换 即 在单位y间隔 y 1 取样 并计算每个连续的x值 xk 1 xk 1 m 2 假如起始点在右侧 则取 x 1 且 yk 1 yk m 3 或 当斜率大于1时 y 1 且 xk 1 xk 1 m 4 由于m可以是0与1之间的任意实数 所以 计算出的y值必须取整 输出图元生成 线画图元生成 DDA算法 算法原理 算法特点 算法程序 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 DDA算法原理 计算具有负斜率线段的像素位置也可用上述方程进行 假如斜率的绝对值小于1 起始端点在左侧 可设置 x 1并用方程 1 计算y值 起始端点在右侧 设置 x 1用方程 3 得到y位置 假如斜率的绝对值大于1时 起始端点在左侧 用 y 1和方程 2 当起始端点在右侧 y 1和方程 4 输出图元生成 线画图元生成 DDA算法 算法原理 算法特点 算法程序 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 DDA算法特点 DDA方法计算像素位置要比直接使用直线方程更快 它利用光栅特性 x 1或 y 1 而在x和y方向使用合适的增量 x 1或 y 1 来逐步沿线的路径推出各像素位置 消除了直线方程中的乘法 由于直线斜率m以是0与1之间的任意实数 因此 DDA算法的求每一隔点的位置都必须进行取整操作浮点增量的连续迭加中取整误差的积累会使长线段所计算的像素位置偏离实际线段 同时 程序中的取整操作和浮点运算仍十分耗时 可利用直线构成的连贯性 通过将增量m和1 m分离成整数和小数部分使所有的计算都简化为整数操作来改善DDA算法的性能 相关内容将在后面的有关章节中介绍 输出图元生成 线画图元生成 DDA算法 算法原理 算法特点 算法程序 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 inclnde device h defineROUND a int a 0 5 voidlineDDA intxa intya intxb intyb intdx xb xa dy yb ya steps k flootxIncremt yIncremt x xa y ya if abs dx abs dy steps abs dx elsesteps abs dy xIneremt dx float steps yIncremt dy float steps setPixel ROUND x ROUND y for k 0 k steps k x xIncremt y yIncremt setpixel ROUND x ROUND y DDA算法程序 两个端点的像素位置作为输入 其过程可概括为 端点位置间的水平和垂直差值赋给参数dx和dy 两者绝对值大者决定参量steps的值 从像素位置 xa ya 开始 确定沿线段生成下一个像素位置每个步的所需偏移量 并循环上述过程steps次 假如dx绝对值大于dy绝对值 且xa小于xb 那么x和y方向的增量值分别为1和m 假如x方向变化大 但xa大于xb 那么就采用减量 1和 m来生成线上的每个新点 其它情况下 在y方向使用单位增量 减量 x方向使用1 m的增量 减量 输出图元生成 线画图元生成 DDA算法 算法原理 算法特点 算法程序 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 Bresenham画线算法 由Bresenham提出的一种精确而有效的光栅线段生成算法 它可用于圆和其它曲线显示的整数增量运算 以单位x间距取样 需确定每个放样步长时哪两个像素位置更接近于线段路径 Bresenham算法通过引入 正比于两像素与实际线段点间偏移 的整型参量 采取对整型参量值的符号进行检测而选择两像素之一 输出图元生成 线画图元生成 DDA算法 Bresenham算法 问题定义 算法推导 决策参数 增量处理 生成过程 算法示例 算法说明 通用规则 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 Bresenham算法问题定义 先考虑具有小于1的斜率线的扫描转换过程沿线路径的像素位置由以单位x间距的取样来决定 从给定线段的左端点 x0 y0 开始 逐步处理每个后继点 x位置 并在扫描线y值最接近线段的像素上绘出一点 输出图元生成 线画图元生成 DDA算法 Bresenham算法 问题定义 算法推导 决策参数 增量处理 生成过程 算法示例 算法说明 通用规则 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 Bresenham算法推导 在取样位置xk 1 用d1和d2来标识两个候选像素与线段数学路径点的垂直偏移 在像素列位置xk 1处的数学线段点的y坐标可计算为 y m xk 1 b m xk 1 b 屏幕坐标为单位网格 有 xk 1 xk 1 yk 1 yk 1 那么 d1 y yk m xk 1 b yk d2 yk 1 y yk 1 m xk 1 b 这两个分离点的差分为 d1 d2 2m xk 1 2yk 2b 1 1 设 y和 x分别为端点的垂直和水平偏离量 令 m y x 代入方程得 pk x d1 d2 2 yxk 2 xyk c 2 方程 2 仅包含整数运算 参数c 2 y x 2b 1 是常量 与像素位置无关 且会在增量循环计算pk时被消除 输出图元生成 线画图元生成 DDA算法 Bresenham算法 问题定义 算法推导 决策参数 增量处理 生成过程 算法示例 算法说明 通用规则 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 Bresenham算法的决策参数 根据决策参数的符号 可判别第k 1步所选择的像素 假如yk处像素比yk 1处像素更接近于线段数学点 即 d1 d2 那么 参数pk是负的 此时 选择绘制较低像素 xk 1 yk 反之 假如yk 1处像素比yk处像素更接近于线段数学点 即 d2 d1 那么 参数pk是正的 此时 选择绘制较高像素 xk 1 yk 1 yk xk yk 1 xk 1 根据算法推导 得到 pk x d1 d2 2 yxk xyk cpk称为画线算法中第k步的决策参数 pk的符号与d1 d2的符号相同 x 0 输出图元生成 线画图元生成 DDA算法 Bresenham算法 问题定义 算法推导 决策参数 增量处理 生成过程 算法示例 算法说明 通用规则 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 Bresenham算法的增量处理 线画图元生成过程中 每一单位步长都会引起沿线段x和y方向坐标变化 因此 可利用递增整数运算得到后继决策参数值 在k步 决策参数为 pk 2 y xk 2 x yk c在k 1步 决策参数为 pk 1 2 y xk 1 2 x yk 1 c上述两方程相减 可得到 pk 1 pk 2 y xk 1 xk 2 x yk 1 yk 由xk 1 xk 1 因而得到 pk 1 pk 2 y 2 x yk 1 yk 取决于参数pk的符号 yk 1 yk取0或1 也就是 取高像素 xk 1 yk 1 yk 1 yk 0 pk 1 pk 2 y 2 x 取低像素 xk 1 yk yk 1 yk 1 pk 1 pk 2 y 起始像素位置 x0 y0 第一个参数p0从方程 2 及m y x计算出 p0 2 y x在每个整数x位置 从线段的坐标端点开始 反复进行决策参数的这种递归运算 输出图元生成 线画图元生成 DDA算法 Bresenham算法 问题定义 算法推导 决策参数 增量处理 生成过程 算法示例 算法说明 通用规则 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 Bresenham算法生成过程 m 1的Bresenham画线算法 输入线的两个端点 并将左端点存贮在 x0 y0 中 将 x0 y0 装入帧缓冲器 画第一个点 计算常量 x y 2 y和2 y 2 x 并得到决策参数的第一个值 p0 2 y x 像素生成过程 从k 0开始 在沿线的每个xk处 进行下列检测 假如pk 0 画下一点 xk 1 yk 且 pk 1 pk 2 y 否则 下一待画点 xk 1 yk 1 且 pk 1 pk 2 y 2 x k k 1 重复步骤4 共 x次 输出图元生成 线画图元生成 DDA算法 Bresenham算法 问题定义 算法推导 决策参数 增量处理 生成过程 算法示例 算法说明 通用规则 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 Bresenham算法示例 例 计算端点分别为 20 10 和 30 18 直线生成像素点坐标 计算常量 斜率小于1 x方向取单位步长 选取y方向象素 输出图元生成 线画图元生成 DDA算法 Bresenham算法 问题定义 算法推导 决策参数 增量处理 生成过程 算法示例 算法说明 通用规则 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 Bresenham算法说明 斜率为正且大于1的线段 只要交换x和y之间的规则 即沿y方向以单位步长步进并计算最接近线段路径的x连续值 起始端点 当然 也能改变程序使之能从任何端点开始绘制像素 假如具有正斜率线段的初始位置是右端点 那么在从右至左的步进中x和y都递减 相同像素 为了确信不管从何端点开始都能绘制相同的像素 当候选像素相对于线段的两个垂直偏高相等时 d1 d2 总是选择其中较高 或较低 的像素 负斜率 除非一个坐标递减而另一个递增 否则程序是类似的 特殊情况水平线 y 0 垂直线 x 0 和对角线 x y 它们都可直接装入帧缓冲器而无需进行画线算法处理 输出图元生成 线画图元生成 DDA算法 Bresenham算法 问题定义 算法推导 决策参数 增量处理 生成过程 算法示例 算法说明 通用规则 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 Bresenham算法通用规则 通过考虑xy平面各种八分和四分区域间的对称性 Bresenham算法对任意斜率的线段具有通用性 输出图元生成 线画图元生成 DDA算法 Bresenham算法 问题定义 算法推导 决策参数 增量处理 生成过程 算法示例 算法说明 通用规则 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 并行画线算法 设计并行算法时 很重要的是 平衡各可用的处理器间的处理负载利用并行计算机则可通过将计算分割到多个处理器中来得到线段的像素位置 将现有的顺序算法放到多个处理器上 寻找其它处理办法以使像素位置能以并行方式有效地计算 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 子段分割 子段生成 像素分配 区域像素 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 子段分割分配法 给定np个处理器 把线段分割成np个子段 并在每个子段中同时生成线段可建立起并行Bresenham画线算法 对于斜率为0 m 1 且左端点坐标为 x0 y0 的线段沿正x方向对线段进行分割 相邻分段的起始x位置间的距离为 xp x np 1 np 其中 x是线段的水平宽度 分段水平宽度 xp的值用整数除法来计算 将分段和处理器从0 1 2至np 1编号 第k分段的起始x的坐标为 xk x0 k xk 这种分段策略 有些情况下最后的子段会比其它段小 此外 假如线段的端点不是整数 舍入误差将导致沿线的长度产生宽度不同的分段 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 子段分割 子段生成 像素分配 区域像素 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 子段分割分配生成 为将Bresenham算法用于各分段 需要有每个分段的y坐标初始值和决策参数的初始值每个分段y方向的变化 yp可从线段斜率m和分段宽度 xp计算出 yp m xp 第k分段的起始y坐标为 yk y0 round k xp 起始处的初始决策参数为 pk k xp 2 y round k yp 2 x 2 y x 各处理器用该子段的起始决策参数值和起始坐标 xk yk 计算子段上的像素位置 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 子段分割 子段生成 像素分配 区域像素 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 扫描线像素分配 按扫描线或列像素分配根据线段的斜率 为每个处理器分配一条扫描线或一个像素列 每个处理器计算线段与分配给该处理器的水平行或垂直列的交点 对于斜率 m 1的线 每个处理器简单地按给定的x值从线方程中求解y 对于斜率值大于1的线 处理器则在给定扫描线y值下从线方程中求解x 尽管这种直接方法在顺序算法机器中很慢 但用多处理器能十分有效地完成 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 子段分割 子段生成 像素分配 区域像素 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 区域像素分配 为每个处理器分配一组屏幕像素 只要具有足够数量的处理器 就可为每个处理器分配给某个屏幕区域内的像素 通过为一个处理器分配线段坐标范围 包围矩形 之内的像素并计算像素离线段的距离而移植成线段显示 在线段的包围盒中的像素数目为 x y 计算从线到坐标 x y 处像素的垂直距离d d小于指定的线的粗细参数就画一个像素 可用下列算式得到距离d d Ax By C A y L B x L C x0 y y0 x L L squr x y 一旦线段的常数A B和C已经估算出 每个处理器只需完成两次乘法和两次加法来计算像素距离d 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 子段分割 子段生成 像素分配 区域像素 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 帧缓冲器地址计算 用光栅系统进行直线段和其它物体扫描转换显示时 必须计算帧缓冲器的位置 假设帧缓冲器矩阵是以行序来编址 且像素位置从屏幕左下方为 0 0 变化到屏幕右上方为 xmax ymax 帧缓冲器的位置计算的表达式add x y 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 增量计算 中点圆生成 中点椭圆生成 线画图元属性 帧缓冲器地址增量计算 单色系统 每个像素1位 像素位置 x y 的帧缓冲器位地址可计算为 addr x y addr 0 0 y xmax 1 x 1 沿扫描线移动 像素 x 1 y 处的帧缓冲器地址可以从位置 x y 的地址作偏移来计算 addr x 1 y addr x y 1从 x y 对角地跳到下一条扫描线 x 1 y 1 的帧缓冲器地址算式为 addr x 1 y 1 addr x y xmax 2其中 常数xmax 2对所有线段来说只需计算一次 同样 从方程 1 中可以得到屏幕x和y负方向单位步长的增量计算 每个这样的地址计算仅包含一个整数加法 彩色或多灰度系统 帧缓冲器地址计算包括像素宽度 位数n 以及像素屏幕位置 addr x y addr 0 0 yn xmax 1 nx addr x 1 y 1 addr x y nxmax 2n 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 增量计算 中点圆生成 中点椭圆生成 线画图元属性 传统圆生成方法 直接采用圆方程 x xc 2 y yc 2 r2沿x轴从xc r到xc r以单位步长计算对应的y值来得到圆周每点的位置 每一步包含很大的计算量 而且 所画像素位置间的间距是不一致的 圆斜率绝对值大于1后 交换x和y来调整间距 但增加计算量和处理过程 利用圆参数极坐标方程x xc rcos y yc rsin 以固定角度为步长生成显示时 圆就可沿圆周等距点绘制出来 沿圆周使用较大的角度分步时 可用直线段连接逼近圆的路径 为在光栅系统上得到更连续的边界 可将步长设为1 r 绘制的像素位置约为一个单位间隔 消除了上述不等间距现象 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 传统方法 传统缺点 基本思路 基本处理 算法原理 算法处理 算法过程 中点椭圆生成 线画图元属性 传统圆生成特性 考虑圆的对称性可以减少计算量 一个像限内的相邻八分圆的圆弧对于分割两个部分的45度是对称的 八分之一圆上的一点 x y 被映射到xy平面的其它七个八分圆的点 利用圆对称性仅需计算从x 0到x y段内的点 就可得到整个圆的所有像素位置 采用上述两种方法决定圆周上的像素位置都仍需要大量的计算时间 笛卡尔方程包括乘法和平方根运算 参数方程中包含乘法和三角运算 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 传统方法 传统缺点 基本思路 基本处理 算法原理 算法处理 算法过程 中点椭圆生成 线画图元属性 中点圆生成基本思路 直接利用光栅系统的Bresenham画线算法通过设定在每一取样步寻找最接近圆周的像素的决策参数 而将Bresenham线生成算法移植为画圆算法 但是 圆方程是非线性的 像素与圆周距离计算必须进行平方根运算 中点圆生成算法思想 比较像素与圆距离的平方 避免平方根运算 通过检验两候选像素间中间点与圆周边界的相对位置 在圆边界内或外 来选择像素 适应性 这种方法更易应用于其它圆锥曲线 误差 对于整数圆半径 中点方法生成与Bresenham线画圆算法相同的像素位置 且使用中点检验时 沿任何圆锥曲线段所确定像素位置误差限制在像素分段的1 2以内 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 传统方法 传统缺点 基本思路 基本处理 算法原理 算法处理 算法过程 中点椭圆生成 线画图元属性 中点圆生成基本处理 给定半径为r和圆中心在 xc yc 的圆运用平移 先给出中心在坐标原点 0 0 圆像素位置的算法 然后通过将xc加到x和yc加到y 而把每个计算出的位置 x y 移动到满足给定条件的屏幕位置 利用对称 在第一像限中 圆弧段从x 0到x y 曲线的斜率从0变化到 1 因此 可先计算这八分圆上圆弧段的像素位置 而后利用对称性计算其它七个八分圆弧的位置 定义圆函数 fcircle x y x2 y2 r2圆边界上任何具有半径r的点 x y 满足方程 fcircle x y 0 任何点 x y 的相对位置可由对圆函数符号的检测来决定 fcircle x y 0 x y 位于圆边界内 fcircle x y 0 x y 位于圆边界上 fcircle x y 0 x y 位于圆边界外 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 传统方法 传统缺点 基本思路 基本处理 算法原理 算法处理 算法过程 中点椭圆生成 线画图元属性 中点圆生成算法原理 在中点算法中圆函数是决策参数圆函数的检测在每个取样上对接近圆周的两个像素的中点进行 并可像在画线算法中一样为这个函数设置增量运算 决策参数是圆函数在这两个候选像素的中点处求值 Pk fcircle xk 1 yk 1 2 或者Pk fcircle xk 1 yk 1 1 2 根据决策参数判断 假如pk 0 中点在圆内 高像素接近于圆边界 假如pk 0 中点位于圆外或在圆周边界上 选择低像素 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 传统方法 传统缺点 基本思路 基本处理 算法原理 算法处理 算法过程 中点椭圆生成 线画图元属性 中点圆生成算法处理 以单位间隔在x方向取样 并在每个步长中确定离指定圆边界最近的像素位置 下图为位置xk 1处两候选像素间的中点 假设 xk yk 为前一像素 注意 圆在第一像限 y0 中点位于圆外或在圆周边界上 选择扫描线yk 1的像素 低像素 像素位置 xk 1 yk 1 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 传统方法 传统缺点 基本思路 基本处理 算法原理 算法处理 算法过程 中点椭圆生成 线画图元属性 中点圆生成算法过程 中点画圆算法输入圆半径r和圆心 xc yc 并得到圆心在原点的圆周上的第一点为 x0 y0 0 r 计算决策参数的初始值为 p0 5 4 r 在每个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 2 且2yk 1 2yk 2 4 确定在其它七个八分圆中的对称点 5 将每个计算出的像素位置 x y 移动到中心在 xc yc 的圆路径上 并画坐标值 x x xc y y yc 6 重复步骤3到5 直止x y 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 传统方法 传统缺点 基本思路 基本处理 算法原理 算法处理 算法过程 中点椭圆生成 线画图元属性 标准位置椭圆的参数方程 x xc rxcos y yc rysin 考虑对称性可用来进一步减少计算量 标准位置椭圆在四分像限中是对称的 必须计算一个整四分像限中椭圆曲线的像素位置 再由对称性得到其它三个像限中的像素位置 椭圆生成方法 椭圆的生成可通过考虑椭圆沿长轴和短轴尺寸不同而修改画圆程序来实现 椭圆为到两定点 焦点 距离之和等于常数的点的集合 假如短轴和长轴与坐标轴方向平行 可简化椭圆方程 标准位置 椭圆是指其长轴和短轴平行于x和y轴 参数rx和ry标出长 短半轴 椭圆方程可借助于椭圆中心坐标和参数rx和ry写为 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 基本思想 区域划分 路径选择 区域1生成 区域2生成 生成过程1 生成过程2 其它曲线 线画图元属性 中点椭圆生成基本思想 给定长短轴参数rx ry 假设ry rx 和椭圆中心位置 xc yc 先确定中心在原点的标准位置的椭圆点 x y 即 取 xc yc 0 0 然后 将点变换为圆心在 xc yc 的点 定义椭圆函数为 fellipse x y ry2x2 rx2y2 rx2ry2该函数具有下列特性 fellipse x y 0 假如 x y 位于椭圆边界内 fellipse x y 0 假如 x y 在椭圆边界上 fellipse x y 0 假如 x y 位于椭圆边界外 将椭圆函数fellipse x y 作为中点算法的决策参数 在每个取样位置 按照椭圆函数在沿椭圆轨迹两个候选像素间中点求值的符号选择下一个像素 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 基本思想 区域划分 路径选择 区域1生成 区域2生成 生成过程1 生成过程2 其它曲线 线画图元属性 中点椭圆生成区域划分 中点法依据椭圆斜率将第一像限的椭圆 ry rx 分成两部分 根据斜率变化确定步长方向 斜率绝对值小于1的区域1内x方向取单位步长 斜率绝对值大于1的区域2内y方向取单位步长 第一象限椭圆区域划分区域1 椭圆切线斜率小于1 区域2 椭圆切线斜率大于1 区域分割条件在每一步中 需检测曲线的斜率值 椭圆的斜率可从椭圆方程中计算出 dy dx 2ry2x 2rx2y在两区域交界处 dy dx 1 即 2ry2x 2rx2y 因此 区域1和区域2的交替条件是 2ry2x 2rx2y 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 基本思想 区域划分 路径选择 区域1生成 区域2生成 生成过程1 生成过程2 其它曲线 线画图元属性 中点椭圆生成路径选择 区域1和区域2可以多种方法来处理 从 0 ry 开始 先沿椭圆路径顺时针x方向步进 x 1 y 0 斜率绝对值大于1时 变为y方向步进 y 1 x 0 从 rx 0 开始 先沿椭圆路径逆时针y方向步进 y 1 x 0 当斜率绝对值小于1时 变为x方向步进 x 1 y 0 利用并行处理器可同时计算两区域内的像素位置 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 基本思想 区域划分 路径选择 区域1生成 区域2生成 生成过程1 生成过程2 其它曲线 线画图元属性 区域1中点椭圆生成算法 下面考察从 0 ry 开始顺时针方向生成椭圆的过程 区域1中 切线斜率 1 假如前一步的选择为 xk yk 将取样位置xk 1处两个候选像素间中点对决策参数 即椭圆函数 求值来决定沿椭圆轨迹的下一个位置 p1k fellipse xk 1 yk 1 2 ry2 xk 1 2 rx2 yk 1 2 2 rx2ry2假如p1k 0 中点位于椭圆内 扫描线yk上的像素更接近于椭圆边界 否则 中点在椭圆外或边界上 所选像素应在扫描线yk 1上 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 基本思想 区域划分 路径选择 区域1生成 区域2生成 生成过程1 生成过程2 其它曲线 线画图元属性 区域2中点椭圆生成算法 区域2中 切线斜率 1 当进入区域2时 其初始点取区域1中选择的最后位置 在区域2中 在负y方向以单位步长取样 在每一步中取水平像素间的中点对决策参数求值为 p2k fellipse xk 1 2 yk 1 ry2 xk 1 2 2 rx2 yk 1 2 rx2ry2假如p2k 0 中点位于椭圆边界之外 选择xk处像素 假如p2k 0 中点位于椭圆边界之内或上 选择xk 1处像素 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 基本思想 区域划分 路径选择 区域1生成 区域2生成 生成过程1 生成过程2 其它曲线 线画图元属性 中点椭圆生成过程1 1 输入rx ry和中心 xc yc 并得到中心在原点的椭圆上的第一个点 x0 y0 0 ry 2 计算区域1中决策参数的初值为 p10 ry2 rx2ry rx2 43 在区域1中每个xk位置处 从k 0开始 完成下列测试 假如p1k 0 椭圆的下一个点为 xk 1 yk 且 p1k 1 p1k 2ry2xk 1 ry2 不然 沿椭圆的下一个点为 xk 1 yk 1 且 p1k 1 p1k 2ry2xk 1 2rx2yk 1 ry2 其中 2ry2xk 1 2ry2xk 2ry2 2rx2yk 1 2rx2yk 2rx2 循环至 2ry2x 2rx2y4 使用区域1中最后点 x0 y0 来计算区域2中参数初值为 p20 ry2 x0 1 2 2 rx2 y0 1 rx2ry2 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 基本思想 区域划分 路径选择 区域1生成 区域2生成 生成过程1 生成过程2 其它曲线 线画图元属性 中点椭圆生成过程2 5 在区域2的每个yk位置处 从k 0开始 完成下列检测 假如p2k 0 椭圆下一点选为 xk yk 1 且 p2k 1 p2k 2rx2yk 1 rx2 否则 沿椭圆的下一个点为 xk 1 yk 1 且 p2k 1 p2k 2ry2xk 1 2rx2yk 1 rx2 使用与区域1中相同的x和y增量计算 循环至 rx 0 6 确定其它三个像限中对称的点 7 将每个计算出的像素位置 x y 平移到中心在 xc yc 的椭圆轨迹上 并按坐标值画点 x x xc y y yc 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 基本思想 区域划分 路径选择 区域1生成 区域2生成 生成过程1 生成过程2 其它曲线 线画图元属性 其它曲线生成算法 常见曲线包括圆锥曲线 三角和指数函数 概率分布 通用多项式和样条函数 这些曲线的显示可采用类似于圆和椭圆函数来生成直接从显式表示y f x 或参数方程中得到 用中点法绘制隐式函数f x y 0曲线 直接逼近 直接方法是用直线段来逼近曲线 以直代曲 沿曲线轨迹等距的线端点位置可使用参数表示 按曲线的斜率选择独立变量从显式表示中生成等距位置 直线拟合 可将曲线离散成坐标点数据集 用直线段来将离散点连结在一起 或采用线性或非线性回归来拟合数据组 利用对称 利用函数对称性来减少曲线轨迹坐标位置的计算量 中点法 根据隐式函数f x y 0确定合适的决策参数 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 基本思想 区域划分 路径选择 区域1生成 区域2生成 生成过程1 生成过程2 其它曲线 线画图元属性 线画图元的属性控制 任何影响图元显示方法的参数被称为属性参数 诸如颜色和大小等属性参数确定图元的基本特性 其它则指出在特定条件下怎样显示图元 这里 仅考虑哪些控制图元基本显示特性的属性 而不考虑特定条件 将属性选择加入图形软件包的方法为每个输出图元功能扩充相关的属性表来包含合适属性 提供一张系统当前属性值表 用包含在图形软件包中而独立的函数来为属性表设置当前值 为了生成一个输出图元 系统要检测相关属性并使用当前属性设置调用该显示程序 线画图元的基本属性有线型 宽度和颜色 在一些软件包中 线可用选择的笔或刷来显示 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 直线函数 曲线函数 线型 线宽 线帽 线连接 笔刷选择 线颜色 直线函数 在PHIGS GKS和其它软件包中 二维线函数为 polyline n wcPoints 参数n为输入坐标点数 整数 wcPoints是输入线段端点世界坐标值数组 用来定义由n 1相互连接的直线段 在图形应用中 一系列连接着的线段比单个线段更经常出现 因而 polyline提供了一个更通用的线函数 要显示单个线段 只要设n 2并在wcPoints中列出两个端点坐标的x和y值 polyline引用的坐标为绝对坐标值 即 所指定的值是坐标系中的实际点位置 有些图形系统使用具有相对坐标的线 和点 函数 这种情况下 坐标值被规定为从引入的最后位置 称为当前位置 的偏移量 有些图形软件包让用户选择使用相对坐标 还是绝对坐标指定线段端点 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 直线函数 曲线函数 线型 线宽 线帽 线连接 笔刷选择 线颜色 曲线函数 图形软件包包括圆 样条和其它常用曲线生成程序PHIGS标准中不提供这些曲线的显式函数 但它包含下列通用曲线函数 generalizedDrawingPrimitive n wcPoints id datalist wcPoints是n个坐标位置的列表 datalist包含非坐标数据值 参数id则用来选择所希望的功能 如 圆 id 1 椭圆 id 2 等等 生成圆和椭圆的函数常包括通过指定端点的参数来绘制曲线段的能力 扩充的参数表允许指定圆弧的起始角和终止角 设计圆弧或椭圆弧的另一个方法是输入弧的起始和终止坐标位置 输出图元生成 线画图元生成 DDA算法 Bresenham算法 平行画线算法 帧缓冲器地址 中点圆生成 中点椭圆生成 线画图元属性 直线函数 曲线函数 线型 线宽 线帽 线连接 笔刷选择 线颜色 线型 线型属性包括实线 虚线和点线等 通过设置沿线路径显示的实线段的长度和间距来修