发布时间 : 星期二 文章计算机图形学实验报告及代码- 更新完毕开始阅读6856d0c258f5f61fb73666c4
为4、5、6时的AET表。AET表中的记录顺序仍是按x增大排序的。 4．多边形区域填充算法过程
（1）根据给出的顶点坐标数据，按y递增顺序建立ET表 （2）根据AET指针，使之为空。
（3）使y=Ymin （Ymin为顶点坐标中最小y值）。
（4）反复做下述各步，直至y=Ymax（顶点坐标中y的最大值）或ET与AET为空： ①将ET表加入到AET中，并保持AET链中的记录按x值 增大排序。
②对扫描线yi依次成对取出AET中xi值，并在每对xi 之间填上所要求的颜色或图案。 ③从AET表中删去yi=ymax的记录。
④对保留下来的AET中的每个记录，用xi+1/m代替xi ，并重新按x递增排序。 ⑤使yi+1，以便进入下一轮循环。
①开始y＝1，将ET表中y＝1结点加入至AET表，同时保持AET链中记录按x增大排序 ②由于上例中是6－6，是顶点，所以中间不填象素颜色。
③上例由于而Ymax＝3和5，所以不必删去，当yi＝3时，此时 就得将第一个结点即（3，6，－2）删去。
④对保留下来的AET中的每个记录，用xi+1/m代替xi，并重新按x递增排序。如上例变成(实际求出y=2时新的交点x坐标）
⑤使yi+1，以便进入下一轮循环。即y＝2再进入以上循环 继续：①由y＝2，ET表中是空，所以不需ET表加入AET表 ②取x＝4和x＝6.5,将4－6.5之间填上象素颜色。 ③由于y=2,不必删去结点。 ④再改变xi的值为
⑤使yi ＝3，重复继续。继续：①由y＝3，将ET表中y＝3结点加入，即 ②将2－7之间填上象素颜色。 ③删去结点Ymax＝3 结点。
④再改变xi的值为
⑤使yi ＝4，重复继续。 二、 边填充
边填充算法的基本原理是：
（1）对多边形的每条边进行直线扫描转换，即对多边形边界经过的像素打上边标志； （2）对多边形内部进行填充。填充时，对每条扫描线，依从左到右的顺序，逐个访问扫描线上的像素，用一个布尔量来标志当前点是在多边形内部还是外部（一开始设布尔量的值为假，当碰到设有边标志的点时，就把其值取反；对没有边标志的点，则其值保持不变） （3）将其布尔量值为“真”的内部置为图形色，把其布尔量的值为“假”的外部点置为底色即可。
三、 种子填充
1、种子填充基本思路
首先假设在多边形区域的内部，至少有一个像素点（称为种子）是已知的，然后算法开始搜索与种子点相邻且位于区域内的其它像素。如果相邻点不在区域内，那么到达区域的边界；如果相邻点位于区域内，那么这一点就成为新的种子点，然后继续递归地搜索下去。 区域的连通情况可以分为四连通和八连通两种
四连通区域：各像素在水平和垂直四个方向上是连通的八连通区域：各像素在水平、垂直以及四个对角线方向上都是连通的。
在种子填充算法中，如果允许从四个方向搜寻下一个像素点，则该算法称为四向算法；如果允许从八个方法搜寻下一个像素点，则该算法称为八向算法。一个八向算法可以用在四连通区域的填充上，也可用在八连通区域的填充上；而一个四向算法只能用于填充四连通区域。无论是四向算法还是八向算法，它们的填充算法基本思想是相同的。为简单起见，下面只讨论四向种子填充算法。
2．简单种子填充算法
这是对内定义区域进行填充的算法，此算法所采用的基本方法是：将（x,y）点与边界值相比较，检测该点的像素是否处在区域之内；同时与新值相比，以确定该点是否已被访问过。这种测试的前提条件是：在初始状态下，区域内没有一个像素已被设置为新值；同时允许新值等于边界值。
如果用堆栈的方法来实现简单种子填充算法，则算法的基本步骤如下： （1）种子像素压入堆栈。
（2）当堆栈非空时，重复执行以下操作。
①从堆栈中推出一个像素，并将该像素置成所要的值； ②对于每个与当前像素邻接的四连通像素，进行上述两 部份的测试；
③若所测试的像素在区域内且又未被填充过，则将该像 素压入堆栈； （递归）泛填充算法 内点表示的4连通区域
void FloodFill4(int x,int y,int oldColor,int newColor) { if (GetPixel(x,y) == oldColor) { PutPixel(x,y,newColor);
FloodFill4(x+1,y,oldColor,newColor); FloodFill4(x,y+1,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor); }
}/*end of FloodFill4() */ 取(x,y)为种子点 特点：
(1) 有些象素会入栈多次，降低算法效率；栈结构占空间。
(2) 递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。 种子填充法
上述简单种子填充算法操作过程非常简单，却要进行深度的递归，这不仅要花费许多时间，降低了算法的效率，而且还要花费许多空间要构造堆栈结构。因此出现了改进的扫描线种子填充算法。
3．扫描线种子填充算法
扫描线种子填充算法适用于边界定义的四连通区域。区域可凹可凸，还可以包括一个或多个孔。在边界定义区域外或与其邻接的区域中像素的值或颜色不同于填充区域或多边形的值或颜色。
其基本思想是以种子所在扫描线进行从左到右填充直至边界为止 借助于堆栈，算法可分为以下五步实现：
初始化。将算法设置的堆栈置为空。将给定的种子（x,y）压入堆栈。
出栈。如果堆栈为空，算法结束。否则从包含种子像素的堆栈中取出栈顶元素（x,y）作为种子像素。
区间填充。沿当前扫描线对种子像素的左右像素进行填充（像素值为new_color），直至遇到边界像素为止，从而填满包含种子像素的区间。
(4) 定范围。以xl和xr分别表示步骤（３）区间内最左和最右的两个像素。
(5) 进栈。在xl≤x≤xr中，检查与当前扫描线相邻的上下两条扫描线是否全为边界像素(boundary_color)或者前面已经填充过的像素（new_color），是则转到步骤(2),否则在xl≤x≤xr中把每一个区间的最右像素作为种子像素压入堆栈，再转到步骤（2）继续执行。 4.5 二维图形变换 一、图形变换基本概念 1、定义
即对原图形进行平移、旋转、缩小或放大等变换操作。
在计算机图形显示或绘图输入过程中，往往需要对图形指定部分的形状、尺寸大小及显示方向进行修改，以达到改变整幅图形的目的，这就需要对图形进行平移、旋转、缩小或放大等变换操作。因此，图形变换是计算机绘图基本技术之一，利用它可以用一些很简单的图组合成相当复杂的图，可以把用户坐标系下的图形变换到设备坐标系下。利用图形变换还可以实现二维图形和三维图形之间转换，甚至还可以把静态图形变为动态图形，从而实现景物画面的动态显示，下面主要讨论二维图形变换。 2、图形变换分类
图形变换有两种形式：
视象变换:图形不动，而坐标系变动，即变换前与变换后的图形是针对不同的坐标而言的，也称之为坐标模式
几何变换:另一种是坐标系不动，而图形改变，即变换前与变换后的坐标值是针对同一坐标系而言的，也称之为图形模式变换，
实际应用中后种图形变换更具有实际意义，我们讨论的图形变换主要是属于后一种变换
二、二维图形几何变换的基本原理 1．几何变换
在计算机绘图应用中，经常要实现从一个几何图形到另一个几何图形的变换。例如，将图沿某一方向平移一段距离；将图形旋转一定的角度；或将图形放大；反之把图形缩小等等。这些图形变换的效果虽然各不相同，本质上却都是依照一定的规则，将一个几何图形的点都变为另一个几何图形的确定的点，这种变换过程称为几何变换。
几何变换的规则是可以用函数来表示的。由于一个二维图形可以分解成点、直线、曲线。把曲线离散化，它可以用一串短直线段来逼近；而直线段可以是一系列点的集合，因此点是构成图形的基本几何元素之一。我们先来讨论点的几何变换的函数表示。 二维平面图形的几何变换是指在不改变图形连线次序的情况下，对一个平面点集进行的线性变换。
二维平面图形的轮廓线，不论是由直线段组成（多边形），还是由曲线段组成，都可以用它的轮廓线上顺序排列的平面点集来描述，例如长方形ABCD，是由四个角点A（x1，y1），B（x2，y2），C（x3，y3），D（x4，y4）顺序连接而成，为了使画出的图形是闭合的，首尾两点必须连接。二维平面图形变换的结果有两种，一是使图形产生位置的改变；另一种是使图形产生变形，例如把图形放大。
对二维图形进行几何变形有五种基本变换形式，它们是：平移、旋转、比例、对称和错切。
2．基本几何变换的解析表示 （l）平移变换
平面上一点P（x，y），如果在X轴方向的平移增量为tx，在Y轴方向平移增量为ty时，则平移后所得新点P‘
(x'，y')坐标表达式为： x' = x + tx， y' = y + ty 我们把这一变换称为平移变换。
如果对一图形的每个点都进行上述变换，即可得到该图形的平移变换。实际上，直线的平移变换，可以通过对其定义端点的平移变换来实现，对于其它类型的变换这种处理方法也是可行的。
平移变换只改变图形的位置，不改变图形的大小和形状 （2）比例变换
一个图形中的坐标点（x，y），若在X轴方向有一个比例系数Sx，在Y轴方向有一个比例系数Sy，则该图形的新坐标点（x'，y'）的表达式为 x' = xSx y' = ySy； 这一变换称为比例变换。
比例变换不仅改变图形的位置，而且改变图形的大小 （3）旋转变换
若图形中的坐标点（x，y）绕坐标原点逆时针旋转一个角度θ ，则该点变换后的新坐标
（x‘，y’）与交换前的坐标(x，y)的关系为： x' = xcosθ - ysinθ y' = xsinθ + ycosθ
旋转变换只能改变图形的方位，而图形的大小和形状不变， （4）对称变换
如果经过变换后所得到的图形与变换前的图形关于X坐标轴是对称的，则称此变换为关于X轴的对称变换。经过这一变换后的坐标点（x'，y'）与变换前的对应坐标点（x，y）的关系为：
x' = x， y' = -y
与此类似，若变换前后的图形关于Y轴对称，则称为关于Y轴的对称变换。这一变换前后点的坐标间的关系： x' = -x，y' = y
当图形对X轴和Y轴都进行对称变换时，即得相对于原点的中心对称变换。这一变换前后点的坐标之间的关系为：
x' = -x，y' = -y
对称变换只改变图形方位，不改变其形状和大小。 （5）错切变换
如果变换前坐标点（x，y）与变换后对应的新坐标点（x'，y'）的关系为： x' = x + cy，y' = y
我们称这一变换为沿X轴的错切变换，式中c为错切系数 与此类似，若变换前后对应点的坐标关系为： x' = x， y' = y + bx
则称此变换为沿Y轴的错切变换，其中b为错切系数。
错切变换不仅改变图形的形状，而且改变图形的方位，但图形中的平行关系不变， 一般把上述变换统称为基本的图形变换，绝大部分复杂的图形变换都可以通过这些基本交换的适当组合来实现。
3．二维图形几何变换的基本原理 我们知道，在计算机图形中，一个无论多么复杂的平面图形最终都可看成为由一系列直线段组成的，而每一条直线段均由两点所决定，那么，对平面图形进行几何变换，究竟是对图形的每一点变换，还是仅对组成这幅图形的直线段进行几何变换或者只需对直线段的端点进行几何变换呢？
4.6 二维图像裁剪 一、概述 1、定义
为了描述图形对象，我们必须存储它的全部信息，但有时为了达到分区描述或重点描述某一部分的目的，往往将要描述的部分置于一个窗口之内，而将窗口之外的部分“剪掉”，这个处理过程叫做裁剪。
裁剪实质上是从数据集合中抽取信息的过程，这个过程是通过一定计算方法实现的。裁剪就是将指定窗口作为图形边界，从一幅大的画面中抽取所需的具体信息，以显示某一局部画面或视图。
在实际应用中，经常会遇到一些大而复杂的图形，如集成电路布线图、建筑结构图、地形地貌图等。由于显示屏幕的尺寸及其分辨率限制，这样复杂的图形往往不能全部显示出来，即使将它们采用比例变换后全部显示在同一屏幕上，也只能表现一个大致轮廓，并且图形拥挤不清。因此对复杂图形，一般只能显示它的局部内容，我们在研究某复杂图形时，往往对某特定画面感兴趣，在这种情况下，我们将这一特定区域放大后显示出来，而把周围画面部分全部擦除，这样可清晰地观察其细节部分。
我们假定裁剪是针对用户坐标中窗口边界进行的，裁剪完成后，再把窗口内图形映射到视区。所以裁剪的目的是显示可见点和可见部分，删除视区外的部分。例如，下图（a）定义了一个矩形窗口A’B’C’D’，窗口内会有E'F'G'的一部分，而直线段E'G'、F'G'都有一部分在窗口外。然后将落在窗口内这部分图形传送到视图区内显示，如图（b）所示。此时，窗口外那部分被裁剪掉。