计算机图形学基础教程——第2章1

《计算机图形学基础教程——第2章1》由会员分享，可在线阅读，更多相关《计算机图形学基础教程——第2章1（51页珍藏版）》请在金锄头文库上搜索。

1、第二章 光栅图形学 什么是光栅图形学 光栅显示器 图形光栅化 光栅化图形的处理 计算机图形学基础 光栅图形学的研究内容 直线段的扫描转换算法 圆弧的扫描转换算法 多边形的扫描转换与区域填充 字符 裁剪 反走样 消隐 计算机图形学基础 2 1 直线段的扫描转换算法 直线的扫描转换 确定最佳逼近于该直线的一组 象素 并且按扫描线顺序 对这些象素进行写操 作 三个常用算法 数值微分法 DDA 中点画线法 Bresenham算法 计算机图形学基础 2 1 1 数值微分 DDA 法 基本思想 已知过端点 的直线段L 直线斜率为 从 的左端点 开始 向 右端点步进 步长 1 个象素 计算相应的y坐标 取象

2、素点 x round y 作为 当前点的坐标 计算机图形学基础 作为最底层的光栅图形算法 在通常的CAD 图形系 统中 会被大量应用 因此 哪怕节约一个加法或减 法 也是很了不起的改进 由此出发点 导致增量算法的思想 计算机图形学基础 计算 当 时 即 当x每递增1 y递增k 即直线斜率 计算机图形学基础 例 画直线段 x int y 0 5 y 0 5 000 100 4 0 5 210 8 0 5 311 2 0 5 421 6 0 5 522 0 0 5 注 网格点表示象素 计算机图形学基础 void DDALine int x0 int y0 int x1 int y1 int col

3、or int x float dx 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 计算机图形学基础 问题 当 k 1时 会如何 计算机图形学基础 注意上述分析的算法仅适用于 k 1的情形 在这种情况 下 x每增加1 y最多增加1 当 k 1时 必须把x y地位互换 k DDA算法采用点斜式 可否采用其他的直 线表示方式 计算机图形学基础 基本思想 当前象素点为 xp yp 下一个象素点为P1 或P2 设M xp 1 yp 0 5 为p1与p2 之中点 Q为理想直线与

4、x xp 1 垂线的交点 将Q与M的y坐标进 行比较 当M在Q的下方 则P2 应为 下一个象素点 M在Q的上方 应取P1为下一点 计算机图形学基础 构造判别式 d F M F xp 1 yp 0 5 a xp 1 b yp 0 5 c 其中a y0 y1 b x1 x0 c x0y1 x1y0 当d0 M在L Q点 上方 取右方P1为下一个象素 当d 0 选P1或P2均可 约定取P1为下一个象素 计算机图形学基础 但这样做 每一个象素的计算量是4个加法 两 个乘法 山穷水尽疑无路 如果也采用增量算法呢 d是xp yp的线性函数 因此可采用增量计算 提 高运算效率 计算机图形学基础 若当前象素处

5、于d 0情况 则取正右方象素P1 xp 1 yp 要 判下一个象素位置 应计算 d1 F xp 2 yp 0 5 a xp 2 b yp 0 5 d a 增量为a 若d 0时 则取右上方象素P2 xp 1 yp 1 要判断再下一 象素 则要计算 d2 F xp 2 yp 1 5 a xp 2 b yp 1 5 c d a b 增量为a b 计算机图形学基础 至此 至少新算法可以和DDA算法一样好 能否再做改进 能否实现整数运算 计算机图形学基础 画线从 x0 y0 开始 d的初值 d0 F x0 1 y0 0 5 F x0 y0 a 0 5b a 0 5b 可以用2d代替d来摆脱小数 提高效率

6、 令 d0 2a b d1 2a d2 2a 2b 我们有如下算法 计算机图形学基础 void Midpoint Line int x0 int y0 int x1 int y1 int color int a 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 mid PointLine 计算机图形学基础 例 用中点画线法 ixi yid 1001

7、210 3 3213 431 1 5425 计算机图形学基础 2 1 3 Bresenham算法 基本思想 DDA算法采用点斜式 中点法采用隐式表示 中点法可以有整数算法 其他表示可以推出整数算法吗 计算机图形学基础 过各行各列象素中心构造一组虚拟网格线 按直线 从起点到终点的顺序计算直线与各垂直网格线的交点 然后根据误差项的符号确定该列象素中与此交点最 近的象素 计算机图形学基础 设直线方程为 其中k dy dx 因为直 线的起始点在象素中心 所以误差项d的初值d0 0 X下标每增加1 d的值相应递增直线的斜率值k 即d d k 一旦d 1 就把它减去1 这样保证d在0 1之间 当d 0 5

8、时 最接近于当前象素的右上方象素 而当d 0 5时 更接近于右方象素 为方便计算 令e d 0 5 e的初值为 0 5 增量为k 当e 0时 取当前象素 xi yi 的右上方象素 而当e 0时 更接近于右方象素 计算机图形学基础 可以改用整数以避免除法 由于算法中只用到误差项的符号 因此可作 如下替换 例 Line P0 0 0 P1 5 2 k dy dx 0 4 x y e 0 0 0 5 1 0 0 1 2 1 0 3 3 1 0 3 4 2 0 1 5 2 0 5 大于零 y加一 小于零 不变 计算机图形学基础 void Bresenhamline int x0 int y0 int

9、x1 int y1 int color int x y dx dy float k e dx x1 x0 dy y1 y0 k dy dx e 0 5 x x0 y y0 for i 0 i dx i drawpixel x y color x x 1 e e k if e 0 y e e 1 计算机图形学基础 最终 Bresenham算法也是每个象素 需一个整数算法 其优点是可以用于其他二次曲线 至此 直线光栅化是否终结 计算机图形学基础 新方法 BRDC binary representation of displacement code for line Miao LF Liu XG P

10、eng QS Bao HJ COMPUTERS float d x 0 y r d 1 25 r circlepoints x y color 显示圆弧上的八个对称点 while x y if d i 结点的x值递增 x 若允许多边形的边自相交 则用冒泡排序法对AET表重新排序 polyfill 计算机图形学基础 2 3 1 2边界标志算法 基本思想 帧缓冲器中对多边形的每条边进行直线扫描转换 亦即对多边形边界所经过的象素打上标志 然后再采用和扫描线算法类似的方法将位于多边形 内的各个区段着上所需颜色 使用一个布尔量inside来指示当前点是否在多边形 内的状态 计算机图形学基础 算法过程 v

11、oid edgemark fill polydef color 多边形定义 polydef int color 对多边形polydef 每条边进行直线扫描转换 inside FALSE for 每条与多边形polydef相交的扫描线y for 扫描线上每个象素x if 象素 x 被打上边标志 inside inside if inside FALSE drawpixel x y color else drawpixel x y background 计算机图形学基础 用软件实现时 扫描线算法与边界标志算法的执行速 度几乎相同 但由于边界标志算法不必建立维护边表以及对它进行 排序 所以边界标志算

12、法更适合硬件实现 这时它的执 行速度比有序边表算法快一至两个数量级 计算机图形学基础 2 3 2区域填充算法 区域指已经表示成点阵形式的填充图形 它是 象素的集合 区域可采用内点表示和边界表示两种表示形式 区域可分为4向连通区域和8向连通区域 区域填充指先将区域的一点赋予指定的颜色 然后将该颜色扩展到整个区域的过程 区域填充 算法要求区域是连通的 计算机图形学基础 4向连通区域和8向连通区域 四个方向运动 八个方向运动 四连通区域 八连通区域 计算机图形学基础 2 3 2 1区域填充的递归算法 内点表示的4连通区域的递归填充算法 void FloodFill4 int x int y int

13、oldcolor int newcolor if getpixel x y oldcolor 属于区域内点oldcolor drawpixel x y newcolor FloodFill4 x y 1 oldcolor newcolor FloodFill4 x y 1 oldcolor newcolor FloodFill4 x 1 y oldcolor newcolor FloodFill4 x 1 y oldcolor newcolor 计算机图形学基础 边界表示的4连通区域的递归填充算法 void BoundaryFill4 int x int y int boundarycolor

14、 int newcolor int color if color newcolor BoundaryFill4 x y 1 boundarycolor newcolor BoundaryFill4 x y 1 boundarycolor newcolor BoundaryFill4 x 1 y boundarycolor newcolor BoundaryFill4 x 1 y boundarycolor newcolor 计算机图形学基础 2 3 2 2区域填充的扫描线算 法 算法步骤 首先填充种子点所在扫描线上的位于给定区域的一个 区段 然后确定与这一区段相连通的上 下两条扫描线上位 于给

15、定区域内的区段 并依次保存下来 反复这个过程 直到填充结束 计算机图形学基础 1 初始化 堆栈置空 将种子点 x y 入栈 2 出栈 若栈空则结束 否则取栈顶元素 x y 以y作为当前扫描线 3 填充并确定种子点所在区段 从种子点 x y 出发 沿当前扫描线向 左 右两个方向填充 直到边界 分别标记区段的左 右端点坐标为xl和 xr 4 并确定新的种子点 在区间 xl xr 中检查与当前扫描线y上 下相邻的 两条扫描线上的象素 若存在非边界 未填充的象素 则把每一区间的最 右象素作为种子点压入堆栈 返回第 2 步 上述算法对于每一个待填充区段 只需压栈一次 因此 扫描线填充算 法提高了区域填充的效率 计算机图形学基础 本课总结 直线段的扫描转换算法 DDA 中点算法 Bresenham算法 圆弧的扫描转换算法 多边形的扫描转换与区域填充 扫描转换 区域填充 计算机图形学基础 谢谢 计算机图形学基础