计算机图形学第3章-基本光栅图形生成算法.ppt

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