计算机图形学完整.pptx

第一章、绪论1.1、概述1.2、计算机图形学的发展1.3、计算机图形学的应用1.4、计算机图形系统1.5、计算机图形标准第1页/共326页1.1 概述计算机图形学的概念 计算机图形学Computer Graphics 是一门新兴学科，国际标准化组织ISO定义为:计算机图形学是一门研究通过计算机将数据转换成图形，并在专门显示设备上显示的原理方法和技术的学科。它是建立在传统的图学理论，应用数学及计算机科学基础上的一门边缘学科。第2页/共326页计算机图形学的研究内容 1.基于图形设备的基本图形元素的生成算法。2.图形元素的几何变换。3.自由曲线和曲线的插值、拟合、拼接、分解、过渡、光顺、整体和局部修改等。4.三维几何造型技术。5.三维形体的实时显示。6.真实感图形的生成算法。7.山、水、花、草、烟云等模糊景物的模拟生成和虚拟现实环境的生成。8.科学计算可视化和三维或高维数据场的可视化。第3页/共326页计算机图形学与图象处理的关系 计算机图形学的基本含义是使用计算机通过算法和程序在显示设备上构造出图形来。也就是说，图形是人们通过计算机设计和构造出来的，不是通过摄象机和扫描仪等设备输入的图象。所设计和构造的图形可以是现实世界已经存在的物体的图形，也可以显示完全虚构的物体。因此，计算机图形学是真实的物体或虚构物体图形的综合技术。第4页/共326页 与此相反，图象处理是景物或图象的分析技术，它所研究的是计算机图与此相反，图象处理是景物或图象的分析技术，它所研究的是计算机图形学的逆过程，图象增加、模式识别、景物分析、计算机视觉等，并研究如形学的逆过程，图象增加、模式识别、景物分析、计算机视觉等，并研究如何从图象中提取二维或三维物体的模型。何从图象中提取二维或三维物体的模型。第5页/共326页 尽管计算机图形学和图象处理所涉及的都是用计算机来处理图形和图尽管计算机图形学和图象处理所涉及的都是用计算机来处理图形和图象，但是长期以来却属于不同的两个技术领域。近年来，由于多媒体技术、象，但是长期以来却属于不同的两个技术领域。近年来，由于多媒体技术、计算机动画、三维空间数据场显示及纹理映射等的迅速发展，计算机图形计算机动画、三维空间数据场显示及纹理映射等的迅速发展，计算机图形学和图象处理的结合日益紧密，并相互渗透。学和图象处理的结合日益紧密，并相互渗透。第6页/共326页1.2 计算机图形学的发展计算机图形学的发展简史年代准备阶段年代发展阶段年代推广应用阶段年代系统实用化阶段年代标准化智能化阶段第7页/共326页计算机图形学的发展方向 造型技术的发展 真实图形生成技术的发展 人机交互技术的发展 模拟艺术的仿真 计算机动画第8页/共326页1.3 计算机图形学的应用1.用户接口2.计算机辅助设计与制造（CAD/CAM）3.地形地貌和自然资源图4.计算机动画和艺术5.科学计算可视化6.游戏第9页/共326页1.4 计算机图形系统 计算机图形系统硬件 计算机图形系统软件 计算机图形显示原理 光栅扫描式图形显示器第10页/共326页1.5 计算机图形标准GKS PHIGS CGM CGI第11页/共326页第二章、基本图形生成原理2.1 直线的生成2.2 圆与椭圆的生成第12页/共326页2.1 直线的生成数值微分法(DDA法)中点画线法画线算法图形函数介绍第13页/共326页数值微分法:直线方程 y=kx+b 给出线段的两个端点 (x1,y 1)和(x2,y2)可以算出k和b k=y/x=(y2-y1)/(x2-x1)b=y1-kx1再用setpixel(x,int(y0.5),color)输出该系统的颜色值便可画出直线.但是画线效率太低,这是因为每步都需浮点乘法运算和一个四舍五入.第14页/共326页数值微分算法的描述 对任何沿直线给定的x的增量x,可以从下中计算出y的增量 y=kx 同样可以得出对应于指定的 x=y/k 当对于斜率的绝对值|k|1的线段怎么实现呢?算法演示第15页/共326页中点画线法 那么，下一个与直线最近的像素只能是正右方那么，下一个与直线最近的像素只能是正右方的的p1(p1(，)或右上方或右上方 p2p2（，）用空心小圆表示。再以用空心小圆表示。再以MM表示表示P1P1与与p2p2的中点，的中点，即即M=M=（，）。又设）。又设Q Q是理想直线与是理想直线与垂线垂线 交点。显然，若交点。显然，若MM在在Q Q的下方，的下方，则则p2p2离直线近，应取为下一个像素；否则应取离直线近，应取为下一个像素；否则应取p1p1。这就是中点画线法的基本原理。这就是中点画线法的基本原理。为了讨论方便，这里假定直线斜率在为了讨论方便，这里假定直线斜率在0-10-1之之间，其它两种情况可参照下述讨论进行相应间，其它两种情况可参照下述讨论进行相应处理。处理。如图所示，若直线在如图所示，若直线在x x方向增加一个单位，方向增加一个单位，则在则在y y方向的增量只能在方向的增量只能在0-10-1之间。假设直线之间。假设直线上当前已确定的一个像素点坐标为（上当前已确定的一个像素点坐标为（x xp p，y yp p），用实心小圆表示。），用实心小圆表示。P=(xp,yp)G第16页/共326页算法推导：下面我们来讨论中点画线算法的实现。假设直线的起点和终点分别为（x1,y1）和（x2,y2）则直线方程为 F(x,y)=ax+by+c=0 第17页/共326页 其中，a=y1-y2，b=x2-x1,c=x1y2-x2y1。对于直线上的点F(x,y)=0;对于直线上方的点F(x,y)0;对于直线下方的点F(x,y)0。因此，欲判前述Q在M的上方还是下方，只要把M代入F(x,y),并判断它的符号。构造判别式 d=F(M)=F(,)=a()+b()+c第18页/共326页当d0,则应取正右方的p1。当d=0是，二者一样合适，可以随便取一个。第19页/共326页 我们约定取正右方的p1。对每一个象素计算判别式d，根据它的符号确定下一象素。由于d是xp和yp的线性函数，可采用增量计算，以便提高运算效率。第20页/共326页 在在d0d0的情况下，取正右方的象素的情况下，取正右方的象素p1p1，欲判断再下一个象素应取哪个，应计算，欲判断再下一个象素应取哪个，应计算d1=F(+2,+0.5)d1=F(+2,+0.5)=a(+2)+b(+0.5)+c =a(+2)+b(+0.5)+c =(a(+1)+b(+0.5)+c)+a =(a(+1)+b(+0.5)+c)+a =d+a =d+a故故d d的增量为的增量为a a。第21页/共326页而若而若d0d0，则取右上方象素，则取右上方象素p2p2。要判断再下一个象素，则要计算。要判断再下一个象素，则要计算d2=F(+2,+1.5)d2=F(+2,+1.5)=a(+2)+b(+1.5)+c =a(+2)+b(+1.5)+c =(a(+1)+b(+0.5)+c)+a+b =(a(+1)+b(+0.5)+c)+a+b =d+a+b =d+a+b故在第二种情况，故在第二种情况，d d的增量为的增量为a ab b。第22页/共326页 再看再看d d的初始值。显然，第一个象素应取左端点（的初始值。显然，第一个象素应取左端点（x1x1，y1y1），相应的判别式值为），相应的判别式值为d d0 0=F(+1,+0.5)=F(+1,+0.5)=a(+1)+b(+0.5)+c =a(+1)+b(+0.5)+c =(a =(a x1+bx1+b y1+c)+a+0.5y1+c)+a+0.5 b b =F(x1,y1)+a+0.5 =F(x1,y1)+a+0.5 b b但由于（但由于（x1,y1x1,y1）在直线上，故）在直线上，故F(x1,y1)=0F(x1,y1)=0。因此因此d d的初始值为的初始值为d0=a+0.5d0=a+0.5 b b第23页/共326页 由于我们使用的只是由于我们使用的只是d d的符号，而且的符号，而且d d的增量都是整数，只是其的增量都是整数，只是其初始值包含小数。因此，我们可以用初始值包含小数。因此，我们可以用2d2d代替代替d d，来摆脱小数，写出仅，来摆脱小数，写出仅包含整数运算的算法：包含整数运算的算法：第24页/共326页void MidpointLine(x1,y1,x2,y2,color)void MidpointLine(x1,y1,x2,y2,color)int x1,y1,x2,y2,color;int x1,y1,x2,y2,color;int a,b,d1,d2,dx,y;int a,b,d1,d2,dx,y;a=y1-y2;a=y1-y2;b=x2-x1;b=x2-x1;d=2*a+b;d=2*a+b;d1=2*a;d1=2*a;d2=2*(a+b);d2=2*(a+b);x=x1;x=x1;y=y1;y=y1;setpixel(x,y,color);setpixel(x,y,color);while(xx2)while(xx2)If(d0)If(d0)x+;y+d+=d2;x+;y+d+=d2;elseelsex+;d+=d1;x+;d+=d1;setpixel(x,y,color);setpixel(x,y,color);第25页/共326页画线算法算法分析第26页/共326页算法推导第27页/共326页可视化效果图第28页/共326页图形环境的设置#include”graphics.h”图形方式初始化函数：initgraph(*gdriver,*gmode,*path);gdriver:是一个空型指针，用来指定要装入的图形驱动程序，该值在头文件中定义；gmode:是一个空型指针，用来指定显示模式path:图形驱动程序所在的路径第29页/共326页若用VGA图形驱动程序,图形显示模式为VGAHI,则调用方式如下:int gdriver,gmode;gdriver=VGA gmode=VGAHI initgraph(&gdriver,&gmode,”c:TC”);关闭图形方式函数为 closegraph()第30页/共326页直线类绘图函数 line(x1,y1,x2,y2);lineto(x,y);moveto(x,y);line(dx,dy);几个直线段组成的图形图一图二第31页/共326页2.2 圆与椭圆的生成 由于圆是图形和图像中经常使用的元素，因此在大多数图形软件中都包含有生成圆和圆弧的过程。也会提供一个既能显示圆曲线，又能显示椭圆曲线的绘图函数。圆的特性 圆被定义为所有离一中心位置（xc ,yc）距离为给定值r的点集，可用如下方程式表示：(x-xc)2+(y-yc)2=r2第32页/共326页 利用这个方程，我们可以沿x轴从xc-r到xc+r以单位步长计算对应的y值来得到圆周上每点的位置：y=yc (r2-(xc-x)2)但这并非是生成圆的最好方法。这个方法的第一个问题是每一步包含很大的计算量。第33页/共326页 第二个问题是所画像素位置间的间距是不一样的，在靠近x轴的0o180o处像素点之间的间距越来越大。当然可以在圆斜率的绝对值大于1后，交换x和y（即步进y值，计算x 值）来调整间距。但这样增加了算法所需的计算量和处理过程。第34页/共326页 另一种消除不等间距的方法是使用极坐标另一种消除不等间距的方法是使用极坐标r r和和 来计算沿圆周的点。来计算沿圆周的点。以参数极坐标形式表示圆方程可得到方程组：以参数极坐标形式表示圆方程可得到方程组：x=xc+r cosy=yc+r sin第35页/共326页 使用上述方法以固定角度为步长生成显示时，圆就可沿圆周等距点绘制出来。但这个方法使用了三角函数调用和浮点运算，运算速度太慢。必须寻找只需做一些简单的 整数运算和判别运算的方法即可确定圆上的象素点的算法。第36页/共326页考虑到圆的对称性可考虑到圆的对称性可以减少计算量。只要以减少计算量。只要能生成能生成8 8分圆，那么圆分圆，那么圆的其它部分可以通过的其它部分可以通过一系列的简单映射变一系列的简单映射变换得到。如图所示，换得到。如图所示，假设已知一个圆心在假设已知一个圆心在原点的圆上一点原点的圆上一点(x(x，y)y)，第37页/共326页 根据对称性可得另外七个根据对称性可得另外七个8 8分圆上的对应点分圆上的对应点 (y,x)(y,x)，(y,-x)(y,-x)，(x,-y)(x,-y)，(-x,-y)(-x,-y)，(-y,-x)(-y,-x)，(-y,x)(-y,x)，(-x,y)(-x,y)。因此，只需讨论因此，只需讨论8 8分圆的生成算法。分圆的生成算法。第38页/共326页 另外，为了方便起见，我们只考虑中心在原点，半径为整数R的圆x2+y2=R2。对于中心不在原点的圆，可先通过平移变换，化为中心在原点的圆，再进行扫描转换，把所得的像素坐标加上一个位移量即得所求像素坐标。第39页/共326页中点画圆法 考虑中心在原点，半径为R的圆的第二8分圆。我们来讨论如何从（0，R）到（R/），（R/）顺时针的确定最佳逼近于该圆弧的像素序列。第40页/共326页假定当前已确定了一个象素点为假定当前已确定了一个象素点为 p(xp(xp p,y,yp p)那么那么 下一个象素只能是正右方的下一个象素只能是正右方的p1(xp1(xp p+1,y+1,yp p)或右下方的或右下方的p2(xp2(xp p+1,y+1,yp p-1)-1)。p1P=(x,y)xp xp+1 xp+2ypyp-1yp-2p2M第41页/共326页如图所示，构造函数：如图所示，构造函数：F(x,y)=xF(x,y)=x2 2+y+y2 2-R-R2 2对于圆上的点，对于圆上的点，F(x,y)=0;F(x,y)=0;对于圆外的点，对于圆外的点，F(x,y)F(x,y)0;0;而对于圆内的点而对于圆内的点F(x,y)F(x,y)0.0.假设假设MM是是P1P1和和P2P2的中点，的中点，即即MM（x xp p+1,y+1,yp p-0.5-0.5）P=(x,y)xp xp+1 xp+2p2Mypyp-1yp-2p1第42页/共326页那么那么当当F(M)0F(M)0F(M)0时，时，p2p2离圆弧更近，应取离圆弧更近，应取p2p2。当当F(M)=0F(M)=0时，在时，在p1p1与与p2p2之中随便取一个即之中随便取一个即可，我们约定取可，我们约定取p2p2P=(x,y)xp xp+1 xp+2p2Mypyp-1yp-2p1第43页/共326页与中点画线法一样，构造判别式与中点画线法一样，构造判别式 d=F(M)d=F(M)=F(x =F(xp p+1,y+1,yp p-0.5)-0.5)=(x =(xp p+1)+1)2 2+(y+(yp p-0.5)-0.5)2 2-R-R2 2当当d0d0，则应取，则应取p1p1为下一象素，而且再下一个为下一象素，而且再下一个象素的判别式为象素的判别式为 d=F(xd=F(xp p+2,y+2,yp p-0.5)-0.5)=(x =(xp p+2)2+(y+2)2+(yp p-0.5)-0.5)2 2-R-R2 2 =d+2x =d+2xp p+3+3p1P=(x,y)xp xp+1 xp+2p2Mypyp-1yp-2第44页/共326页所以，沿正右方，所以，沿正右方，d d的增量为的增量为2x2xp p+3+3。而若而若d0d0，则，则p2p2是下一象素，而且下一象素的是下一象素，而且下一象素的判别式为判别式为:d=F(x d=F(xp p+2,y+2,yp p-1.5)-1.5)=(x =(xp p+2)+2)2 2+(y+(yp p-1.5)-1.5)2 2-R-R2 2 =d+(2x =d+(2xp p+3)+(-2y+3)+(-2yp p+2)+2)=d+2(xp-yp)+5P=(x,y)xp xp+1 xp+2p2Mypyp-1yp-2p1第45页/共326页所以，沿右下方向判别式所以，沿右下方向判别式 d d的增量为的增量为2(x2(xp p-y-yp p)+5)+5。由于我们这里讨论的是用顺时针方向生成第二个由于我们这里讨论的是用顺时针方向生成第二个8 8分圆，因此第一个象素分圆，因此第一个象素点是点是(0,R)(0,R)判别式判别式d d的初值为：的初值为：d d0 0=F(1,R-0.5)=F(1,R-0.5)=1+(R-0.5)=1+(R-0.5)2 2-R-R2 2 =1.25-R =1.25-R第46页/共326页 由于使用了浮点数来表示判别式由于使用了浮点数来表示判别式d d，为了简化运算，摆脱浮点数，在，为了简化运算，摆脱浮点数，在算法中全部使用整数，我们使用算法中全部使用整数，我们使用e=d-0.25e=d-0.25代替代替d d。显然，初始化运算。显然，初始化运算d=1.25-rd=1.25-r对应于对应于e=1-re=1-r。判别式。判别式d0d0对应于对应于e-0.25e-0.25。第47页/共326页 算法中其它与算法中其它与d d有关的式子可把有关的式子可把d d直接换成直接换成e e。又由于。又由于d d的初值为整数，且的初值为整数，且在运算过程中的增量也是整数，故在运算过程中的增量也是整数，故e e始终是整数，所以始终是整数，所以e-0.25e-0.25等价于等价于e0e0）。讨论：若a=d=1，为恒等变换，即变换后点的坐标不变。若a=d1，则为等比变换，变换结果是图形等比例放大（a=d1）后等比例缩小（a=d0c0时沿时沿+x+x向错切；向错切；c0c0b0时，沿时，沿+y+y方向错切；方向错切；b0b0n0），以使其与正投影面处于同一平面，使水平投影图和正面投影图拉开一个距），以使其与正投影面处于同一平面，使水平投影图和正面投影图拉开一个距离离，变换过程为：第114页/共326页 变换结果为（x，y，z，1）*Th=（x，0，-y-d3，1）=（x，y，z，1）第115页/共326页 设立体图的点集矩阵为（Dj），各投影图之间的距离为10，求立体的三面投影。已知：21356789104yxz第116页/共326页解：1）正面投影第117页/共326页(2)水平投影 第118页/共326页(3)侧面投影 第119页/共326页用变换后的 ，画出的三视图如下图xz第120页/共326页正轴测投影图 轴测图是一种简单的立体图形轴测图是一种简单的立体图形,能给人一种直观的形象能给人一种直观的形象,以帮助建立空间的概以帮助建立空间的概念念.由于它的绘制方法比较简单由于它的绘制方法比较简单,所以在工程制图中经常用到所以在工程制图中经常用到.1.1.正轴测投影图的形成过程是这样的正轴测投影图的形成过程是这样的:先将空间一立体绕先将空间一立体绕z z轴正向旋转轴正向旋转角角,然后然后再绕再绕x x轴反向旋转轴反向旋转角角,最后让经过两次旋转后的立体向正立投影面做正投影。最后让经过两次旋转后的立体向正立投影面做正投影。第121页/共326页整个形成过程可以用矩阵表示为式子中，和均取大于0的值。第122页/共326页 上面的矩阵上面的矩阵T T是经过是经过 3 3个单步简单矩阵变换的级联形成的，它是一个正轴个单步简单矩阵变换的级联形成的，它是一个正轴测投影交换矩阵的一般形式。因此，只要任意给定一组测投影交换矩阵的一般形式。因此，只要任意给定一组 和和角，代入矩阵角，代入矩阵T T，就可以产生一种正轴测投影矩阵，由此，可用以生成正轴测投影图。，就可以产生一种正轴测投影矩阵，由此，可用以生成正轴测投影图。第123页/共326页在正轴测变换过程中：在正轴测变换过程中：x x y y z z 1=x y z 1 T1=x y z 1 T=xcos-ysin 0 -sin(xsin+ycos)+zcos 1=xcos-ysin 0 -sin(xsin+ycos)+zcos 1从上式可以看到，交换的结果使从上式可以看到，交换的结果使y y坐标为坐标为0 0，所以对于一般的二维坐标系来说，所以对于一般的二维坐标系来说，y y坐标就坐标就相应于现在的相应于现在的z z坐标。坐标。第124页/共326页2.2.正等测和正二测正等测和正二测 正等轴测投影图和正二等轴测投影图是正轴测投影图中常用的两种，其中正等轴测投影图和正二等轴测投影图是正轴测投影图中常用的两种，其中正等测用手工绘制方法简便；正二测的立体感较好，但手工绘制方法没有正等正等测用手工绘制方法简便；正二测的立体感较好，但手工绘制方法没有正等测方便。当用计算机来生成的时候，就不存在方法上的差别，区别只是变换矩测方便。当用计算机来生成的时候，就不存在方法上的差别，区别只是变换矩阵中的元素值不同而已。阵中的元素值不同而已。第125页/共326页（1 1）正等测的变换矩阵）正等测的变换矩阵任一组任一组 和和的角，可以产生一种正轴测投影变换矩阵。当取的角，可以产生一种正轴测投影变换矩阵。当取=45=45o o，=35=35o o1616时，时，代入矩阵代入矩阵T T，就可以得到正等轴测投影的变换矩阵，就可以得到正等轴测投影的变换矩阵T T。第126页/共326页（2）正二测的变换矩阵 形成正二等轴测投影的一组角度形成正二等轴测投影的一组角度 和和的取值为：的取值为：=20=20o o 4242；=19=19o o 2828。将此。将此 和和的值代入正轴测矩阵，便可得到正二测的变换矩阵的值代入正轴测矩阵，便可得到正二测的变换矩阵。第127页/共326页3.轴测图的编程步骤下面，我们通过一个简单的立体例子，来说明设计和编写绘制轴测图的绘图程序的步下面，我们通过一个简单的立体例子，来说明设计和编写绘制轴测图的绘图程序的步骤。设所需绘制的立体如下图骤。设所需绘制的立体如下图则工作步骤如下：则工作步骤如下：在草纸上绘制出草图，并确定各顶点的序号和相应顶点的坐标值，建立顶在草纸上绘制出草图，并确定各顶点的序号和相应顶点的坐标值，建立顶点表和边表，如下二个表。点表和边表，如下二个表。123456789101112zyx第128页/共326页 顶点表顶点号 x y z 1 0 0 0 2 0 0 200 3 200 0 200 4 0 50 40 5 0 50 40 6 0 50 200 7 200 50 200 8 200 50 40 9 200 150 40 10 0 150 0 11 0 150 0 12 200 150 0边号 连边顶点 1 1 2 2 2 3 3 3 4 4 4 1 5 1 11 6 11 12 7 12 4 8 5 6 9 6 7 10 7 8 11 8 5 12 5 10 13 10 9 14 9 8 15 9 12 16 10 11 17 3 7 18 2 6 第129页/共326页 在程序中定义两个数组，用于定义顶点表和连边表。通过数组的初始化给两个数组赋初值。实施对立体进行正轴测投影变换，即用正轴测投影变换矩阵顶点表实现。这样，可以得到一个变换后的新的顶点表。第130页/共326页 用新顶点表的顶点坐标值，注意此时只有x坐标轴和z坐标轴，y坐标轴已在投影中消掉，所以是以x坐标为绘图的x坐标，以z坐标为绘图的y 坐标。按连边表中的连边规则，用line函数在顶点之间两两连线。第131页/共326页在绘图程序中要注意两点：在绘图程序中要注意两点：在建立立体坐标时，为了取顶点坐标值简便，我们把立体的一个顶点放置在坐标在建立立体坐标时，为了取顶点坐标值简便，我们把立体的一个顶点放置在坐标的原点，所以，整个轴测投影变换后的图形是以该原点为中心。但图形输出时的中心应的原点，所以，整个轴测投影变换后的图形是以该原点为中心。但图形输出时的中心应以屏幕中心为宜，比如，对于以屏幕中心为宜，比如，对于VGAVGA来说，这个中央点在（来说，这个中央点在（320320，240240）处。）处。该绘图程序目前只能按连边表把立体的所有棱边都画出来，而不考虑是否可见，该绘图程序目前只能按连边表把立体的所有棱边都画出来，而不考虑是否可见，即没有经过消除隐藏线处理。即没有经过消除隐藏线处理。第132页/共326页四.透视投影图1.透视变换矩阵在前面讲的三维变换矩阵中，已经说过，所产生透视投影的效果。现在我们来具体讨论，当其中的p，q，r三个参数为非全0时，这样的变换矩阵会对变换产生什么样的影响。第133页/共326页（1）一点透视先设 q0，p=r=0。然后对点（x，y，z，1）进行变换，结果如下：对其结果进行齐次化处理，得：第134页/共326页当y取值不同时，上式会产生如下不同的结果：当y=0时，得：而原来处于y=0的平面内的点，经过变换以后没有变化。当y 时，得：第135页/共326页这说明，当y 时，所有的点的变换结果都集中到了y轴上的1/q处。即所有平行与y轴的直线最终延伸将相交（0，1/q，0）的点，该点称为“灭点”。而象这样形成的一个灭点的透视变换称为“一点透视”。为了取得较好的效果，我们取q0，让灭点位于y轴的负半轴上。一点透视的效果如下zyx第136页/共326页根据同样的道理，当p0，q=r=0时，则将含在x轴上的1/q处产生一个灭点，其坐标值为（1/q，0，0）。在这种情况下，所有平行于x轴的直线将延伸交于该点。当r 0，p=q=0时，产生的一个灭点位于z轴上的1/r处，灭点的坐标为（0，0，1/r）。所有平行与这轴的直线将延伸交于该点。第137页/共326页（2）多点透视根据一点透视的原理予以推广，如果在p，q，r三个元素中有两个为非零元素时，这将会产生两个灭点，因此得到两点透视。经过齐次处理结果为：第138页/共326页从以上结果可以得到：当x 时，一个灭点在x轴上的1/p处。当z 时，另一个灭点在z轴上的1/r处。这时，立体上所有平行于x轴的棱线，延伸时将相交于x轴上点（0，0，1/r）处。同理，当p，q，r三个元素全为零时，结果将会产生三个灭点，从而形成三点透视。产生的三个灭点分别在x轴上的1/p处，y轴上的1/q处和z轴的1/r处。第139页/共326页2.2.生成透视投影图的方法生成透视投影图的方法生成透视投影图的过程分为两步：先是对立体进行透视变换；生成透视投影图的过程分为两步：先是对立体进行透视变换；然后是将其投影到正面投影面上，然后是将其投影到正面投影面上，形成投影面上，形成正投影图。用矩形成投影面上，形成正投影图。用矩阵形式表示为：阵形式表示为：第140页/共326页（1）一点透视图的生成 在生成一点透视图时，为了避免把图所属立体安置在坐标系的原点而产生如下图所示的透视效果zxoxzo第141页/共326页通常是在进行透视投影变换前，先将立体平移到一个合适的位置，然后再进行透视投影变换，使得产生的透视图效果较好。生成一点透视投影的变换矩阵为:第142页/共326页当d1，d2，d3和q取确定的非零值后，该矩阵中包含的三个透视变换参数中有一个为非零，所以该变换矩阵能产生一点透视图。在q的取值时，一般取-1q0）；c.进行透视变换；d.往正投影面进行正投影。第145页/共326页用矩阵的形式表示这个变换过程为：从以上的变换矩阵T可以看到，矩阵中的三个透视变换参数均非0，因此可以变换生成三点透视图。第146页/共326页第四章、多边形及多边形填充算法 在这一节中将讨论图形系统中的新图元多边形，研究有关多边形的概念以及如何表示多边形，学习如何判断一个点是否在多边形内的方法，以及多边形填充的各种方法。第147页/共326页一、多边形的概念 所谓多边形，就是用一系列首尾相连的线段构成图形。这些组成多边形边界的线段称为多边形的边，多边形的边的端点称为多边形的顶点。一般来说，一个多边形应是封闭的。第148页/共326页1.凸多边形与凹多边形 多边形又分为两大类：凸多边形与凹多边形。所谓凸多边形，是指这样一类多边形：如果在多边形内任找两个点，将这两个点用线段连接后，此线段上所有的点都在多边形内，这就是凸多边形。而凹多边形就是非凸多边形。第149页/共326页 下面给出了凸多边形与凹多边形的例子，可见，三角形总是凸多边形。凸多边形凹多边形第150页/共326页2.多边形的描述 考虑到多边形的特征属性：顶点和边，在描述多边形时，既要指明组成多边形的顶点，又要指出组成多边形的边。一般来说，用顶点的序列来表示多边形，其中的边即指两顶点所构成的线段，这样来表示的多边形如下：p1p2p3p4p5p6p7第151页/共326页 图中多边形顶点序列为p1 p2 p3 p4 p5 p6 p7。可以根据这种方法写出在计算机上绘制多边形的算法：draw_polygon(int N,int pN2)if(N=2)return();else for(i=1;iN;i+)line(pi0,p i1,pi+10,pi+11);line(p10,p11,pN0,pN1);第152页/共326页二多边形的填充1.点是否在内部的检验p1p2p4p3p5第153页/共326页s1p1s2p2p3s5S3(s4)第154页/共326页Pi+1piPi-1Yi+1YiYi-1第155页/共326页Pi+1piPi-1Yi+1YiYi-1第156页/共326页2连贯性原理p2p1p3p4p5p6p7p8p9x2x1x3x4x5x6 梯形的两底边分别在y=yk和y=yk+1两条扫描线上，腰在多边形p的边上或在显示屏幕的边界上。区域的连贯性区域的连贯性Yk+1yk第157页/共326页 这些梯形分为两类：一类位于多边形内部（图中粉色部分），另一类位多这些梯形分为两类：一类位于多边形内部（图中粉色部分），另一类位多边形外部。边形外部。两类梯形在长方形区域上相间排列，即相邻的两个梯形必有一个在多边形两类梯形在长方形区域上相间排列，即相邻的两个梯形必有一个在多边形内，一个在多边形外。内，一个在多边形外。第158页/共326页 交点数为偶数；相邻交点间的线段也分为两类：一类线段上所有点均在多边形内部，另一类线段上所有点均在多边形外部；两类线段在扫描线上相间排列。扫描线的连贯性扫描线的连贯性 对于多边形与扫描线对于多边形与扫描线y=yy=yk k相交相交,交点序列交点序列 x1,x2,x3,x4,x5,x6 x1,x2,x3,x4,x5,x6 由连贯性可知由连贯性可知，此交点序列具有下列性质此交点序列具有下列性质第159页/共326页边的连贯性边的连贯性ABY Yi+1i+1Y Yi ixi xi+1第160页/共326页三、多边形填充算法1、扫描线算法76543210 1 2 3 4 5 6 7 8r1 r2 r3 r4r5 r6扫描线算法的步骤为：扫描线算法的步骤为：在在ELEL中找出非空元素的最小序号：中找出非空元素的最小序号：将边的活化链表置空；将边的活化链表置空；按从下至上的顺序分别处理每一条扫描线，按从下至上的顺序分别处理每一条扫描线，直到边的分类表直到边的分类表ELEL和边的活化链表均为空为和边的活化链表均为空为止。止。第161页/共326页处理扫描线步骤为：对于扫描线y=yc,若EL中非空，则将其所有的边从EL中取出，并且插入到边的活化链表中，并将AEL中各边按x递增顺序；若相对于当前扫描线，边的活化链表AEL非空，则将AEL中的边两两依次配对，即第1，2边为一对，第3，4边为一对，依次类推，每一对边与当前扫描线交点所构成的线段位于多边形内，依次将这些线段上的点进行着色；第162页/共326页 将边的活化链表中满足将边的活化链表中满足y=yy=ymaxmax的边删去；的边删去；将边的活化链表将边的活化链表AELAEL中剩下的每一条边的中剩下的每一条边的x x域累加域累加x x，即，即x=x+x=x+x x；将当前的扫描线的纵坐标将当前的扫描线的纵坐标y y累加累加1 1，即，即y=y+1y=y+1，重复执行重复执行第163页/共326页种子填充算法将种子象素压入栈；当栈非空时 a.从堆栈弹出一个象素；b.将该象素置成所要求的色彩值；c.检查当前每个象素邻接的四连接象素是否是边界色或已置成所要求的色彩值，若是则返回，否则将该象素压入堆栈后再回到。76543210 1 2 3 4 5 6 7 8第164页/共326页多边形填充函数1.drawpoly 1.drawpoly 画多边形画多边形 drawpolydrawpoly（n,*ptn,*pt）n n是多边形顶点数，是多边形顶点数，*ptpt是多边形顶点坐标数组名是多边形顶点坐标数组名2.fillpoly 2.fillpoly 画并填充一多边形画并填充一多边形 fillpoly(n,*pt)fillpoly(n,*pt)3.floodfill 3.floodfill 填充一个有界区域填充一个有界区域 floodfill(x,y,bcolor)x,yfloodfill(x,y,bcolor)x,y填充区域内的一点坐标，填充区域内的一点坐标，bcolorbcolor填该域边界颜色填该域边界颜色4.setfilllstyle(pallern,color)4.setfilllstyle(pallern,color)设置填充模式和颜色设置填充模式和颜色 第165页/共326页扫描线种子填充算法步骤1.1.从包含种子象素的栈中弹出种子象素从包含种子象素的栈中弹出种子象素2.2.沿着扫描线对种子象素左右象素进行填充，直到遇到边界象素为止，这样就将沿着扫描线对种子象素左右象素进行填充，直到遇到边界象素为止，这样就将种子所在的扫描线中元素填充；种子所在的扫描线中元素填充；第166页/共326页 3.3.区间内最左最右元素为区间内最左最右元素为xleft xleft、xrightxright。则在则在xleftxxrightxleftxxright中检查与当前扫描线相邻的上、下两条扫描线是否全为边界象素或中检查与当前扫描线相邻的上、下两条扫描线是否全为边界象素或正填充过的象素，若不是，则对于正填充过的象素，若不是，则对于xleftxxrightxleftxxright，把每一区间的最右象素作为种子压，把每一区间的最右象素作为种子压入堆栈中算法结束条件为栈空。此算法适用于边界定义的区域。入堆栈中算法结束条件为栈空。此算法适用于边界定义的区域。第167页/共326页0 1 2 3 4 5 6 7 8 9 1012345678910AcBDHGFES1SS2XY第168页/共326页区域填充算法扫描线填充算法扫描线填充算法种子填充算法种子填充算法边缘填充算法边缘填充算法4-4-连通边界填充算法连通边界填充算法4-4-连通边界填充算法连通边界填充算法(2)(2)8-8-连通边界填充算法连通边界填充算法8-8-连通泛填充算法连通泛填充算法第169页/共326页第五章 图案及动画程序设计 第一节、图案程序设计第二节、动画程序设计 第170页/共326页第一节 图案程序设计1.构造功能模块的原则（1）独立性 （3）开放性（2）抽象性 （4）继承性第171页/共326页2.正多边形子程序的设计（1）顶点定位的正凸多边形a.选择绘图参数对于一个任意的正多边形来说，如下图所示p1p2p3p4p0（x0，y0）第172页/共326页它所需要的定形参数为：边数n（n不能小于3）；边长a。定位参数为：定位顶点Po的坐标（x0，y0）起使边的倾角。给定了这两组参数，就可以唯一地确定一个任意位置、形状和大小的正多边形。但在绘图程序中，必须把这两组参数转化为具体的绘图用数据。第173页/共326页 根据图形中的几何关系，可以列出计算机正多变形各顶点坐标的算式。其中，=2/n。第174页/共326页b.编写汇编绘图程序根据以上的分析和数据的准备，下面便可以着手编写绘制任意正多边形的程序。图形程序见程序2_4。其中，函数polygon为绘制任意正多边形的通用绘图程序，函数中有5个形参。.X0，Y0 定位顶点坐标；.A 正多边形边长；.n 正多边形边数；.af 起始边与x轴正向的夹角。第175页/共326页第176页/共326页（2）以外接圆圆心