计算机图形学第3章-基本光栅图形生成算法.ppt
直线生成算法DDA方法Bresenham算法圆弧生成算法中点圆生成算法多边形的填充多边形表示方法多边形填充的扫描线算法边缘填充算法边界标志算法区域填充区域的基本概念简单种子填充算法扫描线种子填充算法光栅图形的反走样算法,基本光栅图形生成算法,在计算机上绘图的一般方法,用现有绘图软件系统画图Word中的图文编辑工具AutoCADPhotoshop等大型绘图软件 用绘图软件包 OpenGL就是一个典型的、已经被接受的国际工业标准的图形软件包。Java3D用操作系统的绘图功能 如Windows中Win32API中就提供了基本的绘图功能,在数学上，理想的直线是一条由无穷多个无限小的连续的点组成。在光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。,直线生成算法,直线生成算法DDA算法,直线生成算法DDA算法,直线生成算法DDA算法,直线生成算法Bresenham算法,直线生成算法Bresenham算法,直线生成算法Bresenham算法,直线生成算法Bresenham算法,Bresenham算法基本思想上述算法扩展到任一八分圆坐标空间图，从而形成一般的Bresenham算法。下图是各象限的判断条件。,直线生成算法Bresenham算法,例题2：已知起点A(20,10)和终点B(30,18)，用Bresenham法在A和B之间生成一段直线。解：x=10,y=8,斜率在0和1之间；,直线生成算法Bresenham算法,这里仅讨论圆心位于坐标原点的圆的扫描转换算法，对于圆心不在原点的圆，可先用平移变换，将它的圆心平移到原点，然后进行扫描转换，最后再平移到原来的位置；圆的八分对称性中点算法生成圆,圆的生成算法,圆心位于原点的圆有四条对称轴x=0、y=0、y=x和y=x，见下图。从而若已知圆弧上一点P(x，y)，就可以得到其关于四条对称轴的七个对称点，这种性质称为八分对称性。因此只要能画出八分之一的圆弧，就可以利用对称性的原理得到整个圆弧。,圆的生成算法圆的八分对称性,圆的生成算法中点算法生成圆,图a,图b,圆的生成算法中点算法生成圆,di0,di0,圆的生成算法中点算法生成圆,圆的生成算法中点算法生成圆,输入:圆的半径R；算法步骤：计算初始决策变量值d=1.25-R、x=0、y=R；绘制点(x,y)及其在八分圆中的另外七个对称点；判断决策变量d的符号：若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)；当x=y时，重复步骤3和4。否则结束。,void midPointCircle(int r)float d;x=0;y=r;d=1.25-r;while(x=y)draw(x,y);/绘制点(x,y)及其七个对称点；if(d0)d+=x*2.0+3;elsed+=2.0*(x-y)+5;y-;x+;,圆的生成算法中点算法生成圆,多边形的表示方法顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但不能直观地说明哪些像素在多边形内；点阵表示是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，但具有面着色所需要的图像表示形式；多边形填充就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。,多边形顶点表示,多边形点阵表示,多边形的填充,填充条件：多边形的顶点序列(Pi，i=0，1，n)、填充色。对多边形进行填充，关键是找出多边形内的象素。多边形内点的判别准则从测试点引出一条伸向无穷远处的射线(假设是水平向右的射线)，那么：若射线与多边形边界的交点个数为奇数时，则该点为内点；若交点个数为偶数时，则该点为外点。奇异点,上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它们应该是内点，但实际上却是外点。而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。,多边形的填充,奇异点的处理将多边形的顶点分为两大类：局部极值点：如图中的点P1、P2、P4和P6。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的同一侧。非极值点：如图中的点P3、P5。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的两侧。处理奇异点规则对于局部极值点，应看成两个点；对于非极值点，应看成一个点。,多边形的填充,逐点判别算法求出多边形的最小包围盒：从Pi(xi，yi)中求极值，xmin、ymin、xmax、ymax。对包围盒中的每个象素引水平射线进行测试。求出该射线与多边形每条边的有效交点个数。如果个数为奇数：该点置为填充色。逐点判别算法虽然简单，但不可取，原因是速度慢。它割断了各象素之间的联系，孤立地考虑问题，由于要对每个象素进行多次求交运算，求交时要做大量的乘除运算，从而影响了填充速度。,多边形的填充逐点判别算法,边相关扫描线多边形填充算法边相关扫描线填充算法比逐点判别算法速度提高很多，是一种较经典的多边形填充算法。该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进行处理。,多边形的填充扫描线算法,扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变。见下图(a)。边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线yi与该边的交点为xi，而后一条扫描线yi+1=yi+1与该边的交点则为xi+1=xi+1/m，利用这种相关性可以省去大量的求交运算。见下图(b)所示。,(a)扫描线的相关性,(b)边的相关性,多边形的填充扫描线算法,数据结构边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。边表（ET：Edge Table）用来对除水平边外的所有边进行登记，来建立边的记录。边的记录定义为：,第一项：某边的最大y值（ymax）。注意要进行奇异点处理：对于非极值点应该ymax=ymax-1。第二项：某边的最小的y对应的x值。第三项：某边斜率的倒数:1/m。第四项：指针。用来指向同一条扫描线相交的其它边，如果其它边不存在，则该项置空,多边形的填充扫描线算法,数据结构活动边表（AET：Active Edge Table）：ET表建立以后，就可以开始扫描转换了。对不同的扫描线，与之相交的边线也是不同的，当对某一条扫描线进行扫描转换时，我们只需要考虑与它相交的那些边线，为此需要建立一个只与当前扫描线相交的边记录链表，称之为活动边表。,多边形的填充扫描线算法,算法步骤根据给出的多边形顶点坐标，建立ET表；求出顶点坐标中最大y值ymax和最小y值ymin。初始化AET表指针，使它为空。使用扫描线的yj值作为循环变量，使其初值为ymin。对于循环变量yj的每一整数值，重复作以下事情，直到yj大于ymax，或ET表与AET表都为空为止：如果ET表中yj桶非空，则将yj桶中的全部记录合并到AET表中。对AET表链中的记录按x的大小从小到大排序。依次取出AET表各记录中的xi坐标值，两两配对填充，即将每对xi之间的象素填上所要求的颜色。如果AET表中某记录的ymax=yj，则删除该记录。对于仍留在AET表中的每个记录，用xi+1/m代替xi进行修改，这就是该记录的边线与下一条扫描线yj+1的交点。使yj加1，以便进入下一轮循环。,多边形的填充扫描线算法,算法实现：对多边形P的每一非水平边（i=0,1,n）上的各像素做向右求反运算即可，见下图，其中(a)为给定的多边形；(b)为对区域赋初值；(c)，(d)，(e)和(f)表示逐边向右求反。,多边形的填充边缘填充算法,基本原理：首先用一种特殊的颜色在帧缓冲器中将多边形的边界（水平边的部分边界除外）勾画出来。然后再把位于多边形内的各个像素着上所需的颜色 步骤1：以值为boundary-color 的特殊颜色勾画多边形的边界。设多边形顶点为Pi=(xi,yi),0in，xi,yi均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。步骤2：设interior_point 是一布尔变量。对每一条扫描线从左到右进行搜索，如果当前是像素位于多边形内，则interior_point=true，需要填上值为polygon_color的颜色；否则该像素在多边形外，需要填上值background_color的颜色,多边形的填充边界标志算法,3.5.1 区域的基本概念,区域是指已经表示成点阵形式的像素集合在光栅图形中，区域可采用内点表示和边界表示两种形式进行描述。,区域填充是指先将区域内的一点(常称种子点)赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。,区域填充的基本概念,内点表示法：把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。,边界表示法：把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。,图3.25内点表示的区域,图3.26边界表示的区域,区域填充的基本概念,4连通的区域:取区域内任意两点，在该区域内若从其中一点出发通过上、下、左、右四种运动可到达另一点。,8连通区域:取区域内任意两点，若从其中任一点出发，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点。,区域填充的基本概念,4连通区域也可理解成8连通区域，但是两者的边界不尽相同。如果图中标有号的象素组成的区域作为4连通区域，则其边界由图中的标有号的象素组成。如果将该区域作为8连通的区域，则其边界由图中标有号和号的两种象素组成。,3.5.2 简单的种子填充算法,基本思想：给定区域G一种子点（x,y）首先判断该点是否是区域内的一点，如果是，则将该点填充为新的颜色，然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充,3.5.3 扫描线种子填充算法,基本思想：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来。反复进行这个过程，直到所保存的各区段都填充完毕,扫描线种子填充算法,算法步骤：,步骤 1：将算法设置的堆栈置为空。将给定的种子点（x,y）压入堆栈。,步骤 2：如果堆栈为空，算法结束；否则取栈顶元素（x,y）作为种子点。,步骤 3：从种子点（x,y）开始，沿纵坐标为y的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充，直到边界为止。设区间两边界的横坐标分别为xleft 和xright。,步骤4：在与当前扫描线相邻的上下两条扫描线上，以区间xleft,xright为搜索范围，求出需要填充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到步骤2。,扫描线种子填充算法,执行过程,图3.32扫描线种子填充算法的执行过程,3.6.1 光栅图形的走样现象,图形的边界一般都呈阶梯形 图形的细节失真、狭小图形遗失,狭小图形遗失和运动图形的闪光现象,3.6.2 提高分辨率的反走样方法,提高分辨率的方法：,提高分辨率的方法采用硬件:采用高分辨率的光栅图形显示器，花费的代价大。采用软件:花费的代价小，也容易实现。用软件提高分辨率的方法是：高分辨率计算，低分辨率显示。,高分辨率计算：将低分辨的图形显示象素划分为许多子象素，如22划分，33划分等，然后按通常的算法计算出各个子象素的颜色值或灰度值。低分辨率显示：将一象素内的各个子象素的颜色值或灰度值的平均值作为该象素的颜色值或灰度值。求平均值时可取算术平均，也可取加权平均。,图3.37 加权表,线段反混淆/走样算法,线段的反混淆算法的基本思想可归纳如下：(1)把线段看作是有宽度的狭长的矩形(2)线段具有一定的面积，当线段通过某象素时，可以求出两者面积的交(3)根据每一象素与线段相交部分的面积值决定该象素的颜色值或灰度值,用反混淆算法显示的线段称为反混淆/走样线段。反混淆线段是将位于原相邻阶梯之间的象素置为过渡颜色或灰度，使得颜色或者灰度过渡自然，变化柔和，阶梯被淡化后，线形就显得平直了。,反混淆算法极大地改善了显示时线段的线形质量。由于要计算面积，使得计算量大大增加，速度也由此而减慢，所以它不适合于动态的交互式图形显示。,图3.38 有宽度的线段,
