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

1、直线生成算法 DDA方法 Bresenham算法 圆弧生成算法 中点圆生成算法 多边形的填充 多边形表示方法 多边形填充的扫描线算法 边缘填充算法 边界标志算法 区域填充 区域的基本概念 简单种子填充算法 扫描线种子填充算法 光栅图形的反走样算法,基本光栅图形生成算法,在计算机上绘图的一般方法,用现有绘图软件系统 画图Word中的图文编辑工具AutoCADPhotoshop等大型绘图软件 用绘图软件包 OpenGL就是一个典型的、已经被接受的国际工业标准的图形软件包。 Java3D 用操作系统的绘图功能 如Windows中Win32API中就提供了基本的绘图功能,在数学上，理想的直线是一条由无

2、穷多个无限小的连续的点组成。 在光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。,直线生成算法,DDA算法描述 设(xs,ys)和(xe,ye)分别为直线的起点坐标和终点坐标，则： 直线的斜率= = 可通过计算由x方向的增量引起y的改变来生成直线。由 +1 = +，得到： +1 = + = + 同样，可通过计算由y方向的增量引起x的改变来生成直线。由 +1 = +，得到： +1 = + = + ,直线生成算法DDA算法,DDA算法基本

3、思想 选定 和 中较大者作为步进方向，在此方向上每次增加（或者减少）一个像素，然后计算另一个方向上增量的值，把每次计算出的值经取整后顺序输出到显示器，则可以得到光栅化的直线。 DDA算法特点 算法简单，实现容易，但计算量较大，每产生一个像素需要取整运算，此外算法还要除法运算，因此生成直线的速度较慢。,直线生成算法DDA算法,例题1：已知起点A(16,-5)和终点B(-4,8)，用DDA法在A和B之间生成一段直线。 第一步：计算初值： = 4 16=20， =8 5 =13，由于2013，所以选定x轴方向作为步进方向；= =20 第二步：在x轴方向上每次的变化量为= =1，则y轴方向的变化量为=

4、 =0.65 第三步：循环计算点的坐标，并取整显示：,直线生成算法DDA算法,Bresenham算法基本思想 令= ，直线方程：= + ，其中（ , ）为起点坐标； 考虑01，则x方向增加1，y方向增加m，由起点(xs,ys)可求得直线上的点(xi，yi)， i=1,2,3, 其中 x1= xs, y1= ys； 用坐标为(xi，round(yi)的象素来表示直线上的点，其中round(yi)表示最靠近y的整数；,直线生成算法Bresenham算法,Bresenham算法基本思想 令yi,r=round(yi), 用坐标为(xi，yi,r)的象素来表示直线上的点，第i+1个点只能在C和D中选取

5、。 令误差项 +1 = +1 = +1 + 2 = +1 , + , +1 2 = +1 , 1 2 当( +1 )0时， +1, = , +1，即选C点 当( +1 )0时， +1, = , ，即选D点,直线生成算法Bresenham算法,Bresenham算法基本思想 ( +2 )的递推公式 +2 = +2 +1, 1 2 = ( +1 +) +1, 1 2 = +1 + , 1 2 当( +1 )0时 +1 + ( , +1) 1 2 当( +1 )0时 = +1 + 当( +1 )0时 +1 +1 当( +1 )0时 = +1 + 当 +1 0时 +1 + 1 当( +1 )0时 初始

6、值 2 = 2 1, 1 2 = 2 1 1 2 = 1 2 = 1 2,直线生成算法Bresenham算法,实际上，误差项( )的数值大小与算法的执行没有关系，相关的只是( )的符号，因而我们可以改变( )的定义，在两边同乘以2 ，可消除除法运算： 令初始 2 =2 如果( +1 )0，则: +2 , +2 =( +1 +1, +1 +1) +2 = +1 +2() 如果 +1 0 ，则: +2 , +2 =( +1 +1, +1 ) +2 = +1 +2,直线生成算法Bresenham算法,Bresenham算法基本思想 上述算法扩展到任一八分圆坐标空间图，从而形成一般的Bresenham

7、算法。下图是各象限的判断条件。,直线生成算法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)，就可以得到其关于四条对称轴的七个对称点，这种

8、性质称为八分对称性。因此只要能画出八分之一的圆弧，就可以利用对称性的原理得到整个圆弧。,圆的生成算法圆的八分对称性,设要显示圆的圆心在原点(0,0)，半径为R，起点在(0,R)处，终点在( 2 , 2 )，顺时针生成八分之一圆，利用对称性扫描转换全部圆； 为了应用圆的生成算法，我们定义一个圆函数： F(x,y)= 2 + 2 2 任何点(x,y)的相对位置可由圆函数的符号来确定： 若F(x,y)0，点(x,y)位于圆外,圆的生成算法中点算法生成圆,如何选取下一象素点？ 假定当前取点为P (xi，yi)，如果顺时针生成圆，那么下一点只能取正右方的点E(xi+1，yi)或右下方的点SE(xi+1，

9、yi-1)两者之一。 假设M是E和SE的中点，即 M(xi+1, yi-0.5)，用中点M的圆函数作为决策变量di，则： = +1, 1 2 = ( +1) 2 + ( 1 2 ) 2 2 当di 0时，M在圆外(如图a)，说明点SE距离圆更近，应取点SE作为下一象素点； 当di =0时，在E点与SE点之中随便取一个即可，我们约定取点SE作为下一象素点。,图a,图b,圆的生成算法中点算法生成圆,如何计算新的决策变量？ 当前决策变量： = +1, 1 2 = ( +1) 2 + ( 1 2 ) 2 2 （1） 下面分两种情况来讨论在迭代计算中决策变量di+1的推导： 若di0，则选择E点，接着下

10、一个中点就是M(xi+2, yi 1 2 ),这时新的决策变量为 +1 = +2, 1 2 = ( +2) 2 + ( 1 2 ) 2 2 （2） (2)-(1)得： +1 = +2 +3 若di0，则选择SE点，接着下一个中点就是M(xi+2, yi 3 2 ),这时新的决策变量为 +1 = +2, 3 2 = ( +2) 2 + ( 3 2 ) 2 2 （3） (3)-(1)得： +1 = +2 ( )+5,di0,di0,圆的生成算法中点算法生成圆,如何计算初始决策变量？ 对于初始点(0，R)，顺时针生成八分之一圆，下一个中点M的坐标是(1,R-0.5)，所以： 0 = 1,0.5 =

11、1 2 + (0.5) 2 2 = 5 4 ,圆的生成算法中点算法生成圆,输入:圆的半径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)及其

12、七个对称点； if(d0) d+=x*2.0+3; else d+=2.0*(x-y)+5; y-; x+; ,圆的生成算法中点算法生成圆,多边形的表示方法 顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但不能直观地说明哪些像素在多边形内； 点阵表示是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，但具有面着色所需要的图像表示形式； 多边形填充就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。,多边形顶点表示,多边形点阵表示,多边形的填充,填充条件：多边形

13、的顶点序列(Pi，i=0，1，n)、填充色。 对多边形进行填充，关键是找出多边形内的象素。 多边形内点的判别准则 从测试点引出一条伸向无穷远处的射线(假设是水平向右的射线)，那么：若射线与多边形边界的交点个数为奇数时，则该点为内点；若交点个数为偶数时，则该点为外点。 奇异点,上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它们应该是内点，但实际上却是外点。 而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。,多边形的填充,奇异点的处理 将多边形的顶点分为两大类： 局部极

14、值点：如图中的点P1、P2、P4和P6。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的同一侧。 非极值点：如图中的点P3、P5。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的两侧。 处理奇异点规则 对于局部极值点，应看成两个点； 对于非极值点，应看成一个点。,多边形的填充,逐点判别算法 求出多边形的最小包围盒：从Pi(xi，yi)中求极值，xmin、ymin、xmax、ymax。 对包围盒中的每个象素引水平射线进行测试。 求出该射线与多边形每条边的有效交点个数。 如果个数为奇数：该点置为填充色。 逐点判别算法虽然简单，但不可取，原因是速度慢。它割断了各象素之

15、间的联系，孤立地考虑问题，由于要对每个象素进行多次求交运算，求交时要做大量的乘除运算，从而影响了填充速度。,多边形的填充逐点判别算法,边相关扫描线多边形填充算法 边相关扫描线填充算法比逐点判别算法速度提高很多，是一种较经典的多边形填充算法。 该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进行处理。,多边形的填充扫描线算法,扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变。见下图(a)。 边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线yi与该边的交点为xi，而后一条扫描线yi+

16、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。 第四项：指针。用来指向同一条扫描线相交的其它边，如果其它边不存在，

17、则该项置空,多边形的填充扫描线算法,数据结构 活动边表（AET：Active Edge Table）：ET表建立以后，就可以开始扫描转换了。对不同的扫描线，与之相交的边线也是不同的，当对某一条扫描线进行扫描转换时，我们只需要考虑与它相交的那些边线，为此需要建立一个只与当前扫描线相交的边记录链表，称之为活动边表。,多边形的填充扫描线算法,算法步骤 根据给出的多边形顶点坐标，建立ET表； 求出顶点坐标中最大y值ymax和最小y值ymin。 初始化AET表指针，使它为空。 使用扫描线的yj值作为循环变量，使其初值为ymin。 对于循环变量yj的每一整数值，重复作以下事情，直到yj大于ymax，或ET

18、表与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)为对区域赋初值；(

19、c)，(d)，(e)和(f)表示逐边向右求反。,多边形的填充边缘填充算法,基本原理：首先用一种特殊的颜色在帧缓冲器中将多边形的边界（水平边的部分边界除外）勾画出来。然后再把位于多边形内的各个像素着上所需的颜色 步骤1：以值为boundary-color 的特殊颜色勾画多边形的边界。设多边形顶点为Pi= (xi, yi),0in， xi, yi均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。 步骤2：设interior_point 是一布尔变量。对每一条扫描线从左到右进行搜索，如果当前是像素位于多边形内，则interior_point=true，需要填上

20、值为polygon_color的颜色；否则该像素在多边形外，需要填上值background_color的颜色,多边形的填充边界标志算法,3.5.1 区域的基本概念,区域是指已经表示成点阵形式的像素集合在光栅图形中，区域可采用内点表示和边界表示两种形式进行描述。,区域填充是指先将区域内的一点(常称种子点)赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。,区域填充的基本概念,内点表示法：把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。,边界表示法：把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。,图3.25内点表示的区域,图3.26边界表示的区域,区域填充的基本概念,4

21、连通的区域: 取区域内任意两点，在该区域内若从其中一点出发通过上、下、左、右四种运动可到达另一点。,8连通区域: 取区域内任意两点，若从其中任一点出发，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点。,区域填充的基本概念,4连通区域也可理解成8连通区域，但是两者的边界不尽相同。如果图中标有号的象素组成的区域作为4连通区域，则其边界由图中的标有号的象素组成。如果将该区域作为8连通的区域，则其边界由图中标有号和号的两种象素组成。,3.5.2 简单的种子填充算法,基本思想：给定区域G一种子点（x, y）首先判断该点是否是区域内的一点，如果是，则将该点填充为新的颜色，然后将该点周

22、围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充,3.5.3 扫描线种子填充算法,基本思想：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来。反复进行这个过程，直到所保存的各区段都填充完毕,扫描线种子填充算法,算法步骤：,步骤 1：将算法设置的堆栈置为空。将给定的种子点（x, y）压入堆栈。,步骤 2：如果堆栈为空，算法结束；否则取栈顶元素（x, y）作为种子点。,步骤 3：从种子点（x, y）开始，沿纵坐标为y的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充，直到边界为止。设区间两边界的横坐标分别为xleft 和