计算机图形学课件1-20讲

计算机图形学教材和参考书教材计算机图形学，倪明田等，北京大学出版社，2000年。参考书1、OpenGL编程指南（第四版），DaveShreiner等（邓郑祥译），人民邮电出版社，2005年。2、计算机图形学（第三版），DonaldHearn，电子工业出版社，2004年。3、计算机图形学基础，唐泽圣等，清华大学出版社，2001年。第1讲

计算机图形学概述

—硬件

1．图形及其在计算机中的表示图形:能够在人们视觉系统中形成视觉印象的对象称为图形,包括自然景物和人工绘图等。计算机图形学研究的对象就是图形。构成图形的要素（1）刻画形状的几何要素，如点、线、面和体；（2）反映表面属性的非几何要素，如灰度、颜色和纹理等。图形在计算机中的表示方法（1）点阵法：该方法列举图形中的所有点，强调图形由哪些点构成。点阵法描述的图形称为像素图或图像。（2）参数法：该方法用图形的形状参数和属性参数来表示图形。参数法描述的图形叫做参数图。第1讲

计算机图形学概述

—硬件2.计算机图形学的研究内容图形输入：研究图形输入设备及软件，目的在于将图形输入到计算机中。图形处理：研究图形变换和图形运算，如旋转、求交等。图形生成和输出：研究如何生成在输出设备上显示的图形和完成输出的软硬件。第1讲

计算机图形学概述

—硬件3．计算机图形学的应用（1）图形用户界面（2）计算机辅助设计（CAD）（3）科学计算可视化（4）计算机艺术（5）多媒体系统（6）虚拟现实系统（7）地理信息系统（8）计算机动画、广告和娱乐（9）科技、教育和商业领域中的交互绘图第1讲

计算机图形学概述

—硬件4．计算机图形系统的硬件设备主机设备输入设备：鼠标、键盘、光笔和数字化仪等。输出设备：显示器、打印机和绘图仪等。存储设备：磁盘机、磁带机和光盘机等。第1讲

计算机图形学概述

—硬件5.显示设备阴极射线管（CRT）显示器是目前占统治地位的显示设备。CRT显示器的核心部件是CRT，它由电子枪、偏转系统和荧光屏三个关键部件组成。

光栅扫描显示器随机扫描显示器第1讲

计算机图形学概述

—硬件6.光栅扫描显示器光栅扫描显示器中，图形是通过电子枪从上往下一行一行扫描并点亮其中的某些点而形成的。电子枪扫过的一行称为一条扫描线。光栅扫描显示器的屏幕可以分为m行扫描线，每一行分为n个小点，整个屏幕分成mxn个小点，其中每个小点称为一个像素。屏幕上各个点的颜色和亮度信息需要存储在存储器中，每个点需要用若干个二制位来存储相应的信息。存储颜色和亮度信息的相应存储器称为帧缓冲存储器，所存储的信息被称为位图。

第2讲

计算机图形学概述

—软件

1．图形软件的组成图形软件通常组织成一个层次结构。这种层次结构使得整个系统易于设计、调试和维护，便于扩充和移植。支撑软件（基本图形软件）底层软件基本子程序功能子程序用户程序。

第2讲

计算机图形学概述

—软件2．图形软件的建立方法图形程序包：可以通过图形程序包来建立基本图形软件。这种方法通常以某种高级语言为基础，加上扩充的图形处理子程序包。修改高级语言：在某种高级语言为基础上，通过修改其编译系统，以增加处理图形的语言和数据结构。专用高级语言：图形专用高级语言是从语句、数据结构和输入、输出等各方面都按照处理图形的需要来设计的高级语言。第2讲

计算机图形学概述

—软件3．图形软件标准1981年，IGES（InitialGraphicsExchangeSpecification）被ANSI采纳为图形系统之间数据交换的标准。IGES定义了表示图形系统中常用的几何和非几何数据的格式及相应文件结构。原西德标准局DIN于1977年提出GKS（GraphicsKernalSystem）二维图形系统。1982年ISO接受它为国际标准草案，1985年正式批准为二维图形国际标准。GKS提供了在应用程序和图形输入输出设备之间的功能接口，它包括点元素、线元素、字符元素和光栅元素四种基本图素。为了适应三维图形处理的需要，GKS已发展为GKS-3D。

第2讲

计算机图形学概述

—软件4．图形软件标准（续）ANSI于1986年公布了PHIGS（Programmer’sHierarchicalInteractiveGraphicsSystem）图形软件标准。与GKS不同，PHIGS的图形数据按层次结构来组织，使多层次的应用模型能方便地利用它来进行描述。CGI（ComputerGraphicsInterface）是ISOTC97提出的图形设备接口标准草案，与ANSI1985年公布的VDI（VirtualDeviceInterface）标准一致。CGI提供一种与设备无关的方法，其几何图素和结构图形定义在虚拟的设备坐标空间中，即二维笛卡尔坐标系中。第2讲

计算机图形学概述

—软件5．图形软件标准（续）CGM（ComputerGraphicsMetafile）是ANSI于1986年公布的图形标准，随后成为ISO标准。CGM能生成静态图形元文件，但不能产生动态效果。CGM具有通用性，能广泛地适用于各种设备及应用系统。

第2讲

计算机图形学概述

—软件6．学习本课程的目标

困难：学习过程中将碰到大量算法，这些算法绝大多数又与数学有关。目标：理解图形学的基本原理和方法，关注算法本身的特点，如时间复杂度和空间复杂度，以及算法将要生成的几何对象的特点，如Hermite曲线与Bezier曲线在特征上有何区别。实际编程：可以利用现成的图形软件包或图形工具软件，例如可以用OpenGL软件包进行图形编程或用AutoCAD、3DMax之类的图形工具生成图形。一旦把握了算法和几何对象的特点，就能够正确地利用现成的代码或图形包进行编程。

第3讲二维图形—直线图形1．直线生成DDA算法

直线生成DDA算法即数值微分法（DigitalDifferentialAnalyzer）,这是一种基于直线的微分方程生成直线段的方法，也是直线段生成的一种最基本方法。下面为直线的参数方程。第3讲二维图形—直线图形2．直线生成DDA算法（续）递推公式第3讲二维图形—直线图形3．直线生成Bresenham算法前述DDA算法中的浮点加法和浮点取整对该算法的运算效率带来影响，Bresenham算法实际上也是DDA算法，但它只用到整数运算，因此在算法效率上得到了很大的提高。第3讲二维图形—直线图形第3讲二维图形—直线图形4．直线生成Bresenham算法（续）如果di大于或等于0,yi离yi-1+1近，取yi=yi-1+1,此时，

di+1=di+2(dy-dx),

否则，yi离yi-1近，取yi=yi-1,此时，

di+1=di+2dy。初始值d1=dx(2y1-2y0-1)=2dy-dx。第3讲二维图形—直线图形5．直线属性直线的属性包括线型、线宽和颜色。线型有实线、虚线和点划线等；线宽以像素的整数倍来规定；颜色通常用红、绿和蓝三原色的含量来表示，对不具有彩色功能的显示系统，颜色显示为灰度级（或亮度级）。

第4讲

二维图形—圆和椭圆

1.圆周生成DDA算法

第4讲

二维图形—圆和椭圆第4讲

二维图形—圆和椭圆2．椭圆生成DDA算法第4讲

二维图形—圆和椭圆3．椭圆生成DDA算法(续)第4讲

二维图形—圆和椭圆4．圆周生成Bresenham算法用DDA算法生成圆周或椭圆需要用到三角运算。因为三角运算计算量大，所以对算法的效率造成严重影响。圆周生成Bresenham算法避开了三角运算,它采用类似于直线生成Bresenham算法中的迭代公式来判定圆周生成过程中每一步的走向。第4讲

二维图形—圆和椭圆第4讲

二维图形—圆和椭圆第4讲

二维图形—圆和椭圆5．圆周生成Bresenham算法(续)第5讲

二维图形

—二次曲线参数拟合

椭圆、抛物线和双曲线在平面直角坐标系中可以表示为二次方程，因此称它们为二次曲线。二次曲线除了可以用直角坐标方程表示外，还可以用参数方程和参数向量方程等表示。一个标量表示一个数值，一个向量则是由若干个标量组成的一个元组，其中每个标量称为向量的一个分量，如平面直角坐标系上的一个向量表示为一个二元组。参数向量方程是包含参数和向量的方程。

第5讲

二维图形

—二次曲线参数拟合1．二次曲线一般参数方程第5讲

二维图形

—二次曲线参数拟合2．二次曲线一般参数方程(续)通常由三个控制点P0（x0,y0）、P1（x1,y1）和P2（x2,y2）来规定曲线的边界（或初始）条件：当t=0时，曲线过P0点，且曲线在该点处的切线平行于线段P0P1；当t=1时，曲线过P2点，且曲线在该点处的切线平行于线段P1P2。第5讲

二维图形

—二次曲线参数拟合3．抛物线参数拟合

第5讲

二维图形

—二次曲线参数拟合4．抛物线参数拟合第5讲

二维图形

—二次曲线参数拟合5．双曲线参数拟合

第5讲

二维图形

—二次曲线参数拟合6．椭圆参数拟合

第6讲

二维图形—抛物线样条曲线和Hermite曲线

形状比较复杂、不能用二次方程来表示的曲线（曲面）称为自由曲线（曲面），也称为复杂曲线(曲面)，通常以三次参数方程来表示。给定一个点列，用该点列来构造曲线的方法称为曲线拟合。已知曲线上的一个点列，求曲线上的其他点的方法称为曲线插值。

第6讲

二维图形—抛物线样条曲线和Hermite曲线1．抛物线参数样条曲线样条是一根富有弹性的细木条或类似物，其两端连接着起固定作用的压铁。通过调整样条两端的压铁可以改变样条的形态，它是手工绘制自由曲线的一种工具。沿着样条绘制的曲线称为样条曲线。样条曲线可以表示为参数多项式曲线或分段参数多项式曲线。

第6讲

二维图形—抛物线样条曲线和Hermite曲线2．抛物线参数样条曲线(续)第6讲

二维图形—抛物线样条曲线和Hermite曲线3．Hermite曲线

第6讲

二维图形—抛物线样条曲线和Hermite曲线4．Hermite曲线(续)对于端点处坐标和切线方向都相同的Hermite曲线，它们的形状随着切向矢量的长度的变化而变化。此外，如果取与z相关的系数为0，则得到平面上的Hermite曲线。Hermite曲线通过端点和端点处的切向矢量来控制曲线的形状，一条单独的Hermite曲线不适合于用来拟合一个空间点列，它主要用在样条曲线中用来表示其中的某一段曲线。第7讲二维图形—三次参数样条曲线第7讲二维图形—三次参数样条曲线1．Hermite曲线的二阶导数形式

第7讲二维图形—三次参数样条曲线2．三次参数样条曲线

设有点列{Pi}(i=0,1,…,n)，用Hermite三次参数曲线将相邻点连接起来，使得最终的曲线在已知点处具有连续的二阶导数，该曲线是一条三次样条曲线。

第7讲二维图形—三次参数样条曲线第7讲二维图形—三次参数样条曲线第8讲二维图形—Bezier曲线第8讲二维图形—Bezier曲线3．Bezier曲线的性质

第8讲二维图形—Bezier曲线4．Bezier曲线的性质(续)第8讲二维图形—Bezier曲线5．常用Bezier曲线的矩阵表示

第8讲二维图形—Bezier曲线6．常用Bezier曲线的矩阵表示第8讲二维图形—Bezier曲线7．三次Bezier样条曲线增加控制顶点必然增加Bezier曲线的阶次，造成计算比较复杂。将分段三次Bezier曲线连接起来成为一条曲线，并且使得整条曲线具有二阶连续导数，该曲线称为三次Bezier样条曲线。

第9讲二维图形—B样条曲线Bezier曲线有许多优越性，但有两点不足：1）特征多边形的顶点个数决定了Bezier曲线的阶次，并且在阶次较大时，特征多边形对曲线的控制将会减弱；2）Bezier曲线不能作局部修改，改变一个控制点的位置对整条曲线都有影响，其原因是调和函数Bernstein基函数是其参数t在[0，1]区间内均不为零。1972年，Gordon,Rie-feld等人拓展了Bezier曲线，用B样条基函数代替Bernstein基函数，即形成了B样条曲线（或曲面）

第9讲二维图形—B样条曲线1．B样条基函数

第9讲二维图形—B样条曲线2．B样条基函数的性质第9讲二维图形—B样条曲线3．B样条曲线

第9讲二维图形—B样条曲线4．B样条曲线的性质

第9讲二维图形—B样条曲线5．B样条曲线的性质(续)第10讲

二维图形—字符

1．图形的表示平面图形在内存中的表示方法有两种，即栅格表示法和矢量表示法。栅格表示法用像素点的集合来表示图形，同一图形的像素点具有相同的属性值；矢量表示法根据平面图形的类型采用不同的表示方法，点用一个数对（x,y）表示，线用点列表示，多边形用边界线表示。不同的表示法对存储和计算带来不同的影响。字符作为图形有点阵字符和矢量字符之分，点阵字符是栅格图形，矢量字符是矢量图形。

第10讲

二维图形—字符2．字符编码字符编码通常分为输入码、机内码和字形码。五笔字型、拼音和区位码等编码用于（汉字）字符的输入，它们都是输入码。机内码用于在机器内部表示字符。字形码用于在输出设备上显示字符。在这些编码之间存在着对应关系，从输入码得到机内码，从机内码得到字形码，根据字形码才能在输出设备上把字符显示出来。字形码分为点阵字符码和矢量字符码两种类型。字符的编码通常存储在字库中，所以字库也点阵字库和矢量字库之分。第10讲

二维图形—字符3．点阵字符点阵字符用一个位图来表示，位图中的1对应点亮的像素，用前景色绘制；位图中的0对应未点亮的像素，用背景色绘制。位图是由正方形组成的网格，其中每个方格称为一个像素，每个像素具有一个属性值，如0或1。常见的字符点阵有16x16、24x24、32x32和48x48等。点阵字符的显示需要经过两个步骤，首先，从字库中把字符的位图检索出来，由于同一型号字符的位图占有的空间相同，字符在字库中的位置可以从字符的序号计算出来；其次，将检索到的位图输出到输出设备。第10讲

二维图形—字符4．矢量字符矢量字符表示法用（曲）线段记录字形的边缘轮廓线。相比点阵字符来说，矢量字符占用的空间少、美观和易于变换，普遍应用在排版、工程绘图和其它软件中。将点阵字符旋转或放大时，显示的结果通常会变得粗糙难看，同样的变换不会改变矢量字符的显示效果。此外，相同字体、不同字号的矢量字符只需要一个字库，不同字号可以通过几何变换来产生。

第10讲

二维图形—字符5．字型技术轮廓字型法采用直线段或Bezier曲线来描述字符的轮廓线，在加上一些表示宽度、基点、基线的控制信息而构成字符的压缩数据，采用区域填充算法最终生成各种字符。

第11讲

二维图形—种子填充

1．区域和区域填充在光栅图形中，区域是由相连的像素组成的集合，这些像素具有相同的属性值或者它们位于某边界线的内部。区域的表示有内点表示和边界表示两种形式。内点表示法枚举区域内的所有像素，通过给区域内的像素赋予同一属性值来实现内点表示。边界表示法枚举区域边界上的所有像素，通过给区域边界的像素点赋予同一属性值来实现边界表示。根据像素的属性值、边或顶点的简单描述，生成区域的过程称为区域填充。区域填充有种子填充和扫描转换填充。第11讲

二维图形—种子填充第11讲

二维图形—种子填充第11讲

二维图形—种子填充2．简单种子填充种子填充算法首先假定封闭轮廓线内某个已知点，然后开始搜索与种子点相邻且位于轮廓线内的点。如果相邻点在轮廓线内，则它们成为新的种子点；否则相邻点达到了区域的边界第11讲

二维图形—种子填充3．简单种子填充（续）（1）内点表示泛滥（漫水法）填充下面将以4连通区域为例，讨论内点表示泛滥填充算法。设（x,y）为区域内的一点，oldColor为区域的原色，newColor是将要填充的新颜色。取(x,y)为种子点，若该点颜色不等于oldColor，则该点在区域之外或已被填充过，对该点的处理结束；否则置该点的颜色为newColor，以它的上、下、左和右四个相邻像素点为种子点继续填充。

第11讲

二维图形—种子填充4．简单种子填充（续）（2）边界表示泛滥填充下面将以4连通区域为例，讨论边界表示泛滥填充算法。设（x,y）为区域内的一点，

boundaryColor为边界颜色，newColor是将要填充的新颜色。取(x,y)为种子点，若该点颜色等于

boundaryColor或newColor，则该点在边界上或已被填充过，对该点的处理结束；否则置该点的颜色为newColor，以它的上、下、左和右四个相邻像素点为种子点继续填充。

第11讲

二维图形—种子填充5．扫描线种子填充扫描线种子填充是一种适合于边界表示的四连通区域的填充算法。假设区域内部像素点颜色为oldColor,将要填充的新颜色为newColor。扫描线种子填充算法描述如下：（1）填充并确定种子点所在区段：从给定的种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点，则三元组（

y,xLeft,xRight）唯一确定了该区段。第11讲

二维图形—种子填充6．扫描线种子填充（续）（2）种子区段：将算法设置的堆栈置空，把第（1）步产生的三元组压入堆栈。（3）出栈：如果堆栈为空，则算法结束；否则，取栈顶元素(y,xLeft,xRight)，以纵坐标为y的扫描线为当前扫描线，［xLeft,xRight］为搜索区间。（4）填充并确定新的区段：在与当前扫描线上、下相邻的两条扫描线上，确定与区段（y,xLeft,xRight）连通且位于所讨论区域内的区段。第12讲

二维图形

—扫描转换填充

在矢量图形中，多边形用顶点序列来表示，为了在光栅显示器或打印机等设备上显示多边形，必须把它转换为点阵表示。这种转换称为扫描转换。扫描转换填充算法适用于规则边界的封闭区域，通常是将由顶点定义的多边形的边及其内部用预期的像素值进行填充，因此该填充方法又称为多边形的扫描变换。与种子填充算法不同的是，该算法不需要预先定义区域内部或边界的像素值。第12讲

二维图形

—扫描转换填充1．逐点判断算法逐点判断算法根据某种判断方法对绘图窗口的每个像素进行判断，看它们是否在已知多边形的内部，从而求出多边形内部的像素组成的集合。判断一个点是否在多边形内部的常用方法有以下几种：（1）射线法：从已知点发出射线与多边形的边相交，若交点个数为奇数，则点位于多边形内部，否则点位于多边形外部。使用该方法时要特别注意两种特殊情况，一种情况是射线与多边形的交点正好在多边形的一个顶点，另一种情况是射线过多边形的一条边。射线法最准确的描述方法是计算射线穿过多边形的次数，若穿过次数为奇数，则已知点在多边形内部，否则在多边形外部。第12讲

二维图形

—扫描转换填充2．逐点判断算法（续）（2）累计角度法：已知平面上一个点v。设多边形的顶点依次为P0,P1,…,Pn，其中起点与终点重合。如果各有向角∠PivPi+1的角度之和为零，则v在多边形的外部，否则它在多边形的内部。第12讲

二维图形

—扫描转换填充3．扫描线算法对于一个给定的多边形，用一组水平（垂直）的扫描线进行扫描，求出每条扫描线与多边形边的交点，这些交点将扫描线分割为相间排列的落在多边形内和外的线段，将落在多边形内的线段上的所有象素点赋以给定的多边形的颜色值。计算过程如下：a.

求交：计算扫描线与多边形各边的交点；b.

排序：把所有交点按递增顺序进行排序；c.

交点配对d.区间填色第12讲

二维图形

—扫描转换填充4．区域填充属性区域填充属性包括填充式样、填充颜色和填充图案等。用户可以对这些属性进行选择以表达某些信息。（1）填充式样：表示区域内部是空心的、实心的或是用图案填充的。（2）填充颜色：实心区域可以选择其填充颜色。（3）填充图案：用户定义或系统提供的图案，它们可以用来填充一个区域。第13讲二维图形裁剪

—线段裁剪1．窗口和视（图）区程序员用来定义草图的整个自然空间称为用户域(空间)。把用户指定的在用户域中任一区域称为窗口，也称为用户域的子域。窗口通常是矩形域，可以用它的左下角和右上角坐标来表示，或用左下角坐标及矩形的长、宽来表示。屏幕域（空间）是设备输出图形的最大区域，其中的点具有整数坐标。在屏幕域中指定的一个区域称为视区。视区一般定义为矩形，由左下角坐标和右上角坐标来定义，或由左下角坐标和坐标轴方向边框的长度来定义。第13讲二维图形裁剪

—线段裁剪2．窗口和视（图）区（续）窗口技术使用户便于观察感兴趣的部分图形，视区用于显示用户观察的结果。图形在窗口中的表示转换到视区中的表示需要进行坐标变换。

第13讲二维图形裁剪

—线段裁剪3．裁剪的原理裁剪的基本目的是判断图形元素是否部分或全部落在窗口区域之内，如果是，则进一步求出位于窗口内的部分。裁剪处理包括两个方面：判断图形元素是否在窗口内以及求图形元素与窗口的交。裁剪可以在用户坐标系（即用户空间坐标系）下相对于窗口的边框进行裁剪，只有落在窗口内的部分变换到视区；也可以把用户坐标转换为屏幕坐标，在屏幕坐标下相对于视区进行裁剪。先裁剪后变换和先变换后裁剪，这两种方法各有利弊。前者需要用到比较复杂的裁剪处理，后者则可能造成无效的生成（变换）运算。第13讲二维图形裁剪

—线段裁剪4．矢量裁剪法（1）线段与窗口关系判断如果线段的两端点在窗口内，那么线段完全在窗口内；如果线段的一个端点在窗口内，另一个在窗口外，则线段只有一部分在窗口内，线段与窗口的边有一个交点，该交点与窗口内的端点的连线为线段的可见部分；如果线段的两个端点都在窗口外，则需要进步计算线段是否与窗口相交，在有两个交点的情况下，这两个交点的连线为线段的可见部分。

第13讲二维图形裁剪

—线段裁剪5．矢量裁剪法（续）第13讲二维图形裁剪

—线段裁剪6．编码裁剪法如图10所示，将用户域用为9个区域，每个区域都有相应的编码，当线段的端点落在某个区域内时，对该端点进行相应的编码。从高位开始，每位编码如下：（1）第1位，端点在y=ymax上方则取1，否则取0；（2）第2位，端点在y=ymin下方则取1，否则取0；（3）第3位，端点在x=xmax右方则取1，否则取0；（4）第4位，端点在x=xmin左方则取1，否则取0。第13讲二维图形裁剪

—线段裁剪7．编码裁剪法（续）如果线段两端点的4位编码全为零，则线段全部在窗口内；如果两端点的4位编码按位进行与运算，结果为非零，则此线段全部在窗口之外；其他情况下，线段部分在窗口内，部分在窗口外。编码裁剪法的编码用于判断线段与窗口的关系。第13讲二维图形裁剪

—线段裁剪8．中点分割裁剪法

第14讲

二维图形裁剪—字符和多边形裁剪1．字符裁剪（1）矢量裁剪

把字符看成是线段（笔划）的组合，每一条线段单独进行裁剪。这种裁剪能产生令人满意的效果，但速度慢。（2）（单个）字符裁剪

把每个字符与包围它的一个矩形框相关联，当矩形框中某个点、或一条对角线或整个框在窗口内时，显示此字符。第14讲

二维图形裁剪—字符和多边形裁剪2．字符裁剪（续）（3）字符串裁剪

把字符串作为一个整体来处理，方法与单个字符裁剪类似，该字符串要么全部显示，要么都不显示。

第14讲

二维图形裁剪—字符和多边形裁剪

3．多边形裁剪

多边形裁剪以线段裁剪为基础。多边形由有序的线段组成，裁剪后的多边形仍应保持原多边形各边的连接顺序和多边形的封闭性。

第14讲

二维图形裁剪—字符和多边形裁剪4．多边形裁剪（续）（1）逐边裁剪法每次用窗口的一条边界对多边形进行裁剪，把落在窗口边框外侧的图形去掉，只保留在窗口边框内侧的图形，并把它作为下一次待裁剪的多边形。如图12所示，左边为原图，右边是经上窗口上边框裁剪后的图形。连续用窗口的四条边对原始多边形进行裁剪，最后得到所需的裁剪多边形。

第14讲

二维图形裁剪—字符和多边形裁剪5．多边形裁剪（续）第14讲

二维图形裁剪—字符和多边形裁剪6．多边形裁剪（续）（2）双边裁剪法双边裁剪法又称为Weiler-Atherton裁剪算法。设用户多边形为P1，窗口为多边形P2，每个多边形的顶点按顺时针方向排列，即多边形内部总在有向边的右侧。如图13所示，从P1的任一顶点出发沿多边形的边（顺时）行走，直到回到出发点为止。当两多边形相交时做如下处理：（1）若P1的边进入P2，则继续沿P1的边往前走，同时输出P1上从进入点到下一个交点之间的部分。（2）若P1的边从P2离开，则沿P2的边往前走，同时输出P2上从离开点到下一个交点之间的部分。返回离开点，继续沿P1往前走。第14讲

二维图形裁剪—字符和多边形裁剪7．多边形裁剪（续）第15讲

二维图形几何变换

—一般表示

图形变换一般是指将图形的几何信息经过几何变换后产生新的图形。图形变换既可以看作是图形不动而坐标系变动，变动后该图形在新的坐标系下具有新的坐标值，也可以看作是坐标系不动而图形变动，变动后的图形在坐标系中的坐标值发生变化。大多数几何变换（如平移、旋转和变比）是保持拓扑不变的，不改变图形的连接关系和平行关系。对于线框图形，通常是以点变换为基础，把图形的一系列顶点作几何变换后，连接新的顶点序列即可产生新的变换后的图形。对于用参数方程描述的图形，可以通过参数方程几何变换，实现对图形的变换。

第15讲

二维图形几何变换

—一般表示图形变换的数学基础是是矢量运算和矩阵运算。矢量运算包括矢量的和、差、长度、点积和叉积，矩阵运算包括矩阵的加法、减法、数乘和乘法。平面点的坐标可以用行向量（x,y）表示，也可以用列向量（x,y）T表示，这里T表示转置，即把行变成相应的列。设P(x,y),P’(x’,y’)分别是变换前和变换后的点。第15讲

二维图形几何变换

—一般表示1．平移变换设T=[Tx,Ty]表示平移量，则平移变换可以表示为：

第15讲

二维图形几何变换

—一般表示2．比例变换设