多边形扫描转换.ppt

1、第4章多边形的扫描变换和区域填充、4.1多边形扫描变换4.2区域填充、多边形分为凸面多边形、凹面多边形和具有内环的多边形。4.1多边形的扫描变换、4.1多边形的扫描变换、多边形的表示方法顶点以晶格表示顶点表示：以多边形顶点的序列雕刻多边形。直观、几何和占用的内存较少。不能直接用于面着色。点阵式表现法：透过多边形中像素的集合雕刻多边形。失去了很多重要的几何信息。使用帧缓冲区内存表示图形，易于面着色。4.1多边形的扫描转换、多边形的扫描转换：将多边形的顶点表示转换为晶格表示。也就是说，在多边形的给定边界处查找单个像素，并为帧缓冲区中的每个相应元素设置相应的灰度和颜色。通常称为转换为多边形的扫描转换

2、。两种方法：扫描线算法；边界显示法。扫描线算法，扫描线算法目标：利用相邻像素之间的一致性提高算法效率对象：非自相交多边形(边与边之间没有顶点以外的交点)，扫描线算法，相交规则要求：生成的像素都位于多边形内部，线绘制元素用于扫描转换的舍入原理导致某些像素位于多边形外部，那么非水平边与扫描线y=e相交，交点的横坐标x规则如下：扫描线算法，规则1: x是小数。也就是说，交点确保扫描线两个相邻像素之间的(a)交点位于左上角，整个(b)交点位于右上角，左侧清理，规则2:边界的像素跟踪问题，填充没有扩展。解决方法：边界像素：指定位于右上角边界的像素不填充。具体实施例中，扫描线和多边形的相交部分只要向左和向

3、右打开，扫描线算法、规则3:扫描线与多边形的顶点相交时，交叉的取舍选择确保了正确的交叉对。解决方法：确定两个相邻边位于扫描线的哪一侧。如果仅检查顶点两条边的其他两个端点的y值，则大于交点y值的两个y值的数目将为0，1，2，以确定0，1，2的交点。扫描线算法，多边形扫描转换常用的算法。与逐点判断算法相比，扫描线算法充分利用相邻像素之间的一致性，防止对象单位的逐点判断和迭代交叉运算，从而减少计算量并提高速度。开发和利用相邻像素之间的一致性是光栅图形算法研究的重要组成部分。扫描转换算法综合运用了区域一致性、扫描线一致性、边缘一致性等三种形式的一致性。扫描线算法，设置多边形p的顶点Pi=(xi，yi)

4、，i=0，1，n，yi0，yi1，yin是每个顶点Pi的坐标yi的减少序列，即yikyik 1，0kn-12)这些梯形可分为位于多边形p内部的类的两类。其他类位于多边形p的外部。(3)两种梯形在矩形区域yik，yik 1中上下排列。也就是说，两个相邻的梯形必须分别位于多边形p内，而另一个梯形必须位于p外。y=yik 1，y=yik，根据区域的一致性，实际上只知道矩形区域内任意梯形内多边形p的内侧和外侧关系的一点，即可确定区域内所有梯形p的内侧和外侧关系。将e设定为整数，yi0eyin。如果扫描线y=e与多边形p的Pi-1Pi相交，则交点的横坐标为xei。xei 1、xei 2、xe3、xeil

5、现在是此扫描线和p的边界相交横坐标的增量序列，此序列称为相交序列。从区域的一致性可以看出，该交叉序列具有将扫描线的一致性、扫描线的一致性、1) l设置为偶数的特性。2)在相应的扫描线中，分段(xeik，xeik 1)、k=1，3，5、L-1仅位于多边形p内，其馀分段位于p外。上述称为扫描线一致性的特性反映了多边形区域的一致性。将d设置为整数，并将d=e-1和yi0dyin设置为整数。位于扫描线y=d的交叉顺序为xdj1、xdj2、xdj3和xdjk。现在，我们来看看扫描线d，e相交顺序之间的关系。如果多边形p的边Pr-1Pr和扫描线y=e，y=d都相交，则在相交顺序中与该元素xer，xdr 1

6、/Mr (1)匹配。其中Mr是边Pr-1Pr的斜度。边的一致性，y=e，y=d，边的一致性。因此，e的相交顺序是使用d的相交顺序计算的。也就是说，首先使用递归关系(1)从与扫描线y=e和y=d相交的所有多边形中获取交叉xer，从与扫描线y=e不相交但与扫描线y=e相交的所有边PqPq 1中获取交叉xeq。如果p的顶点坐标为整数，则按升序排列xeq=xq或xeq=xq 1和这两个部分，可以得到e的相交顺序。y=e，y=d，边的一致性，特别是整数k，0kn-1存在，因此，如果yike，dyik 1成立，那么，d的相交序列和e的相交序列之间存在以下关系：1)两个序列元素的数量如上图所示。2)点(xe

7、ir，e)位于(xdjr，d)和多边形p的同一侧，因此xeir=xdjr 1/kj (2)可以使用递归关系(2)直接访问d的交点序列和e的结果e的交点序列。上述特性称为边缘的一致性，相邻的两条扫描线反映了该区域的一致性。如果扫描线和多边形p的交点是p的顶点，则此交点称为奇点。上述多边形的三种形式的一致性基于各扫描线和多边形p的边界交点数为偶数的几何事实。但是，如果简单地将每个奇点计算为一个交点，或简单地计算为两个交点，则可能会出现奇数交点。那么，你能保证触点是偶数吗？奇点处理，奇点处理，奇点交叉处理的话，a，交叉数不是偶数。如果奇点有两个交叉处理，那么b的情况下，交叉数不是偶数。奇点处理，多边

8、形p的顶点可以分为两类：极值奇点和非极值奇点。(yi-1-yi)(yi 1-yi)为0时，顶点Pi称为极值点；否则，Pi称为非极值点。规定：如果奇点不是极值点，则在两个交点计算点，否则在一个交点计算点。数据结构和实现阶段，算法基本思想：首先获取d=yin。扫描线y=d处的相交顺序为xdj1、xdj2、xdjn，此序列由扫描线y=d处多边形p的顶点组成。根据多边形的边一致性，从yin的交集顺序开始，从上到下求出每个扫描线的交集顺序。根据扫描线的一致性，可以检查多边形p内每个扫描线的分段，并将其表示为光栅。数据结构和实施阶段、所有边缘和扫描线交叉、效率低下。因为一条扫描线通常只有少数几条边相交。如

9、何知道多边形的一条边是否与扫描线相交？与当前扫描线相交的边称为“活动边”(active edge)，它以与扫描线相交x坐标增量的顺序存储在“连接列表”(AEL，Active edge table)中。记录沿扫描线的多边形边的相交顺序。只需更新当前扫描线的活动边表，即可获得下一扫描线的活动边表。数据结构和实现阶段，下一扫描线和边的交点的计算方法。线方程式：ax by c=0目前交叉座标：(xi，yi)下一个交叉座标：(Xi 1，Yi1)Xi 1=(-byi 1)-c)/a=(-byi 1)存储的信息：x:扫描线及其角的初始交点dx: x的增量ymax:该角的最大y值，即算法中采用了更灵活的数据结

10、构。由边的分类表Edge Table(ET)和边的活动链接表active edget list(ael)组成。表格结构ET和AEL的基本元素是多边形的边。边的结构由四个域组成，称为ymax边上端的y坐标。x表示ET中边底部端点的x坐标，AEL表示边与扫描线交点的坐标。x侧坡率的倒数；Next指向下一条边的指针。数据结构和实施阶段、数据结构和实施阶段、边缘的分类表ET是指针数组，它按边缘下端点的y坐标对非水平边缘进行分类。子端点的y坐标的值与I的边分类为类I的值相同。设置几条扫描线，几个类。在同一类中，每个边按x值(如果x值相同，则为x值)递增的顺序排序。边表，(Ymax，x，x，next)，活

11、动边表示例，活动边表示例，算法实现步骤。这样，在生成角的分类表ET后，扫描线算法可以继续下一步。(1)扫描线纵坐标y的初始值是ET中非空元素的最小序列号。(2)将边的激活链接列表AEL留空。(3)对坐标值为y的扫描线(当前扫描线)执行以下步骤，直到边的分类表ET和边的激活链接表均为空。算法实现阶段，1)如果边分类表ET的类y元素不为空，则属于该类的所有边都将从ET中删除，插入到边的激活链接表中，并且AEL的每个边将根据x值(如果x值相同，则为x值)按增量方向排序。2)基于当前扫描线的边的活动连接列表AEL不为空时，将AEL的边成对排列，1，2面成对，3，4面成对，依此类推。由每对角和当前扫描线

12、的交点组成的线段位于多边形内，这些线段上的点(像素)依次按多边形属性着色。3)删除边的活动链接列表AEL中满足y=ymax的边。4)将边缘的活动链接列表AEL中剩馀的每个边缘的x域加到x域(即x:=x x)中。5)将当前扫描线的坐标值y加1(即y:=y 1)。扫描线算法，特征：算法更有效。缺点：各种表的裴珉姬和排序开销太大，适合软件实现而不是硬件实现。扫描线算法，问题：如何处理多边形的水平边？如何修改扫描线算法以处理边自交的多边形？1 .扫描多边形的每条边。也就是说，多边形边界经过的像素具有边界标志。2.填满。对于与多边形相交的每个扫描线，从左到右依次访问扫描线中的每个像素。使用布尔变量ins

13、ide指示当前点的状态，如果点位于多边形内，则inside为真。如果点位于多边形之外，则inside为假。Inside的初始值为false，只要当前访问像素是标记的点，inside就会反向排序。inside不会变更未签章的点。，边界标志算法，边界标志算法：算法过程，void edge mark _ fill (polydef，color)多边形为poly def；Int color对多边形多边形多边形的每个边执行直线扫描变换。Inside=FALSEFor(与多边形多边形多边形定义相交的每个扫描线y) for(扫描线的每个像素x) if(像素x是顶部标志)inside=！(inside)；If

14、(inside！=FALSE) drawpixel (x，y，color)；Else drawpixel (x，y，background)；边界标志算法，在软件实现的情况下，扫描线算法的运行速度与边界标志算法几乎相同，但边界标志算法不需要构建和排序裴珉姬管理边表，因此边界标志算法更适合硬件实现，此时运行速度比排序边表算法快1 2倍。边界符号算法，思考：如何使边界的交叉数成偶数？第4章多边形扫描转换和区域填充、4.1多边形扫描转换4.2区域填充、4.2区域填充算法、区域表示以光栅格式表示的填充形状，是像素集合。区域填充是首先指定区域中的一点作为指定颜色，然后将该颜色扩展到整个区域的过程。区域填充

15、算法要求连接区域并填充4.2区域。即，内部点表示，边界表示内部点表示区域内所有像素内部的所有像素表示相同的颜色边界像素，与内部像素不同的颜色边界表示边界内的所有像素表示填充相同颜色内部像素不同的颜色，4.2区域。区域填充要求区域是连接的连接4连接、8连接4连接：8连接、4.2区域填充、4连接和8连接区域之间的区别连接：虽然可以将4连接视为8连接区域，但是边界的要求是在适合内部点表示区域的填充算法中将g设置为内部点表示区域，将(x，y)区域内的一个点，将old_color视为g的印刷色点选择(x，y)以填充种子点的区域g。也就是说，首先将像素(x，y)的颜色设置为new_color，然后将整个区

16、域g放置为相同的颜色。步骤如下：种子像素进入堆栈，如果堆栈不为空，请执行以下步骤3:(1)堆栈顶部像素堆栈；(2)将堆栈像素放入多边形颜色。(3)检查与堆栈像素相邻的四个像素，依次为上、下、左、右，如果其中一个像素不在边框上，并且未放置为多边形颜色，则该像素将导入堆栈中。种子填充算法，种子填充算法，S1，2 3 4，9 7 6 5，11 12 13 14，10，(2 10 8 13)(3 7 13 10 8 13)(4 6 14 7 13 10 13)(5 6 14 7 13 10 8最后一个像素的选择和填充顺序在图中显示为箭头，void flood fill 4 (int x，int y，int oldcolor，int new color) if (getpixel (x，y)=oldFlood fill 4 (x，y 1，oldcolor，new color)；Flood fill 4 (x、y-1、oldcolor、new color)；Flood fill 4