计算机图形学完整课件

计算机图形学,第一章、绪论第二章、基本图形生成原理第三章、图形几何变换第四章、多边形及多边形填充算法第五章、图案及动画程序设计第六章、裁剪算法第七章、自由曲线,第一章、绪论,1.1、概述1.2、计算机图形学的发展1.3、计算机图形学的应用1.4、计算机图形系统1.5、计算机图形标准,1.1概述,1.1.1计算机图形学的概念计算机图形学ComputerGraphics是一门新兴学科，国际标准化组织ISO定义为:计算机图形学是一门研究通过计算机将数据转换成图形，并在专门显示设备上显示的原理方法和技术的学科。它是建立在传统的图学理论，应用数学及计算机科学基础上的一门边缘学科。,1.1.2计算机图形学的研究内容,1.基于图形设备的基本图形元素的生成算法。2.图形元素的几何变换。3.自由曲线和曲线的插值、拟合、拼接、分解、过渡、光顺、整体和局部修改等。4.三维几何造型技术。5.三维形体的实时显示。6.真实感图形的生成算法。7.山、水、花、草、烟云等模糊景物的模拟生成和虚拟现实环境的生成。8.科学计算可视化和三维或高维数据场的可视化。,1.1.3计算机图形学与图象处理的关系,计算机图形学的基本含义是使用计算机通过算法和程序在显示设备上构造出图形来。也就是说，图形是人们通过计算机设计和构造出来的，不是通过摄象机和扫描仪等设备输入的图象。所设计和构造的图形可以是现实世界已经存在的物体的图形，也可以显示完全虚构的物体。因此，计算机图形学是真实的物体或虚构物体图形的综合技术。,与此相反，图象处理是景物或图象的分析技术，它所研究的是计算机图形学的逆过程，图象增加、模式识别、景物分析、计算机视觉等，并研究如何从图象中提取二维或三维物体的模型。,尽管计算机图形学和图象处理所涉及的都是用计算机来处理图形和图象，但是长期以来却属于不同的两个技术领域。近年来，由于多媒体技术、计算机动画、三维空间数据场显示及纹理映射等的迅速发展，计算机图形学和图象处理的结合日益紧密，并相互渗透。,1.2计算机图形学的发展,1.2.1计算机图形学的发展简史年代准备阶段年代发展阶段年代推广应用阶段年代系统实用化阶段年代标准化智能化阶段,1.2.2计算机图形学的发展方向造型技术的发展真实图形生成技术的发展人机交互技术的发展模拟艺术的仿真计算机动画,1.3计算机图形学的应用,1.用户接口2.计算机辅助设计与制造（CAD/CAM）3.地形地貌和自然资源图4.计算机动画和艺术5.科学计算可视化6.游戏,1.4计算机图形系统,计算机图形系统硬件计算机图形系统软件计算机图形显示原理光栅扫描式图形显示器,1.5计算机图形标准,GKSPHIGSCGMCGI,第二章、基本图形生成原理,2.1直线的生成2.2圆与椭圆的生成,2.1直线的生成,2.1.1数值微分法(DDA法)2.1.2中点画线法2.1.3Bresenham画线算法2.1.4Turboc2.0图形函数介绍,2.1.1数值微分法:直线方程y=kx+b给出线段的两个端点(x1,y1)和(x2,y2)可以算出k和bk=y/x=(y2-y1)/(x2-x1)b=y1-kx1再用setpixel(x,int(y0.5),color)输出该系统的颜色值便可画出直线.但是画线效率太低,这是因为每步都需浮点乘法运算和一个四舍五入.,数值微分算法的描述对任何沿直线给定的x的增量x,可以从下中计算出y的增量y=kx同样可以得出对应于指定的x=y/k当对于斜率的绝对值|k|1的线段怎么实现呢?,算法演示,2.1.2中点画线法,那么，下一个与直线最近的像素只能是正右方的p1(，)或右上方p2（，）用空心小圆表示。再以M表示P1与p2的中点，即M=（，）。又设Q是理想直线与垂线交点。显然，若M在Q的下方，则p2离直线近，应取为下一个像素；否则应取p1。这就是中点画线法的基本原理。,为了讨论方便，这里假定直线斜率在0-1之间，其它两种情况可参照下述讨论进行相应处理。如图所示，若直线在x方向增加一个单位，则在y方向的增量只能在0-1之间。假设直线上当前已确定的一个像素点坐标为（xp，yp），用实心小圆表示。,G,算法推导：下面我们来讨论中点画线算法的实现。假设直线的起点和终点分别为（x1,y1）和（x2,y2）则直线方程为F(x,y)=ax+by+c=0,其中，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,当d0,则应取正右方的p1。当d=0是，二者一样合适，可以随便取一个。,我们约定取正右方的p1。对每一个象素计算判别式d，根据它的符号确定下一象素。由于d是xp和yp的线性函数，可采用增量计算，以便提高运算效率。,在d0的情况下，取正右方的象素p1，欲判断再下一个象素应取哪个，应计算d1=F(+2,+0.5)=a(+2)+b(+0.5)+c=(a(+1)+b(+0.5)+c)+a=d+a故d的增量为a。,而若d0，则取右上方象素p2。要判断再下一个象素，则要计算d2=F(+2,+1.5)=a(+2)+b(+1.5)+c=(a(+1)+b(+0.5)+c)+a+b=d+a+b故在第二种情况，d的增量为ab。,再看d的初始值。显然，第一个象素应取左端点（x1，y1），相应的判别式值为d0=F(+1,+0.5)=a(+1)+b(+0.5)+c=(ax1+by1+c)+a+0.5b=F(x1,y1)+a+0.5b但由于（x1,y1）在直线上，故F(x1,y1)=0。因此d的初始值为d0=a+0.5b,由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，来摆脱小数，写出仅包含整数运算的算法：,voidMidpointLine(x1,y1,x2,y2,color)intx1,y1,x2,y2,color;inta,b,d1,d2,dx,y;a=y1-y2;b=x2-x1;d=2*a+b;d1=2*a;d2=2*(a+b);x=x1;y=y1;,setpixel(x,y,color);while(xx2)If(d0)x+;y+d+=d2;elsex+;d+=d1;setpixel(x,y,color);,2.1.3Bresenham画线算法,算法分析,算法推导,可视化效果图,2.1.4图形环境的设置,#include”graphics.h”图形方式初始化函数：initgraph(*gdriver,*gmode,*path);gdriver:是一个空型指针，用来指定要装入的图形驱动程序，该值在头文件中定义；gmode:是一个空型指针，用来指定显示模式path:图形驱动程序所在的路径,若用VGA图形驱动程序,图形显示模式为VGAHI,则调用方式如下:intgdriver,gmode;gdriver=VGAgmode=VGAHIinitgraph(关闭图形方式函数为closegraph(),直线类绘图函数line(x1,y1,x2,y2);lineto(x,y);moveto(x,y);line(dx,dy);几个直线段组成的图形,图一,图二,2.2圆与椭圆的生成,由于圆是图形和图像中经常使用的元素，因此在大多数图形软件中都包含有生成圆和圆弧的过程。也会提供一个既能显示圆曲线，又能显示椭圆曲线的绘图函数。2.2.1圆的特性圆被定义为所有离一中心位置（xc,yc）距离为给定值r的点集，可用如下方程式表示：(x-xc)2+(y-yc)2=r2,利用这个方程，我们可以沿x轴从xc-r到xc+r以单位步长计算对应的y值来得到圆周上每点的位置：y=yc(r2-(xc-x)2)但这并非是生成圆的最好方法。这个方法的第一个问题是每一步包含很大的计算量。,第二个问题是所画像素位置间的间距是不一样的，在靠近x轴的0o180o处像素点之间的间距越来越大。当然可以在圆斜率的绝对值大于1后，交换x和y（即步进y值，计算x值）来调整间距。但这样增加了算法所需的计算量和处理过程。,另一种消除不等间距的方法是使用极坐标r和来计算沿圆周的点。以参数极坐标形式表示圆方程可得到方程组：,使用上述方法以固定角度为步长生成显示时，圆就可沿圆周等距点绘制出来。但这个方法使用了三角函数调用和浮点运算，运算速度太慢。必须寻找只需做一些简单的整数运算和判别运算的方法即可确定圆上的象素点的算法。,考虑到圆的对称性可以减少计算量。只要能生成8分圆，那么圆的其它部分可以通过一系列的简单映射变换得到。如图所示，假设已知一个圆心在原点的圆上一点(x，y)，,根据对称性可得另外七个8分圆上的对应点(y,x)，(y,-x)，(x,-y)，(-x,-y)，(-y,-x)，(-y,x)，(-x,y)。因此，只需讨论8分圆的生成算法。,另外，为了方便起见，我们只考虑中心在原点，半径为整数R的圆x2+y2=R2。对于中心不在原点的圆，可先通过平移变换，化为中心在原点的圆，再进行扫描转换，把所得的像素坐标加上一个位移量即得所求像素坐标。,2.2.2中点画圆法,考虑中心在原点，半径为R的圆的第二8分圆。我们来讨论如何从（0，R）到（R/），（R/）顺时针的确定最佳逼近于该圆弧的像素序列。,假定当前已确定了一个象素点为p(xp,yp)那么下一个象素只能是正右方的p1(xp+1,yp)或右下方的p2(xp+1,yp-1)。,如图所示，构造函数：F(x,y)=x2+y2-R2对于圆上的点，F(x,y)=0;对于圆外的点，F(x,y)0;而对于圆内的点F(x,y)0.假设M是P1和P2的中点，即M（xp+1,yp-0.5）,那么当F(M)0时，p2离圆弧更近，应取p2。当F(M)=0时，在p1与p2之中随便取一个即可，我们约定取p2,与中点画线法一样，构造判别式d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2当d0，则应取p1为下一象素，而且再下一个象素的判别式为d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3,p1,所以，沿正右方，d的增量为2xp+3。而若d0，则p2是下一象素，而且下一象素的判别式为:d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+(2xp+3)+(-2yp+2)=d+2(xp-yp)+5,所以，沿右下方向判别式d的增量为2(xp-yp)+5。由于我们这里讨论的是用顺时针方向生成第二个8分圆，因此第一个象素点是(0,R)判别式d的初值为：d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R,由于使用了浮点数来表示判别式d，为了简化运算，摆脱浮点数，在算法中全部使用整数，我们使用e=d-0.25代替d。显然，初始化运算d=1.25-r对应于e=1-r。判别式d0对应于e-0.25。,算法中其它与d有关的式子可把d直接换成e。又由于d的初值为整数，且在运算过程中的增量也是整数，故e始终是整数，所以e1）后等比例缩小（a=d0时沿+x向错切；c0时，沿+y方向错切；b0），以使其与正投影面处于同一平面，使水平投影图和正面投影图拉开一个距离，变换过程为：,变换结果为（x，y，z，1）*Th=（x，0，-y-d3，1）=（x，y，z，1）,设立体图的点集矩阵为（Dj），各投影图之间的距离为10，求立体的三面投影。已知：,解：1）正面投影,(2)水平投影,(3)侧面投影,用变换后的，画出的三视图如下图,x,z,4.4.2正轴测投影图,轴测图是一种简单的立体图形,能给人一种直观的形象,以帮助建立空间的概念.由于它的绘制方法比较简单,所以在工程制图中经常用到.1.正轴测投影图的形成过程是这样的:先将空间一立体绕z轴正向旋转角,然后再绕x轴反向旋转角,最后让经过两次旋转后的立体向正立投影面做正投影。,整个形成过程可以用矩阵表示为,式子中，和均取大于0的值。,上面的矩阵T是经过3个单步简单矩阵变换的级联形成的，它是一个正轴测投影交换矩阵的一般形式。因此，只要任意给定一组和角，代入矩阵T，就可以产生一种正轴测投影矩阵，由此，可用以生成正轴测投影图。,在正轴测变换过程中：xyz1=xyz1T=xcos-ysin0-sin(xsin+ycos)+zcos1,从上式可以看到，交换的结果使y坐标为0，所以对于一般的二维坐标系来说，y坐标就相应于现在的z坐标。,2.正等测和正二测正等轴测投影图和正二等轴测投影图是正轴测投影图中常用的两种，其中正等测用手工绘制方法简便；正二测的立体感较好，但手工绘制方法没有正等测方便。当用计算机来生成的时候，就不存在方法上的差别，区别只是变换矩阵中的元素值不同而已。,（1）正等测的变换矩阵任一组和的角，可以产生一种正轴测投影变换矩阵。当取=45o，=35o16时，代入矩阵T，就可以得到正等轴测投影的变换矩阵T。,（2）正二测的变换矩阵,形成正二等轴测投影的一组角度和的取值为：=20o42；=19o28。将此和的值代入正轴测矩阵，便可得到正二测的变换矩阵。,3.轴测图的编程步骤,下面，我们通过一个简单的立体例子，来说明设计和编写绘制轴测图的绘图程序的步骤。设所需绘制的立体如下图,则工作步骤如下：在草纸上绘制出草图，并确定各顶点的序号和相应顶点的坐标值，建立顶点表和边表，如下二个表。,在程序中定义两个数组，用于定义顶点表和连边表。通过数组的初始化给两个数组赋初值。实施对立体进行正轴测投影变换，即用正轴测投影变换矩阵顶点表实现。这样，可以得到一个变换后的新的顶点表。,用新顶点表的顶点坐标值，注意此时只有x坐标轴和z坐标轴，y坐标轴已在投影中消掉，所以是以x坐标为绘图的x坐标，以z坐标为绘图的y坐标。按连边表中的连边规则，用line函数在顶点之间两两连线。,在绘图程序中要注意两点：在建立立体坐标时，为了取顶点坐标值简便，我们把立体的一个顶点放置在坐标的原点，所以，整个轴测投影变换后的图形是以该原点为中心。但图形输出时的中心应以屏幕中心为宜，比如，对于VGA来说，这个中央点在（320，240）处。该绘图程序目前只能按连边表把立体的所有棱边都画出来，而不考虑是否可见，即没有经过消除隐藏线处理。,四.透视投影图1.透视变换矩阵在前面讲的三维变换矩阵中，已经说过，所产生透视投影的效果。现在我们来具体讨论，当其中的p，q，r三个参数为非全0时，这样的变换矩阵会对变换产生什么样的影响。,（1）一点透视先设q0，p=r=0。然后对点（x，y，z，1）进行变换，结果如下：对其结果进行齐次化处理，得：,当y取值不同时，上式会产生如下不同的结果：当y=0时，得：而原来处于y=0的平面内的点，经过变换以后没有变化。当y时，得：,这说明，当y时，所有的点的变换结果都集中到了y轴上的1/q处。即所有平行与y轴的直线最终延伸将相交（0，1/q，0）的点，该点称为“灭点”。而象这样形成的一个灭点的透视变换称为“一点透视”。为了取得较好的效果，我们取q0，让灭点位于y轴的负半轴上。一点透视的效果如下,根据同样的道理，当p0，q=r=0时，则将含在x轴上的1/q处产生一个灭点，其坐标值为（1/q，0，0）。在这种情况下，所有平行于x轴的直线将延伸交于该点。当r0，p=q=0时，产生的一个灭点位于z轴上的1/r处，灭点的坐标为（0，0，1/r）。所有平行与这轴的直线将延伸交于该点。,（2）多点透视根据一点透视的原理予以推广，如果在p，q，r三个元素中有两个为非零元素时，这将会产生两个灭点，因此得到两点透视。经过齐次处理结果为：,从以上结果可以得到：当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处。,2.生成透视投影图的方法生成透视投影图的过程分为两步：先是对立体进行透视变换；然后是将其投影到正面投影面上，形成投影面上，形成正投影图。用矩阵形式表示为：,（1）一点透视图的生成在生成一点透视图时，为了避免把图所属立体安置在坐标系的原点而产生如下图所示的透视效果,z,x,o,x,z,o,通常是在进行透视投影变换前，先将立体平移到一个合适的位置，然后再进行透视投影变换，使得产生的透视图效果较好。生成一点透视投影的变换矩阵为:,当d1，d2，d3和q取确定的非零值后，该矩阵中包含的三个透视变换参数中有一个为非零，所以该变换矩阵能产生一点透视图。在q的取值时，一般取-1q0）；c.进行透视变换；d.往正投影面进行正投影。,用矩阵的形式表示这个变换过程为：从以上的变换矩阵T可以看到，矩阵中的三个透视变换参数均非0，因此可以变换生成三点透视图。,第四章、多边形及多边形填充算法,在这一节中将讨论图形系统中的新图元多边形，研究有关多边形的概念以及如何表示多边形，学习如何判断一个点是否在多边形内的方法，以及多边形填充的各种方法。,一、多边形的概念,所谓多边形，就是用一系列首尾相连的线段构成图形。这些组成多边形边界的线段称为多边形的边，多边形的边的端点称为多边形的顶点。一般来说，一个多边形应是封闭的。,1.凸多边形与凹多边形,多边形又分为两大类：凸多边形与凹多边形。所谓凸多边形，是指这样一类多边形：如果在多边形内任找两个点，将这两个点用线段连接后，此线段上所有的点都在多边形内，这就是凸多边形。而凹多边形就是非凸多边形。,下面给出了凸多边形与凹多边形的例子，可见，三角形总是凸多边形。,凸多边形,凹多边形,2.多边形的描述,考虑到多边形的特征属性：顶点和边，在描述多边形时，既要指明组成多边形的顶点，又要指出组成多边形的边。一般来说，用顶点的序列来表示多边形，其中的边即指两顶点所构成的线段，这样来表示的多边形如下：,图中多边形顶点序列为p1p2p3p4p5p6p7。可以根据这种方法写出在计算机上绘制多边形的算法：draw_polygon(intN,intpN2)if(N=2)return();elsefor(i=1;iN;i+)line(pi0,pi1,pi+10,pi+11);line(p10,p11,pN0,pN1);,二多边形的填充,1.点是否在内部的检验,p5,S3(s4),2连贯性原理,梯形的两底边分别在y=yk和y=yk+1两条扫描线上，腰在多边形p的边上或在显示屏幕的边界上。,区域的连贯性,Yk+1,yk,这些梯形分为两类：一类位于多边形内部（图中粉色部分），另一类位多边形外部。两类梯形在长方形区域上相间排列，即相邻的两个梯形必有一个在多边形内，一个在多边形外。,交点数为偶数；相邻交点间的线段也分为两类：一类线段上所有点均在多边形内部，另一类线段上所有点均在多边形外部；两类线段在扫描线上相间排列。,扫描线的连贯性对于多边形与扫描线y=yk相交,交点序列x1,x2,x3,x4,x5,x6由连贯性可知，此交点序列具有下列性质,边的连贯性,三、多边形填充算法,1、扫描线算法,扫描线算法的步骤为：在EL中找出非空元素的最小序号：将边的活化链表置空；按从下至上的顺序分别处理每一条扫描线，直到边的分类表EL和边的活化链表均为空为止。,处理扫描线步骤为：,对于扫描线y=yc,若EL中非空，则将其所有的边从EL中取出，并且插入到边的活化链表中，并将AEL中各边按x递增顺序；若相对于当前扫描线，边的活化链表AEL非空，则将AEL中的边两两依次配对，即第1，2边为一对，第3，4边为一对，依次类推，每一对边与当前扫描线交点所构成的线段位于多边形内，依次将这些线段上的点进行着色；,将边的活化链表中满足y=ymax的边删去；将边的活化链表AEL中剩下的每一条边的x域累加x，即x=x+x；将当前的扫描线的纵坐标y累加1，即y=y+1，重复执行,种子填充算法,将种子象素压入栈；当栈非空时a.从堆栈弹出一个象素；b.将该象素置成所要求的色彩值；c.检查当前每个象素邻接的四连接象素是否是边界色或已置成所要求的色彩值，若是则返回，否则将该象素压入堆栈后再回到。,多边形填充函数,1.drawpoly画多边形drawpoly（n,*pt）n是多边形顶点数，*pt是多边形顶点坐标数组名2.fillpoly画并填充一多边形fillpoly(n,*pt)3.floodfill填充一个有界区域floodfill(x,y,bcolor)x,y填充区域内的一点坐标，bcolor填该域边界颜色4.setfilllstyle(pallern,color)设置填充模式和颜色,扫描线种子填充算法步骤,1.从包含种子象素的栈中弹出种子象素2.沿着扫描线对种子象素左右象素进行填充，直到遇到边界象素为止，这样就将种子所在的扫描线中元素填充；,3.区间内最左最右元素为xleft、xright。则在xleftxxright中检查与当前扫描线相邻的上、下两条扫描线是否全为边界象素或正填充过的象素，若不是，则对于xleftxxright，把每一区间的最右象素作为种子压入堆栈中算法结束条件为栈空。此算法适用于边界定义的区域。,区域填充算法,扫描线填充算法,种子填充算法,边缘填充算法,4-连通边界填充算法,4-连通边界填充算法(2),8-连通边界填充算法,8-连通泛填充算法,第五章图案及动画程序设计,第一节、图案程序设计第二节、动画程序设计,第一节图案程序设计1.构造功能模块的原则（1）独立性（3）开放性（2）抽象性（4）继承性,2.正多边形子程序的设计（1）顶点定位的正凸多边形a.选择绘图参数对于一个任意的正多边形来说，如下图所示,p1,p2,p3,p4,p0（x0，y0）,它所需要的定形参数为：边数n（n不能小于3）；边长a。定位参数为：定位顶点Po的坐标（x0，y0）起使边的倾角。给定了这两组参数，就可以唯一地确定一个任意位置、形状和大小的正多边形。但在绘图程序中，必须把这两组参数转化为具体的绘图用数据。,根据图形中的几何关系，可以列出计算机正多变形各顶点坐标的算式。其中，=2/n。,b.编写汇编绘图程序根据以上的分析和数据的准备，下面便可以着手编写绘制任意正多边形的程序。图形程序见程序2_4。其中，函数polygon为绘制任意正多边形的通用绘图程序，函数中有5个形参。.X0，Y0定位顶点坐标；.A正多边形边长；.n正多边形边数；.af起始边与x轴正向的夹角。,（2）以外接圆圆心定位的正多边形a.选择绘图参数利用正多边形的外接圆这种方法中，定形参数为：.边数n（n不能小于3）；.外接圆半径R。定位参数为：.外接圆圆心坐标（x0，y0）；.起始点半径的倾角。,根据以上给定的参数，同样可以列出计算多边形各顶点坐标的算式。其中:=2/n。,b.编写绘图程序,（3）正凹多边形子程序所谓正凹多边形，即通常所称的多角形。如下图所示的五角形和六角形。,p3,p5,p1,p7,p9,p4,p2,p6,p8,p10,五角形,六角形,也就是说，N角形有2N个顶点。顶点分别位于外接圆和内接圆圆周上，称作外顶点和内顶点。若奇数点为外顶点，则偶数点一定为内顶点。当一个N角形的外接圆半径R已知时，其内接圆半径R通过下面的推到求得：抽出三角形PoP=2/2N=/N=（N-4）/N,p2,p1,o,在三角形op1p2中。p1op2=op1p2=/2所以，p1op2=-p1op2-op1p2=-（N-4）/N+/N）=-（N-2）/2N,因此，根据多角形的外顶点N，外接圆半径R，第一个顶点的其实角及中心点O的坐标（x0，y0），就可编出正凹多边形的程序,算法实例,程序1,分形图形,程序2,程序3,程序4,方块旋转,动画1,动画2,动画3,第六章、裁剪算法,第一节窗口和裁减第二节直线的裁减第三节多边形的裁减第四节窗口视区变换,第一节窗口和裁减,窗口裁减覆盖,(xl,yb),(xr,yt),窗口,剪裁的应用包括,1、从定义的场景中抽取出用于观察的部分；2、在三维视图中标识出可见面；3、防止线段或对象的边界混淆；4、用实体造型来创建对象；5、显示多窗口的环境；6、允许选择图形的一部分来进行拷贝，移动和删除。,第二节直线段的剪裁,被剪裁的可以有各种不同类型的图形元素,比如点、线段、圆弧、字符以及多边形.剪裁判断的依据是一对不等式,通过它们可以测定点（x,y）是否落在窗口内,xlxxrybyyt,剪裁方法：只要逐点比较每个点的坐标值（xi,yi）,看其是否同时满足不等式组时，才能确定该点是落在窗口内的，否则是在窗口外的。,对于任意一条直线，它相对于一个正定义的窗口的位置关系不外乎有四种情况：,直线在窗口外a直线包含在窗口内b直线段和窗口的一条边框相交c直线贯穿整个窗口fe,归纳可得出一个结论：对于任意一条直线，它要么被排除在窗口外，要么在窗口内留下一个可见段，并且只有一个可见段。因为一个直线段可以用它的两个端点唯一确定，所以，要确定一条直线段上位于窗口以内的可见段，仅需求得它的两个可见端点就行。,算法演示,一、cohen-sutherlanol算法（编码剪裁算法）,算法包括两部分，第一部分是先判断该直线是否完全位于窗口以内。如果是，则输出线段，过程结束。如果不是，那么进而判断该直线段是否完全位于窗口之外，如果是，去除该线段无输出，过程结束。如果以上两种测试都不满足进入第二部分。,第二部分：首先把直线分两段，然后对每一段进行上述第一部分的两个测试。算法所依据的是这样一个事实：即每条线段要么全部落在窗口边框之内，要么可以被分成两段，使得其中有一段因完全处于窗口之外而被排除掉。,采用编码裁减的步骤如下：,编码（对给定的直线两端点进行编码）a计算端点坐标和窗口边界之差b用每次差运算结果的符号位来设置区域代码的对应位置，也就是说，第一位是x-w1符号位；第二位是w2-x的符号位，第二位是y-w3的符号位，第四位是w4-y的符号位。,A,按组这种方法a点的代码为（四位）；第一位：x-w1结果为负所以为1；第二位：w2-x结果为正，所以为0；第三位：y-w3结果为正，所以为0；第四位：w4-y结果为正，所以为0，即a的代码为0001同样b点的代码为0000。,1001100010100001窗口0010010101000110,判别,一旦所有线的端点编码都已建立，就能很快决定哪些位于窗口内，哪些位于窗口外，这有三种情况：a.线段两端点都在窗口内，两端点编码均为0000；b.线段两端点都在窗口外，两端点编码均不为0000；c.线段一端点在窗口内，只有一个编码为0000；,剪裁原则,a全部位于窗口内的线段，其两个端点的编码均为0000，这条线段一定可以画出。,b如果一条线的两个端点的编码在相同位置上的值都为1，该线段完全在窗口之外，应当全部删除。比如一个端点的区域码为1001，而另一个端点的区域码0101它的两个端点都在窗口左边，其编码的第一位为1，应把它删掉。,这个测试可以用“与”操作实现，将两个编码进行“与”，如果结果不为0000，这条直线位于窗口之外。C.如果“与”的结果为0，则还有三种情况，如右图中的p3p4,p5p6,p7p8三条线段,求交,循环测试剪裁,二、矢量裁减算法,若线段a满足下列条件之一即:,max(x1,x2)wxr;或max(y1,y2)wyt;,则a在窗口外，无输出，剪裁过程结束,(x2,y2),(x1,y1),wxlwxr,1,0,2,3,4,5,6,7,8,若a满足：,wxlx1wxrwyby1wyt,则a的讨论在0区域内，即可见线段的新起点坐标为：否则，a与窗口的关系其新起点（xs,ys）的求解过程如若x1wxr,即a的起始点可能在6、7、8区，此时可用类似的步骤求出a与窗口边界的交点。若(x1,x2)在一二区，则分别用式2和式3求出a与上、下窗口的交点（xs,ys）如果wxl0）要表示成参数坐标式至今未能成功，因此无法使用计算机绘制它的图形。不过常用重要曲线基本上都能用参数坐标表示。例如星形线直角坐标表示式：X2/3Y2/3R2/3(R为常数),可写成参数坐标表达式：XR*cos3YR*sin3（02）从而可用计算机绘出,2、极坐标曲线对任一极坐标曲线（）,可利用极坐标与直角坐标变换关系式X=cosY=sin将此曲线转换成参数坐标表示为X=()cosY=()sin这里成为参数坐标,例重要曲线阿基米德螺线=a(a为正号常数)极坐标与直角坐标变换关系式X=cosY=sin将阿基米德螺线=a代入上面两式,便得X=acosY=asin这样就将阿基米德螺线极坐标表示转换成了参数坐标表示。,由阿基米德螺线参数表示式X=acosY=asin可以计算出曲线上的点的坐标值，然后用这些点的坐标值调用给图形函数就可以给出阿基米德螺线曲线图。3、参数坐标曲线曲线的参数坐标表示一般为Xx（t）Yy（t）,如弹道曲线XV0t*cosaY=V0t*sina-gt2/2(0t2V0sina/g)式中V0,g,a均为常数,t为参变量。4、参数曲线的优点在曲线的表示上参数方程比显式、隐式方程有更多的优越性。,1、有更大的自由度来控制曲线的形状。2、对非参数方程表示的曲线进行变换，必须对曲线上的每个型值点进行几何变换。3、便于处理斜率的无限大问题，不会因此而中断计算。4、参数方程中，代数、几何相关和无关的变量是完全分离的，而且对变量个数不限，从而便于用户把低维空间中的曲线扩展到高维空间去。,5、规格化的参数变量t0，1，使其相应的几何变量是有界的，而不必用另外的参数去定义其边界。6、易于用矢量和矩阵表示几何分量，简化了计算。基于这些优点，我们在以后将用参数表达式讨论曲线问题。本章将讨论参数样条曲线的绘制方法,二、参数样条曲线的常用术语二次参数样条曲线：P(t)=A0+A1t+A2t2三次参数样条曲线：P(t)=A0+A1t+A2t2+A3t31、型值点和控制点所谓型值点，是指通过测量或计算得到的曲线上少量描述曲线几何形状的数据点。由于型值点的数量有限，不足以充分描述曲线的形状。,因此通常是在求得一些型值点后，采用一定的数学方法建立曲线的数学模型，从而再根据数学模型去获得曲线上每一点的几何信息。所谓控制点，是指用来控制或调整曲线形状的特殊点，曲线段本身不通过该控制点。,2、切线、法线和曲率3、插值、逼近和拟合插值与逼近是曲线设计中的两种不同方法。插值设计方法要求建立的曲线数学模型严格通过已知的每一个型值点。而逼近设计方法，顾名思义，用这种方法建立的曲线数学模型只是近似的接近已知的型值点。,而曲线的拟合是这两种方法的统称，是指在曲线的设计过程中用插值或逼近方法使生成的曲线达到某些设计要求，如在允许的范围内贴近原始的型值点或控制点序列，或曲线看上去很光滑等。4、参数连续性和几何连续性为保证分段参数曲线从一段到另一段平滑过渡，我们可以在连接点处要求各种参数连续性条件。,零阶参数连续性，记作C0连续，是指曲线相连，即第一个曲线段的终点与第二个曲线段的起点相同。一阶参数连续，记作C1连续性，是指代表两个相邻曲线段的方程在相交点处有相同的一阶导数（切线）。,二阶参数连续性，记作C2连续性，是指两个曲线段在焦点处有相同的一阶和二阶导数。连接两个相邻曲线的另一个方法是指定几何连续性条件。这种情况下，只需两曲线线段在相交处的参数导数成比例而不是相等。,零阶几何连续性，记为G0连续性，与零阶参数连续性相同，即两个曲线段在公共点处有相同的坐标。一阶几何连续性，记为G1连续性，指一阶导数在两个相邻段的交点处成比例但不一定相等。二阶几何连续性，记为G2连续性，指两个曲线段在相交处其一阶和二阶导数均成比例。G2连续性下，两个曲线段在交点处的曲率相等。,第二节抛物样条曲线一、过三点定义一段抛物线由于离散点的要求，我们首先要解决给定点意义抛物线的问题。设有不在同一直线上的三点：P1、P2、P3，现在要求通过这3点定义一条抛物线。假如采用矢量表达式来表示参数化的二次曲线，那么可以把抛物线的表达式写成如下的一般形式：P（t）A1A2tA3t2抛物线是一条二次曲线，所以表达式中参数t的最高次数为2，同时让参数t在01之间取值。,这就是说，只要确定了式中的3个系数A1、A2、A3，那么就确定了抛物线的表达式，随之抛物线的曲线图形也就可以确定。所以，进行的工作是要通过设定一些已知条件来求出这3个系数。要确定这3个系数（目前尚为未知数），必须要有3个独立的条件。设给定这3个独立条件为：该抛物线经过p1、p2、p33个点，并且：（1）抛物线段以p1点为始点。即当参变量t0时，曲线经过p1点,（2）抛物线段以p3点为终点。即当参变量t1时，曲线经过p3点。（3）当参变量t0.5时，曲线过p2点，且切矢量平行于p3p1。在这3个设定的条件下，构造的抛物线如下图所示。图中的数据是这样的：A点为p1p3的中点，Ap2=p2Q，抛物线在p1点处与p1Q相切，在P3点处与QP3相切,曲线在P2点处的切向矢量与P1P3平行。,Qp2p2t0.5P1t0p3根据以上设定的条件，可以列出3个方程：t0p（0）A1p1t1p（1）A1A2A3p3t0.5p（0.5）A10.5A20.25A3p2解以上3个联立方程：,A,t=1,A1p1P3=A1+A2+A3=p1+A2+A3A2p3p1A3P2A10.5A20.25A3亦即：4p24A12A2A3=2p1+2p3-A3A3=2p1+2p3-4p2以上式回代到A2p3p1A3中，得：A24p2p33p1把求出的该3个系数的值，代入到抛物线的表达式中，可得：,P(t)=A1+A2t+A3t2=p1+(4p2-p3-3p1)t+(2p1+2p3-4p2)t2=(2t2-3t+1)p1+(4t-4t2)p2+(2t2-t)p3式中：0t1。亦可把上式改写成矩阵形式为P（t）t2t1,3、抛物线加权合成由3点可以定义一条抛物线。设有一离散型值点列pi（i=1,2,n）,则每经过相邻3点作一段抛物线，由于有n个型值点，于是像这样的抛物线段一共可以作出n2条。在这n2条抛物线段中：第i条抛物线段为经过pi，pi1，pi23点，所以它的表达式应为：Si+1（ti+1）（2t2i+13ti+11）pi+1（4ti14t2i1）pi+2（2t2i1ti1）pi+3,即经过4点可画出两条抛物线段Si（ti）和Si+1（ti+1）。一般说来，每两段曲线之间的搭接区间，两条抛物线是不可能会自然地重合成一条曲线。但对于拟合曲线来说，整个型值点列必须只能用一条光滑的曲线连接起来。为了做到这一点，在Si和Si+1这样两条曲线的共同区间内，必须有一个办法让它们按照一个一定的法则结合成一条曲线，这结合的办法就是“加权合成”。,在加权合成的过程中，首先要选择两个合适的权函数。如果在这里选择的两个权函数分别为f(T)和g(T)，加权合成后的曲线为pi+1(t)f(T)Si(ti)g(T)Si+1(ti+1)在抛物样条曲线中，选择的权函数f(T)和g(T)是简单的一次函数，且它们之间存在互补性。它们分别为：f(T)1T；g(T)T(0T1)。,假如使t的取值范围为：0t0.5，则上面的3个参变量可统一形式为T2t，ti0.5t，ti+1t。于是，合成曲线可写成如下的形式：pi+1(t)=(1-2t)Si(t+0.5)+2tSi+1(t)=(-4t3+4t2-t)pi+(12t3-10t2+1)pi+1+(-12t3+8t2+t)pi+2+(4t3-2t2)pi+3(i=1,2,n-3;0t0.5),该式的实质是:每相邻的4个点可以决定中间的一段抛物样条曲线.假如一个离散点列pi具有n个型值点:即i=1,2,n,那么根据该式,可以加权合成后生成n-3段抛物样条曲线.,曲线的讨论1抛物线条曲线的端点条件上面已经说到,从全部点列Pi(i=1,2,n)中,只能得到n-3段曲线,但n个型值点之间应有n-1个区段.所缺的两段曲线,是因点列的首尾两段曲线P1,P2和Pn-1,Pn,段缺乏连续相邻的4点这样的条件而无法产生.,所以,为了要产生首尾两段曲线,一个直观的想法就是在原点列的两端各添加一个辅助点P0和Pn+1。当点列的两端增加了两个点P0和Pn+1以后，就可以依据P0，P1，P2和P34点产生曲线段P1，P2；同样，可依据Pn-2,Pn-1,Pn和Pn+14点产生曲线段Pn-1，Pn。这样，原来首尾两端所缺的曲线段就可以补上了。,余下的问题是这P0和Pn+1两点是如何加上去的，它必须依据什么原则，这就是所谓的“端点“。这里介绍常用的3种方法。1）已知两端点的切矢P1和Pn前面已经说过，在由P1，P2，P3三点所确定的抛物线中，过P2点曲线的切矢P2=P3-P1，即P1=P3-P2。这样，在抛物样条曲线中，当条件给出了两端的切矢P1和Pn之后，根据上面的原理可得：,2）自由端条件另一种补点的方法的原理比较简单，它让所补之辅助点P0和Pn+1与原两端点P1和Pn分别重合，即：P0=P1；Pn+1=Pn这种方法一般适用于对曲线的两端点没有什么特殊的要求的情况，所以这样的补点方法称为自由端条件。,3）形成封闭曲线为了在n个型值点之间形成封闭曲线，那么就要生成n段曲线段，而不是原来的n-1段。所以在补点工作中要添加3个辅助点，首先让首尾两点重合，然后各向前延长一点，即Pn+1=P1；P0=Pn；Pn+2=P2；,曲线程序,抛物样条曲线的绘图程序见下例。在程序中，绘图程序parsp1中的参数含义如下：p型值点的坐标数组；n型值点数目；k插值数，即是把参变量t区间细分的份数；e端点条件。e=1时为自由端；e=2时为封闭曲线,2、抛物样条曲线的性质无论用什么方法把离散的型值点连成曲线，总是希望所得到的曲线是光滑的，这应该在所用的数学方法上予以保证。那么，拿什么标准作为评价曲线光滑程度的指标呢？根据抛物样条曲线的推导过程，可以知道整条曲线是由若干个曲线段组成的，每两个相邻的型值点之间形成一段曲线，每相邻的两段曲线在型值点处相接，相邻两曲线段的连接处称为“节点”。,可见，节点是两段曲线的过渡处，是决定整个曲线是否光滑的关键之处。所以，一般都是拿两段曲线在节点处的导数是否相等来衡量曲线是否光滑，并以导数的阶次来评定光滑的程度。假如在节点p处，相邻两个曲线段的一阶导数相等，那么就可以称该曲线为一阶（C1）连续。更好一些，如在节点处不仅两曲线段的一阶导数相等，而且二阶导数相等，那么就可以称该曲线为二阶（C2）连续。以此类推到更高阶次连续的意义。,显然，连续的阶次愈高，曲线愈光滑。但太高的连续阶次会给设计工作和制造工作增加难度，提高成本。所以不必盲目地提高连续的阶次，只要能满足使用要求就可以了。在实际的工程应用中，一般达到C2连续就足够好了；对于一般的应用场合，达到C1连续也就可以了。,下面依据上述的判定方法和标准，来简单讨论抛物样条曲线的连续性问题。设两曲线段pi+1(t)和pi+2(t)在节点p处相连。在p点处，pi+1(t)的参变量t0.5,而曲线pi+2(t)在p点处的参变量t0。两曲线对t微分求值得Pt+1(t)=(-12t2+8t-1)pi+(36t2-20t)pi+1+(-36t2+16t+1)pi+2+(12t2-4t)pi+3=pi+3-pi+1Pi+2(t)=(-12t2+8t-1)pi+1+(36t2-20t)pi+2+(-36t2+16t+1)pi+3+(12t2-4t)pi+4=pi+3-pi+1,因此得出pi+1（0.5）pi+2（0）说明抛物样条曲线可以达到C1连续。照此方法，可以检验抛物样条曲线能否达到C2连续，大家可以自己去试一试,第4节贝塞尔曲线贝塞尔曲线是由多项式调和函数推导出来的，通常n+1个顶点定义一个n次多项式，其参数向量表达式为：在式中，Pi为各顶点的位置向量，为伯恩斯坦基函数，也就是贝塞尔多边形的各顶点位置向量之间的调和函数。,（1）,该函数的表达式为：如果我们规定：0和0！均为1，那么，当t=0时:当t=1时：,（2）,从以上结果可以得出，曲线通过多边折线的起点和终点。下面