《(2.4)--第4章 多边形填充高级计算机图形学原理与实践.ppt》由会员分享，可在线阅读，更多相关《(2.4)--第4章 多边形填充高级计算机图形学原理与实践.ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、有效边表填充算法有效边表填充算法边缘填充算法边缘填充算法种子填充算法种子填充算法n n4.14.1实面积图形的概念实面积图形的概念n n4.2 4.2 有效边表填充算法有效边表填充算法n n4.3 4.3 边缘填充算法边缘填充算法n n4.5 4.5 本章小结本章小结n n4.6 4.6 习题习题4.14.1实面积图形的概念实面积图形的概念 实面积图形既能描述物体的几何轮廓，又能表现物体的表面的颜色，与人们观察物体表面的习惯相一致，同时，实面积图形也是描述三维物体表面模型、绘制真实感图形的基础。4.1.1 4.1.1 多边形多边形的定的定义义多边形是由折线段组成的封闭图形。它由有序顶点的点集P
2、i（i=0n-1）及有向边的线集Ei（i=0n-1）定义，n为多边形的顶点数或边数，且EiPiPi+1，i=0n-1。这里PnP0，用以保证了多边形的封闭性。多边形可以分为凸、凹多边形以及环。P0P1P2P3P4P5E0E1E2E3E4E5顺时针逆时针 多边形上任意两顶点间的连线都在多边形之内，凸点对应的内角小于180，只具有凸点的多边形称为凸多边形。1.1.凸多边形凸多边形2.2.凹多边形凹多边形 多边形上任意两顶点间的连线有不在多边形内部的部分，凹点对应的内角大于180，有一个凹点的多边形称为凹多边形。3.3.环环 多边形内包含有另外的多边形。如果规定：每条有向边的左侧为其内部实面积区域。
3、则当观察者沿着边界行走时，内部区域总在其左侧，也就是说多边形外轮廓线的环行方向为逆时针，内轮廓线的环行方向为顺时针。这种定义了环行方向的多边形称为环。4.1.2 4.1.2 多边形的表示多边形的表示 在计算机图形学中，多边形有两种示方法：顶点表示法和点阵表示法。多边形的顶点表示法 P P0 0P P1 1P P2 2P P3 3P P4 4P P5 5多边形的点阵表示法 P P6 6 多边形的顶点表示法是用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换。1.1.顶点表示法顶点表示法2.2.点阵
4、表示法点阵表示法 多边形的点阵表示法是用多边形覆盖的像素点集来描述。特点是便于直接确定实面积图形覆盖的像素点，是多边形填充所需要的表示形式，但是缺少了多边形顶点的几何信息。3.3.多边形的扫描转换多边形的扫描转换 将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出多边形内部的各个像素点信息。4.1.3 4.1.3 多边形的填多边形的填充充 多边形的填充是确定穿越多边形内部的扫描线的覆盖区间。首先确定多边形覆盖的扫描线条数（yyminymax），对每一条扫描线，计算扫描线与多边形边界的交点区间（xminxmax），然后再将该区间内的像素赋予指定
5、的颜色。在扫描线从多边形顶点的最小值ymin到多边形顶点的最大值ymax的移动过程中，重复上述工作，就可以填充多边形。4.2 4.2 有效边表填充算法有效边表填充算法n4.2.1 4.2.1 填充原理填充原理n4.2.2 4.2.2 边界像素的处理原则边界像素的处理原则n4.2.3 4.2.3 有效边和有效边表有效边和有效边表n4.2.4 4.2.4 桶表和边表桶表和边表4.2.1 4.2.1 填充原理填充原理 多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与有效边有效边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色设置填
6、充区间内的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。图 4-5 用一条扫描线填充多边形内部 P P0 0P P1 1P P2 2P P3 3P P4 4P P5 5P P6 6 图中多边形覆盖了12条扫描线。扫描线y3与多边形有4个交点（2.3，3），(4.5，3），（7，3）和（9，3）。对交点进行圆整处理后的结果为（2，3），(5，3），（7，3）和（9，3）。按x值递增的顺序对交点进行排序、配对后的填充区间为2，5和7，9，共有7个像素点需要填充为指定颜色。4.2.2 4.2.2 边界像素的
7、处理原则边界像素的处理原则 在实际填充过程中，需要考虑到边界像素影响问题：图4-6中正方形P0P2P4P6被等分为4个小正方形。假定小正方形P0P1P8P7被填充为绿色，P1P2P3P8被填充为橙色，P8P3P4P5被填充为绿色，P7P8P5P6被填充为橙色。4个小正方形的公共边为：P1P8、P8P5、P7P8和P8P3。考虑到公共边P1P8既是正方形P0P1P8P7的右边界，又是正方形P1P2P3P8的左边界；考虑到P7P8既是是正方形P0P1P8P7的上边界，又是正方形P7P8P5P6的下边界，那么P1P8和P7P8应该填充为哪一个小正方形的颜色？同理，P8P5 和P8P3应该填充为哪一个
8、小正方形的颜色？图 4-6 边界像素的问题 P P0 0P P1 1P P2 2P P3 3P P4 4P P5 5P P6 6P P7 7图 4-7 边界像素的处理 P P8 8P P0 0P P1 1P P2 2P P3 3P P4 4P P5 5P P6 6P P7 7P P8 8 在实际填充过程中，也需要考虑到像素面积大小的影响问题：对左下角为（1，1），右上角为（3，3）的正方形进行填充时，若边界上的所有像素全部填充，就得到图4-8所示的结果。所填像素覆盖的面积为33个单位，而正方形的面积实际只有22个单位。图 4-8 面积33 为了保解决这些问题，在多边形填充过程中，常采用“下闭上
9、开”和“左闭右开”的原则对边界像素进行处理。图4-6的处理结果如图4-7所示，每个小正方形的右边界像素和上边界像素都没有填充。图4-8的处理结果如图4-9所示，上面一行像素和右面一列像素没有填充。图 4-9 面积22图4-5中P2是边P3P2的终点，同时也是边P2P1的起点。按照“下闭上开”的原则，可以自动处理。图4-10 局部点的处理P P0 0P P1 1P P2 2P P3 3P P4 4P P5 5P P6 61.P1.P2 2点的处理原则点的处理原则 P0 0点、P3 3和P5 5是局部最低点，P4 4点是局部最高点。如果处理不当，扫描线y1会填充区间3，8，结果填充了P3 3和P5
10、 5点之间的像素，如图4-10所示。对局部最低点P0 0、P3 3和P5 5的处理方法为，填充时设置一个逻辑变量（初始值为假），每访问一个结点，逻辑变量值取反一次，若逻辑变量值为真，则填充该区间，这样可以保证局部最低点处理正确。对局部最高点P4，根据“下闭上开”的原则，P4点不予填充，y5扫描线会自动填充P4点，如图4-10所示。2.P2.P0 0、P P3 3、P P5 5点和点和P P4 4点的处理原则点的处理原则 事实上，这种处理方法是将每个局部最低点P0点、P3和P5都看作是两个点处理；局部最高点P4看作是零个点处理，普通点P2看作是一个点处理。4.2.3 4.2.3 有效边和有效边表
11、有效边和有效边表 1.1.有效边有效边 多边形内与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行求交运算，可以避免与多边形的所有边求交，提高了算法效率。有效边上的扫描线由起点到终点每次加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 有效边交点相关性1 图 4-12
12、有效边表结点2.2.有效边表有效边表 把有效边按照与扫描线交点x坐标递增的顺序存放在一个链表中，称为有效边表，有效边表的结点如图4-12所示。class CAET/有效边表类 public:CAET();/构造函数virtual CAET();/析构函数double x;int yMax;double k;/程序中令：CAET*next;P P0 0P P1 1P P2 2P P3 3P P4 4P P5 5P P6 6图 4-13 示例多边形对于图4-13所示的多边形，顶点表示法为：P0（7,8）,P1（3,12）,P2（1,7）,P3（3,1）,P4（6,5）,P5（8,1）,P6（12,
13、9）。扫描线的最大值为Smax12，最小值为Smin1，共有12条扫描线，每条扫描线之间间隔1个像素单位。每条扫描线的有效边表为如图418所示。这条扫描线处理完毕后 对于P3P4和P4P5两条边，因为下一条扫描线S=5和ymax相等，根据“下闭上开”的原则予以删除。这条扫描线处理完毕后 对于P2P3边，因为下一条扫描线S=7和ymax相等，根据“下闭上开”的原则予以删除。当S7时，添加上新边P1、P2。当S8时，添加上新边P0P1和P0P6。这条扫描线处理完毕后 对于P5P6边和P0P6边，因为下一条扫描线S=9和ymax相等，根据“下闭上开”的原则予以删除。S=11的扫描线处理完毕后 对于P
14、1P2边和P0P1边，因为下一条扫描线S=12和ymax相等，根据“下闭上开”的原则予以删除。至此，全部有效边表已经给出。4.2.4 4.2.4 桶表和边表桶表和边表 从有效边表的建立过程可以看出，有效边表给出了扫描线和有效边交点坐标的计算方法，但是没有给出新边出现的位置坐标。为了确定在哪条扫描线上插入了新边，就需要构造一个边表（Edge Table，ET），用以存放扫描线上多边形各条边出现的信息。因为水平边的1/k为，并且水平边本身就是扫描线，在建立边表时可以不予考虑。1.桶表是按照扫描线顺序管理边的出现情况的一个数据结构。首先，构造一个纵向扫描线链表，链表的长度为多边形所占有的最大扫描线数
15、，链表的每个结点称为桶，对应多边形覆盖的每一条扫描线。1.1.桶表和边表的表示法桶表和边表的表示法class CBucket public:CBucket();virtual CBucket();int ScanLine;/扫描线AET*p;/桶上的边表指针CBucket*next;2.将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就存放在相应的扫描线桶中。3.对于每一条扫描线，如果新增多条边，则按x|ymin坐标递增的顺序存放在一个链表中，若x|ymin 相等，则按照1/k由小到大排序，这样就形成边表，如图4-14所示。图 4-14
16、边表结点 其中，x为新增边低端的x|ymin值，用于判断边表在桶中的排序；ymax是该边所在的最大扫描线值，用于判断该边何时成为无效边。1/k是边在x方向的变化量和在y方向的变化量的比值，即x/y。从图4-14可以看出边表是有效边表的特例，即该边的最低点处的有效边表，有效边表和边表可以使用同一个数据结构来表示。2.2.边表示例边表示例图 4-15 边表4.3 4.3 边缘填充算法边缘填充算法n4.3.1 4.3.1 填充原理填充原理n4.3.2 4.3.2 填充过程填充过程4.3.1 4.3.1 填充原理填充原理 边缘填充算法是求出多边形的每条边与扫描线的交点，然后将交点右侧的所有像素颜色全部
17、取为反色。按任意顺序处理完多边形的所有边后，就完成了多边形的填充任务。4.3.2 4.3.2 填充过程填充过程 假定边的顺序为E0、E1、E2、E3、E4、E5、E6，如图4-16所示。填充过程如图4-17所示。图 4-16 边缘填充算法示例多边形P0（x0，y0）P1（x1，y1）E E0 0E1E2E3E4E5E6图 4-17 边缘填充算法原理对每一条边，如E0边，起点为P0（x0，y0），终点为P1（x1，y1）。该边扫描线的最小值为ymin=y0，最大值为ymax=y1，斜率为 ，边上当前扫描线的坐标为xi，则边上下一条扫描线的坐标为xi+1=xi+1/k。在扫描线沿着该边从y0移动到
18、y1的过程中，将该边右侧边界内的所有像素的颜色全部取反，即如果当前右侧像素的颜色为背景色，则改为填充色，反之亦然。全部扫描完每一条边后，填充过程也就结束了。边缘填充算法的效率受到交点右侧像素点的数量影响，右侧像素点越多，需要取反的像素点也就越多。为了提高填充效率，可以在图4-18所示多边形的外接矩形范围内进行像素取反，或者如图4-19所示，在多边形内添加栅栏，在处理每条边与扫描线的交点时，只将交点与栅栏之间的像素取反。若交点位于栅栏左侧，将交点之右，栅栏之左的所有像素取反；若交点位于栅栏右侧，将栅栏之右，交点之左的所有像素取反。图 4-18 带外接矩形的多边形 图 4-19 带栅栏形的多边形4
19、.4 4.4 区域填充算法区域填充算法n4.4.1 4.4.1 填充原理填充原理n4.4.2 4.4.2 四邻接点与八邻接点四邻接点与八邻接点n4.4.3 4.4.3 四连通域与八连通域四连通域与八连通域n4.4.4 4.4.4 四邻接点与八邻接点填四邻接点与八邻接点填充算法充算法n扫描线种子填充算法扫描线种子填充算法4.4.1 4.4.1 填充原理填充原理用点阵方法表示的多边形区域，如果其内部像素具有同一种颜色，而边界像素具有另一种颜色，可以使用种子算法进行填充。种子填充算法是从区域内任一个种子像素位置开始，由内向外将填充色扩散到整个多边形区域的填充过程。4.4.2 4.4.2 四邻接点和八
20、邻接点四邻接点和八邻接点 4.4.3 4.4.3 四连通域和八连通域四连通域和八连通域 四连通域及其四连通边界 四连通域及其八连通边界 八连通域及其四连通边界 八连通域及其八连通边界 四邻接点算法填充八连通域 八邻接点算法填充八连通域 4.4.4 4.4.4 4.4.4 4.4.4 四邻接点填充算法和八邻接点填充算法四邻接点填充算法和八邻接点填充算法四邻接点填充算法和八邻接点填充算法四邻接点填充算法和八邻接点填充算法 1.算法定义算法定义 从种子像素点开始，使用四邻接点方式搜索下一像素点的填充算法称为四邻接点填充算法。从种子像素点开始，使用八邻接点方式搜索下一像素点的填充算法称为八邻接点填充算
21、法。四邻接点填充算法的缺点是不能通过狭窄区域，即不能填充八连通域。八邻接点填充算法既可以填充四连通域，也可以填充八连通域。八邻接点填充算法的设计和四邻接点填充算法基本相似，只要把搜索方式由四邻接点修改为八邻接点即可。2.算法原理算法原理 种子填充算法一般要求区域边界色和填充色不同，输入参数只有种子坐标位置和颜色。种子填充算法一般需要使用堆栈数据结构来实现。算法原理为：先将种子像素入栈，种子像素为栈底像素，如果栈不为空，执行如下三步操作：栈顶像素出栈；按填充色绘制出栈像素。按左、上、右、下（或左、左上、上、右上、右、右下、下、左下）顺序搜索与出栈像素相邻的四（八）个像素，若该像素的颜色不是边界色
22、并且未置成填充色，则把该像素入栈；否则丢弃该像素。3.扫描线种子填充算法扫描线种子填充算法种子填充算法会把大量的像素压入堆栈，有些像素甚至入栈多次，不仅降低了算法的效率，而且占用了很大的存储空间。有效的改进方法是使用扫描线种子填充算法。算法原理为：先将种子像素入栈，种子像素为栈底像素，如果栈不为空，执行如下3步操作：栈顶像素出栈；沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止。同时记录填充该区间，其最左端像素记为xl，最右端像素记为xr。在区间xl，xr上，检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界色或填充色，若存在非边界且未填充的像素，则把上下扫描线的最右端像素取
23、作种子像素入栈，该种子像素的横坐标为xr或xr1。4.5 4.5 本章小结本章小结 本章主要讲解了多边形的填充原理。有效边表算法可以访问多边形内的每一个像素，是光照模型的基础，请读者深刻体会AET表和ET表的内涵。AET表表示的是扫描线在一条边上的连贯性，ET表表示的是新边在扫描线上的插入位置，ET表是AET表的特例。种子填充算法主要包括四邻接点算法和八邻接点算法，特别要注意区分四连通域和八连通域。4.6 4.6 习题习题1.1.试写出图试写出图4-334-33所示多边形的边表和扫描所示多边形的边表和扫描线线y y4 4的有效边表。的有效边表。P P0 0P P1 1P P2 2P P3 3P
24、 P4 4P P5 5P P6 6图图4-33 4-33 多边形多边形 4.6 4.6 习题习题2.2.给定四个点绘制图给定四个点绘制图4-344-34所示的不同转角的两个正方所示的不同转角的两个正方形，使用有效边表算法进行填充，填充效果如图形，使用有效边表算法进行填充，填充效果如图4-354-35所示，注意采用所示，注意采用“左闭右开左闭右开”和和“上闭下开上闭下开”的原的原则，使得每个正方形的右边界和下边界没有填充。则，使得每个正方形的右边界和下边界没有填充。图图4-34 4-34 填充正方形填充正方形 图图4-35 4-35 正方形填充效果图正方形填充效果图 4.6 4.6 习题习题3.
25、3.图图4-364-36所示的每个正方形由两个三角形面片组成，可所示的每个正方形由两个三角形面片组成，可以通过填充三角形面片完成正方形的填充任务，填充效以通过填充三角形面片完成正方形的填充任务，填充效果如图果如图4-374-37所示。请编程实现并观察在每个正方形的三所示。请编程实现并观察在每个正方形的三角形面片连接处是否填充完整。角形面片连接处是否填充完整。图图4-36 4-36 三角形面片填充正方形三角形面片填充正方形 图图4-37 4-37 正方形填充效果图正方形填充效果图 4.6 4.6 习题习题4.4.图图4-384-38所示的每个正方形由两个三角形面片所示的每个正方形由两个三角形面片
26、组成，可以通过填充三角形面片完成正方形的组成，可以通过填充三角形面片完成正方形的填充任务，填充效果如图填充任务，填充效果如图4-394-39所示。请修改上所示。请修改上题的三角形定义编程实现。题的三角形定义编程实现。图图4-38 4-38 三角形面片填充正方形三角形面片填充正方形 图图4-39 4-39 正方形填充效果图正方形填充效果图 4.6 4.6 习题习题5.5.图图4-404-40所示正方形由所示正方形由4 4个三角形面片组成，可个三角形面片组成，可以通过填充三角形面片完成正方形的填充任务。以通过填充三角形面片完成正方形的填充任务。使用有效边表算法编程实现，填充效果如图使用有效边表算法
27、编程实现，填充效果如图4-414-41所示。请观察在每个正方形的三角形连接处是否所示。请观察在每个正方形的三角形连接处是否有没有填充到的线段。有没有填充到的线段。图图4-404-40三角形面片填充正方形三角形面片填充正方形 图图4-41 4-41 正方形填充效果正方形填充效果4.6 4.6 习题习题6.6.绘制一个正方形，把正方形四等分，如图绘制一个正方形，把正方形四等分，如图4-4-4242所示，使用红、绿、黄、蓝四种颜色填充每所示，使用红、绿、黄、蓝四种颜色填充每个小四边形面片，如图个小四边形面片，如图4-434-43所示，请使用有效所示，请使用有效边表算法编程实现。边表算法编程实现。图图
28、4-424-42四边形面片填充正方形四边形面片填充正方形 图图4-43 4-43 正方形填充效果图正方形填充效果图4.6 4.6 习题习题7.7.边缘填充算法中，像素的取补范围为每条边到边缘填充算法中，像素的取补范围为每条边到屏幕整个客户区的右边界。请设置如图屏幕整个客户区的右边界。请设置如图4-444-44所示所示的外接矩形，并使用边缘填充算法编程实现多边的外接矩形，并使用边缘填充算法编程实现多边形的填充。填充效果如图形的填充。填充效果如图4-454-45所示。所示。图图 4-44 4-44 带外接矩形的多边形带外接矩形的多边形 4-454-45带外接矩形的多边形填充效果图带外接矩形的多边形
29、填充效果图4.6 4.6 习题习题8.8.边缘填充算法的最大缺点是填充过程中，每一个像素边缘填充算法的最大缺点是填充过程中，每一个像素可能被多次访问。为此，常在多边形外接矩形的中心设可能被多次访问。为此，常在多边形外接矩形的中心设置栅栏，把多边形分成两部分，如图置栅栏，把多边形分成两部分，如图4-464-46所示。在处理所示。在处理每条扫描线时，只将交点与栅栏间的像素取补，请编程每条扫描线时，只将交点与栅栏间的像素取补，请编程实现。填充效果如图实现。填充效果如图4-474-47所示。所示。图图 4-46 4-46 带栅栏的的多边形带栅栏的的多边形 4-47 4-47 带栅栏的多边形填充效果图带
30、栅栏的多边形填充效果图4.6 4.6 习题习题9.9.设定图设定图4-484-48所示的八连通区域边界色为黑色，填充色所示的八连通区域边界色为黑色，填充色为蓝色，请使用八邻接点算法编程填充八连通域。请注为蓝色，请使用八邻接点算法编程填充八连通域。请注意图中两个四边形区域的连接处的放大效果如图意图中两个四边形区域的连接处的放大效果如图4-494-49所所示。示。图图 4-484-48八连通域八连通域 图图 4-494-49八连通域连接点放大效果图八连通域连接点放大效果图4.6 4.6 习题习题10.*10.*扫描线种子填充算法是通过扫描线来填充多边形扫描线种子填充算法是通过扫描线来填充多边形内的
31、水平像素段，处理每条扫描线时仅需将其最右端内的水平像素段，处理每条扫描线时仅需将其最右端像素入栈，可以有效提高填充效率。请使用像素入栈，可以有效提高填充效率。请使用MFCMFC编程填编程填充图充图4-504-50所示的空心体汉字（四连通），填充效果如所示的空心体汉字（四连通），填充效果如图图4-514-51所示。所示。图 4-50 四连通空心汉字 图 4-51填充效果图4.6 4.6 习题习题11.*11.*使用鼠标在屏幕上绘制任意顶点数的封闭多边形使用鼠标在屏幕上绘制任意顶点数的封闭多边形并填充，填充效果如图并填充，填充效果如图4-524-52所示，请编程实现。编程所示，请编程实现。编程要求：要求：多边形的顶点数不受限制；多边形的顶点数不受限制；按下鼠标左键，按下鼠标左键，拖动鼠标绘制多边形，同时按下拖动鼠标绘制多边形，同时按下ShiftShift键可以绘制水平键可以绘制水平边或垂直边；边或垂直边；单击鼠标右键闭合多边形；单击鼠标右键闭合多边形；使用边使用边缘填充算法填充多边形。缘填充算法填充多边形。图图 4-524-52任意多边形填充算法任意多边形填充算法