计算机图形学第七章.ppt

第七章,光栅图形的扫描转换与区域填色,多边形的两种表示方法,多边形的表示方法,顶点表示用多边形的顶点来表示,点阵表示用多边形内的象素来表示,两种表示方法的优缺点,顶点表示：,直观，几何意义强，占内存少，用得普遍，但不能直接用于面着色。,点阵表示：,便于用帧缓冲器表示图形，便于面着色。,什么是多边形的扫描转换,顶点表示,点阵表示,多边形的扫描转换,逐点判断算法,算法思想：逐个像素判别，检测其是否在多边形内部，从而给出位于多边形内部的像素集合。,逐点判断算法的具体实现,假设P=P0P1P2PnP0为一个给定多边形，P0,P1,P2Pn为其顶点表示。假设inside(P,x,y)是验证点(x,y)是否在多边形P内的布尔函数。,Inside函数的实现原理,计算从(x,y)到(+,y)的射线与多边形的交点个数。若交点个数是奇数的话，就表明该点在多边形内部，否则该点在多边形外部。,逐点判断算法的具体实现,假设framebuffer(x,y)是与(x,y)对应的帧缓冲器中的元素，用以存放对应像素的颜色值。设polygon_color为多边形内的颜色值，background_color为背景颜色。,逐点判断算法的伪代码程序,fory:=screen_ymintoscreen_ymaxdoforx:=screen_xmintoscreen_xmaxdoifinside(P,x+0.5,y+0.5)thensetpixel(framebuffer,x,y,polygon_color)elsesetpixel(framebuffer,x,y,background_color),逐点判断算法的优缺点,优点：简单，易于理解。缺点：忽略了像素与像素之间的联系，如果整个平面有几千万个像素，也要一一进行判别，要做大量的计算工作，效率太低。,扫描线算法,扫描线算法利用了相邻像素之间的连贯性，避免了反复求交的运算。扫描线算法综合利用了区域的连贯性，扫描线的连贯性和边的连贯性。,区域的连贯性,假设多边形P的顶点Pi(xi,yi),i=0,1,2n各个顶点Pi的纵坐标按yi递减排序：yi0,yi1,yi2yin其中yi,k=yi,k+1,区域的分割,现在作两条扫描线y=yi,k和y=yi,k+1，这两条扫描线之间的区域被多边形分割成若干个梯形。梯形上下两底分别为两条扫描线，腰在多边形P的边上或在显示屏幕的边界上。,分割后区域的分类,这些梯形分为两类：在多边形P内部和在多边形P外部。两类梯形交替地排列在长方形区域内。如果知道了某点q所在区域在多边形内(或外)，就能知道整个长方形区域内的梯形排列情况。此性质称为区域的连贯性。,扫描线的连贯性,假设e为一整数满足若扫描线y=e与多边形P的边Pi-1Pi相交，则记其交点的横坐标xei。现在假设xei1,xei2,xeil为扫描线与P的边界各交点的横坐标的递增序列，称为交点序列。,交点序列的性质,l是偶数。在该扫描线上只有区段(xeik,xei,k+1)，(k=1,3,5l-1)位于多边形P内，其余均在多边形P外，两种区段沿扫描线相间排列。此性质称为扫描线的连贯性。,交点序列,若d=e-1，则位于扫描线y=d上的交点序列为xdj1,xdj2,xdjk。若多边形P的边Pr-1Pr与扫描线y=e和y=d都相交，则xer和xdr满足：,怎样得到y=e上的交点序列,通过递推式可以算出与y=e和y=d都相交的点若再求出与扫描线y=d不相交但与下一扫描线y=e相交的所有边PqPq+1上的交点xeq然后把这些点按底层的顺序排列，就能得到了y=e上的交点序列,边的连贯性,当取某一整数k，0=k0不是极值点的顶点称为非极值点。,P所有的顶点,极值点,非极值点,对于奇点的两种情况的处理,交点个数加一,交点个数不变,扫描线算法的数据结构,数据结构,边的分类表ET,边的活化链表AEL,Ymax:边的上端点的y坐标,x:在ET中表示边的下端点的x坐标，在AEL中则表示边与扫描线交点的x坐标,x:边的斜率的倒数,next:指向下一条边的指针,边的分类表ET,边的分类表ET是按边下端点的纵坐标y对非水平边进行分类的链表数组。,2,10,2,16,1,2,3,4,5,6,e7,e5,e7,e5,e4,e4,e1,e1,e2,e2,e3,e3,边的活化表AEL,边的活化表AEL由与当前扫描线相交的所有多边形的边组成，它记录了多边形边沿扫描线的交点序列，并根据递推式：,AEL,e1,e2,e3,e4,AEL在y=8的扫描线上的状态,不断刷新交点序列。,扫描线算法的描述,步骤1：(y初始化)建立ET表，并且取扫描线纵坐标y的初始值为ET中非空元素的最小序列。步骤2：(AEL初始化)将边的活化链表AEL设置为空。步骤3：按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行子算法，直到ET和AEL都变为空为止。,子算法步骤,1)如果边分类表ET中第y类元素为非空，则将属于该类的所有边从ET中取出并插入边的活化链表AEL中，AEL中各边按x的值(当x的值相等时，按x值)递增方式排序。,子算法步骤,2)若相对于当前扫描线，边的活化链表AEL非空，则将AEL中边两两依次配对(位置位于1,2的配对；位置位于3,4的配对)，依次配对的边的内部点(像素)按多边形的颜色属性进行着色。,子算法步骤,3)将边的活化链表AEL中ymaxy的边删去4)将边的活化链表AEL剩下的每一条边的x域累加x，即x:=x+x5)将当前扫描线的纵坐标值y累加1，即y:=y+1,扫描线算法的优缺点,优点：效率高。缺点：程序复杂，需要排序。,边缘填充算法,由于扫描线算法需要对多边形的边进行排序，如果采用求余的方法，就不用对边进行排序了。,什么是求余？,数学上：A为一个给定的正数，数M的余是指A-M的差。记为,易得光栅图形上：若某区域已着上值为M的某种颜色，对M作偶数次求余运算后，此区域颜色不变，作奇数次求余运算后，区域颜色变为。,求余运算的函数表示,Complement(framebuffer,x,y)为实施求余运算的函数，其作用为framebuffer(x,y):=A-framebuffer(x,y),边缘填充算法的描述,假设x1,x2,xm为扫描线与多边形P的交点的数列(不要求是递增序列)。步骤1:在y=e上所有像素都上值为的颜色：forx:=screen_xmintoscreen_xmaxdosetpixel(framebuffer,x,e,M),边缘填充算法的描述,步骤2：对位于扫描线y=e上的所有x坐标大于xi(I=1,2,m)的像素求余。称为向右求余:fori:=1tomdoforx:=xitoscreen_xmaxdoComplement(framebuffer,x,y)这样，多边形内被着色M，多边形外被着色。,边缘填充算法的图示,边缘填充算法的边界求余,边缘填充算法的优缺点,优点：数据结构和程序都比较简单。缺点：需对帧缓冲器中大批元素反复赋值，速度并不比扫描线算法快。,边界标志算法,边界标志算法采用先画边界后填色的方法，对帧缓冲器中每个元素赋值不超过2次。,边界标志算法的算法思想,算法思想：先把多边形边界用另一种颜色标识出来，由于边界已经标识出来了，边界之间的各个区段要么填上多边形内部的颜色，要么填上背景色。,步骤1：以值为boundary_color的特殊颜色勾画多边形P的边界。见书上的程序。步骤2：逐条扫描线对多边形着色。因为已经标志为特殊颜色的边界是两两配对的。一对边界点中间可能是多边形区域内的点，也可能是多边形区域外的点。,边界标志算法的描述,如何判断边对中间的点是否在多边形内部,采用一个布尔变量interior_point，如果当前像素位于多边形内，则为true，应着polygon_color，否则为false，应着background_color。,interior_point如何变化,此布尔变量起始在多边形外，初始值为false，每碰到一个边界像素，就取反。,边界标志算法的优缺点,优点：避免了对帧缓冲器中大量元素的多次赋值，速度与扫描线算法相当。缺点：需逐条扫描线对帧缓冲器中的元素进行搜索和比较。,区域填充,区域填充是指先将区域内一点赋予给定颜色,然后将这种颜色扩展到整个区域的过程。最先的那点也叫做种子点。,区域的表示法,内点表示法：把所给区域内所有象素一一列举出来。边界表示法：把所给区域边界上的象素一一列举出来。,区域的连通性,在区域填充算法中要求区域具有一定的连通性。,4连通性,4连通：区域任意两点，从一点出发通过上、下、左、右方向，只经过区域内的点可到达另一点。,8连通性,8连通：区域任意两点，从一点出发通过水平、垂直和对角线方向，只经过区域内的点可到达另一点。,具体表现形式,内点表示的4连通区域边界表示的4连通区域内点表示的8连通区域边界表示的8连通区域,两种连通性的边界不同,同一个区域可以看成是4连通区域，也可以看成是8连通区域，但是两者的边界是不同的。4连通区域的边界是8连通区域；8连通区域的边界是4连通区域。,递归算法,算法思想：先选取一个种子象素(x,y)，然后设此象素(x,y)为new_color，然后逐步按照连通性进行递归调用将整个区域G都设置为new_color。,递归算法的算法步骤,先测试象素(x,y)的颜色是否等于old_color，若不是则说明该象素在区域G外，不能取为种子，停止填充；否则置该象素颜色为new_color，再对上、下、左、右四个象素递归调用本身函数。,算法程序(内点表示的4连通),Procedureflood-fill-4(x,y,old_color,new_color:integer)Beginifgetpixel(framebuffer,x,y)=old_colorthenbeginsetpixel(framebuffer,x,y,new_color)flood-fill-4(x,y+1,old_color,new_color)flood-fill-4(x,y-1,old_color,new_color)flood-fill-4(x-1,y,old_color,new_color)flood-fill-4(x+1,y,old_color,new_color)endend,递归算法的特点,递归这种方法必须包含两个部分：自身调用和停止条件。,其他形式的区域表示如何变动,若是边界表示的4连通区域的程序只要改动判断条件就行了。ifgetpixel(framebuffer,x,y)boundary_colorandgetpixel(framebuffer,x,y)new_color,递归算法的优缺点和作业,优点：程序简单明了。缺点：数据和函数反复进出系统堆栈，费时费内存。作业：内点表示的8连通区域、边界表示的8连通区域的递归算法的程序。,扫描线算法,区域填充的扫描线算法适用于边界表示的4连通区域。,扫描线算法的算法思想,首先填充种子点所在的当前扫描线上位于给定区域内的一区段。然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把这些区段的右端点入栈。然后不断取出栈顶的种子重复继续上一过程，直到栈空。,算法的实现（1）,1）初始化:将种子点压入初始化后的栈。2）出栈：如果栈为空，算法结束；否则取栈顶元素为当前种子点。3）区段填充：从当前种子点开始沿水平扫描线向左右两个方向逐个像素进行填色，直至抵达边界为止。4）定范围：以XLEFT和XRIGHT分别表示第三步中填充的区段两个端点的横坐标。,算法的实现（2）,5）进栈：分别在于当前扫描线相邻的上下两条扫描线上，确定位于区间【XLEFT,XRIGHT】内的给定区域的区段。如果这些区段内的像素颜色值为内部点或边界点的颜色的话，则转到第二步，否则从XLEFT开始向右逐点判断，直到碰到边界点停下，此时把边界点左端的点（区段右端点）入栈。向右继续逐点判断是否还存在空白区段，如果有，把这些区段的右端点依次入栈。,实例,算法的优点和缺点,优点：只需把扫描线右端种子入栈，而无须把全部象素入栈，进出栈次数大为减少，内存节省很多，速度提高很快。缺点：对于已经填充的直线可能会多次地重复检查是否已经填充。,多边形扫描转换与区域填充的互相转化,若把多边形内一点作为种子点，并用以前学过的直线生成算法将多边形的边界表示为8连通区域的话，多边形的扫描转换问题可以转换为区域填充问题。反过来，若已知多边形的顶点表示，则区域填充问题可以转换为多边形的扫描转换问题。,多边形的扫描转换和区域填充的不同（1）,基本思想不同：多边形的扫描转换：将多边形的顶点表示转换为点阵表示，利用多边形各种形式的连贯性。区域填充：只改变区域内的颜色，不改变区域表示方法，利用区域的连通性。,多边形的扫描转换和区域填充的不同（2）,对边界的要求不同：多边形的扫描转换：要求每一条扫描线与多边形边界的交点个数是偶数。区域填充：要求4连通区域边界为封闭8连通区域，要求8连通区域边界为封闭4连通区域。,多边形的扫描转换和区域填充的不同（3）,出发点（初始点）不同：多边形的扫描转换：要求多边形顶点要依次给出。区域填充：要求指定区域内一点为种子点，但对任意多边形来说，要确定某点为多边形内部一点要做大量的计算。,光栅图形的走样现象,边界阶梯形：采用离散量表示连续量而引起的,细节失真,狭小图形遗失,运动图形的闪光现象：出现在缓慢移动的物体中,线段反走样算法的要点,线段有一定的宽度，应把线段看作狭长的矩形。线段有一定的面积，当线段通过某象素时，可以求出两者交的面积。,线段反走样算法的要点,再根据每一象素与线段交的面积，决定象素的灰度值。K(灰度值)系数(比如100)X线段在象素内的面积象素的面积。,反走样算法的优缺点,优点：大大改善了线型的质量，使原来阶梯之间的象素置为过渡颜色或灰度，使得颜色或灰度过渡自然，变化柔和。缺点：由于计算面积的计算量较大，速度较缓慢，不适合动态的交互式图形显示。,反走样多边形,多边形的反走样，主要表现在边界上。具体就是当某象素与多边形边界相交时，求出两者交的面积，然后以此面积值来决定该象素的颜色值或灰度值。一般采用的是Pitteway和Wakinson的将画直线的Bresenham算法发展成的多边形反走样算法。,用提高分辨率的方法来实现反走样,显然在高分辨率下直线比在低分辨率下要平直，阶梯性不明显。所以可以采取提高分辨率的方法来达到反走样的效果。硬件：换显示设备，但花费大，且不能无限提高。软件：花费小，容易实现。,用软件提高分辨率的方法来实现反走样,总体思想：高分辨率计算，低分辨率显示。高分辨率计算是指把低分辨率下的一个象素划分成许多子象素，比如2X2，3X3，7X7，然后采用相交面积法计算各个子象素的颜色值或灰度值。,用软件提高分辨率的方法来实现反走样,低分辨率显示指的是将一象素内各个子象素的颜色值或灰度值的平均值作为显示该象素的颜色值或灰度值。这里的平均值可以是算术平均，也可以是加权平均。,用软件提高分辨率的方法来实现反走样的优点,能在非反走样算法的基础上进行反走样的工作。,