《计算机图形学基础》课件第4章

第4章多边形的扫描转换与区域填充4.1多边形的扫描转换

4.2区域填充技术

4.3反走样

习题4

4.1多边形的扫描转换

4.1.1多边形的扫描转换的定义

多边形的扫描转换算法对多边形的形状没有限制，但多边形的边界必须是封闭的，且不自交。由于大多数图形都是采用顶点序列表示的，而顶点表示又不能直接进行显示，因此，就必须将图形从顶点表示转换为点阵表示。多边形的扫描转换就是从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓存器内的各个对应元素设置相应的灰度和颜色。如图4-1所示是多边形的顶点表示。图4-1多边形的顶点表示多边形的扫描转换过程实际上是给多边形包围的区域着色的过程，是一种面着色的方法。运用面着色方法可以使画面明暗自然，色彩丰富，形象逼真。面着色图形体现了光栅显示系统的优势。将图4-1转换为点阵图形，如图4-2所示。图4-2多边形的点阵表示4.1.2逐点判断算法(x扫描线算法)

对多边形所围成的区域进行填充，就是要找出所有位于多边形内部的像素，并赋以适当的像素值，产生面填充的图形。多边形区域具有内部相邻的像素空间连贯的特点，当

一条扫描线穿过多边形时，必然与多边形的边相交并有交点，依据交点可以确定哪些像素在区域内。一般来讲，这些像素在水平方向是相邻、连续的，我们只要知道扫描线与多边形的两个交点，就能确定填充区间，知道哪些像素是要填充的。注意到在一般情况下，一条直线与任意封闭曲线相交时，总是从第一个交点进入内部，再从第二个交点退出，以后交替地进入、退出，即奇数次交点进入多边形、偶数次交点退出多边形，如图4-3所示。这就是多边形扫描转换算法的基本思想，当然还有一些特殊情况应特殊处理。图4-3扫描线与多边形的交点逐点判断算法的基本思想就是采用累计交点的方法进行多边形内部像素点的判断，若从一点出发的射线与多边形边界的交点个数为奇数，则该点位于多边形内，否则该点在多边形外。

由于用于画线图元扫描转换的四舍五入原则会导致部分像素位于多边形之外，因而不可用。为了使生成的像素全部位于多边形之内，当交点坐标不是整数时，需要制定交点的取整规则。假定非水平边与扫描线y=e相交，交点的横坐标为x，规则如下：

规则1：x为小数，即交点落于扫描线上两个相邻像素之间(如图4-4所示)，若交点位于左边，则向右取整；若交点位于右边，则向左取整。图4-4交点位于左、右边之上规则2：边界上像素的取舍问题，避免填充扩大化。对于边界像素，规定落在右上边界的像素不予填充。具体实现时，只要对扫描线与多边形的相交区间左闭右开(如图4-5所示)即可。图4-5边界交点左闭右开逐点判断算法的步骤如下：

(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值(ymin和ymax)。

(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。

(3)对一条扫描线填充的过程可分为四个步骤：

①求交：计算扫描线与多边形各边的交点；

②排序：把所有交点按递增顺序排列；

③交点配对：将奇数与偶数交点进行配对，每对交点就代表扫描线与多边形的一个相交区间；

④区间填色：把这些相交区间内的像素置成不同于背景色的填充色。例如在图4-3中，对扫描线y＝3，交点经排序后表示为(2，4，7，9)，因此，对区间(2，4)和(7，9)进行填充。

采用逐点判断算法还要解决的一个问题是扫描线与多边形顶点相交的特殊情况，这时如果排序后交点表中的交点个数是奇数，填充就会出错。例如，图4-3中的扫描线y＝1，y＝7等就是这种情况。以y＝1为例，它与多边形所有各边的交点排序后所得是(3，8)，其中两个x坐标为3，表明扫描线同时与多边形的两条边在顶点相交。如果还是按区间填充，则需要填充的区域是(3，8)，这时就会发生填充错误。上述问题称为奇点问题，其解决办法是：当顶点表现为局部极大或局部极小时，就看做是零个或两个交点，否则看做一个。如果这个顶点的两条边同在扫描线的下面，这个顶点是局部极大，反之称这个顶点是局部极小。例如，在图4-3中，与扫描线y＝1相交的两个奇点都是极小点，交点个数算做零个。而与扫描线y＝7相交的奇点是非极值点，其交点个数算做一个。设inside(P，x，y)是验证点(x，y)是否在多边形P内的布尔函数。当从(x，y)到(+∞，y)的射线与P的交点个数是奇数时，该函数取值为true，否则取值为false。设framebuffer是用以存放图形的帧缓存器，framebuffer(x，y)对应帧缓存器中的元素，用以存放屏幕上对应像素的颜色值。设polygon-color是多边形P的颜色值，background-color是背景色。逐点判断算法可以采用下列程序表示：由上述程序可以看出，逐点判断算法的特点是程序非常简单，易于实现。但由于运行速度很慢，该算法并没有实用价值。逐点判断算法效率极低的原因在于，该算法需要孤立地考察各个像素与多边形的内外关系，使得大量像素都要一一判断，每次判断又要多次求交点，需要做大量的乘除运算，花费很多时间。4.1.3扫描线算法

扫描线算法是多边形扫描转换的常用方法。扫描线算法的处理对象是非自交多边形(边与边之间除了顶点外无其他交点)。图4-6中(a)为非自交多边形，(b)为自交多边形。扫描线算法是多边形扫描转换的常用算法，与逐点判断算法相比，扫描线算法充分利用了相邻像素之间的连贯性，避免了对像素的逐点判断和反复求交的运算，达到了减少计算量和提高速度的目的。

开发和利用相邻像素之间的连贯性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。图4-6非自交及自交多边形

1.区域的连贯性

设多边形P的顶点Pi=(xi，yi)，i=0，1，…，n，又设yi0，yi1，…，yin是各顶点Pi的坐标yi的递减数列，即yik≥yik+1，0≤k≤n－1。这样，屏幕上位于y=yik和y=yik+1两条扫描线之间的长方形区域被多边形P的边分割成若干梯形(三角形可看做其中一底边长为零的梯形)，如图4-7所示。图4-7区域的连贯性从图4-7中可以看出，区域的连贯性具有如下性质：

(1)梯形的两底边分别在y=yik和y=yik+1两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。

(2)这些梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。

(3)两类梯形在长方形区域{yik，yik+1}内相间地排列，即相邻的两梯形必有一个在多边形P内，另一个在P外。

根据这些性质，实际上只需知道该长方形区域任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。

2.扫描线的连贯性

设e为一整数，yi0≥e≥yin。若扫描线y=e与多边形P的Pi－1Pi相交，则记其交点的横坐标为xei。现设xei1，xei2，xei3，…，xeil是该扫描线与P的边界各交点横坐标的递增序列，称此序列为交点序列，如图4-8所示。

由区域的连贯性可知，此交点序列具有以下性质：

(1)设L是偶数。

(2)在该扫描线上，只有区段(xeik，xeik+1)，k=1，3，5，…，L－1，位于多边形P内，其余区段都在P外。

以上性质称为扫描线的连贯性，它是多边形区域连贯性在一条扫描线上的反映。图4-8扫描线的连贯性

3.边的连贯性

设d为一整数，并且d=e－1，yi0≥d≥yin。设位于扫描线y=d上的交点序列为xdj1，xdj2，xdj3，…，xdjk。对于扫描线d、e的交点序列，若多边形P的边Pr－1Pr与扫描线y=e，y=d都相交，则交点序列中的对应元素xer，xdr满足下列关系：

其中，mr为边Pr－1Pr的斜率。

从图4-9中可以看出，可利用d的交点序列计算e的交点序列，则由区域的连贯性可知，d的交点序列和e的交点序列之间有以下关系：

(1)两序列元素的个数相等。

(2)点(xeir，e)与点(xdjr，d)位于多边形P的同一边上，于是

这样，运用上述递推关系式可直接由d的交点序列得到e的交点序列。以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。图4-9边的连贯性

4.数据结构与实现步骤

算法基本思想：取d=yin，容易求得扫描线y=d上的交点序列为xdj1，xdj2，…，xdjn，这一序列由位于扫描线y=d上的0多边形P的顶点组成；由yin的交点序列开始，根据多边形的

边的连贯性，按从上到下的顺序求得各条扫描线的交点序列；根据扫描线的连贯性，可确定各条扫描线上位于多边形P内的区段，并表示成点阵形式。如果算法对每条扫描线与所有的边求交点，则效率很低，因为一条扫描线往往只和少数几条边相交。因此，如果只对与该扫描线相交的边求交点，算法的效率将有很大的提高。如何判断多边形的一条边与扫描线是否相交成为算法的关键。扫描线算法采用如下方法解决上述问题：与当前扫描线相交的边称为活性边(activeedge)，把它们按与扫描线交点x坐标递增的顺序存入一个表中，称为边的活化边表(ActiveEdgeTable，AET)，它记录了多边形边沿扫描线的交点序列。

经过上述处理，扫描线算法只需对当前扫描线的活化边表作更新，即可得到下一条扫描线的活化边表(可采用边的连贯性计算下一条扫描线与边的交点)。设直线方程为ax+by+c=0，当前交点坐标为(xi，yi)，下一交点坐标为(xi+1，yi+1)，则xi+1=xi+1/mr。

活化边表中需要存放的信息如下：

x：当前扫描线与边的交点；

dx＝－b/a：从当前扫描线到下一条扫描线之间的x增量；

ymax：边所交的最高扫描线。

为了方便活化边表的更新，先建立另一个表，称为边表(EdgeTable,ET)，也叫边的分类表，边表存放多边形各边的初始状态。因此，扫描线算法中采用了较灵活的数据结构。它由边的分类表(ET)和活化边表(AET)两部分组成。表结构ET和AET中的基本元素为多边形的边。边的结构由以下四个域组成：

ymax：边的上端点的y坐标；

x：在ET中表示边的下端点的x坐标，在AET中为边与扫描线的交点的坐标；

Δx：斜率的倒数；

Next：指向下一条边的指针。

边的分类表(ET)是按边的下端点的y坐标对非水平边进行分类的指针数组。下端点的y坐标的值等于i的边归入第i类。有多少条扫描线，就设多少类。同一类中，各边按x值(x值相等时，按Δx的值)递增的顺序排列成行。图4-10为ET表的结构，该表为静态表，表示多边形的结构。而AET表是动态表，其节点数据随着多边形扫描线的变动而变动，如图4-11所示。图4-10

ET表的结构图4-11

AET表的结构这样当建立了边的分类表(ET)后，扫描线算法可按下列步骤进行：

(1)取扫描线纵坐标y的初始值为ET中非空元素的最小序号。

(2)将边的活化边表(AET)设置为空。

(3)按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行下列步骤，直到边的分类表和活化边表都变成空为止。

AET表的动态更新步骤如下：

(1)如ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入边的AET中，AET中的各边按照x值(当x值相等时，按Δx值)递增方向排序。

(2)若相对于当前扫描线，边的AET非空，则将AET中的边两两依次配对，即1、2边为一对，3、4边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点(像素)按多边形属性着色。

(3)将边的AET中满足y=ymax的边删去。

(4)将边的AET中剩下的每一条边的x域累加Δx，即x′=x+Δx。

(5)将当前的扫描线的纵坐标值y累加1，即y′=y+1。扫描转换算法利用了扫描线的相关性和边的相关性，极大地提高了效率。扫描线相关性指在一条扫描线上，相邻的像素只有通过边界线时才能从内部变到外部或者从外部变到内部。边的相关性指对多边形的每一条边，相邻的扫描线只有在通过线段的端点时才会改变与边的相交情形。同时，这是一种非常有效的算法，它使所显示的每—个像素只访问一次，输入、输出的要求可降为最少。由于该算法与输入、输出的细节无关，因而它也与设备无关。扫描线算法的主要缺点在于：对各种表的维持和排序的开销太大，适合软件实现而不适合硬件实现。

扫描转换算法描述如下：4.1.4边界标志算法

扫描转换算法存在的问题是：如何处理多边形的水平边，以及如何修改扫描线算法，使它能处理边自交的多边形。边界标志算法解决了上述问题，其基本思想是：首先，对多边形的每一条边进行扫描转换，即对多边形边界所经过的像素作一个边界标志；然后，对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的像素。

取一个布尔变量inside来指示当前点的状态。若点在多边形内，则inside为真；若点在多边形外，则inside为假。Inside的初始值为假，每当当前访问像素为被打上标志的点时，就把inside取反。对未打标志的点，inside不变。如图4-12所示为边界标志算法的示意图。图4-12边界标志算法边界标志算法描述如下：如果使用软件实现，则扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立和维护边表以及对它进行排序，因此边界标志算法更适合硬件实现，这时它的执行速度比扫描线算法快一至两个数量级。

4.2区域填充技术

区域指已经表示成点阵形式的填充图形，它是像素的集合。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。一个封闭区域确定以后，填充要解决的问题是如何确定填充的像素以及如何高效地填充。

4.2.1区域的表示

区域有两种表示方法：内点表示和边界表示。内点表示是枚举出区域内部的所有像素，使这些像素着同一个颜色。边界表示是枚举出边界上所有的像素，使这些像素着同一颜色。内部像素着与边界像素不同的颜色。区域填充要求区域是连通的。区域的连通方式分为两种：4连通区域和8连通区域。首先定义4邻接点和8邻接点。4邻接点是指一个点的上、下、左、右四个相邻的点，而8邻接点是指其上、下、左、右、左上、右上、左下、右下8个相邻的点，如图4-13所示。

从图4-13可以看出，4连通区域是指从区域的一点出发，通过访问已知点的4邻接点，在不越出区域的前提下，遍历区域内的所有像素。8连通区域则是指从区域的一点出发，通过访问已知点的8邻接点，遍历区域内的所有像素。4连通区域与8连通区域的区别在于，对边界的要求有所不同，如图4-14所示。图4-13邻接点的定义图4-14

4连通区域与8连通区域的边界从图4-14中可以看出，8连通区域比4连通区域对边界的要求更高。通过上述分析，可以将区域的表示方式与区域的连通性相结合，共得到4种区域的表示方式，分别是以边界表示的4连通区域、以内点表示的4连通区域、以边界表示的8连通区域、以内点表示的8连通区域，如图4-15所示。图4-15区域的表示方式4.2.2递归算法

递归算法的思想是，在一个封闭区域内部有一已知像素，由此出发通过某种方法找到区域内的所有像素。递归的基本方法是设种子像素为(x，y)，种子点是4连通区域内的一点，old_color为区域内的原有像素的颜色，new_color是要填充的颜色。递归填充的过程是：如果种子像素是区域内原有颜色old_color，说明该种子像素在区域内，则将像素置为被填充颜色new_color，同时将种子像素的上、下、左、右像素当做种子，递归调用填充算法；否则说明该像素已被填充，不再处理。种子递归填充算法如下：递归算法的原理和程序都很简单，但由于要进行多次递归，因此费时、费内存，计算机的效率将非常低。4.2.3栈结构的种子填充算法

设G为一内点表示的区域，(x，y)为区域内一点，old_color为G的原色。现取(x，y)为种子点对区域G进行填充，即先置像素(x，y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下：

种子像素入栈，当栈非空时，执行如下三步操作：

(1)栈顶像素出栈；

(2)将出栈像素置成多边形当前颜色；

(3)按上、下、左、右的顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形当前颜色，则把该像素入栈。

例4-1有多边形P0(1，5)P1(5，5)P2(7，3)P3(7，1)P4(1，1)。设种子点为(3，3)，搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图4-16中箭头所示。

像素的出栈与入栈顺序表如下所示：

(210812)

(371310812)

(461471310812)

(561471310812)

从上述的出栈及入栈顺序可以看出，基于栈结构的填充算法会出现有些像素反复入栈的情况，因此，出栈时需要先判断后决定是否填充。这一方面降低了算法的效率，另一方面还要求很大的存储空间以实现栈结构。图4-16区域的填充过程4.2.4扫描线填充算法

扫描线填充算法的目标是减少递归层次以及像素的入栈次数，该算法适用于边界表示的4连通区域。扫描线填充算法的思想是在任意不间断区间中只取一个种子像素(不间断区间指在一条扫描线上的一组相邻元素)，填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的各区段都填充完毕。算法步骤如下。

种子像素入栈。当栈非空时作如下四步操作：

(1)栈顶像素出栈；

(2)沿扫描线对出栈像素的左右像素进行填充，直至遇到边界像素为止，即每出栈一个像素，就对包含该像素的整个区间进行填充；

(3)将上述区间内最左、最右的像素分别记为xl和xr；

(4)在区间检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充的像素，若存在非边界、未填充的像素，则把每一区间的最右或最左像素取作种子像素入栈，继续执行步骤(1)。

扫描线填充算法的填充过程如图4-17所示。图4-17扫描线填充过程图4-17演示了4连通区域中扫描线填充的过程，白色像素为种子。图(a)是填充过程的开始，表示了种子位置和第一条扫描线上的填充区域，相邻扫描线上准备入栈的像素及位置；图(b)是第一条扫描线之上的第二条扫描线填充的像素区段及入栈像素；图(c)是在第一条扫描线之上的第三条扫描线的填充像素区段及入栈像素；图(d)定义区域右上角部分的完整像素区段及剩余的待处理栈内种子像素。图中的数字表示了入栈像素的位置和入栈顺序。

上述算法对于每一个待填充区段，只需压栈一次，因此，扫描线填充算法提高了区域填充的效率。4.2.5区域填充图案

进行区域填充时，有时需要用一种图案来填充平面区域。用图案来填充平面区域的基本思想是：首先用模板定义各种图案；然后修改填充的扫描转换算法，即在确定了区域内的一个像素之后，不是马上往该像素填色，而是先查询模板位图的对应位置，若对应位置有图案，即图案的对应位置为1时，则对像素填充颜色，否则，不改变该像素的值。填充图案有两种方式，一种是以不透明方式填充图案，另一种是以透明方式填充图案。不透明图案填充的算法是根据模板位图对应位置为0或1来决定是用前景色还是背景色去写像素的。若以透明方式填充，则当模板位图的对应位置为1时，用前景色写像素，否则，不改变像素的颜色。图案填充算法首先要进行图案的定义，可以使用一个M×N的二维数组来记录，color［i］［j］表示局部坐标系(i，j)处的像素值；其次是图案与区域的定位问题，有两种定位方式：相对定位和绝对定位；最后是像素着色模式的定义，同样有两种方式：透明(Transparent)方式和不透明(Opaque)方式。

绝对定位方式是指将图案在区域所在的绘图空间坐标系中定位。此时若区域的位置不同，则区域中填充的图案也不同。此时的视觉效果是：若区域移动，则区域中的填充图案发生变化。定位公式为，value［x］［y］=color［x%M］［y%N］。绝对定位方式如图4-18所示。图4-18绝对定位方式相对定位方式是指将图案在区域的局部坐标系中定义。记局部坐标系原点为(x0，y0)，则value［x］［y］=color［(x－x0)%M］［(y－y0)%N］。相对定位方式如图4-19所示。图4-19相对定位方式图案填充算法在扫描转换算法中对像素着色操作需增加额外控制。在着色模式下，将图案中标记为1的位置对应的像素写为前景色。在透明模式下，对图案中标记为0的位置对应的像素不进行写操作；在不透明模式下，将图案中标记为0的位置对应的像素写为背景色。像素着色模式的本质是规定前景色与背景色的组合规则，如前景色优先、背景色优先、前景色与背景色的加权组合或各种规则的组合。

例4-2以不透明模式实现图案填充(如图4-20所示)。

填充过程：图(d)为待填充区域的像素位图，图(e)擦除图(a)中图(d)区域，并将待填充区域像素写为背景色，图(f)

对待填充区域进行图案填充，图(g)以透明模式把图(f)绘制在屏幕上。图4-20图案填充过程4.2.6多边形的扫描转换与区域填充方法比较

多边形的扫描转换和区域填充均为平面着色问题，它们的联系非常紧密。如采用画线算法将多边形表示成8连通区域，并取区域内一点作为种子点，则多边形的扫描转换问题可转化成区域填充问题；反之，当已知多边形区域的顶点表示，则区域填充问题也可转化为多边形的扫描转换问题。但是这两类算法的区别还是很明显的，主要体现在以下几个方面：

(1)基本思想不同。扫描转换是将顶点表示转换成点阵表示，主要利用多边形各种形式的连贯性。区域填充只改变区域内的填充颜色，没有改变区域的表示方法，在填充过程中利用了区域的连通性。

(2)对边界的要求不同。扫描转换只要求扫描线与多边形边界交点个数为偶数。区域填充的区域边界是封闭的，这样可以防止递归填充时跨越边界。

(3)基本的条件不同。扫描转换是从边界顶点信息出发的。区域填充是以区域内的一点作为种子点，然后从这点开始对区域进行着色的。 4.3反走样

对多边形进行扫描转换后，多边形的边界一般呈现锯齿形状，这是由于在光栅图形显示器上显示的图形都是由一系列相同亮度的离散像素构成的，因此，会形成或多或少的台阶或锯齿状。这种用离散量表示连续量引起的失真，就叫做走样。反走样技术就是减少或消除这种不良效果的技术。走样现象还有其他的表现形式，如纹理图形走样、图形细节失真。当图形中包含相对微小的物体时，这些物体在静态图形中显示时容易被丢弃或忽略，而在动画显示时会时隐时现，产生闪烁。常用的反走样方法分为两类：一类是提高分辨率，增加采样点；另一类是把像素作为一个有限区域，对区域进行采样。4.3.1提高分辨率

提高显示器分辨率可改进图形的显示效果。如图4-21(a)所示，在理想直线经过的每一列像素中，选择离直线最近的一个，置为直线颜色(黑色)，每当前一列所选的像素不同行时，在线上就出现一个台阶。现在假设我们把显示器分辨率提高一倍，如图4-21(b)所示，直线经过两倍的像素，台阶也增加一倍。但是由于每个台阶在水平方向与垂直方向的台阶大小只有原先的一半，因此效果会好很多。这种改进需要付出较高的代价，扫描转换算法的执行时间也成倍增加，因此增加分辨率是不经济的方法，同时它也只能减轻而不能消除锯齿问题。图4-21提高分辨率前后的锯齿现象比较提高分辨率显然可以通过硬件实现，但是，当无法采用硬件进一步提高分辨率时，可采用软件的方法提高分辨率，即采用某种平均算法，把结果转化到较低分辨率的显示器上进行显示。

用软件方式提高分辨率是对单个像素进行进一步的细分。假设初始分辨率是m×n，单个像素被细分成s×t个子像素，显示图形按照s×t×m×n的分辨率进行扫描转换，记录每个子像素的颜色。原分辨率下像素所对应的颜色由其细分后的子像素颜色值的某种平均来定义，得到像素的颜色值显示。实践证明，这种方法对于改进图形质量有较好的效果。采用