基本图形生成算法.ppt

计算机图形学与数字地图,第4章 基本图形生成算法,Email： yujieqing,余接情,区域的表示 多边形有两种重要的表示方法：顶点表示和点阵表示。,顶点表示点阵表示：通过扫描转换实现，（边界表示、内点表示）。用于图形显示、矢量数据栅格化。 点阵表示顶点表示：通过边界提取实现（模式识别），用于图形表示、建模，栅格数据矢量化。,4.4 区域的生成,凸多边形 凹多边形 环状多边形,多边形分为三种：凸多边形、凹多边形、含内环的多边形。,多边形扫描转换算法对多边形的形状没有限制，但多边形的边界不自交。,4.4 区域的生成,多边形区域的生成过程,多边形顶点坐标序列,区域（边界表示）,直线的扫描转换,扫描转换,区域填充,区域（内点表示）,扫描转换：按扫描线的顺序确定一点是否位于区域内部，再用要求的显示属性显示该像素,区域填充：则是指先将在点阵表示的多边形区域内的一点（称为种子点）赋予指定的颜色和灰度，然后将这种颜色和灰度扩展到整个区域内的过程。,4.4 区域的生成,4.4.1 扫描线算法 4.4.2 边填充算法 4.4.3 边界标志算法 4.4.4 简单种子填充算法 4.4.5 扫描线种子填充算法 4.4.6 图案填充算法,扫描转换算法,区域填充算法,4.4 区域的生成,原理：建立在图形的空间联惯性和扫描线的连惯性基础上，推广计算图形封闭区域边界与扫描线交点，将扫描线分成区间，并对区间进行填充,总体思路： 算出交点；划分区间；分配颜色 步骤：对每条扫描线分为4步 (以扫描线6为例),(1) 求交点，即计算该扫描线与多边形各边的交点；,(2) 排序，由于交点不一定由左到右求出，因此将求出的交点按 x 坐标值排序；,(3) 交点配对，1与2，3与4， ，每对表示一个区间；,(4)把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。,9,4.4.1 扫描线算法,顶点交点的取舍 分3种情况： 1）共享顶点的两条边分别落于扫描线的两侧，这时交点算一个，如F，D。 2）共享顶点的两条边位于扫描线同一侧，且该顶点为局部最低点，则算2个，如B、E。 3）共享顶点的两条边位于扫描线同一侧，且该顶点为局部最高点，则算0个，如A、C。 具体实现时，则检查顶点与相连两条边的另外两个端点的Y值的关系来判断。,0次,0次,0或2次,1次,2次,1次,A,B,C,D,E,F,4.4.1 扫描线算法,处理一条扫描线时，只需与相交的边进行求交运算。由于边的连续性，某条边与当前扫描线相交时，则很可能也与下一条扫描线相交。 为此，下一条扫描的交点可通过当前扫描线交点加上一个反斜率即可，即： Xk+1=Xk+1/m (m为斜率),通常将与当前扫描线相交的边称为活化边，并按它们与扫描线交点x坐标递增的顺序存放在一个链表中，该链表被称为活化边表(Active Edge Table),4.4.1 扫描线算法,活性边表结构,交点x值,1/m,边最高扫描线号,指针,P6P1,P5P6,P4P5,P3P4,P4P5,P3P4,4.4.1 扫描线算法,新边表结构,左边低端x值,1/m,边最高扫描线号,指针,P1P2,P2P3,P0P1,P3P4,P4P5,P5P6,扫描线号,4.4.1 扫描线算法,算法过程： 当沿扫描线号从小到大的顺序依次处理时，随时准备为每一条扫描线建立一个活化边表。 如果扫描线的y值正好与某边的较低端点的ymin值相等，则开始从新边表将该边调入活化边表，然后随着扫描线的变化不断更新活化边。 更新：加上dx（求交），或插入新边，或剔除不再相交边（扫描线号=ymax） 排序、交点配对、填充,活化边的建立与更新基于有序边表的建立。,4.4.1 扫描线算法,8 7 6 5 4 3 2 1 0,扫描线号,4.4.1 扫描线算法,扫描线算法是一种非常有效多边形扫描转换算法，它使所显示的象素只访问一次，因而输入/输出的要求低，但须对表进行维持和排序操作，不适合硬件实现。,void polyfill (polygon, color) for (各条扫描线i ) 初始化新边表头指针NET i； 把ymin = i 的边放进边表NET i; y = 最低扫描线号； 初始化活性边表AET为空； for (各条扫描线i ) 把新边表NETi中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列； 遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)， 用Setpixel (x, y, color) 改写象素颜色值； 遍历AET表，把ymax= i 的结点从AET表中删除，并把ymax i结点的x值递增x； 若允许多边形的边自相交，则用冒泡排序法对AET表重新排序； /* polyfill */,4.4.1 扫描线算法,1） 简单的边填充算法 基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取补。,4.4.2 边填充算法,优点： 1）对多边形的每条边作此处理，与边的顺序无关； 2）方法简单； 缺点： 每一个像素被访问多次，输入输出工作量大,4.4.2 边填充算法,优点： 1）方法简单 2）减少了被重复访问的像素，特别是有多个填充对象时，效果显著,2. 栅栏填充算法 栅栏：与扫描线垂直的直线，通常过多边形顶点，且将多边形分成两半,方法：对每个扫描线与多边形的交点，将交点与栅栏间的像素取 “补”,4.4.3 边界标志算法,原理：为每个像素建立inside标志，初始值为假。1）各边扫描变换，打上标志；2）对每条扫描线，依从左到右访问各象素，若点在多边形内，则inside为真，否则，inside为假。每当访问到象素为被打上边标志的点时，就把inside取反。其它，inside保持不变。若访问象素时，inside为真，则把该象素置为多边形色。,用软件实现时，扫描线算法与边标志算法的执行速度几乎相同，但由于在帧缓冲存储器中应用边标志算法时，不必建立、维护边表以及对它进行排序，所以边标志算法更适合于硬件实现，这时它的执行速度比有序边表算法快到一至两个数量级。 与边填充算法比，边标志算法不存在像素被访问多次的问题，但要时刻读取象素标志，也很耗时。,4.4.3 边界标志算法,4.4.4 简单种子填充算法,多边形扫描转换是对多边形边界及内部的所有象素赋予我们设定的颜色，把顶点表示的多边形转换成区域表达的多边形，是矢量图形向点阵图形转换的途径。 区域填充是指对区域的操作，填充过程是用新值去替换象素原来的值，对于内点表示的区域，可通过区域填充更改区域各象素的属性值。,区域指已经表示成点阵形式的填充图形，它是一组邻近而又相连的象素集合。 区域可采用内点表示和边界表示两种表示形式。在内点表示中，区域内的所有象素着同一颜色，而区域边界上的象素着不同颜色。在边界表示中，区域的边界点着同一颜色，而区域内的所有象素着不同颜色。,连通性 分为：四连通和八连通,4.4.4 简单种子填充算法,SeedFill( x, y) 若种子点不是边界也未填充，则填充；否则，函数结束。（适合边界表示的区域） SeedFill( x+1, y); SeedFill( x, y+1) ； SeedFill( x-1, y) ； SeedFill( x, y-1) ； ,4.4.4 简单种子填充算法,基本思想: 首先，确定区域内的点(x,y)是否是老像素值，若是，将其改变成新像素值; 然后，按四连通或八连通方法检测该点相邻的像素值，递归调用该算法。,简单种子填充算法思路简单、程序简洁，但由于调用了递归函数，系统开销大，许多象素被重复访问，效率不高。 由计算机编译原理可知，递归函数都可以改写为顺序执行程序，为了消除递归调用的负面作用，下面把上面的递归算法改为循序执行的算法，前提是增加一个足够大的堆栈空间（Stack）来存放未填充的种子点。,4.4.4 简单种子填充算法,基本思想：利用一个足够大的堆栈空间，将递归调用改为顺序执行。,1. 初始化：种子像素入栈，当栈非空时，重复24的步骤； 2. 栈顶像素出栈； 3. 将出栈像素置为多边形颜色； 4. 按右、上、左、下顺序依次检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，则该像素入栈； 5. 当堆栈为空时，算法终止。,4.4.4 简单种子填充算法,4.4.4 简单种子填充算法,4.4.5 扫描线种子填充算法,简单种子填充算法操作过程非常简单，却要进行深度的递归，这不仅要花费许多时间，降低了算法的效率，而且还要花费许多空间要构造堆栈结构。因此，出现了改进的扫描线种子填充算法。 扫描线种子填充算法适用于边界定义的四连通区域。区域可凹可凸，还可以包括一个或多个孔。在边界定义区域外或与其邻接的区域中像素的值或颜色不同于填充区域或多边形的值或颜色。 其基本思想是以种子所在扫描线进行从左到右填充直至边界为止,借助于堆栈，算法可分为以下五步实现： 初始化。将算法设置的堆栈置为空。将给定的种子（x,y）压入堆栈。 出栈。如果堆栈为空，算法结束。否则从包含种子像素的堆栈中取出栈顶元素（x,y）作为种子像素。 区间填充。沿当前扫描线对种子像素的左右像素进行填充（像素值为new_color），直至遇到边界像素为止，从而填满包含种子像素的区间。 (4) 定范围。以xl和xr分别表示步骤（）区间内最左和最右的两个像素。 (5) 进栈。在xlxxr中，检查与当前扫描线相邻的上下两条扫描线是否全为边界像素(boundary_color)或者前面已经填充过的像素（new_color），是则转到步骤(2),否则在xlxxr中把每一个区间的最右像素作为种子像素压入堆栈，再转到步骤（2）继续执行。,4.4.5 扫描线种子填充算法,B是边界点,C是最初种子点,13,7, 或（1）表示出栈顺序， 1表示压栈顺序,4.4.5 扫描线种子填充算法,多边形的扫描转换与区域填充的比较,联系： 是两类典型的面着色问题，用于真实感图形显示，具有密切的联系。如在一定条件下，多边形的扫描问题与区域填充问题可互相转化。 差别： （1）基本思想不同： 多边形扫描转换是指将多边形的顶点表示转化为点阵表示； 区域填充只改变了区域的填充颜色，没有改变区域的表示方法。,（2）对边界的要求不同 多边形扫描转换的扫描算法只要求一条扫描线与多边形边界的交点个数为偶数，多边形的边界可以不封闭； 在区域填充算法中，为了防止递归填充时跨越区域的边界，要求四连通区域的边界是封闭的八连通区域，八连通区域的边界为封闭的四连通区域。 （3）基于的条件不同 在区域填充算法中，要求给定区域内一点作为种子点然后从这点根据连通性将新的颜色散到整个区域； 扫描转换多边形是从多边形的边界顶点信息出发，利用多种形式的连贯性进行填充的。,图案填充是用一个图案模式来填充一个给定的区域，它是针对光栅扫描系统的一种填充方式。,图案填充的两个主要过程是： 1)定义图案：一个图案模式P通常定义为较小的NN的像素阵列。Pij(i=0,1,.,n-1;j=0，1,.,n-1)代表在模式(i,j)处的颜色/亮度值。 2)填充区域：在扫描线转换填充算法中,增加一个相应的控制机构,使之实际填充像素的颜色/亮度值是从图案模式中提取出来即可。,4.4.6 图案填充算法,4.4.6 图案填充算法,绝对定位：i=x mod n；j=(n-1)- (y mod n)；,相对定位：i=(x-xmin) mod n；j=(n-1)-(y-ymin) mod n,关键问题：找到填充位置后，如何确定与其对应的图案上的象素位置,字符： 是一种图形，通常指数字、字母、汉字等符号。计算机中字符由一个数字编码唯一标识。 字符编码标准： 国际上流行的字符集是“美国信息交换用标准代码集”简称ASCII码。 我国除采用ASCII码外，还另外制定了汉字编码的国家标准字符集GB231280。 字库： 为了在显示器等输出设备上输出字符，系统中必须装备有相应的字库。字库存储了每个字符的形状信息，分为矢量和点阵型两种。,4.5 字符,点阵字符 点阵字符是由一个位图表示，保存字符就是保存表示它的位图。字型7x9、9x16、1624等指的是位图的尺寸。一个汉字需要1624=384位，即48个字节，而常用汉字有6763个，从而存储这种型号需要6763X48324KB。,点阵字符的显示分为两步。首先从字库中将它的位图检索出来；然后将检索到的位图写到帧缓冲器中。,4.5 字符,不同字体、大小型号 - 字库很庞大 - 压缩技术 常见压缩技术：黑白段压缩、部件压缩、轮廓字形压缩等，其中，轮廓字形法压缩比大，且能保证字符质量，是当今国际上最流行的一种方法。,4.5 字符,轮廓字形法采用直线或二/三次bezier曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义加上一些指示横宽、竖宽、基点、基线等等控制信息就构成了字符的压缩数据，,矢量字符,矢量字符记录字符的笔画信息而不是整个位图。选一个正方形格网作为字符的局部坐标空间，网格大小可取1616、3232、6464等。,对一个字符来说，它由构成它的笔画组成，而每一笔又由其两端确定。对于每一个端点，只要保存它的坐标值和它与前一点的连接关系即可。,矢量字符的显示也分为两步，首先根据给定字符的编码，在字库中检索出表示该字符的信息。然后取出端点坐标，对其进行适当的几何变换，再根据各端点的标志显示出字符。,4.5 字符,矢量字符VS点阵字符 矢量字符具有存储空间小，美观、变换方便等优点。对于字符的旋转、缩放等变换，点阵字符的变换需要对表示字符位图中的每一象素进行；而矢量字符的变换只要对其笔画端点进行变换就可以了。,4.5 字符,走样：离散量表示连续量引起的失真现象。 反走样：用以减少或消除失真现象的技术，为了改善图形的生成质量和效果，实质上，反走样技术就是计算机图形学中的图像处理技术。 常用的反走样技术：提高分辨率、区域采样、加权区域采样,图形生成是以像素集近似替代真实图形，这种近似使得最终在显示器上所显示的图形会产生图形的边界误差及边界的“锯齿”形状，这将会影响到图形显示的视觉质量和真实感效果。,4.6 反走样,（1）提高分辨率 把显示器分辨率提高一倍，直线经过两倍的象素，锯齿也增加一倍，但同时每个阶梯的宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了一些。,这种方法是以4倍的存储器代价和扫描转换时间获得的。因此，增加分辨率虽然简单，但是不经济的方法，而且它也只能减轻而不能消除锯齿问题。,4.6 反走样,（2）区域采样 将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。,4.6 反走样,假设一条直线段的斜率为m(0m1)，且所画直线为一个象素单位，则直线段与象素相交有五种情况：,与： D2/2m ； 与： D - m/2 ；： 1 - D2/m。 用上述值乘以象素的最大灰度值，再取整，即可得到象素的显示灰度值，这种区域取样法的反走样效果较好。,4.6 反走样,为了简化计算可以采用离散的方法。首先将屏幕象素均分成n个子象素，然后计算中心点落在直线段内的子象素的个数k。最后将屏幕该象素的亮度置为相交区域面积的近似值可k/n。,n=9,k=3近似面积为1/3,4.6 反走样,非加权区域采样方法有两个缺点： （1）象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应。 （2）直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。,（3）加权区域取样 相交区域对象素亮度的贡献依赖于该区域与象素中心的距离。,4.6 反走样,优点：算法简单、效率高。 缺点：1）线的始末端总是水平或垂直的。当线宽较大时，看起来很不自然。当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口。 2）水平线或垂直线，最粗。45斜线，最细，1/ 2 0.7倍。,4.7 线宽与线型,（1）线刷子方法,始末端也是水平或垂直的，且线宽与线条方向有关。 水平线与垂直线，线宽最小，而对于斜率为1的线条，线宽最大，为垂直（水平）的2 倍。 缺点：重复地写象素。,（2）方形刷子法,实现方法：把方形中心对准单象素宽的线条上各个象素，并把方形内的象素全部置成线条颜色。,4.7 线宽与线型,4.7 线宽与线型,（3）圆弧线宽的处理,线型可以用一个布尔值的序列来存放。例如，用一个32位整数可以存放32个布尔值。用这样的整数存放线型定义时，线型必须以32个象素为周期进行重复。可以把扫描变换算法中的写象素语句改为： if(bitstringi%32) SetPixel(x，y，value); 其中i为循环变量，在扫描变换算法的内循环中每处理一个象素递增1，然后除以32取余(“%”为C语言中求模运算符),余数变化范围是031。 例子: bitstring=11111111110000000000111111111100,（4）线型的处理,4.7 线宽与线型,Thank You !,