基本光栅图形生成算法PPT讲稿.ppt

《基本光栅图形生成算法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《基本光栅图形生成算法PPT讲稿.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基本光栅图形生成算基本光栅图形生成算法法2022/10/8第1页，共41页，编辑于2022年，星期六在计算机上绘图的一般方法在计算机上绘图的一般方法用现有绘图软件系统用现有绘图软件系统画图Word中的图文编辑工具AutoCADPhotoshop等大型绘图软件 用绘图软件包用绘图软件包 OpenGL就是一个典型的、已经被接受的国际工业标准的图形软件包。Java3D用操作系统的绘图功能用操作系统的绘图功能 如Windows中Win32API中就提供了基本的绘图功能第2页，共41页，编辑于2022年，星期六在数学上，理想的直线是一条由无穷多个无限小的连续的点组成。在光栅显示平面上，我们只能用二维光栅

2、格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。直线生成算法直线生成算法第3页，共41页，编辑于2022年，星期六DDA算法描述算法描述设(xs,ys)和(xe,ye)分别为直线的起点坐标和终点坐标，则：可通过计算由x方向的增量引起y的改变来生成直线。由，得到：同样，可通过计算由y方向的增量引起x的改变来生成直线。由，得到：直线生成算法直线生成算法DDA算法算法第4页，共41页，编辑于2022年，星期六DDA算法基本思想算法基本思想选定和中较大者作为步进方向，在此方向

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

4、法DDA算法算法第6页，共41页，编辑于2022年，星期六Bresenham算法基本思想算法基本思想令，直线方程：，其中为起点坐标；考虑，则x方向增加1，y方向增加m，由起点(xs,ys)可求得直线上的点(xi，yi)，i=1,2,3,其中 x1=xs,y1=ys；用坐标为(xi，round(yi)的象素来表示直线上的点，其中round(yi)表示最靠近y的整数；直线生成算法直线生成算法Bresenham算法算法第7页，共41页，编辑于2022年，星期六Bresenham算法基本思想算法基本思想令yi,r=round(yi),用坐标为(xi，yi,r)的象素来表示直线上的点，第i+1个点只能在

5、C和D中选取。令误差项当时，即选C点当时，即选D点直线生成算法直线生成算法Bresenham算法算法第8页，共41页，编辑于2022年，星期六Bresenham算法基本思想算法基本思想的递推公式=初始值直线生成算法直线生成算法Bresenham算法算法第9页，共41页，编辑于2022年，星期六实际上，误差项的数值大小与算法的执行没有关系，相关的只是的符号，因而我们可以改变的定义，在两边同乘以，可消除除法运算：令初始如果，则:如果，则:直线生成算法直线生成算法Bresenham算法算法第10页，共41页，编辑于2022年，星期六 Bresenham算法基本思想算法基本思想上述算法扩展到任一八分圆

6、坐标空间图，从而形成一般的Bresenham算法。下图是各象限的判断条件。直线生成算法直线生成算法Bresenham算法算法第11页，共41页，编辑于2022年，星期六例题2：已知起点A(20,10)和终点B(30,18)，用Bresenham法在A和B之间生成一段直线。解：解：x=10,y=8,斜率在0和1之间；直线生成算法直线生成算法Bresenham算法算法ixiyi12010=2*8-10=6x加1，y加122111x加1，y加132212x加1，y不变42312x加1，y加152413x加1，y加162514x加1，y加172615x加1，y加182716x加1，y不变92816x加

7、1，y加1102917x加1，y加1ixiyi12010 x加1，y加122111x加1，y加132212x加1，y不变42312x加1，y加152413x加1，y加162514x加1，y加172615x加1，y加182716x加1，y不变92816x加1，y加1102917x加1，y加1第12页，共41页，编辑于2022年，星期六这里仅讨论圆心位于坐标原点的圆的扫描转换算法，对于圆心不在原点的圆，可先用平移变换，将它的圆心平移到原点，然后进行扫描转换，最后再平移到原来的位置；圆的八分对称性中点算法生成圆圆的生成算法圆的生成算法第13页，共41页，编辑于2022年，星期六圆心位于原点的圆有四条

8、对称轴x=0、y=0、y=x和y=x，见下图。从而若已知圆弧上一点P(x，y)，就可以得到其关于四条对称轴的七个对称点，这种性质称为八分对称性。因此只要能画出八分之一的圆弧，就可以利用对称性的原理得到整个圆弧。圆的生成算法圆的生成算法圆的八分对称性圆的八分对称性第14页，共41页，编辑于2022年，星期六设要显示圆的圆心在原点(0,0)，半径为R，起点在(0,R)处，终点在(,)，顺时针生成八分之一圆，利用对称性扫描转换全部圆；为了应用圆的生成算法，我们定义一个圆函数：F(x,y)=任何点(x,y)的相对位置可由圆函数的符号来确定：若F(x,y)0，点(x,y)位于圆外圆的生成算法圆的生成算法

9、中点算法生成圆中点算法生成圆第15页，共41页，编辑于2022年，星期六如何选取下一象素点？如何选取下一象素点？假定当前取点为P(xi，yi)，如果顺时针生成圆，那么下一点只能取正右方的点E(xi+1，yi)或右下方的点SE(xi+1，yi-1)两者之一。假设M是E和SE的中点，即 M(xi+1,yi-0.5)，用中点M的圆函数作为决策变量di，则：l当di 0时，M在圆外(如图a)，说明点SE距离圆更近，应取点SE作为下一象素点；l当di=0时，在E点与SE点之中随便取一个即可，我们约定取点SE作为下一象素点。图a图b圆的生成算法圆的生成算法中点算法生成圆中点算法生成圆第16页，共41页，编

10、辑于2022年，星期六如何计算新的决策变量？如何计算新的决策变量？当前（1）下面分两种情况来讨论在迭代计算中决策变量di+1的推导：若di0，则选择E点，接着下一个中点就是M(xi+2,yi),这时新的决策变量为（2）(2)-(1)得：若di0，则选择SE点，接着下一个中点就是M(xi+2,yi),这时新的决策变量为（3）(3)-(1)得：di0di0圆的生成算法圆的生成算法中点算法生成圆中点算法生成圆第17页，共41页，编辑于2022年，星期六如何计算初始决策变量？如何计算初始决策变量？对于初始点(0，R)，顺时针生成八分之一圆，下一个中点M的坐标是(1,R-0.5)，所以：圆的生成算法圆的

11、生成算法中点算法生成圆中点算法生成圆第18页，共41页，编辑于2022年，星期六输入:圆的半径R；算法步骤：1.计算初始决策变量值d=1.25-R、x=0、y=R；2.绘制点(x,y)及其在八分圆中的另外七个对称点；3.判断决策变量d的符号：若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)；4.当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;elsed+=2.0*(x-y)+5;y-;x+;圆的生成算法圆的生成算法中点算法生成圆中点算法生成圆第19页，共41页，编辑于2022年，星期六多边形的表示方法多边形的表示方法顶点表示顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但不能直观地说明哪些像素在多边形内；点阵表示点阵表示是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，但具有面着色所需要的图像表示形式；多边形填充多边形填充就是把多边形的顶点表示转换为点阵表示把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像

13、素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。多边形顶点表示多边形点阵表示 多边形的填充多边形的填充第20页，共41页，编辑于2022年，星期六填充条件：多边形的顶点序列(Pi，i=0，1，n)、填充色。对多边形进行填充，关键是找出多边形内的象素。多边形内点的判别准则从测试点引出一条伸向无穷远处的射线(假设是水平向右的射线)，那么：若射线与多边形边界的交点个数为奇数时，则该点为内点；若交点个数为偶数时，则该点为外点。奇异点上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它

14、们应该是内点，但实际上却是外点。而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。多边形的填充多边形的填充第21页，共41页，编辑于2022年，星期六奇异点的处理将多边形的顶点分为两大类：局部极值点：如图中的点P1、P2、P4和P6。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的同一侧。非极值点：如图中的点P3、P5。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的两侧。处理奇异点规则对于局部极值点，应看成两个点；对于非极值点，应看成一个点。多边形的填充多边形的填充第22页，共41页，编辑于2022年，星期六逐点判别算法求出多边形的最小包围盒：从Pi

15、(xi，yi)中求极值，xmin、ymin、xmax、ymax。对包围盒中的每个象素引水平射线进行测试。求出该射线与多边形每条边的有效交点个数。如果个数为奇数：该点置为填充色。逐点判别算法虽然简单，但不可取，原因是速度慢。它割断了各象素之间的联系，孤立地考虑问题，由于要对每个象素进行多次求交运算，求交时要做大量的乘除运算，从而影响了填充速度。多边形的填充多边形的填充逐点判别算法逐点判别算法第23页，共41页，编辑于2022年，星期六边相关扫描线多边形填充算法边相关扫描线填充算法比逐点判别算法速度提高很多，是一种较经典的多边形填充算法。该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进行

16、处理。多边形的填充多边形的填充扫描线算法扫描线算法第24页，共41页，编辑于2022年，星期六扫描线的相关性：扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变。见下图(a)。边的相关性：边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线yi与该边的交点为xi，而后一条扫描线yi+1=yi+1与该边的交点则为xi+1=xi+1/m，利用这种相关性可以省去大量的求交运算。见下图(b)所示。(a)扫描线的相关性扫描线的相关性(b)边的相关性边的相关性多边形的填充多边形的填充扫描线算法扫描线算法第

17、25页，共41页，编辑于2022年，星期六数据结构数据结构边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。边表（边表（ET：Edge Table）用来对除水平边外的所有边进行登记，来建立边的记录。边的记录定义为：第一项：某边的最大y值（ymax）。注意要进行奇异点处理：对于非极值点应该ymax=ymax-1。第二项：某边的最小的y对应的x值。第三项：某边斜率的倒数:1/m。第四项：指针。用来指向同一条扫描线相交的其它边，如果其它边不存在，则该项置空多边形的填充多边形的填充扫描线算法扫描线算法第26页，共41页，编辑于2022年，星期六数据结构数据结构活动边表（活动边

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

19、ax，或ET表与AET表都为空为止：如果ET表中yj桶非空，则将yj桶中的全部记录合并到AET表中。对AET表链中的记录按x的大小从小到大排序。依次取出AET表各记录中的xi坐标值，两两配对填充，即将每对xi之间的象素填上所要求的颜色。如果AET表中某记录的ymax=yj，则删除该记录。对于仍留在AET表中的每个记录，用xi+1/m代替xi进行修改，这就是该记录的边线与下一条扫描线yj+1的交点。使yj加1，以便进入下一轮循环。多边形的填充多边形的填充扫描线算法扫描线算法第28页，共41页，编辑于2022年，星期六算法实现：算法实现：对多边形P的每一非水平边（i=0,1,n）上的各像素做向右求

20、反运算即可，见下图，其中(a)为给定的多边形；(b)为对区域赋初值；(c)，(d)，(e)和(f)表示逐边向右求反。多边形的填充多边形的填充边缘填充算法边缘填充算法第29页，共41页，编辑于2022年，星期六基本原理：基本原理：首先用一种特殊的颜色特殊的颜色在帧缓冲器中将多边形的边界（水平边的部分边界除外）勾画出来。然后再把位于多边形内的各个像素着上所需的颜色 步骤1：以值为boundary-color 的特殊颜色勾画多边形的边界。设多边形顶点为Pi=(xi,yi),0in，xi,yi均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。步骤2：设inter

21、ior_point 是一布尔变量。对每一条扫描线从左到右进行搜索，如果当前是像素位于多边形内，则interior_point=true，需要填上值为polygon_color的颜色；否则该像素在多边形外，需要填上值background_color的颜色 多边形的填充多边形的填充边界标志算法边界标志算法第30页，共41页，编辑于2022年，星期六3.5.1 3.5.1 区域的基本概念区域的基本概念 区域是指已经表示成点阵形式的像素集合在光栅图形中，区域可采用内点表示和边界表示两种形式进行描述。区域填充是指先将区域内的一点(常称种子点)赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。第31页，

22、共41页，编辑于2022年，星期六区域填充的基本概念区域填充的基本概念内点表示法：把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。边界表示法：把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。图3.25内点表示的区域图3.26边界表示的区域第32页，共41页，编辑于2022年，星期六区域填充的基本概念区域填充的基本概念 4连通的区域:取区域内任意两点，在该区域内若从其中一点出发通过上、下、左、右四种运动可到达另一点。图3.27四个方向的运动8连通区域:取区域内任意两点，若从其中任一点出发，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点。图3.28个方

23、向的运动第33页，共41页，编辑于2022年，星期六区域填充的基本概念区域填充的基本概念4连通区域也可理解成8连通区域，但是两者的边界不尽相同。如果图中标有号的象素组成的区域作为4连通区域，则其边界由图中的标有号的象素组成。如果将该区域作为8连通的区域，则其边界由图中标有号和号的两种象素组成。图3.29内点表示的八连通区域图3.30边界表示的八连通区域图3.31四连通区域与八连通区域的不同边界第34页，共41页，编辑于2022年，星期六3.5.2 3.5.2 简单的种子填充算法简单的种子填充算法基本思想：给定区域G一种子点（x,y）首先判断该点是否是区域内的一点，如果是，则将该点填充为新的颜色

24、，然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充 第35页，共41页，编辑于2022年，星期六3.5.3 3.5.3 扫描线种子填充算法扫描线种子填充算法基本思想：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来。反复进行这个过程，直到所保存的各区段都填充完毕第36页，共41页，编辑于2022年，星期六扫描线种子填充算法扫描线种子填充算法算法步骤：步骤步骤 1：将算法设置的堆栈置为空。将给定的种子点（x,y）压入堆栈。步骤步骤 2：如果堆栈为空，算法结束

25、；否则取栈顶元素（x,y）作为种子点。步骤步骤 3：从种子点（x,y）开始，沿纵坐标为y的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充，直到边界为止。设区间两边界的横坐标分别为xleft 和xright。步步骤骤4 4：在与当前扫描线相邻的上下两条扫描线上，以区间xleft,xright为搜索范围，求出需要填充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到步骤2。第37页，共41页，编辑于2022年，星期六扫描线种子填充算法扫描线种子填充算法执行过程图3.32扫描线种子填充算法的执行过程121212123第38页，共41页，编辑于2022年，星期六3.6.1 光栅图形的走

26、样现象光栅图形的走样现象 图形的边界一般都呈阶梯形 图形的细节失真、狭小图形遗失（a）待显示的细小图形（b）显示结果图3.35 细节失真（a）待显示的狭小矩形（b）显示结果图3.36 狭小图形的遗失狭小图形遗失和运动图形的闪光现象 图3.33阶梯形边界图图3.34阶梯形线段第39页，共41页，编辑于2022年，星期六3.6.2 3.6.2 提高分辨率的反走样方法提高分辨率的反走样方法提高分辨率的方法采用硬件:采用高分辨率的光栅图形显示器，花费的代价大。采用软件:花费的代价小，也容易实现。用软件提高分辨率的方法是：高分辨率计算，低分辨率显示。高分辨率计算：将低分辨的图形显示象素划分为许多子象素，

27、如22划分，33划分等，然后按通常的算法计算出各个子象素的颜色值或灰度值。低分辨率显示：将一象素内的各个子象素的颜色值或灰度值的平均值作为该象素的颜色值或灰度值。求平均值时可取算术平均，也可取加权平均。图3.37 加权表第40页，共41页，编辑于2022年，星期六3.6.33.6.3线段反混淆线段反混淆/走样算法走样算法 用反混淆算法显示的线段称为反混淆/走样线段。反混淆线段是将位于原相邻阶梯之间的象素置为过渡颜色或灰度，使得颜色或者灰度过渡自然，变化柔和，阶梯被淡化后，线形就显得平直了。反混淆算法极大地改善了显示时线段的线形质量。由于要计算面积，使得计算量大大增加，速度也由此而减慢，所以它不适合于动态的交互式图形显示。图3.38 有宽度的线段第41页，共41页，编辑于2022年，星期六