《多边形的扫描转换和区域填充技巧》由会员分享，可在线阅读，更多相关《多边形的扫描转换和区域填充技巧（91页珍藏版）》请在金锄头文库上搜索。
1、2020 2 24 多边形的扫描转换和区域填充技巧 第5章 2020 2 24 2 82 上一章讲述了如何生成点 线和圆等基本几何构造 本章重点如何在指定的输出设备上构造多边形域 像素数组等高级图元 提出问题 2020 2 24 3 82 主要内容 矩形填充内外测试多边形扫描转换区域填充多边形扫描转换与区域填充的区别反走样 主要内容 作业 2020 2 24 4 82 学习目标 深入认识图形函数包功能 了解函数是如何实现的 从而可改进图形函数以适应某些特殊的应用需求 开发和改进图形技术 发展网络图形应用 开发更快的实时性更强的图形显示 掌握多边形生成算法掌握区域填充算法了解反走样概念和相应算法
2、 学习目标 2020 2 24 5 82 孙家广 计算机图形学 第三版 ComputerGraphicswithOpenGL 3rdEdition Hearn 参考资料 本章主要参考资料 Content 2020 2 24 6 82 矩形填充 特殊的多边形 在窗口系统中应用很多 在图形软件包中将它单独当作一类图元处理 2020 2 24 7 82 填充前 填充后 如何完成填充的 如何实现算法 2020 2 24 8 82 矩形扫描转换算法 FillRect Rect rect intcolor intx y for y rect ymin yymax y for x rect xmin xxm
3、ax x setPixel x y color Content 2020 2 24 9 82 多边形扫描转换 2020 2 24 10 82 IntroductiontoPolygons DifferenttypesofPolygonsSimpleConvexSimpleConcaveNon simple self intersectingWithholes Convex Concave Self intersecting 2020 2 24 11 82 ConcavePolygons Identifying Crossproductsofsuccessiveedgepairsareofdif
4、ferentsignsVerticesareonbothsidesofanedgeSplitting Alongthelineofthefirstedgeinthecross productpairRotationalmethod Aligneachedgewiththexaxis 2020 2 24 12 82 多边形扫描转换 逐点判断算法扫描线填充算法边缘填充算法 2020 2 24 13 82 逐点判断算法 实现扫描转换多边形最简单的算法是逐点判断 即判断一个像素是否在多边形内部 是则填充颜色 否则放弃两种常用的判断像素在多边形内部的方法 射线法 类似奇偶规则弧长法 类似非0环绕数规则缺
5、点 速度慢 效率低 2020 2 24 14 82 内外测试 区域填充算法和其它图形处理常需要鉴别对象的内部区域 在基本几何形体中 多边形通常被定义为不自交的 标准多边形的例子有三角形 四边形 八角形和十角形 这些对象的组成边仅在顶点处连接 在平面内没有其它公共点 鉴别标准多边形的内部区域通常是 个直观过程 2020 2 24 15 82 但在大多数图形应用中 我们可以指定填充区域顶点的任何次序 包括有相交的边的次序 如图 对这样的形状 平面上哪个区域是 内部 和那个区域是对象的 外部 并不是一目了然的 图形软件包通常采用奇 偶规则或非零环绕数规则来鉴别物体的内部区域 2020 2 24 16
6、 82 奇 偶规则 也称奇偶性规则或偶奇规则 它在概念上从任何位置P到对象坐标范围以外远距离画一直线 射线 并统计沿该射线与各边的交点数目 假如与这条射线相交的多边形边数为奇数 则P是内部点 否则P是外部点 为了得到精确的边数 必须保证所画射线不与任何多边形顶点相交 后面所讨论的多边形扫描线填充算法是用奇偶规则的区域填充的一个例子 奇偶规则 2020 2 24 17 82 非零环绕数规则 它统计有向多边形边环绕某一特定点的次数 这个数称为环绕数 二维物体的内部点被定义为具有环绕数为非0值 判定规则 在对多边形应用非零环绕数规则时 将环绕数初始化为零 从任意位置P画一射线 所选择的射线不能与多边
7、形任何顶点相交 当从P点沿射线方向移动时 对穿过射线的边记数 每当多边形从右到左穿过射线时 环绕数加1 从左到右时 环绕数减1 在所有穿过的边都已记数后的环绕数的最后值决定P的相应位置 假如环绕数为非0 则P定义为内部点 否则P是外部点 非零环绕数规则 2020 2 24 18 82 对于标准多边形和其它简单形状 奇偶规则和非零环绕数规则会给出相同的结果 但对于复杂形状 两种方法会产生不同的内部和外部区域 用两种方法得到内外判断结论不同 2020 2 24 19 82 确定有向边与射线相交的方法 1 将从P点出发的射线向量u与边向量E的叉积u E 如果叉积的z值大于0则 边从右到左穿过射线 环
8、绕数加1 否则环绕数减1 2 较简单的算法是用点积代替叉积 为此 我们建立一个垂直u且p沿u方向看是从右到左指向的向量v 例如u的元素是 ux uy 则垂直于u的向量v的元素 uy ux 如果v E 0 则从右到左穿越射线 环绕数加1 否则减1 Content 2020 2 24 20 82 扫描线多边形填充算法 本算法适合凸多边形 凹多边形 如何进行多边形填充 2020 2 24 21 82 Scan LinePolygon Filling DeterminetheintersectionpositionsoftheregionboundarieswiththescanlinesApplyf
9、illcolorstoeachsectionofascanlinethatliesinsidethefillregion odd evenrule 2020 2 24 22 82 填充步骤 确定扫描线与多边形边的交点位置 将这些点自左至右存储 并给每对交点间对应的帧缓冲器位置设置指定的填充颜色 由于有时交点数目并不为偶数个 因此 有些多边形顶点处的扫描线交点需要专门处理 在这些位置上 扫描线通过一个顶点与多边形的两条边相交 在这根扫描线的交点表上要增加两个点 关键要保证交点数目成偶数 2020 2 24 23 82 影响交点计数的问题发生在 观察两个顶点的区别 有两种方法能使扫描线与多边形交点
10、个数为偶数 2020 2 24 24 82 方法1 如果两条顺序连接的边的端点y坐标单调地增加或减少 那么对于任何该穿过该点的扫描线就必须将该中间顶点计为一个交点 否则 共享的顶点表示多边形边界上的一个局部极值 最大或最小 两条边与穿过该顶点的扫描线的交点可以添加到相关表中 记为两个交点 该方法能保证水平扫描线与多边形的交点的个数为偶数 2020 2 24 25 82 方法2 将多边形某些边缩短以分离那些应计为1个交点的顶点 我们可以以指定的顺时针或逆时针方向处理整个多边形边界上的非水平边 在处理每条边时进行检测 确定该边与下一条非水平边是否有单调递增或单调递减的端点y值 假如有 可将较低的一
11、条边缩短以保证对通过连接两条边的公共顶点的扫描线仅有一个交点生成 当两条边的端点y值增加时 当前边的较高的端点y值减去1 当端点y值单凋递减时 紧随当前边的那个边的较高端点的y坐标减1 2020 2 24 26 82 每次填充都是以画水平线来进行 且每条水平线都是以落笔开始 由于y值保持不变 所以 每次落笔时画出一条水平线 再抬笔 落笔 又画出一条水平线 填充方法 2020 2 24 27 82 1 求交点 2 交点排序 3 交点配对 4 区间填色 填充步骤 如何高效率求交点 2020 2 24 28 82 m yk 1 yk xk 1 xk 由于两扫描线间y坐标的变化 yk 1 yk 1 所
12、以 xk 1 xk 1 m扫描线k沿一条具有斜率m的边 相对于最初扫描线的交点x0 xk可计算为 xk x0 k m 而m y x 其中 y和 x分别是边端点y和x坐标值间的差 因此 xk 1 xk x y xk x0 k x y 如何有效求交点 2020 2 24 29 82 为了有效地完成多边形填充 可首先将多边形的边存储在包含有效地处理扫描线所需要的全部信息的有序边表中 无论以顺时针或逆时针方向沿边处理时 按每条边最小y值排序 存储在一个相应编号的扫描线位置 有序边表中仅存非水平线 在处理边时 可以缩短某些边以解决顶点相交问题 对于某条特定的扫描线 表中的每个入口包含该边的最大y值 边的
13、x交点值 在较低顶点处 和边斜率的倒数 对于每条扫描线 边以从左到右的次序排序 一个多边形及相应的有序边表如图 高效求交点 数据结构 2020 2 24 30 82 一个多边形及相应的有序边表 ET ET举例 讨论 如何从ET从高效率计算交点 结论 从ET计算交点会引入不必要的计算 效率低 2020 2 24 31 82 从多边形的底部到顶部处理扫描线 每条与多边形边相交的扫描线生成一个活化边表 扫描线的活化边表 AET 包含所有与该扫描线相交的边 并用循环连贯性计算得到扫描线与边的交点 2020 2 24 32 82 AET举例 注 对每条与多边形相交的扫描线都会有一个AET 问题 如果扫描
14、线ye的AET 利用连贯性 构造下一扫描线ye 1的AET 2020 2 24 33 82 BasicIdea x Ackland B andWeste N RealTimeAnimationonFrameStoreDisplaySystem ComputerGraphics 14 1980 182 188 Complementthepixelsontherightofanedge EdgeFillAlgorithm 2020 2 24 34 82 EdgeFillAlgorithm Cont EdgeP2P3 EdgeP3P4 EdgeP4P5 EdgeP5P1 Nosorting Simp
15、leDataStructureHowever eachpixelmaybeaccessedmorethanonce Canwereducethenumberofaccessestoeachpixel 2020 2 24 35 82 区域填充 区域 一个区域是一组相邻而又相连的像素 或者说是一组相互毗邻而又连通的像素 区域填充 先将区域内的一点赋予一颜色 然后将该颜色扩充到真个区域内的过程 2020 2 24 36 82 区域分类 根据区域的定义和生成方式分为 内部定义区域 区域内所有的像素具有同一的颜色或亮度值 区域外不同 填充该区域的算法为漫水法或种子泛滥填充算法边界定义区域 由一个边界来定
16、义的区域 边界部分的像素具有单一值 边界包围的部分就是区域本身 区域本身部分的像素值具有不同于边界上的像素值 可以互不相同 填充该区域的算法为边界填充算法 2020 2 24 37 82 区域分类 根据像素之间的连通方式可分为两类 四连通区域 当把一个区域看成是四连通区域时 区域中任何一个像素可访问其上下左右的四个相邻像素 即这个像素最多与四个相邻的像素连通八连通区域 此时 区域中的任何一个像素可访问其上下左右四个相邻像素外 还可访问两条对角线方向上的四个近邻像素 四连通区域是八连通区域的一种特殊情况 2020 2 24 38 82 区域填充算法要求区域是连通的 通常只考虑两种简单的连通性 4连通和8连通 4连通区域和8连通区域 2020 2 24 39 82 区域举例 4连通和8连通的内部定义区域 2020 2 24 40 82 区域举例 4连通和8连通的边界定义区域 2020 2 24 41 82 一个8连通区域的边界是4连通的 而一个4连通区域的边界则是8连通的一个8连通区域填充算法可以填充4连通区域 但由于可以跳过对角线 故可能越界 产生意想不到的效果 有哪些方法用于填充区域
