《计算机图形学基础教程.ppt》由会员分享，可在线阅读，更多相关《计算机图形学基础教程.ppt（54页珍藏版）》请在三一办公上搜索。
1、第四章,多边形填充,有效边表填充算法边缘填充算法种子填充算法,本章学习目标,本章内容,4.1实面积图形的概念4.2 有效边表填充算法4.3 边缘填充算法4.4 种子填充算法4.5 本章小结4.6 习题,4.1实面积图形的概念,实面积图形既能描述物体的几何轮廓，又能表现物体的表面色彩，与人们观察物体表面的习惯相一致，同时，实面积图形也是描述三维物体、绘制三维真实感图形的基础。,4.1.1 多边形的表示,在计算机图形学中，多边形有两种示方法：顶点表示法和点阵表示法。,图 4-3 多边形的顶点表示法,P0,P1,P2,P3,P4,P5,图 4-4 多边形的点阵表示法,多边形的顶点表示法是用多边形的顶
2、点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换，顶点表示法如图4-3所示。,顶点表示法,点阵表示法,多边形的点阵表示法是用多边形覆盖的像素点集来描述。特点是便于直接确定实面积图形覆盖的像素点，是多边形填充所需要的表示形式，但是缺少了多边形顶点的几何信息，如图4-4所示。,多边形的扫描转换,将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出多边形内部的各个像素点信息。,4.2 有效边表填充算法,4.2.1 填充原理4.2.2 边界像素的处理原则4.2.3
3、 有效边和有效边表4.2.4 边表,4.2.1 填充原理,多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间内的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。,图 4-5 用一条扫描线填充多边形,P0,P1,P2,P3,P4,P5,P6,在图4-5中，多边形覆盖了12条扫描线。扫描线y3与多边形有4个交点（2.3，3），(4.5，3），（7，3）和（9，3）。对交点
4、进行圆整处理后的结果为（2，3），(5，3），（7，3）和（9，3）。按x值递增的顺序对交点进行排序、配对后的填充区间为（2，5）和（7，9），共有7个像素点需要填充为指定颜色。,4.2.2 边界像素的处理原则,在实际填充过程中，需要考虑到边界像素影响问题：图4-6中正方形P0P2P4P6被等分为四个小正方形。假定小正方形P0P1P8P7被填充为绿色，P1P2P3P8被填充为橙色，P8P3P4P5被填充为绿色，P7P8P5P6被填充为橙色。四个小正方形的公共边为：P1P8、P8P5、P7P8和P8P3。考虑到公共边P1P8既是正方形P0P1P8P7的右边界，又是正方形P1P2P3P8的左边界；
5、考虑到P7P8既是是正方形P0P1P8P7的上边界，又是正方形P7P8P5P6的下边界，那么P1P8和P7P8应该填充为哪一个小正方形的颜色？同理，P8P5 和P8P3应该填充为哪一个小正方形的颜色？,图 4-6 边界像素的问题,P0,P1,P2,P3,P4,P5,P6,P7,图 4-7 边界像素的处理,P8,P0,P1,P2,P3,P4,P5,P6,P7,P8,在实际填充过程中，也需要考虑到像素面积大小的影响问题：对左下角为（1，1），右上角为（3，3）的正方形进行填充时，若边界上的所有像素全部填充，就得到图4-8所示的结果。所填像素覆盖的面积为33个单位，而正方形的面积实际只有22个单位。
6、,图 4-8 面积33,图 4-9 面积22,为了保解决这些问题，在多边形填充过程中，常采用“下闭上开”和“左闭右开”的原则对边界像素进行处理。图4-6的处理结果如图4-7所示，每个小正方形的右边界像素和上边界像素都没有填充。图4-8的处理结果如图4-9所示，上面一行像素和右面一列像素没有填充。,按照此原则对图4-5中的一些特殊点进行处理：1.P2点的处理原则 图4-5中P2是边P3P2的终点，同时也是边P2P1的起点。按照“下闭上开”的原则，可以自动处理。,图4-10 局部点的处理,P0,P1,P2,P3,P4,P5,P6,2.P0、P3、P5点和P4点的处理原则 P0点、P3和P5是局部最
7、低点，P4点是局部最高点。如果处理不当，扫描线y1会填充区间（3，8），结果填充了P3和P5点之间的像素，如图4-10所示。对局部最低点P0、P3和P5的处理方法为，填充时设置一个逻辑变量（初始值为假），每访问一个结点，逻辑变量值取反一次，若逻辑变量值为真，则填充该区间，这样可以保证局部最低点处理正确。对局部最高点P4，根据“下闭上开”的原则，P4点不予填充，y5扫描线会自动填充P4点，如图4-10所示。,4.2.3 有效边和有效边表形,1.有效边（Active Edge，AE）多边形内与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行求交运算，可以避免与多边形的所有边求交，提高
8、了算法效率。有效边上的扫描线由起点到终点每次加1，即像素点的y坐标为：yy+1，x坐标的变化可以按如下方法推导。,设有效边的斜率为k。假定有效边与当前扫描线yi的交点为（xi，yi），则有效边与下一条扫描线yi+1的交点为（xi+1，yi+1）。其中,。如图4-11所示。这说明随着扫描线的移动，扫描线与有效边交点的x坐标从起点开始可以按增量1/k计算出来。,（xi+1，yi+1）,（xi，yi）,1/k,图4-11 有效边交点相关性,把有效边按照与扫描线交点x坐标递增的顺序存放在一个链表中，称为有效边表，有效边表的结点如图4-12所示。,图 4-12 有效边表结点,2.有效边表（Active
9、Edge Table，AET）,P0,P1,P2,P3,P4,P5,P6,图 4-13 示例多边形,对于图4-13所示的多边形，顶点表示法为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）,P4（6，5）,P5（8，1）,P6（12，9）。,扫描线的最大值为Smax12，最小值为Smin1，共有12条扫描线，每条扫描线之间间隔1个像素单位。每条扫描线的有效边表为如图418所示。,这条扫描线处理完毕后 对于P3、P4和P4、P5两条边，因为下一条扫描线S=5和ymax相等，根据“下闭上开”的原则予以删除。,这条扫描线处理完毕后 对于P2、P3边，因为下一条扫描线S=7和ymax
10、相等，根据“下闭上开”的原则予以删除。当S7时，添加上新边P1、P2。,当S8时，添加上新边P0、P1和P0、P6。,这条扫描线处理完毕后 对于P5P6边和P0P6边，因为下一条扫描线S=9和ymax相等，根据“下闭上开”的原则予以删除。,S=11的扫描线处理完毕后 对于P1P2边和P0、P1边，因为下一条扫描线S=12和ymax相等，根据“下闭上开”的原则予以删除。至此，全部有效边表已经给出。,4.2.4 边表,从有效边表的建立过程可以看出，有效边表给出了扫描线和有效边交点坐标的计算方法，但是没有给出新边出现的位置坐标。为了确定在哪条扫描线上插入了新边，就需要构造一个边表（Edge Tabl
11、e，ET），用以存放扫描线上多边形各条边出现的信息。因为水平边的1/k为，并且水平边本身就是扫描线，在建立边表时可以不予考虑。,(1)边表是按照扫描线顺序管理边的出现情况的一个数据结构。首先，构造一个纵向扫描线链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点称为桶，对应多边形覆盖的每一条扫描线。,1.边表的表示法,将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就存放在相应的扫描线桶中。,对于每一条扫描线，如果新增多条边，则按x|ymin坐标递增的顺序存放在一个链表中，若x|ymin 相等，则按照1/k由小到大排序，这样就形成
12、边表，如图4-14所示。,图 4-14 边表结点,其中，x为新增边低端的x|ymin值，用于判断边表在桶中的排序；ymax是该边所在的最大扫描线值，用于判断该边何时成为无效边。1/k是边在x方向的变化量和在y方向的变化量的比值，即x/y。从图4-14可以看出边表是有效边表的特例，即该边的最低点处的有效边表，有效边表和边表可以使用同一个数据结构来表示。,对于图 4-13示例多边形。边表结构如图4-15所示。,2.边表示例,图 4-15 边表,4.3 边缘填充算法,4.3.1 填充原理4.3.2 填充过程,4.3.1 填充原理,边缘填充算法是求出多边形的每条边与扫描线的交点，然后将交点右侧的所有像
13、素颜色全部取为反色。按任意顺序处理完多边形的所有边后，就完成了多边形的填充任务。,4.3.2 填充过程,假定边的顺序为E0、E1、E2、E3、E4、E5、E6，如图4-16所示。填充过程如图4-17所示。,图 4-16 边缘填充算法示例多边形,P0（x0，y0）,P1（x1，y1）,E0,E1,E2,E3,E4,E5,E6,图 4-17 边缘填充算法原理,对每一条边，如E0,起点为P0(x0,y0),终点为P1(x1,y1),则该边扫描线的最小值为ymin=y0,最大值为ymax=y1,斜率为边上当前扫描线的坐标为xi，则边上下一条扫描线的坐标为xi+1=xi+1/k。在扫描线沿着该边从y0移
14、动到y1的过程中，将该边右边界内所有像素的颜色取反。,P0（x0，y0）,P1（x1，y1）,E0,E1,E2,E3,E4,E5,E6,4.4 种子填充算法,4.4.1 填充原理4.4.2 四邻接点和八邻接点4.4.3 四连通域和八连通域4.4.4 四邻接点填充算法和八邻接点填充算法,4.4.1 填充原理,用点阵方法表示的多边形区域，如果其内部像素具有同一种颜色，而边界像素具有另一种颜色，可以使用种子算法进行填充。种子填充算法是从区域内任一个种子像素位置开始，由内向外将填充色扩散到整个多边形区域的填充过程。,4.4.2 四邻接点和八邻接点,4.4.3 四连通域和八连通域,4.4.3 四连通域和
15、八连通域,4.4.4 四邻接点填充算法和八邻接点填充算法,4.4.4 四邻接点填充算法和八邻接点填充算法,4.5 本章小结,本章主要讲解了多边形的填充原理。有效边表算法可以访问多边形内的每一个像素，是光照模型的基础，请读者深刻体会AET表和ET表的内涵。AET表表示的是扫描线在一条边上的连贯性，ET表表示的是新边在扫描线上的插入位置，ET表是AET表的特例。种子填充算法主要包括四邻接点算法和八邻接点算法，特别要注意区分四连通域和八连通域。,4.6 习题,试写出图4-33所示多边形的边表和扫描线y4的有效边表。,P0,P1,P2,P3,P4,P5,P6,图4-33 多边形,4.6 习题,2.给定
16、四个点绘制图4-34所示的不同转角的两个正方形，使用有效边表算法进行填充，填充效果如图4-35所示，注意采用“左闭右开”和“上闭下开”的原则，使得每个正方形的右边界和下边界没有填充。,图4-34 填充正方形,图4-35 正方形填充效果图,4.6 习题,3.图4-36所示的每个正方形由两个三角形面片组成，可以通过填充三角形面片完成正方形的填充任务，填充效果如图4-37所示。请编程实现并观察在每个正方形的三角形面片连接处是否填充完整。,图4-36 三角形面片填充正方形,图4-37 正方形填充效果图,4.6 习题,4.图4-38所示的每个正方形由两个三角形面片组成，可以通过填充三角形面片完成正方形的
17、填充任务，填充效果如图4-39所示。请修改上题的三角形定义编程实现。,图4-38 三角形面片填充正方形,图4-39 正方形填充效果图,4.6 习题,5.图4-40所示正方形由4个三角形面片组成，可以通过填充三角形面片完成正方形的填充任务。使用有效边表算法编程实现，填充效果如图4-41所示。请观察在每个正方形的三角形连接处是否有没有填充到的线段。,图4-40三角形面片填充正方形 图4-41 正方形填充效果,4.6 习题,6.绘制一个正方形，把正方形四等分，如图4-42所示，使用红、绿、黄、蓝四种颜色填充每个小四边形面片，如图4-43所示，请使用有效边表算法编程实现。,图4-42四边形面片填充正方
18、形 图4-43 正方形填充效果图,4.6 习题,7.边缘填充算法中，像素的取补范围为每条边到屏幕整个客户区的右边界。请设置如图4-44所示的外接矩形，并使用边缘填充算法编程实现多边形的填充。填充效果如图4-45所示。,图 4-44 带外接矩形的多边形 4-45带外接矩形的多边形填充效果图,4.6 习题,8.边缘填充算法的最大缺点是填充过程中，每一个像素可能被多次访问。为此，常在多边形外接矩形的中心设置栅栏，把多边形分成两部分，如图4-46所示。在处理每条扫描线时，只将交点与栅栏间的像素取补，请编程实现。填充效果如图4-47所示。,图 4-46 带栅栏的的多边形 4-47 带栅栏的多边形填充效果
19、图,4.6 习题,9.设定图4-48所示的八连通区域边界色为黑色，填充色为蓝色，请使用八邻接点算法编程填充八连通域。请注意图中两个四边形区域的连接处的放大效果如图4-49所示。,图 4-48八连通域 图 4-49八连通域连接点放大效果图,4.6 习题,10.*扫描线种子填充算法是通过扫描线来填充多边形内的水平像素段，处理每条扫描线时仅需将其最右端像素入栈，可以有效提高填充效率。请使用MFC编程填充图4-50所示的空心体汉字（四连通），填充效果如图4-51所示。,图 4-50 四连通空心汉字 图 4-51填充效果图,4.6 习题,11.*使用鼠标在屏幕上绘制任意顶点数的封闭多边形并填充，填充效果如图4-52所示，请编程实现。编程要求：多边形的顶点数不受限制；按下鼠标左键，拖动鼠标绘制多边形，同时按下Shift键可以绘制水平边或垂直边；单击鼠标右键闭合多边形；使用边缘填充算法填充多边形。,图 4-52任意多边形填充算法,
