广工数媒计算机图形学之5基本图形生成算法-多边形扫描转换及区域填充.ppt_第1页
广工数媒计算机图形学之5基本图形生成算法-多边形扫描转换及区域填充.ppt_第2页
广工数媒计算机图形学之5基本图形生成算法-多边形扫描转换及区域填充.ppt_第3页
广工数媒计算机图形学之5基本图形生成算法-多边形扫描转换及区域填充.ppt_第4页
广工数媒计算机图形学之5基本图形生成算法-多边形扫描转换及区域填充.ppt_第5页
已阅读5页,还剩15页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、计算机图形学一个重要问题是在一个区域的内部填上不同的图案、灰度或色彩。 计算机图形学领域所说的区域分为两类:一类是以顶点和边界界定的多边形;一类是以像素点阵(即多边形内部的像素的集合)表示的区域。 通常用确定穿越多边形区域的扫描线的覆盖区域的方法来填充多边形。 用从给定的位置开始涂描直到指定的边界条件为止的方法来填充以像素点阵表示的区域。,区域的表示法,以多边形定义的区域用多边形的顶点序列来定义边界。这种方法直观,几何意义强,占用内存小。但是由于没有明确位于多边形内部的像素集合,所以不能直接用于面着色。,点阵表示用位于多边形内部的像素的集合来刻画多边形。这种表示法失去了多边形重要的几何信息(如

2、顶点、几何边界等),但便于用帧缓存表示图形,是面着色所需要的图形表示形式。,区域的表示法,大多数的图形系统采用顶点序列表示多边形。为解决这种表示法“没有明确位于多边形内部的像素集合,所以不能直接用于面着色”的问题,需要有从多边形顶点表示到点阵表示的转换。这种转换称为多边形扫描转换。 多边形扫描转换即多边形的填充,需要从多边形的顶点信息出发,求出位于多边形内部的各个像素点,并将其颜色写入帧缓存的相应单元中。 二维多边形的扫描转换是三维立体面着色的基础。,多边形扫描转换x-扫描线算法,x-扫描线算法填充多边形基本思路: 扫描线与x轴平行。按照扫描顺序,计算每一条扫描线与多边形的相交区间,用指定颜色

3、显示区间内的像素。区间的端点可以通过计算扫描线与多边形边界线的交点获得。 x-扫描线算法可以填充凸、凹多边形,也可填充中间有空的多边形。,多边形扫描转换x-扫描线算法,算法的实现步骤: 一、确定多边形所有顶点的ymax和ymin,得到扫描的范围和最大扫描线数; 二、求交:扫描线与多边形各边求交点,并确定交点的有效性; 三、排序:将所有有效交点按x坐标的大小排序;,多边形扫描转换x-扫描线算法,算法的实现步骤: 四、交点配对:奇数序号和偶数序号的交点配对; 五、区间填色:将位于一对交点之间的像素置换成指定颜色。,多边形扫描转换x-扫描线算法,扫描线y=5与AB边有无效交点k,在做求交运算之前,判

4、断该扫描线的y坐标不在点A和点B的y坐标之间,不做求交运算。,x-扫描线算法涉及的问题: 一、扫描线与多边形边界交点的有效性判别;,多边形扫描转换x-扫描线算法,x-扫描线算法涉及的问题: 二、扫描线与多边形顶点相交时交点的取舍问题; 情况1、共享顶点的两条边分别落在扫描线两侧时,交点记为1个。 情况2、共享顶点的两条边位于扫描线同侧,交点记为0个或2个。 “X-扫描线算法填充.SWF”演示x-扫描线算法实现的过程。,填充算法边缘填充算法,边缘填充算法的基本思想是逐边向右求补。可以按任意顺序处理多边形的每一条边。在处理每一条边时,首先求出该边与扫描线的交点,然后将每一条扫描线上交点右方的所有像

5、素点取补(若这些点为背景色,则置换为填充色;若这些点为填充色,则置换为背景色)。 多边形的所有边处理完毕后,填充完成。,“边缘填充算法的过程.SWF”演示了边缘填充算法的实现过程。 该算法的优点是简单,缺点是对于复杂图形,每一像素可能要访问多次,效率降低。,填充算法边缘填充算法,边标志算法是边缘填充算法的优化实现。 边标志算法的实现步骤: 一、边标记。首先对多边形的每一条边进行直线的扫描转换,然后给扫描转换后得到的像素添加边标记。 二、点标记。对每一个像素使用一个布尔值inside指示当前状态,inside初值为false。每条扫描线依从左到右的顺序扫描。遇到被标记过的点后, inside值取

6、反,直至遇到下一个被标记点为止。,填充算法边标志填充算法,边标志算法的实现步骤: 三、填充。至下而上完成扫描后,将所有inside值为true的像素点集的颜色置换为填充色,完成多边形填充。 “边标志.SWF”演示了边标志算法实现的过程。,填充算法边标志填充算法,区域填充,区域填充针对以像素点阵(即多边形内部的像素的集合)表示的区域的填充。 区域填充的思路为:从区域内的一个点(种子点)开始,由内向外将填充色扩展到整个区域。,区域填充,与区域填充相关的概念: 边界表示把位于边界的像素一一列举出来,即区域边界上的像素用同一种颜色着色。 4-连通区域和8-连通区域确定了区域内点的邻接方式。,4-邻接点

7、,8-邻接点,以4-邻接点定义的区域称为4-连通区域;以8-邻接点定义的区域称为8-连通区域。,与区域填充相关的概念: 栈栈是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top)对数据项进行插入和删除的操作。对栈内数据的操作遵循后进先出(Last-In/First-Out) 的原则。,区域填充,区域填充边界填充算法,算法步骤:用户确定边界颜色;确定填充色和填充模式(4-连通或8-连通边界填充算法);指定内部点(种子点),按规则搜索当前点的4-邻接点或8-邻接点,若这些点非边界色,也非指定填充色,则置换该点的颜色为填充色,直至完成多边形内部填充。 边界填充算法不要求区域内、外颜色不同,即原多边形内部可以为背景色。,区域填充边界填充算法,栈结构实现4-连通边界填充算法步骤: (1)种子像素入栈; (2)栈顶象素出栈; (3)将出栈象素置成填充色; (4)检查出栈象素的4-邻接点,若其中某个象素点不是边界色且未置成多边形色,则把该象素入栈。 (5)检查栈是否为空,若非空,则执行步骤(2),若为空,则结束。 4-连通边界填充.SWF,区域填充泛填充算法,泛填充算法通常用于给区域重新着色。要求原多边

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论