2D图形-变换.ppt

1、,第二章、二维图形,2.1 坐标体系 2.2 窗口与视区 2.3 剪取 2.4 几何变换 2.5 直线的生成 2.6 圆的生成 2.7 多边形填充,第二章,1,第二章,2,坐标体系,坐标体系,对图形的描述、图形的输入输出都是在坐标系中进行的。 1.世界坐标系 WC(World Coordinate System)：包括常用的直角坐标系、几何坐标系等各种坐标系来直接描述对象。或称为用户坐标系UC (User Coordinate System)，取值范围为整个实数域。 2.设备坐标系 DC(Device Coordinate System)图形的显示是在设备上进行的，在设备上描述图形的坐标系称为

2、 设备坐标系 DC(Device Coordinate System),取值范围受设备的输入输出 的精度以及画面，有效范围的限制。 屏幕上显示的图形均以其一个像素点单位为量化单位。,坐标体系,坐标体系,3.规范化坐标系 NC(Normalization Coordinate System)二维，取值范围0，1。 4.不同坐标系的转换:将世界坐标系中的对象转换成设备坐标系中的图形有两种方式： 直接转换。容易实现，可移植性较差。 规范化坐标系。,第二章,3,窗口与视区,第二章,4,坐标体系,使用建模坐标 变换构造 世界坐标场景,世界坐标转换 为观察坐标,使用窗口-视口 描述将观察坐 标映射到 规范

3、化坐标,使用窗口-视口 描述将观察坐标 映射到规范化坐标,2020/8/23,5,窗口:在WC中定义一个矩形区域,该区域内的对象将予以显示。 视区:在VC(观察坐标系)中定义一个矩形区域,所有在窗口内的对象都将显示在该区域中。,窗口与视区,视区转换,xw-xwmin xv-xvmin xwmax-xwmin xvmax-xvm yw-ywmin yv-yvmin ywmax-ywmin yvmax-yvmin xv-xvmin xv=xvmin+(xw-xwmin) xwmax-xwmin yv-yvmin yv=yvmin+(yw-ywmin) ywmax-ywmin 设： xvmax-xv

4、min yvmax-yvmin Sx= , Sy= xwmax-xwmin ywmax-ywmin a=xvmin-Sxxwmin ，b=yvmin-Syywmin 则 xv=Sx*xw+a yv=Sy*yw+b,窗口与视区,第二章,5,讨 论,窗口与视区,第二章,6,选择不同的Window,显示在同一Viewport中窗口位置不同,显示不同的图形。窗口位置不变,只变大小,出现变焦效果。 选择不同的Window,显示在不同Viewport中，显示图形有个调度问题。 如果Window的X:Y与Viewport的X:Y不等时，图形将变形。,第二章,7,二维图形,2.3 剪 取,一、点的剪取 二、直

5、线的剪取 三、多边形的剪取 四、文本的剪取,点的剪取,点的剪取,第二章,8,任何图形都可能包含点、直线、字符、和多边形乃至直线， 但它们都可以分解成点的集合。所以点的剪取是图形剪取中最基本的问题。 假设窗口的左下角坐标为(xmin,ymin),右上角坐标为(xmax,ymax)，对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式：xmin = x = xmaxand ymin = y = ymax否则，P点就在窗口外。,第二章,9,二维图形,2.3 剪 取,一、点的剪取 二、直线的剪取 三、多边形的剪取 四、文本的剪取,直线的剪取,第二章,10,直线的剪取,直线与窗口的关系通常有以

6、下三种情况： 整个线段全在窗口内； 整个线段全在窗口外； 线段部分在窗口外，部分在窗口内。 当窗口采用凸多边形时，任何一条直线只会至多有一段在窗口内： 当一条直线的两个端点全在窗口内时，该直线整个在窗口内 当一条直线的两个端点，一个在窗口内，一个在窗口外时，该直线部分在窗口内，部分在窗口外 当一条直线的两个端点全在窗口外时，该直线可能整个在窗口内，也可能部分在窗口内，部分在窗口外,Cohen-Sutherland算法基本原理,直线的剪取,第二章,11,这是一个最早最流行的线段剪取算法。该算法通过初始测试来减少要计算的交点数目从而加快线段剪取算法的速度。每条线段的端点都赋以四位二进制码，称为区域

7、码（region code）,用来标识出端点相对于剪取矩形边界的位置。区域通过如下所示的边界设定。 区域码的各位指出端点对于剪取矩形边界 的四个相对坐标位置： 左，右，上，下。将区域码的各位从右到左编号，则坐标区域与各位的关系为：上 下 右 左 X X X X任何位赋值为1，代表端点落在相应的位置上，否则该位为0。若端点在剪取矩形内，区域码为0000。如果端点落在矩形的左下角，则区域码为0101。,Cohen-Sutherland算法基本原理,直线的剪取,第二章,12,如果两端点的编码均为0000，表示该直线在窗口内。 如果两端点的编码相与不为0000，表示该直线在窗口外。 如果两端点的编码不

8、全为0000，但相与为0000，则该直线部分可见，需计算直线与窗口的交点，确定哪一部分可见。,一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一下规则：,直线的剪取,Cohen-Sutherland算法描述,Cohen-Sutherland算法的关键在于总是先确定窗口外的一个端点，这样位于此端点至与窗口边的交点之间的线段必为不可见，故可将其抛弃。然后利用此法处理剩余的部分。Cohen-Sutherland算法描述如右：,BOOL done,draw;done表示是否完成，draw表示是否可见；Unsigned char code1,code

9、2；端点1，端口2的编码 While (!done) begin if (判断code1,code2,若为第一种情况) begin done = TRUE; draw = TRUE; end else if (为第二种情况) begin done = TRUE; draw = FALSE; end else if(检查code1 ,若在窗口内) begin 交换端点及端点的编码；以左，右，下，上的次序对端点1进行判断及求交；将交点的值赋给端点1； end end,第二章,13,Cohen-Sutherland直线剪取算法小结,直线的剪取,第二章,14,本算法的优点在于简单，易于实现。他可以简单

10、的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。中点求交法是对于硬件很适合的，它可以用左右移位来代替乘除法，这样就大大加快了速度。另外，本算法对于其他形状的窗口是否同样有效就值得讨论了，这也证明了在图形算法中，没有几个是对大多数情况有效的。,Cyrus-Beck算法基本原理,直线的剪取,第二章,15,Cyrus-Beck算法的基本思想是采用法矢量的概念来判定线段上的一点是在窗口之内，之外，还是在窗口的边界上。对任意凸多边形，其边界上任一处的内法矢量可用下面的矢量点积表示： n(ba)0b为多边

11、形边界上另外一点。 ni与其他任一从a到b的矢量之间的夹角一定使：n(ba)0 。,直线的剪取,第二章,16,Cyrus-Beck算法基本原理,如果A是凸区域边界上的一点，n是凸区域边界在A点的内法向量，则对于线段P1P2 上的一点P(t)，满足下式： 若nP(t)A0，则表示P(t)A指向区域的外部; 若nP(t)A=0，则表示P(t)A与包含A的边界重合且与法矢量n垂直； 若nP(t)A0，则表示P(t)A指向区域的内部。 由此可知，P(t)满足nP(t)A=0的t值的点即为直线与边界的交点。,A,直线的剪取,Cyrus-Beck算法基本原理,Cyrus-Beck算法中对于线段的可见性是这

12、样判断的，设：内法矢量与连接线段上一点至一边界上一点的矢量的点积为：niP(t)-Ai(i=1,2,3.)与式子P(t)=P1 +(P2P1)t(0t1) 合并得：niP1+(P2P1)t-Ai(i=1,2,3.)线段上点在边界上的条件：niP1 +(P2P1)t-Ai=0 (i=1,2,3.) 令：D=P2P1；wi=P1Ai，可得 wini t= - Dni 如果Dni=0，则要么D垂直于ni，要么P2=P1 点与区域和窗口的关系可描述如下： 如果wini0，表示点位于区域和窗口之外； 如果wini0，表示点位于区域和窗口边界上； 如果wini0，表示点位于区域和窗口之内。,第二章,17,

13、第二章,18,直线的剪取,Cyrus-Beck算法基本原理,对于t值的选择：首先，要符合0t1；其次，对于凸窗口来说，每一个线段与其至多有两个交点，既有两个相应的t值。所以我们可以把计算出的t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。这样，只要找出下限组中的最大值及上限组中的最小值，就可确定线段了。 分组的依据是： 如果Dni0，则计算出的值属于上限组 如果Dni0，则计算出的值属于下限组 有了这些，整个算法就可以建立了。,直线的剪取,Cyrus-Beck直线剪取算法描述,第二章,19,置下限最小值tL=0,上限最大值、tU=1 while 对于每

14、一个窗口边i do begin if Dni=0 then If wini0 then /*寻找下限t值*/ If t1 then tL=max(t,tL) else /*寻找上限t值*/ if t0 then tU=min(t,tU) end if tL tU then 画从P(tL)至P(tU)的线段 end of algorithm,Cyrus-Beck算法小结,该算法比Cohen-Sutherland算法适用的范围更广一些，它可以对任何凸多边形适用，但对于凹多边形就失效了,为了解决这个问题，我们又引入了下面的算法：叉积法，旋转法。,直线的剪取,第二章,20,凸多边形判定叉积法,直线的剪

15、取,第二章,21,如果各叉积全部为零，则多边形各边共线； 如果各叉积一部分为正，一部分为负，则多边形为凹多边形； 如果所有叉积全部大于零或等于零，则多边形为凸多边形，此时沿着边的正向，内法矢量指向其左侧； 如果所有叉积全部小于零或等于零，则多边形为凸多边形，此时沿着边的正向，内法矢量指向其右侧。,直线的剪取,第二章,22,旋 转 法,依次平移多边形使Vi重合于坐标原点，且绕原点旋转多边形窗口，使Vi+1落在正方向轴上： 如果所有Vi+2的y分量符号相同，则多边形为凸多边形，否则多边形为凹多边形； 如果Vi+2的y分量为零，则Vi，Vi+1，Vi+2三个定点共线； 如果所有Vi+2的y分量为零，

16、则多边形退化为一条直线。,直线的剪取,第二章,23,旋 转 法,直线的剪取,旋转法切割凹多边形,假定多边形的定点使按时针方向给定的，可以很方便的利用旋转法将一个凹多边形分割为若干个凸多边形。其算法描述如右：,while 对于多边形的每一个顶点Vi do begin 平移多边形使Vi与坐标系原点重合 绕原点按顺时针方向旋转多边形使Vi+1落在正向x 轴上 if Vi+2的y分量大于或等于零，then goto 1 /* 否则Vi+2的y分量小于零，则多边形为凹多边形， 进行分割 */ 计算与x轴相交的多边形边的交点，并沿x轴分割 多边形。 /* 这时多边形分割成两个多边形，其中一个位于 轴上方，

17、一个位于轴下方。*/ 递归的对分割成的新多边形重复执行这个算法，直 至每一个多边形均为凸多边形为止 end end of algorithm,第二章,24,直线的剪取,第二章,25,切割算法小结,这种多边形分割算法并不是最优分割，且不适用于自相交的多边形分割。 接下来讨论一下分割多边形过程中的一个重要问题，也就是上述算法怎样将原多边形中的点分配给两个新多边形。书中所给的算法使这样处理的：找到在Vi+1右边且与它最近的一个交点，将位于x轴上方的点和这个交点组成一个新多边形，将位于x轴下方的点和这个交点组成另一个多边形。可以发现，它并没有谈及如何处理Vi和Vi+1，这时这两个点均在x轴上。,第二章

18、,26,切割算法小结,所以在算法编制过程中特意研究了一下，发现如下规律： 将Vi和交点加入x轴上方的多边形中；将交点和Vi+1加入到x轴下方的多边形中。注意，为了保证多边形的顶点按时针方向给定，将上述的点加入多边形重视一定要按照(1)中提到的顺序加入。 对于其它点的处理我们并不按照步骤五的方法，而是只将从Vi+1起逆时针走碰到的所有的点都加入到x轴下方的多边形中去，知道碰到交点为止。(注意：上述方法是假设多边形的点是按照逆时针顺序给出的，若是按照顺时针顺序给出，则只要将(1)，(2)中的点的顺序颠倒即可),直线的剪取,切割算法小结,右图中（假设多边形的点是按逆时针给出），我们看到这时应该进行分

19、割，按上述算法，可以得到两个多边形：Polygon1=v1,p,v4,v5,v6,v7,v8Polygon2=v2,v3,p，易发现，从Vi+1到交点之间的点均在轴下方。算法中正是利用了这一点，简化了过程。 由此得到分割多边形的算法，这样可以扩展Cyrus-Beck算法了。具体步骤如下： 对输入的多边形进行分割，变换成若干个凸多边形。 用每一个多边形使用Cyrus-Beck算法对所有直线进行剪取。 将每个多边形的剪取结果合成。,直线的剪取,第二章,27,第二章,28,二维图形,2.3 剪 取,一、点的剪取 二、直线的剪取 三、多边形的剪取 四、文本的剪取,多边形的剪取,第二章,28,多边形的剪

20、取,多边形的剪取可分解为一条一条线段进行。如考虑其封闭性，则一个窗口对一个多边形的剪取可产生一个或者多个多边形。 下面将介绍Sutherland-Hodgman和Weiler-Atherton算法。,通过对单一边或面的剪取来实现多边形的剪取。即在算法中，剪取窗口的每一边将逐次对原多边形和每次剪取所生成的多边形进行剪取。,Sutherland-Hodgeman多边形剪取算法基本思想,多边形的剪取,第二章,29,多边形的剪取,第二章,30,Sutherland-Hodgeman多边形剪取算法基本思想,算法的每一次输出（包括中间结果）都是一个多边形的顶点表， 且所有顶点均位于相应窗口剪取边或面的可见

21、一侧。由于多边形的每一条边需要与剪取边或面分别进行比较，因此只需要讨论单条边和单个剪取边或面之间可能的位置关系。假设S,P为多边形的两个相邻顶点，且S为该边的起点，P为该边的终点，则变SP与剪取边或面之间只有4中可能的关系。,第二章,31,多边形的剪取,Sutherland-Hodgeman多边形剪取算法基本思想,由上可见，每一次将多边形的边与剪取边或面比较后，输出一个或两个顶点，也可能无输出点。如果SP边完全可见，则输出P点，不必输出起点S，因为顶点使按顺序处理的，S是作为前一边的终点输出的。如果SP边完全不可见，则无输出。如果SP边部分可见，则SP边可能进入或离开剪取边或面的可见一侧。 如

22、果SP边离开剪取边或面的可见一侧，则输出SP与剪取边或面焦点。如果SP边进入剪取边或面的可见一侧，则输出两点，一个为SP与剪取边或面的交点，一个是P点。 对于多边形的第一个顶点，只需判断其可见性。如果可见，则输出且作为起点S；否则无输出，但还是要作为S保存，以便后续点处理。 对于最后一条边PnP1，其处理方法是：标志第一顶点为F，这样最后一条边则为PnF，可与其他边作相同的处理。,Sutherland-Hodgeman多边形剪取算法描述,while 对于每一个窗口边或面 do begin if P1在窗口边的可见一侧 then 输出P1 for I=1 到 n do begin if Pi在窗

23、口边的可见一侧 then if Pi+1在窗口边的可见一侧 then 输出Pi+1 else 计算交点并输出交点 else if Pi+1在窗口边的可见一侧，then 计算交点并输出交点，同时输出Pi+1 endend end of algorithm,多边形的剪取,第二章,32,Sutherland-Hodgeman多边形裁剪算法小结,对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。 解决这个问题有多种方法，一是把凹多边形分割成

24、若干个凸多边形，然后分别处理各个凸多边形。而是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是Weiler-Atherton算法。,多边形的剪取,第二章,33,第二章,34,Weiler-Atherton多边形剪取 算法主要术语及数据结构,主多边形：用来被剪取的多边形，可以是凸的、凹的、或是有孔的； 剪取多边形：用来剪取主多边形的多边形，也可以是凸的、凹的、或是有孔的； 主多边形的顶点表：用来定义主多边形； 剪取多边形的顶点表：用来定义剪取多边形； 进点表：包含主多边形进入剪取多边形内部时的交点； 出点表：包含主多边形离开剪取多边形内部时的交点； 多边形的内表：位于剪取

25、多边形内部的主多边形的边界以及位于主多边形内的剪取多边形的边界（其构成主多边形的孔）； 主多边形的外表：位于剪取多边形外部的主多边形的边界以及位于主多边形内的剪取多边形的边界，但不包括位于主多边形外的剪取多边形的边界。,多边形的剪取,Weiler-Atherton多边形剪取算法原理,首先从进入交点(进点，即蓝色大箭处）开始，沿主多边形的外部边界(即按顺时针方向)跟踪，直至找到它与剪取多边形的另一交点(出点)为止；在交点处向右转，再沿剪取多边形的外部边界(按顺时针方向)跟踪，直至找到其与主多边形的一个交点(进点)后继续向右转，再次沿主多边形的边界跟踪；重复执行上述过程，直至再回到算法的起始交点(

26、进点)为止。但遇到多边形的内部边界时，按逆时针方向跟踪。,多边形的剪取,第二章,35,Weiler-Atherton多边形剪取算法描述,多边形的剪取,第二章,36,多边形的剪取,第二章,37,Weiler-Atherton多边形剪取算法示例,C2,C3,C4,C1,S1,S7,S6,S5,S3,S2,S4,I1,I2,I3,I4,I5,I6,I7,I8,S1,I2,I3,S2,I4,S3,I5,S4,S5,S6,S7,I6,I7,I8,I1,S1,I2,I3,S2,I4,S3,I5,S4,S5,S6,S7,I6,I7,I8,I1,C1,C2,C3,I1,I2,I3,I4,I5,I6,I7,I8

27、,C4,C1,C1,C2,C3,I1,I2,I3,I4,I5,I6,I7,I8,C4,C1,S1,S1,Weiler-Atherton多边形剪取算法示例,多边形的剪取,第二章,38,C2,C3,C4,C1,S1,S7,S6,S5,S3,S2,S4,I1,I2,I3,I4,I7,I8,S5,S8,S9,S1,I2,I3,S2,I4,S3,S4,S5,S6,S7,I1,C1,C2,C3,I1,I2,I3,I4,C4,C1,S8,S9,S1,S1,I2,I3,S2,I4,S3,S4,S5,S6,S7,I1,C1,C2,C3,I1,I2,I3,I4,C4,C1,S8,S9,S1,Weiler-Athe

28、rton多边形剪取算法示例,多边形的剪取,第二章,39,S1,I3,I4,S2,S3,S4,I1,I2,S5,S6,S7,I5,S8,I6,S5,C1,C2,C3,S1,I4,I5,C4,I6,I1,C1,C5,I2,C6,I3,C7,C8,C5,S3,S1,I3,I4,S2,S3,S4,I1,I2,S5,S6,S7,I5,S8,I6,S5,C1,C2,C3,S1,I4,I5,C4,I6,I1,C1,C5,I2,C6,I3,C7,C8,C5,Weiler-Atherton多边形剪取算法小结,多边形的剪取,第二章,40,保证Weiler-Atherton算法的工作可靠性，要先判定主多边形和剪取多

29、边形有无交点以及它们的位置关系。 左图若主多边形的一个定点或边位于剪取多变形边界上时，则不能看作交点。 右图中，应该考虑主多边形和剪取多边形之间交点的正确位置，以免形成退化的多边形。 标记为“X”的点应看作交点，而标记为圆点的点则不是交点。,第二章,41,二维图形,2.3 剪 取,一、点的剪取 二、直线的剪取 三、多边形的剪取 四、文本的剪取,文本的剪取,第二章,42,Stroke,文本的剪取,文本是由字符组成的。一般地，字符可分为两种：一种是矢量字符，即由若干个线段或笔画构成；一种是点阵字符，即由点阵来表示。所以文本的剪取与多边形的剪取不尽相同，它按剪取的精度可分为笔画剪取、字符剪取、和字符

30、串剪取等三种类型。 笔画剪取是指在显示文本时，把窗口以外的字符予以剪取，并且对与窗口相交的字符，也把其在窗口以外的部分予以剪取。若是矢量字符，可以按直线的剪取方法来剪取与窗口相交的字符。若是点阵字符，则可按点的的剪取方法来剪取与窗口相交的字符。,文本的剪取,文本的剪取,第二章,43,字符剪取是指在显示文本时，把窗口以外的字符予以剪取，同时与窗口相交的字符也予以剪取。 字符串剪取是指在显示文本字符串时，若字符串与窗口相交，则该字符串被整个剪取。一般字符串剪取采取字符串包围盒来判断字符串与窗口的关系。,char,ch,String,String,第二章,44,二维图形,2.3 几何变换,一、概 述

31、 二、平移变换 三、缩放变换 四、旋转变换 五、变形变换 六、组合变换,第二章,45,概 述,概 述,图形变换：是一种几何变换，在二维图形处理过程中，常常需要对平面图形的形状、尺寸、显示方向和显示位置进行修改，来达到改变图形的目的。 几何变换：是一种线性变换，对原来图形中的一点坐标通过变换生成一个新的点坐标；对原来图形中的一条直线的变换是通过直线上的两点作变换生成新的端点坐标，然后连接这两个新的端点，便得到变换后的直线；类似的，可以进行各种图形的几何变换。几何变换的表示采用3*3矩阵的形式，称为变换矩阵，点的坐标表示采用齐次坐标形式，故几何变换操作的过程是将变换矩阵M作用于齐次坐标点P生成新的

32、坐标点P,即P=PM，下边讨论4中基本坐标变换。,第二章,46,二维图形,2.3 几何变换,一、概 述 二、平移变换 三、缩放变换 四、旋转变换 五、变形变换 六、组合变换,点的平移变换是指该点在X轴和Y轴方向上分别移动一段距离。设图形上点P(x,y)，将在X轴和Y轴方向分别移动Tx和Ty，结果生成新的点P(x,y),如图所示，则有 x=x+Tx， y=y+Ty 其中TX,TY称为点在X轴和Y轴上的位移。 用齐次坐标和矩阵形式可表示为： x,y,1=x,y,1 令二维平移变换矩阵为：T2(Tx,Ty)= ；如果Tx 或Ty大于零，则点向右或向上移动；如果Tx或Ty小于零，则点向左或向下移动。,

33、平移变换,平移变换,第二章,47,1 0 0 0 1 0 Tx Ty 1,1 0 0 0 1 0 Tx Ty 1,第二章,48,二、二维图形,2.3 几何变换,一、概 述 二、平移变换 三、缩放变换 四、旋转变换 五、变形变换 六、组合变换,点的缩放是指将该点沿X轴和Y轴方向按比例缩小或放大的变换。设图形上的点P(x,y)，在X轴和Y轴方向分别作Sx和Sy的缩放，结果生成新的点坐标P(x,y)，如图所示，则 x=x . Sx，其中TX,TY称为点在X轴和Y轴上的位移。 y=y . Sy 用齐次坐标和矩阵形式可表示为： x,y,1=x,y,1 令二维缩放变换矩阵为： S2(Sx,Sy)=,缩放变

34、换,缩放变换,第二章,49,Sx 0 0 0 Sy 0 0 0 1,Sx 0 0 0 Sy 0 0 0 1,第二章,50,缩放变换,缩放变换,如果|Sx|或|Sy|大于1，则表示图形在X轴方向或Y轴方向放大； 如果|Sx|或|Sy|小于1，则表示图形在X轴方向或Y轴方向缩小； 如果|Sx|或|Sy|等于1，则表示图形在X轴方向或Y轴方向不变； 如果Sx或Sy小于零，则表示图形在X轴方向或Y轴方向作镜面变换。,第二章,51,二维图形,2.3 几何变换,一、概 述 二、平移变换 三、缩放变换 四、旋转变换 五、变形变换 六、组合变换,旋转变换,旋转变换,第二章,52,点的旋转变换是只将点绕坐标原点

35、旋转一角度的坐标变换。设有图形上点P(x,y)，将其绕原点旋转变换角度(假设按逆时针旋转为正角)，结果生成的新的点坐标P(x,y)。将点P绕原点做逆时针旋转角度的变换看作将坐标系绕原点做顺时针旋转角度的等价变换。 x=xcos-ysin 其中为点绕原点旋转的角度(逆时针为正， y=xsin-ycos 顺时针为负)。用齐次坐标和矩阵形式可表示为x,y,1=x,y,1 令二维旋转变换矩阵为R2()=,cos sin 0 -sin cos 0 0 0 1,cos sin 0 -sin cos 0 0 0 1,第二章,53,二维图形,2.3 几何变换,一、概 述 二、平移变换 三、缩放变换 四、旋转变

36、换 五、变形变换 六、组合变换,变形变换,变形变换是用来产生一个目标图形的失真的变换。现考虑y-变形和x-变形两种： y-变形是将点P(x,y)变换到点P(x,y),使x=xy=yshy+y(shy0) 其中shy为变形系数。当shy大于零时，表示向上变形，如一条垂直线变形后将向上移动，一条水平线变形后将向上倾斜；当shy小于零时，表示向下变形，如一条垂直线变形后将向下移动，一条水平线变形后将向下倾斜。,变形变换,第二章,54,变形变换,变形变换,第二章,55,x-变形变换是指将点P(x,y)变 换到点P(x,y)应有 x=x+yshx (shx0) 其中shx为变形系数，shx的符y=y 号

37、决定了图形向右或向左变形 令x-变形变换矩阵和y-变形变换矩阵分别为： shx(shx)= shy(shy) =,1 shy 0 0 1 0 0 0 1,1 0 0 shx 1 0 0 0 1,第二章,56,二维图形,2.3 几何变换,一、概 述 二、平移变换 三、缩放变换 四、旋转变换 五、变形变换 六、组合变换,第二章,67,组合变换,组合变换,实际上，一般的图形变换更多的是组合变换，即有一系列基本的几何变换组合而成的，则组合变换矩阵也可由一系列基本几何变换矩阵的乘积来表示，矩阵的乘法满足结合律，但不满足交换律。下面将举例说明组合变换的方法。,组合变换举例（一）,组合变换,第二章,58,例

38、:对一线段先放大2倍(即Sx=Sy=2)，再平移Tx=10,Ty=0。 解:设点(x,y)为线段上的任意一点,点(x,y)为点(x,y)放大后的坐标则:设点(x,y)为点(x,y)经平移后的坐标为：x,y,1= x,y,1T2(10,0)则： x,y,1= x,y,1T2(10,0)=x,y,1S2(2,2)T2(10,0),x,y,1=x,y,1S2(2,2),组合变换举例（一）(续),令：M=S2(2,2)T2(10,0)= = M即为组合变换矩阵。 设线段的两端点坐标为(x1,y1) 和(x2,y2)，经M变换后，得到新的坐标(x1,y1)和(x2,y2)，连接这两个新的坐标点便生成了变

39、换后的线段。,2 0 0 0 2 0 0 0 1,1 0 0 0 1 0 10 0 1,2 0 0 0 2 0 10 0 1,组合变换,第二章,58,组合变换举例（二）,组合变换,第二章,59,例：对一图形，绕平面上的一点(Cx,Cy) 作旋转变换，旋转角度为， 计算其变换矩阵。 解：旋转变换是绕坐标原点旋转的，此处不能直接使用旋转变换，应先将点(Cx,Cy)平移至原点，然后作旋转变换，最后再把该点移回原处。设点(x,y)为图形中的点，点(x,y)为点(x,y)经变换后的坐标，则:x,y,1 = x,y,1 = x,y,1T2(-Cx,-Cy)R2()T2(Cx,Cy)则组合矩阵为：M=T2(

40、-Cx,-Cy)R2() T2(Cx,Cy) =,cos sin 0 -sin cos 0 0 0 1,1 0 0 0 1 0 -Cx -Cy 1,1 0 0 0 1 0 Cx Cy 1,第二章,60,二维图形,2.3 直线的生成,一、概 述 二、DDA直线生成算法 三、对称DDA直线生成算法 四、Bresenham直线生成算法,概 述,概 述,第二章,61,在计算机产生的图形中，用到大量的直线，画好直线是非常有意义的，其一般的准则是： 线条应该显得笔直：由连续点组成的直线要显示在离散网格的平面上，一定会有不经过网格的点，如左下图。在这种情况下，必须选择靠近直线的网格点来逼近这条直线。若选择的

41、好，线就显得较直；否则就会较弯曲，如右下图。,概 述,概 述,第二章,62,直线端点位置应该准确：画出的线段如果不准确，往往会使两条线之间不能很好的镶接，如右图。 直线浓度应该均匀：线段的浓度与单位线段中所显示的点数成正比。要保持线段的浓度均匀端点应该等距分布。只有宇宙平行和成45的线才能做到。,第二章,63,概 述,概 述,直线浓度应该与线段的长度和斜率无关：要取得均匀的线段浓度，应该保持每单位长度的点数是个常数。一般，采用线段的近似长度，以及生成直线的算法，使在线段近似长度范围内保持线段浓度均匀。 显示线段的速度应快：生成直线可用软件和硬件来实现，一般情况下，硬件要比软件实现得快。,第二章

42、,64,二维图形,2.3 直线的生成,一、概 述 二、DDA直线生成算法 三、对称DDA直线生成算法 四、Bresenham直线生成算法,DDA直线生成算法原理,直线的微分方程表示为：dx/dy = x/y设直线的斜率小于等于1，起点坐标为(xa,ya)，终点坐标为(xb,yb)，则方程求解步骤分为：x0= xa +0.5，xn=xn-1+1y0= ya +0.5，yn=yn-1+y/x其中：x=xb -xa，y=yb-ya上述解表示x方向积分步长为1，y方向增量为y/x。,DDA直线生成算法,第二章,DDA直线生成算法原理,由于屏幕上的坐标为整数坐标，则真正作为输出显示为：y输出=trunc

43、(yn)，其中函数trunc()是指舍尾的正数。因此y输出和yn 之间的量化误差最大为1。为了改善这方面的误差，使y0的初值增加0.5,使量化误差在(-0.5,0.5)范围之间。同理，若直线斜率大于1，则上述方程的求解步骤可分为：x0=xa+0.5，xn=xn-1+x/y，y0=ya+0.5，yn=yn-1+1，其中x，y意义同上。上述解表示y方向积分步长为1，x方向增量为x/y,其他同上。,DDA直线生成算法,第二章,DDA直线生成算法描述,if |xb-xa|yb-ya| then计算直线在y方向上的增量：length=|yb-ya| else 计算直线在x方向上的增量：length=|x

44、b-xa| 计算x方向的单位增量：dx=(xb-xa)/length 计算y方向的单位增量：dy=(yb-ya)/length 置初值：x=xa+0.5，y=ya+0.5 for i=1 to length do begin 输出点(trunc(x), trunc(y) 计算下一个点坐标 x=x+dx，y=y+dy end end of algorithm,DDA直线生成算法,第二章,66,DDA直线生成算法小结,优点：在同一坐标上,不可能 连续停留两次。 缺点：在本算法中，开始需要执行一个除法y/x 或 x/y来确定增量，这样用硬件来实现比较复杂和昂贵，用软件实现相对容易些，但效率较低。,D

45、DA直线生成算法,第二章,67,第二章,68,二维图形,2.3 直线的生成,一、概 述 二、DDA直线生成算法 三、对称DDA直线生成算法 四、Bresenham直线生成算法,第二章,69,对称DDA直线生成算法,对称DDA直线生成算法,对称DDA直线生成算法是在DDA算法的基础上，引入N变量，直线方程表示为:dx/dn=x/N， dy/dn=y/N 其解为：x0=xa+0.5 xn=xn-1+x/N 其中 x=xb-xa， y0=ya+0.5 yn=yn-1+y/N y=yb-ya 。 基本思想是通过移位来实现坐标点的计算。问题是如何选择N，使直线生成的速度和质量最好？要求1/2Max(x/

46、N,y/N)1令：N=2INT(log2Max(x,y)+1因为:2log2Max(x,y)N=2INT(log2Max(x,y)+12log2Max(x,y)+1 Max(x,y)N2Max(x,y)所以：1/2max(x/N,y/N)1,第二章,69,对称DDA直线生成算法,对称DDA直线生成算法,优点：算法简单，尤其适用实现，因为它无乘除， 只有移位操作 缺点：在同一坐标上可能连续停留两次，但 不可能连续停留三次,第二章,70,二维图形,2.3 直线的生成,一、概 述 二、DDA直线生成算法 三、对称DDA直线生成算法 四、Bresenham直线生成算法,Bresenham直线生成算法原

47、理,Bresenham直线生成算法,第二章,设直线斜率小于1，即xy,x方向的步长总是1， y方向是否有变化，取决于直线的理论值与假设点之间的误差值大小。考虑第i步,即点Pi, 它的前一点Pi-1是最靠近直线的坐标值, 其坐标为(r,q),则Pi的坐标有两种选择：Si (r+1,q)和Ti (r+1,q+1)。取哪一点需判别理论值和这两个假设点之间误差S,t的大小。若St(或S-t0),则取点Ti，反之取点Si。,71,Bresenham直线生成算法,Bresenham直线生成算法原理,假设直线是从(xa,ya)至(xb,yb)，如果把直线平移使点(xa,ya)与原点重合，则直线方程可写成y=

48、y/xx，其中：x=xb-xa， y=yb-ya。则S,t可用下式计算：S=y/x(r+1)-qt=(q+1)-y/x(r+1)S-t=2y/x(r+1)-2q-1 x(S-t)=2(ry-qx)+2y-x 其中：x0。 令di=x(S-t)，则di与S-t的符号相同只要判别di的符号就可确定下一点的坐标是Si还是Ti。,第二章,71,第二章,72,Bresenham直线生成算法,Bresenham直线生成算法原理,于是di=2(ry-qx)+2y-x；当r=xi-1，q=yi-1时， di=2 xi-1 y-2yi-1x+2y-x di+1=2xiy-2yix+2y-x di+1-di=2y

49、(xi-xi-1)-2x(yi-yi-1) di+1=di+2y(xi-xi-1)-2x(yi-yi-1) 因此，di的递推公式为： d1=2y-x di+1= di+2y当di0时，取Si (xi-1+1,yi-1) di+1= di +2y-2x 当di0时，取Ti (xi-1+1,yi-1+1),Bresenham直线生成算法描述,Bresenham直线生成算法,第二章,73,计算x和y方向的增量：dx=|xb-xa|，dy=|yb-ya| 计算递推公式的初值d1: d=2dy-dx 计算两个单位增量：incr1=2dy , incr2=2(dy-dx) if(xaxb) then 置起

50、点为x=xb，y=yb，置终点为xe=xa, ye=ya else 置起点为x=xa，y=ya，置终点为xe=xb，ye=yb 输出起点(x,y) while(xxe) do begin x=x+1 if(d0) then d=d+incr1 else y=y+1，d=d+incr2 输出点(x,y) end end of algorithm,Bresenham直线生成算法小结,本算法的前提是直线斜率小于1，若直线斜率大于1，可用以上方法同样推出di的递推公式。 优点： 无乘除法(计算坐标时)； 在同一坐标上不可能连续停留两次。,Bresenham直线生成算法,第二章,74,圆的生成算法原理,

51、根据圆的方程：(x2+y2)=R2用扫描线方式生成圆时，会出现x方向增量取1，则y=(R2-x2)1/2, 这种方法，既增加了运算复杂性，又会产生点集疏密不均的现象：当x=0时，圆周上的切线斜率为零；当x接近R时，圆周上的切线斜率趋向无穷大，因此出现靠近y轴处点集较密集、平坦，但靠近x轴处间隔较大、陡直。为了克服这一现象，可以使x值的变化范围从0到R/21/2，即处为止，同时对于每一组(x,y)值，利用对称求出其它7个点坐标。 Bresenham圆算法的基本思想是寻找最接近于实际圆周上的点。,圆的生成算法,第二章,75,圆的生成算法原理,现仅讨论八分之一圆周，即x从0到R/21/2范围，所以F

52、，G的情况不必列入在内。对于Pi-1的下一点Pi只有两种可能，即Si(xi-1+1,yi-1)和Ti(xi-1+1,yi-1-1)误差公式：D(Si)=(xi-1+1)2+(yi-1)2-R2 D(Ti)=(xi-1+1)2+(yi-1-1)2-R2当|D(Si)|D(Ti)|，则Ti更接近于圆周，选择Ti当|D(Si)|D(Ti)|，则Si更接近于圆周，选择Si令di=|D(Si)|-|D(Ti)|则di0，取Ti di0，取Si,圆的生成算法,第二章,76,圆的生成算法原理,情况C：因为Si在圆外，所以D(Si)0，因为Ti在圆内， 所以D(Ti)0 所以di=D(Si)+D(Ti) 情况

53、A,B：从圆上看，Si更接近于圆周，选择Si(应属于di0情况） 因为Si,Ti都在圆内或圆上，即D(Si)0， D(Ti)0，所以用式di=D(Si)+D(Ti)(di0,取Si)判别即可。 情况D,E：从圆上看，Ti更接近于圆周，选择Ti (应属于di0情况）因为Si，Ti都在圆外或圆上，即D(Si)0，D(Ti)0，所以用式di=D(Si)+D(Ti)(di0,取Ti)判别即可。 综上所述，得出，只要计算下式di=D(Si)+D(Ti)的符号，便可选定Si或Ti作为下一点。,圆的生成算法,第二章,77,第二章,78,圆的生成算法,圆的生成算法原理,设x0=0，y0=R，则S1为(1,R)

54、，T1为(1,R-1)，d1=(12+R2-R2)+(12+(R-1)2-R2=3-2R设Pi-1为(xi-1,yi-1)，则取下一点Si (xi-1+1,yi-1)，Ti (xi-1+1,yi-1-1)， 则：di=(xi-1+1)2+yi-12-R2+(xi-1+1)2+(yi-1-1)2-R2 假设di0，则取Si作为下一点，即Pi(xi-1+1,yi-1)且Si+1为(xi-1+2,yi-1)，Ti+1为(xi-1+2,yi-1-1)， 则： di+1=(xi-1+2)2+(yi-1)2-R2+(xi-1+2)2+(yi-1-1)2-R2 di+1-di=4xi-1+6di+1=di+

55、4xi-1+6,第二章,79,圆的生成算法,圆的生成算法原理,假设di0，则取Ti作为下一点，即Pi(xi-1+1,yi-1-1)则第i+1次两个可能点为Si+1 (xi-1+2,yi-1-1)，Ti+1 (xi-1+2,yi-1-2) di+1=(xi-1+2)2+(yi-1-1)2-R2+(xi-1+2)2+(yi-1-2)2 -R2 di+1-di=4(xi-1- yi-1)+10 di+1=di+4(xi-1-yi-1)+10即得di的递归式:d1=3-2R (x0=0,y0=R) di+1= di+4xi-1+6 当di0时，取Si(xi-1+1,yi) di+4(xi-1-yi-1

56、)+10 当di0时，取Ti(xi-1+1,yi-1),圆的生成算法描述,置第一点坐标：x=0，y=R 置初始误差：d=3-2R while xy do begin 输出点(x,y)以及其他7点(y,x),(-x,y), (-y,x),(-y,-x),(-x,-y),(x,-y),(y,-x) if d0 then d=d+4x+6 else d=d+4(x-y)+10，y=y-1 x=x+1 end if x=y then 输出点(x,y)以及(-x,y),(-x,-y),(x,-y) end of algorithm,圆的生成算法,第二章,80,算法仅使用加，减，移位进行计算，运算简单，生

57、成速度快。,第二章,81,2.3 多边形填充,一、概 述 二、多边形扫描线填充 三、简单种子填充算法 四、扫描线种子填充 五、模式填充,第二章,82,概 述,概 述,计算机生成的物体常常可以用若干多边形来描述，有些非多边形的物体，也可以用多边形来逼近。在多边形生成以后，就可以利用光栅显示系统对其内部区域进行填充。 填充多边形的方法有多种：如果在多边形边界内的象素都被点亮，则称对该多边形进行了一次实心填充； 按扫描线点亮象素；用任意预先定义的模式进行填充。,第二章,83,二维图形,2.3 多边形填充,一、概 述 二、多边形扫描线填充 三、简单种子填充算法 四、扫描线种子填充 五、模式填充,多边形

58、扫描线填充原理,多边形扫描线填充,第二章,84,0,2,4,6,8,10,12,2,4,6,8,10,1,2,3,4,根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。 判断扫描线上的点是否在多边形之内根据多边形区域连续性，分为3个步骤： 求出扫描线与多边形所有边的交点； 把这些交点的x坐标值以升序排列； 对每一对交点间的区域进行填充。 第三个步骤是从奇数个交点出发到偶数个交点。如右图，排序x坐标得到的表是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。,多边形扫描线填充原理,多边形扫描线填充,第二章,85,p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。 如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。,多边形扫描线填充原理,多