计算机图形学 第四章 光栅转化与消隐(1)课件

1、图形的光栅转化1内容基本概念区域填充多边形的扫描转换多边形的扫描转换与区域填充的比较2内容基本概念区域填充多边形的扫描转换多边形的扫描转换与区域填充的比较3光栅图形的基本概念线框多边形物体填充多边形物体5关于平面多边形图形学中的多边形：无自相交的简单多边形图形学中多边形的两种表示方式顶点表示：用多边形的有序顶点序列表示多边形点阵表示：用位于多边形内部的像素集合来表示多边形光栅图形的基本概念6顶点表示优点直观几何意义明显存贮量小不足难以判断哪些像素位于多边形内部不能直接用于多边形着色?多边形的顶点表示7点阵表示优点便于用帧缓冲器(frame buffer)表示图形面着色所需的图形表示缺点丢失了几

2、何信息占用存储空间多多边形的点阵表示8主要内容基本概念区域填充四连通区域和八连通区域连通区域的种子填充算法多边形的扫描转换多边形的扫描转换与区域填充的比较104.1 区域填充 区域是指已经表示成点阵形式的像素集合。在光栅图形中，区域可采用内点表示和边界表示两种形式进行描述。1、内点表示法：把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。2、边界表示法：把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。1、 区域的表示和类型图3.22 内点表示的区域 图3.23 边界表示的区域12 3） 4连通区域也可理解成8连通区域，即4连通能达到的8连通肯定能达到，4连通只是8连通的一

3、种特殊情况。连通不是指边界而是边界内的区域这里是X围起来的区域号是区域X是边界8连通而非4连通的地方内点表示的八连通区域边界表示的八连通区域14 但是两者的边界不尽相同。如果图中标有号的像素组成的区域作为4连通区域，则其边界由图中的标有号的像素组成。如果将该区域作为8连通的区域，则其边界由图中标有号和号的两种像素组成。 四连通区域与八连通区域的不同边界因为如果区域是8连通的，边界不能将区域有效封堵，X的位置和区域也是连通的。 用于八连通区域的填充算法可用于四连通区域的填充，但用于四连通区域的填充算法并不适用于八连通区域的填充。 15区域的类型四连通区域 八连通区域 16内部表示区域种子填充算法

4、假设内部表示区域为G，其中的像素原有颜色为G0，需要填充的颜色为G1。算法需要提供一个种子点(x,y)，它的颜色为G0。具体算法如下(四连通区域)17内部表示区域种子填充算法Flood_Fill_4(x, y, G0, G1)if(GetPixel(x,y) =G0 ) / GetPixel(x,y) 返回(x,y)的颜色SetPixel(x, y, G1); /将(x,y)的添上颜色G1 Flood_Fill_4(x-1, y, G0, G1);Flood_Fill_4(x, y+1, G0, G1); Flood_Fill_4(x+1, y, G0, G1); Flood_Fill_4(x

5、, y-1, G0, G1);18内容基本概念区域填充多边形的扫描转换逐点判断算法扫描线算法连贯性概念：区域、扫描线、边奇异点的处理算法的数据结构与实现多边形的扫描转换与区域填充的比较201、表示方法：顶点表示和点阵表示1）顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内。2）点阵表示是用位于多边形内的像素的集合来描述多边形，该方法虽然没有多边形的几何信息，但具有面着色所需要的图像表示形式。4.2 多边形的扫描转换 多边形顶点表示P1P0P2P3P4 多边形点阵表示 多边形的扫描转换就是把多边形的顶点表示转换为点阵表示，即从多边形的给

6、定边界出发，求出位于其内部的各个像素，并为帧缓存内的各个对应元素设置相应的灰度或颜色。21逐点判断算法判断一点是否位于多边形内部？23逐点判断算法算法描述for(y=0; y=y_resolution; y+)for(x=0; x=x_resolution; x+)if(inside(polygon, x+0.5, y+0.5)setpixel(framebuffer,x,y,polygon_color)elsesetpixel(framebuffer,x,y,background_color)241、扫描线算法 区域连贯性扫描线连贯性边的连贯性。基本思想 先求出扫描线与多边形边的交点，利用扫

7、描线的连续性求出多边形与扫描线相交的连续区域，然后利用多边形边的连续性，求出下一条扫描线与多边形的交点，对所有扫描线由下到上依次处理。 扫描线算法是按扫描线的顺序计算出扫描线与多边形的相交区间，然后用要求的颜色填充这些区间内的像素。4.2.1 多边形扫描转换的连贯性特点：充分利用了相邻像素之间的连续性，避免对像素的逐点判断和反 复求交运算，减少了计算量，提高了算法速度。26区域连贯性两条扫描线之间的长方形区域被所处理的多边形分割成若干梯形(三角形可以看作退化梯形)梯形的底边为扫描线，梯形的腰为多边形的边或窗口边缘梯形分为两类：多边形内部和多边形外部两类梯形在多边形内部相间排列(相邻的两个梯形必

8、然有一个位于多边形内部，有一个在多边形外部)区域的连贯性是指多边形定义的区域内部相邻的像素具有相同的性质。例如具有相同的颜色推论：如果上述梯形属于多边形内(外)，那么该梯形内所有点的均属于多边形内(外)。效率提高的根源：逐点判断区域判断27扫描线连贯性交点序列：扫描线与多边形的交点个数为偶数(1,2,3,4,5,6)红色区间(1,2)、(3,4)、(5,6)位于多边形内部其余绿色区间位于多边形外部两类区间相间排列区域连贯性在一条扫描线上的反映推论：如果上述交点区间属于多边形内(外)，那么该区间内所有点均属于多边形内(外)。效率提高的根源：逐点判断区间判断28边的连贯性相邻扫描线(y1=y11+

9、1)与多边形的同一条边的交点存在如下关系：当知道扫描线与一条边的一个交点之后，通过上述公式可以通过增量算法迅速求出其他交点 推论：边的连贯性是连接区域连贯性和扫描线连贯性的纽带。扫描线连贯性“”边连贯性“”区域连贯性304.2.2 多边形扫描转换算法 核心思想(从下到上扫描)计算扫描线 y = ymin与多边形的交点，通常这些交点由多边形的顶点组成根据多边形边的连贯性，按从下到上的顺序求得各条扫描线的交点序列根据区域和扫描线的连贯性判断位于多边形内部的区段对位于多边形内的直线段进行着色31多边形扫描转换算法P0P1P2P3P4P5P6P7xy扫描转换示意图32多边形扫描转换算法为了实现上述思想

10、，算法中需要采取灵活的数据结构。分类的边表ET (Sorted Edge Table)：记录多边形信息活化边链表AEL (Active Edge List) ：记录当前扫描线信息它们共同基础是边的数据结构33边的数据结构边的数据结构ymax：边的上端点的y坐标x：边的下端点x坐标，在活化边链表中，表示扫描线与边的交点的x坐标dx：边的斜率的倒数next：指向下一条边的指针 34边的数据结构实例35分类的边表 (ET)分类的边表是按边的下端点的纵坐标y对非水平边进行分类的指针数组下端点的纵坐标y值等于i的边，归入第i类同一类中，各边按x值( x值相等时，按dx的值)递增的顺序排成行水平边不加入分

11、类边表中 36分类的边表实例37活化边链表(AEL)活化链表由与当前扫描线相交的边组成记录了多边形的边沿扫描线的交点序列根据边的连贯性不断刷新交点序列基本单元是边(与扫描线相交的边)与分类边表不同分类边表记录初始状态活化边表随扫描线的移动而动态更新38活化边链表实例ymax xcur dx与分类边表的区别39多边形扫描转换算法(y初始化) 取扫描线纵坐标y的初始值为ET中非空元素的最小序号 (y=2)40多边形扫描转换算法(AEL初始化) 将边的活化链表AEL设置为空 按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行如下步骤，直到分类边表ET和边的活化链表AEL都变成空为止41多边形扫

12、描转换算法如果分类边表ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入边的活化链表AEL中(同时将ET中相应的边表删除)，AEL中的各边按照x值(x值相等时，按dx值)递增方向排序；若对于当前扫描线，边的活化链表非空，则将AEL中的边交点两两依次配对。每一对边与当前扫描线的交点区间位于多边形内部，依次对这些区间上的像素按多边形属性着色；42多边形扫描转换算法将边的活化链表AEL中满足y=ymax的边删除；将边的活化链表AEL中剩下的每一条边的x累加dx，即：x=x+dx;将当前扫描线的纵坐标值y累加，即y=y+1。43多边形扫描转换实例44多边形扫描转换实例45多边形扫描转换实例

13、46多边形扫描转换实例47多边形扫描转换实例48多边形扫描转换实例49多边形扫描转换实例50多边形扫描转换实例51多边形扫描转换实例52多边形扫描转换实例53多边形扫描转换实例54多边形扫描转换优点充分利用多边形的区域、扫描线和边的连贯性，避免了反复求交的大量运算不足算法的数据结构和程序结构复杂对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现55内容基本概念区域填充多边形的扫描转换多边形的扫描转换与区域填充的比较56多边形扫描转换与区域填充比较基本思想不同多边形扫描转换将多边形顶点表示转换为点阵表示，扫描过程利用了多边形的各种连贯性区域填充只改变区域的颜色，不改变区域的表示方法。填充

14、过程利用了区域的连贯性57多边形扫描转换与区域填充比较对边界的要求不同多边形扫描转换只要求每一条扫描线与多边形有偶数个交点区域填充中四连通区域必须是封闭的八连通边界八连通区域必须是封闭的四连通边界58多边形扫描转换与区域填充比较多边形扫描转换允许边界区域填充允许边界对边界的要求不同多边形扫描转换只要求每一条扫描线与多边形有偶数个交点区域填充中四连通区域必须是封闭的八连通边界八连通区域必须是封闭的四连通边界59多边形扫描转换与区域填充比较出发点不同区域填充：知道需要区域内一个种子点(复杂计算)多边形扫描转换：没有要求60总结基本概念区域填充四连通区域和八连通区域连通区域的种子填充算法多边形的扫描

15、转换逐点判断算法扫描线算法区域、扫描线、边的连贯性奇异点的处理数据结构与算法实现多边形的扫描转换与区域填充的比较61具体例子 图2和3是图1中多边形 的新边表NEL和活性边表AEL。在左图中 表示边 ，各顶点为 P0P1P6=(2,5)(2,10)(9,6) (16,9)(16,4)(12,2)(7,2) 其中， 是非极值点，在分类前已对边 作了预处理，即分别在 处把它们截去一个单位长，这样保证扫描线 只和 两边中的一边相交，求得一个交点， 是水平边，不参加分类。 图3.17 边形P0P1P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e662-5/3516/3AELe0

16、e54214AEL在y=3扫描线上的状态AEL-5/3511/3e0e54216AEL在y=4扫描线上的状态AEL-5/35 2e0e49016AEL在y=5扫描线上的状态 010 2e1e210-7/411/2AEL在y=8扫描线上的状态AEL 97/341/3e3 9016e4图3.18 新边表NEL123456e11002xxymaxnexte49016e54212图3.17 多边形P0P1P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e6e2109-7/4e3997/357e0-5/363 如图所示的多边形，若采用改进的有效边表算法进行填充，在填充时采用“下闭上

17、升”的原则（即删除y=ymax的边之后再填充）试画出该多边形的ET表和当扫描线Y=3和Y=8时的AET表。6465作业 已知一多边形如图，其中P1=(2,2),P2=(5,10),P3=(11,3), P4=(11,8),P5=(5,5),P6=(2,7),请写出其新边表的数据结构。6667P0P1P2P3P4P5P6对于图所示的多边形，顶点表示法为：P0（7,8）, P1（3,12）,P2（1,7）,P3（3,1）, P4（6,5）,P5（8,1）,P6（12,9）。试写出每条扫描线的有效边表。作业68 扫描线的最大值为Smax12，最小值为Smin1，共有12条扫描线，每条扫描线之间间隔1个像素单位。每条扫描线的有效边表为如图418所示。6970 这条扫描线处理完毕后 对于P3P4和P4P5两条边，因