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

1、 直线生成算法直线生成算法 扫描线种子填充算法扫描线种子填充算法 光栅图形的反走样算法光栅图形的反走样算法 在数学上，理想的直线是一条由无穷多个无限小的延续的点组成。 在光栅显示平面上，我们只能用二维光栅格网上尽能够接近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是延续的。例题1：知起点A(16,-5)和终点B(-4,8)，用DDA法在A和B之间生成一段直线。第一步：计算初值：，由于，所以选定x轴方向作为步进方向；第二步：在x轴方向上每次的变化量为，那么y轴方向的变化量为第三步：循环计算点

2、的坐标，并取整显示： 实践上，误差项的数值大小与算法的执行没有关系，相关的只是的符号，因此我们可以改动的定义，在两边同乘以 ，可消除除法运算： 令初始 假设，那么: 假设，那么: Bresenham算法根本思想 上述算法扩展到任一八分圆坐标空间图，从而构成普通的Bresenham算法。以下图是各象限的判别条件。例题2：知起点A(20,10)和终点B(30,18)，用Bresenham法在A和B之间生成一段直线。解：x=10, y= 8 ,斜率在0和1之间；ixiyi12010=2*8-10=6x加1，y加122111x加1，y加132212x加1，y不变42312x加1，y加152413x加1

3、，y加162514x加1，y加172615x加1，y加182716x加1，y不变92816x加1，y加1102917x加1，y加1 圆心位于原点的圆有四条对称轴x=0、y=0、y=x和y=x，见以下图。从而假设知圆弧上一点P(x，y)，就可以得到其关于四条对称轴的七个对称点，这种性质称为八分对称性。因此只需能画出八分之一的圆弧，就可以利用对称性的原理得到整个圆弧。 设要显示圆的圆心在原点(0,0)，半径为R，起点在(0,R)处，终点在(, )，顺时针生成八分之一圆，利用对称性扫描转换全部圆； 为了运用圆的生成算法，我们定义一个圆函数： F(x,y)= 任何点(x,y)的相对位置可由圆函数的符号

4、来确定： 假设F(x,y)0，点(x,y)位于圆外图a图b 2 2 (2)-(1) (2)-(1)得：得： 假设假设di0di0，那么选择，那么选择SESE点，点，接着下一个中点就是接着下一个中点就是M(xi+2, M(xi+2, yi),yi),这时新的决策变量为这时新的决策变量为 3 3 (3)-(1) (3)-(1)得：得：di0di0 输入:圆的半径R； 算法步骤： 计算初始决策变量值d=1.25-R、x=0、y=R； 绘制点(x,y)及其在八分圆中的另外七个对称点； 判别决策变量d的符号：假设d0，那么先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否那么先将d更新为d

5、+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)、填充色。 对多边形进展填充，关键是找出多边形内的象素。 多边形内点的判别准那么 从测试点引出一条伸向无穷远处的射线(假设是程度向右的射线)，那么：假设

6、射线与多边形边境的交点个数为奇数时，那么该点为内点；假设交点个数为偶数时，那么该点为外点。 奇特点上述的判别准那么，在大多数情况下是正确的，但当程度扫描线正好经过多边形顶点时，要特别留意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准那么它们应该是内点，但实践上却是外点。 而图中过顶点的射线3、射线5，对于判别准那么的运用又是正确的。 奇特点的处置 将多边形的顶点分为两大类： 部分极值点：如图中的点P1、P2、P4和P6。对于这些点来说，进入该点的边线和分开该点的边线位于过该点扫描线的同一侧。 非极值点：如图中的点P3、P5。对于这些点来说，进入该点的边线和分开该点

7、的边线位于过该点扫描线的两侧。 处置奇特点规那么 对于部分极值点，应看成两个点； 对于非极值点，应看成一个点。 逐点判别算法 求出多边形的最小包围盒：从Pi(xi，yi)中求极值，xmin、ymin、xmax、ymax。 对包围盒中的每个象素引程度射线进展测试。 求出该射线与多边形每条边的有效交点个数。 假设个数为奇数：该点置为填充色。 逐点判别算法虽然简单，但不可取，缘由是速度慢。它割断了各象素之间的联络，孤立地思索问题，由于要对每个象素进展多次求交运算，求交时要做大量的乘除运算，从而影响了填充速度。 边相关扫描线多边形填充算法 边相关扫描线填充算法比逐点判别算法速度提高很多，是一种较经典的

8、多边形填充算法。 该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进展处置。 扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只需遇到多边形边线与该扫描线的交点时才会发生改动。质，这种性质只需遇到多边形边线与该扫描线的交点时才会发生改动。见以下图见以下图(a)(a)。 边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线一条边，前一条扫描线yi yi与该边的交点为与该边的交点为xi xi，而后一条扫描线，而后

9、一条扫描线yi+1=yi+1yi+1=yi+1与该边的交点那么为与该边的交点那么为xi+1=xi+1/mxi+1=xi+1/m，利用这种相关性可以省去大量的求，利用这种相关性可以省去大量的求交运算。见以下图交运算。见以下图(b)(b)所示。所示。(a)扫描线的相关性扫描线的相关性(b)边的相关性边的相关性 第一项：某边的最大y值ymax。留意要进展奇特点处置：对于非极值点应该ymax=ymax-1。 第二项：某边的最小的y对应的x值。 第三项：某边斜率的倒数:1/m。 第四项：指针。用来指向同一条扫描线相交的其它边，假设其它边不存在，那么该项置空3.5.1 3.5.1 区域的根本概念区域的根本

10、概念 区域是指曾经表示成点阵方式的像素集合在光栅图形中，区域可采用内点表示和边境表示两种方式进展描画。 区域填充是指先将区域内的一点(常称种子点)赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。区域填充的根本概念区域填充的根本概念内点表示法：把位于给定区域内的一切像素一一列举出来的方法称为内点表示法。边境表示法：把位于给定区域边境上的像素一一列举出来的方法称为边境表示法。图3.25内点表示的区域图3.26边境表示的区域区域填充的根本概念区域填充的根本概念 4连通的区域: 取区域内恣意两点，在该区域内假设从其中一点出发经过上、下、左、右四种运动可到达另一点。图3.27四个方向的运动8连通区域

11、: 取区域内恣意两点，假设从其中任一点出发，在该区域内经过沿程度方向、垂直方向和对角线方向的八种运动可到达另一点。图3.28个方向的运动区域填充的根本概念区域填充的根本概念4连通区域也可了解成8连通区域，但是两者的边境不尽一样。假设图中标有号的象素组成的区域作为4连通区域，那么其边境由图中的标有号的象素组成。假设将该区域作为8连通的区域，那么其边境由图中标有号和号的两种象素组成。 图3.29内点表示的八连通区域图3.30边境表示的八连通区域图3.31四连通区域与八连通区域的不同边境3.5.2 3.5.2 简单的种子填充算法简单的种子填充算法根本思想：给定区域G一种子点x, y首先判别该点能否是

12、区域内的一点，假设是，那么将该点填充为新的颜色，然后将该点周围的四个点四连通或八个点八连通作为新的种子点进展同样的处置，经过这种分散完成对整个区域的填充 3.5.3 3.5.3 扫描线种子填充算法扫描线种子填充算法根本思想：首先填充任前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保管起来。反复进展这个过程，直到所保管的各区段都填充终了扫描线种子填充算法扫描线种子填充算法算法步骤：步骤步骤 1：将算法设置的堆栈置为空。将给定的种子点：将算法设置的堆栈置为空。将给定的种子点x, y压入压入堆栈。堆栈。步骤步骤 2：假设堆栈为空，算法终了；

13、否那么取栈顶元素：假设堆栈为空，算法终了；否那么取栈顶元素x, y作为作为种子点。种子点。步骤步骤 3：从种子点：从种子点x, y开场，沿纵坐标为开场，沿纵坐标为y的当前扫描线向左右两的当前扫描线向左右两个方向逐个像素用新的颜色值进展填充，直到边境为止。设区间两边个方向逐个像素用新的颜色值进展填充，直到边境为止。设区间两边境的横坐标分别为境的横坐标分别为xleft 和和xright。步 骤步 骤 4 4 ： 在 与 当 前 扫 描 线 相 邻 的 上 下 两 条 扫 描 线 上 ， 以 区 间： 在 与 当 前 扫 描 线 相 邻 的 上 下 两 条 扫 描 线 上 ， 以 区 间xleft,

14、xrightxleft,xright为搜索范围，求出需求填充的各小区间，把各小区间中为搜索范围，求出需求填充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到步骤最右边的点并作为种子点压入堆栈，转到步骤2 2。 扫描线种子填充算法扫描线种子填充算法执行过程图3.32扫描线种子填充算法的执行过程1212121233.6.1 光栅图形的走样景象光栅图形的走样景象 图形的边境普通都呈阶梯形 图形的细节失真、狭小图形遗失 a 待显示的细小图形b 显示结果图3.35 细节失真a待显示的狭小矩形b 显示结果图3.36 狭小图形的遗失狭小图形遗失和运动图形的闪光景象 图3.33阶梯形边境图图3.3

15、4阶梯形线段3.6.2 3.6.2 提高分辨率的反走样方法提高分辨率的反走样方法提高分辨率的方法：提高分辨率的方法采用硬件: 采用高分辨率的光栅图形显示器，破费的代价大。采用软件: 破费的代价小，也容易实现。用软件提高分辨率的方法是：高分辨率计算，低分辨率显示。 高分辨率计算：将低分辨的图形显示象素划分为许多子象素，如22划分，33划分等，然后按通常的算法计算出各个子象素的颜色值或灰度值。低分辨率显示：将一象素内的各个子象素的颜色值或灰度值的平均值作为该象素的颜色值或灰度值。求平均值时可取算术平均，也可取加权平均。 图3.37 加权表3.6.33.6.3线段反混淆线段反混淆/ /走样算法走样算法 线段的反混淆算法的根本思想可归纳如下： (1) 把线段看作是有宽度的狭长的