《图形变换》PPT课件.ppt

第一篇 基 础,练习,阴极射线管由_、_、_、_和_构成。CRT中电子枪中的控制栅，通过控制_，控制荧光屏上相应点的亮度。图形显示系统主要由_和 _ 组成。阴极射线管中聚焦系统的功能是_。光栅显示器的帧缓存中，存放的是_,通过的电子数,显卡,电子枪,聚焦系统,加速电极,偏转系统,荧光屏,保证电子束在轰击屏幕时，汇聚成很细的点。,要显示的图形信息,显示器,影孔板法之所以可以产生多种颜色，因为它在荧光屏中用_个荧光点来表示一个像素点。A、1 B、2 C、3 D、4在光栅扫描显示器中，帧缓存中，对应每个像素的单元有i位，则可以表示_种颜色。A、2*i B、i2 C、2i D、ii灰度等级为256级，分辨率为1024*1024的显示器，至少需要的帧缓存容量为_。A、512KB;B、1MB C、2MB D、3MB,练习,B,练习,阴极射线管的英文缩写为_A、CRT B、DVST C、LCD D、DPU水平或垂直方向上能够识别出的最大光点数称为_ A、可寻址能力 B、分辨率 C、像素 D、位图,练习,对于分辨率为1024*1024的光栅系统，若每一像素用8位和12位二进制来表示存储信息，各需多大光栅存储容量以及显存？每一屏幕最多能显示多少颜色？若R，G，B灰度都占8位，其显示颜色的总数是多少？,1)每一像素用8位二进制来表示存储信息，所需容量为1024*1024*8/(8*1024*1024)=1MB每一屏幕能显示的颜色数为：28=256,练习,2）每一像素用12位二进制来表示存储信息，所需容量为1024*1024*12/(8*1024*1024)=1.5MB,显存大小为2MB。每一屏幕能显示的颜色数为：212=4096,3）颜色总数为：28*28*28=224,对于分辨率为1024*1024的光栅系统，若每一像素用8位和12位二进制来表示存储信息，各需多大光栅存储容量以及显存？每一屏幕最多能显示多少颜色？若R，G，B灰度都占8位，其显示颜色的总数是多少？,第3章 图形变换,主要内容,坐标系统几何变换 投影变换 图形裁剪 视窗变换,3.1 坐标系统,世界坐标系造型坐标系观察坐标系虚拟设备坐标系设备坐标系,世界坐标系(World Coordinates),是在被显示对象所在的空间定义的一个坐标系，一般采用三维右手直角坐标系，其长度单位根据所描述的实际对象的大小确定，通常使用实数，取值范围无限制，也称之为整体坐标系或用户坐标系。计算机图形系统中所涉及的其它坐标系基本上都是参照它进行定义的。,造型坐标系（Modeling Coordinate System）,独立于世界坐标系定义的三维直角坐标系。用来描述世界坐标系中每个具体的形体或图素，每一个形体和图素都有各自的坐标原点和单位长度。也称为局部坐标系。,观察坐标系（View Coordinates）,以视点的位置为原点，通过用户指定的一个向上的观察向量来定义的一个坐标系。一般是三维左手直角坐标系，通过变换可以在世界坐标系的任何位置、任何方向定义。,指定裁剪空间，确定物体要显示输出的部分；通过定义观察平面，把可显示部分的用户坐标转换成规格化的设备坐标。,设备坐标系(Device Coordinates),图形输出设备自身具有的坐标系，它与设备物理参数有关。主要用于在某一特定图形显示设备(如光栅显示器)上定义图形或窗口的位置。通常由沿水平方向的X轴和沿垂直方向的y轴组成，坐标原点可以任意选择，单位根据输出设备的实际大小来确定，一般用整数。,虚拟设备坐标系(Virtual Device Coordinates),也称规格化设备坐标系。为了使图形处理过程做到与设备无关，而采用一种中间坐标系。通常规定原点位于显示器的左下角，轴的正方向分别指向右方和上方，取值范围为0X1，0Y1。,图形变换分为两种：图形不变，而坐标系发生变化；坐标系不变，而图形的位置和形状发生变化。,图形的几何变换是指图形的几何信息发生变化，而拓扑关系不变。,3.2 几何变换-几何变换的含义,图形信息=几何信息+拓扑信息,3.2 几何变换-几何变换的基本思想,由于图形可以用点集来表示，也就是说点集定了，则图形也就确定了，那么，如果点的位置改变了，图形也就随之改变。因此，对图形进行变换，只要变换点就可以了。由于点集可以用矩阵的方式来表达，因此图形的变换可以通过相应的矩阵运算来实现。即：,旧点集 变换矩阵 新点集,矩阵运算,数乘,矩阵乘法。矩阵A=(aij)2X3,矩阵B=(bij)3X2，则,图形变换的数学基础矩阵运算,齐次坐标,为了能用矩阵的形式统一描述图形变换，在计 算机图形学中常采用齐次坐标的形式来描述空 间的点。所谓齐次坐标表示法就是用n+1维向量表示一个 n维向量。二维点（x,y）的齐次表示是（hx,hy,h），这 里h是任何一个非零因子，有时叫做比例因子。齐次点（a,b,h）被投射恢复到二维时简单地就 是（a/h,b/h）,由比例因子h去除。,注意：齐次坐标表示不是唯一的，当h为1时称为规格化的 齐次坐标。,3.2 几何变换-二维基本变换,平移变换 缩放变换 旋转变换 错切变换 反射变换,1、平移变换,平移变换是指将图形从一个坐标位置移到另一个坐标位置的重定位变换。已知一点P的原始坐标是(x,y），沿X，Y方向的平移量为tx 和ty，则新坐标点P（x,y）的表达式为：,3.2 几何变换-二维基本变换,1、平移变换,3.2 几何变换-二维基本变换,3.2 几何变换-二维基本变换,2、缩放（比例）变换,图形中的坐标点P(x,y）,相对于坐标原点，在X轴方向变化一个比例系数sx，在Y轴方向变化一个比例系数sy，则新坐标点P(x,y）的表达式为：,变换方程写成齐次坐标矩阵形式为：,这一变换称为相对于坐标原点的比例变换,sx 和sy分别表示点P(x,y）沿X轴方向和Y轴方向相对坐标原点的比例变换系数。,3.2 几何变换-二维基本变换,缩放变换的性质,当 时，变换前的图形与变换后的图形相似当 时，图形将放大，并远离坐标当 时，图形将缩小，并靠近坐标原点当 时，图形将发生畸变,3.2 几何变换-二维基本变换,3、旋转变换,绕坐标原点旋转角度（逆时针为正，顺时针为负）。,（1）,假定P点绕原点逆时针旋转角到P点，则：,（2）,将式（1）代入式（2）得：,3.2 几何变换-二维基本变换,则变换矩阵为：,注意：旋转变换只能改变图形的方位，而图形的大小和形状不变。,3.2 几何变换-二维基本变换,错切（shear）变换是轴上点不动，其它点沿平行于此轴方向移动变形的变换。错切变换也称为剪切、错位或错移变换。,4、错切变换,3.2 几何变换-二维基本变换,（1）沿X轴方向关于Y轴的错切,将图形上关于y轴的平行线沿x方向推成角的倾斜线，使新的坐标值x在原有值得基础上增加了一个增量，而保持y坐标不变。即整个图形在等高的前提下沿X轴倾斜了一个角度。,x,3.2 几何变换-二维基本变换,x,其中：a为错切系数，当a0时沿+X向错切，当a0时沿-x向错切。,3.2 几何变换-二维基本变换,（2）沿Y轴方向关于x轴的错切,将图形上关于x轴的平行线沿y方向推成角的倾斜线，使得Y坐标产生一增量，而保持x坐标不变。,3.2 几何变换-二维基本变换,注意：上述的错切方向均是对第1象限的点而言，其余象限的 点的错切应作相应的改变。,b为错切系数，当b0时沿+Y向错切，当b0时沿-Y向错切。,3.2 几何变换-二维基本变换,5、反射变换,反射变换是产生图形镜象的一种变换，也称镜象变换或对称变换。,3.2 几何变换-二维基本变换,写出它们的变换矩阵？,（1）对称于X轴的坐标变换,点对X轴对称时：x=x，y=-y则变换方程为,3.2 几何变换-二维基本变换,（2）对称于Y轴的坐标变换,点对Y轴对称时，有：x=-x，y=y则变换方程为：,3.2 几何变换-二维基本变换,（3）对称于原点的坐标变换,点对坐标原点对称时有：x=-x，y=-y则变换矩阵为：,3.2 几何变换-二维基本变换,（4）关于y=x（对称于45线）的坐标变换,关于y=x的对称就是X、Y互换坐标，即 X=Y、Y=X，则变换矩阵为：,3.2 几何变换-二维基本变换,（5）关于y=-x（对称于-45线）的坐标变换,关于y=-x变换时，有：X=-Y，Y=-X，则变换矩阵为：,x,o,y=-x,3.2 几何变换-二维基本变换,5种二维基本变换的变换矩阵都可以用如下的3*3矩阵来描述：,（1）左上角的2*2子块可实现缩放、旋转、反射、错切四种 基本变换；（2）左下角的1*2子块可实现平移变换；（3）右上角的2*1子块可实现投影变换，g的作用是在x轴的 1/g处产生一个灭点，h的作用是在y轴的1/h处产生一个灭点；（4）右下角的1*1子块可实现整体比例变换。,二维变换矩阵的功能分区,由多种基本变换组合而成的变换称之为组合变换，或称为基本变换的级联，相应的多个基本变换矩阵的级联矩阵叫做组合变换矩阵。,设图形经过n次基本几何变换，其变换矩阵分别为T1,T2,Tn，则复合变换矩阵为:T=T1T2 Tn。,二维组合变换,二维组合变换,1、绕任意点（x0,y0）旋转,绕任意点旋转变换的步骤：（1）平移变换（2）对图形绕原点进行旋转变换（3）平移变换,二维基本变换,令：,则有：,二维基本变换,2、相对于任意位置直线的对称变换,（1）平移变换（2）对图形绕原点进行顺时 针旋转变换（3）对称变换（4）对图形绕原点进行逆时 针旋转变换（3）平移变换,二维基本变换,令：,则：,二维基本变换,1、用基本变换的级联来实现图形的组合变换时，矩阵级联的顺序不同，则所得到的最终结果图形也不同。2、对于一般条件下的图形变换，解决问题的思路可以分为3步：首先把任意的一般条件转化为特殊条件，即符合基本变换的条件，然后应用基本变换，最后恢复到原来的初始状态。,注意：,复习题,1、写出下列齐次坐标表示的二维坐标。（6，18，3），（5，8，1），（4，6，8）2、以下关于图形变换的论述那些是错误的_？A）错切变换虽然会引起图形角度的改变，但不会发生图形畸变；B）平移变换不改变图形大小和形状，只改变图形位置；C）拓扑关系不变的几何变换不改变图形的连接关系和平行关系；D）旋转变换后各图形部分之间的线性关系和角度关系不变，变换后直线的长度不变；,A,复习题,3、使用二维图形变换矩阵T=，将产生变换的结果为。A）图形放大2倍 B）图形放大2倍，同时沿X、Y坐标轴方向各移动1个绘 图单位 C）沿X坐标轴方向各移动2个绘图单位 D）沿X坐标轴方向放大2倍，同时沿X、Y坐标轴方向各 平移1个绘图单位,D,复习题,4、在齐次坐标系中，写出下列变换矩阵：（1）整个图形放大2倍。（2）x向放大3倍，y向放大4倍。（3）y方向上移10个单位，x方向上右移5个单位。（4）对称于-45线的坐标变换。（5）图形绕原点顺时针旋转90。（6）相对点(4,5)的比例变换，x方向比例系统为a，y方向的比例系数为b。,复习题,5、如下图所示三角形ABC，将其关于A点逆时针旋转60，写出其变换矩阵和变换后图形各点的规范化齐次坐标。,复习题,6、已知三角形ABC各顶点的坐标A(1,2)、B(5,2)、C(3,5)，相对直线Y=4做对称变换后到达A、B、C。试计算A、B、C的坐标值。（要求用齐次坐标进行变换，列出变换矩阵）,复习题,7、图1中图形经过几何变换后如图2所示，且已知图形中的矩阵变换前后的信息和线段变换前的信息，利用复合几何变换的知识采用矩阵的形式计算变换后线段的两端点坐标。,三维基本变换,三维空间的几何变换是在二维空间几何变换的基础上拓展了z轴所代表的第三维空间变换，其特点如下：（1）在平移、旋转、缩放等变换中增加了第三维分量；（2）旋转变换的参考对象由二维变换中以绕某个点坐标变化为绕某个旋转轴进行；（3）齐次坐标表示变为4元行向量，变换矩阵也变为44矩阵。,三维基本变换,1.平移变换 2.缩放变换 3.旋转变换 4.反射变换,三维基本变换,1、平移变换,假定将空间一点P(x,y,z)平移到点p(x,y,z)，沿x轴、y轴和z轴方向的平移量分别为d1、d2和d3，则可构造平移矩阵T：,三维基本变换,2、缩放变换,（1）局部缩放变换 假定点P相对于坐标原点沿X方向放缩Sx倍，沿Y方向放缩Sy倍，沿Z方向放缩Sz倍，其中Sx、Sy和Sz称为缩放系数，则可构造缩放矩阵T：,三维基本变换,（2）整体缩放变换,其变换矩阵为：,当s1时，则三维图形产生三向等比例缩小的变换；若0s1，则产生等比例放大的变换；因此，s被称为全比例变换系数。,三维基本变换,3、旋转变换,三维空间中的旋转变换比二维空间中的旋转变换复杂。除了需要指定旋转角外，还需指定旋转轴和旋转方向。以坐标系的三个坐标轴x,y,z分别作为旋转轴，图形上各点在此轴的坐标值不变，而点实际上只在垂直坐标轴的平面上作二维旋转。此时用二维旋转公式就可以直接推出三维旋转变换矩阵。规定在右手坐标系中，物体旋转的正方向是右手螺旋方向，即从该轴正半轴向原点看是逆时针方向。,三维基本变换,旋转角度为时，点的正旋转方向：旋转轴 相应的旋转方向 x轴从y轴到z轴 y轴从z轴到x轴 z轴从x轴到y轴,三维基本变换,（1）绕z轴旋转变换,三维图形绕Z轴正向旋转时，图形上各顶点z坐标不变，x、y坐标的变化相当于在XY二维平面内绕原点逆时针旋转。则构造变化矩阵如下：,三维基本变换,（2）绕X轴旋转变换,三维图形绕X轴正向旋转时，图形上各顶点x坐标不变，y、z坐标的变化相当于在YZ二维平面内绕原点逆时针旋转。则变换矩阵为：,三维基本变换,（3）绕Y轴旋转变换,三维图形绕Y轴正向旋转时，图形上各顶点y坐标不变，x、z坐标的变化相当于在XZ二维平面内绕原点顺时针旋转。则变换矩阵为：,三维基本变换,旋转，则该轴坐标的一列元素不变。按照二维图形变换的情况，将其旋转矩阵,中的元素添入相应的位置中，即,对于单位矩阵,旋转变换矩阵规律:,，绕哪个坐标轴,三维基本变换,(1)绕z轴正向旋转,角，旋转后点的z坐标值不变,x、y,坐标的变化相当于在xoy平面内作正,角旋转。,(2)绕x轴正向旋转,角，旋转后点的x坐标值不变，,Y、z坐标的变化相当于在yoz平面内作正,角旋转。,三维基本变换,即,即：绕y轴的旋转变换的矩阵与绕x轴和z轴变换的矩阵从表面上看在符号上有所不同。,(3)绕y轴正向旋转,角，y坐标值不变，z、x的坐标相当,于在zox平面内作正,角旋转，于是,三维基本变换,4、反射变换,（1）对xoy坐标平面的反射变换,变换矩阵为：,三维基本变换,（2）对xoz坐标平面的反射变换,变换矩阵为：,三维基本变换,（3）对yoz坐标平面的反射变换,变换矩阵为：,三维变换矩阵的功能分块,旋转、反射、错切、对称,透视投影,总体反射,平移,三维几何变换小结,三维几何变换小结,三维几何变换小结,习题,1、对于点P(x,y,z)，(1)写出它绕x 轴旋转 角，然后再绕y轴旋转 角的变换矩阵。(2)写出它绕 y 轴旋转 角，然后再绕 x 轴旋转 角的变换矩阵。所得到的变换矩阵的结果一样吗?,2、二维变换中绕原点的旋转相当于三维变换中绕_轴旋转。A、XB、YC、ZD、以上都不是3、分别对称于XOY平面、YOZ平面、XOZ平面的变换矩阵是什么？,C,习题,习题,4、如图所示，物体ABCDEFGH进行如下变换，写出其变换矩阵并求出复合变换后顶点的齐次坐标。（1）平移使点C与点P（1，1，0）重合；（2）绕z轴旋转60。,习题,解：平移点C与点P重合的平移矩阵为：,绕z轴旋转60矩阵为：,所以，复合变换后的矩阵为T1*T2，有：,习题,5、下面给出的四个选项中（）是绕Z轴负向旋转的三维旋转变换矩阵。,A,B,C,D,D,习题,6、形体的定义和图形的输入输出都是在一定的坐标系下进行的，通常这些坐标系分为：建模坐标系（造型坐标系），_，_，规格化设备坐标系和 _。,用户坐标系,观察坐标系,设备坐标系,7、对于基本几何变换，一般有平移、旋转、反射和错切等，这些基本几何变换都是相对于_和_进行的几何变换。,坐标原点,坐标轴,3.3 投影变换,投影概念,投影就是将空间物体投射到投影面上而得到的平面图形，而这一转换过程称为投影变换。,S,A,B,C,a,b,c,投影中心,投影线,投影对象,投影,投影面,投影的要素：投影对象、投影中心、投影平面、投影线和投影,3.3 投影与投影变换,投影分类,投影中心与投影平面之间的距离为无限,根据投影方向与投影平面的夹角,根据投影平面与坐标轴的夹角,投影中心与投影平面之间的距离为有限,3.3 投影变换,定义平行投影时，给出投影线的方向就可以了，而定义透视投影时，还需要指定投影中心的具体位置。,3.3.1 透视投影变换,又称为中心投影，其投影中心与投影平面之间的距离是有限的。现实生活中的景物，由于观察距离及方位不同，在视觉上会引起不同的反映，这种现象就是透视现象。,透视现象产生的原因,图中，AA,BB,CC为一组高度和间隔都相等，排成一条直线的电线杆，从视点E去看，发现AEABEBCEC若在视点E与物体间设置一个透明的画面P，则在画面上看到的各电线杆的投影aabbccaa即EA,EA与画面P的交点的连线;bb即为EB，EB与画面P的交点的连线。cc 即为EC，EC与画面P的交点的连线。近大远小,若连接abc及abc，它们的连线汇聚于一点。实际上，ABC与ABC的连线是两条互相平行的直线，这说明空间任何一束不平行于投影平面的平行线的投影将汇聚在一点，即abc与abc的连线，必交于一点，这点我们称之为灭点。,3.3.1 灭点及产生机理,每一组平行线都有其不同的灭点。一般说来，三维图形中有多少组平行线就有多少个灭点。平行于坐标轴的平行线在投影平面上形成的灭点称为主灭点。因为有X、Y和Z三个坐标轴，所以主灭点最多有三个。,3.3.1 灭点及产生机理,当某个坐标轴与投影面平行时，则该坐标轴方向的平行线在投影面上的投影仍保持平行，不形成灭点。投影中主灭点数目由与投影面相交的坐标轴数目来决定，并据此将透视投影分类为一点、二点或三点透视。一点透视有一个主灭点，即投影面与一个坐标轴正交，与另外两个坐标轴平行；两点透视有两个主灭点，即投影面与两个坐标轴相交，与另一个坐标轴平行；三点透视有三个主灭点，即投影面与三个坐标轴都相交。,3.3.1 灭点及产生机理,3.3.1 灭点及产生机理,一点透视,两点透视,三点透视,透视图一点透视,人眼从正面去观察一个立方体，当z轴与投影平面垂直时，另两根轴ox,oy轴平行于投影平面。这时的立方体透视图只有一个灭点，即与投影面垂直的那组平行线的透视投影交于一点。,透视图两点透视,(1)首先将三维形体平移到适当位置；(2)然后使形体绕y轴旋转角；(3)将形体进行透视变换；(5)将旋转变形后的形体向xoy面作正投影。,透视图三点透视,(1)首先将三维形体平移到适当位置；(2)将形体进行透视变换(3)然后使形体先绕y轴旋转角；(4)再绕x轴旋转角；(5)将变形且旋转后的形体向xoy面作正投影。,透视投影变换,假定投影中心在z轴上（z=d处），投影面在面xoy上，与z轴垂直，d为投影面与投影中心的距离。现在求空间一点p（x,y,z）的透视投影p（x,y,z）点的坐标。,透视投影投影方程,当z时，x 0,y 0,z-d所以，(0,0,-d)为该透视的一个灭点。,根据投影线方向与投影平面的夹角，平行投影分为两类：正投影与斜投影,3.3.2 平行投影变换,正投影 正投影根据投影面与坐标轴的夹角又可分成两类：三视图和正轴测投影。当投影面与某一坐标轴垂直时，得到的投影为三视图，这时投影方向与这个坐标轴的方向一致。否则，得到的投影为正轴测投影。,3.3.2 平行投影变换,俯视图,三视图主要包括主视图、侧视图和俯视图，投影面分别与Y轴、X 轴和Z轴垂直。,3.3.2 平行投影变换,3.3.2 平行投影变换,三视图的投影变换矩阵分别为：,侧视图:,主视图:,俯视图:,3.3.2 平行投影变换,由于在三视图上保持了有关比例的不变性，可以精确地测量长度和角度等量，因此常用于工程制图。,投影方向不垂直于投影平面的平行投影称为斜平行投影，在斜平行投影中，投影平面一般取坐标平面。,(A,B,C),（xo,yo,zo),（xp,yp,zp),3.3.2 平行投影变换,3.4 图形裁剪,裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。图形裁剪算法，直接影响图形系统的效率。,3.4 图形裁剪,裁剪的窗口可以是任意多边形，但常用的裁剪窗口是标准矩形。被裁剪的对象可以是点、线段、圆弧段、符号、多角形以及由他们构成的各种图形。,3.4.1 点的裁剪,图形裁剪中最基本的问题假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式：xL x xR yB y yT否则，P点就在窗口外。,3.4.2 直线的裁剪,直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。裁剪算法的核心问题是速度问题。对一条被裁剪线段，要迅速而准确地判定：它是全部在窗口内还是窗口外；当线段部分在内部时，要较快地找出它与窗口边界的交点，确定窗口内的部分。,线段和窗口的关系,线段完全可见直线段两个端点在窗口内显然不可见直线段的两个端点在窗口外,且与窗口不相交非显然不可见直线段的两个端点在窗口外,但与窗口相交直线段的一个端点在窗口内，一个端点在窗口外,线段和窗口的关系,实交点直线段与窗口矩形边界的交点虚交点直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点,3.4.2 直线的裁剪,主要的两种算法 Cohen-Sutherland算法 中点分割算法,假定条件矩形裁剪窗口：xmin,xmaxXymin,ymax任何平面线段相对于凸多边形窗口进行裁剪后落在窗口内的线段不会多于一条每一线段 或者整个位于窗口的内部 或者能够被分割，使其中的一部分能很快地被删去,3.4.2 直线的裁剪,基本思想：对于每条线段P1P2分为三种情况处理:若P1P2完全在窗口内，则显示该线段P1P2。若P1P2明显在窗口外，则丢弃该线段。若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。,Cohen-Sutherland裁剪,问题：如何判断线段与窗口的关系？,Cohen-Sutherland 算法端点编码,把窗口的边界延长成直线，窗口平面被分成9个区，每一个区设定一个4位二进制编码与之对应。编码的意义如下：,3 2 1 0 上 下 右 左,任何位赋值为1，代表端点落在相应的位置上，否则该位为0。若端点在剪取矩形内，区域码为0000。如果端点落在矩形的左下角，则区域码为0101。,若线段完全在裁剪窗口内，则线段两端点编码均为0000；当线段两端点均在窗口之外，且位于裁剪窗口的同一侧时，则两端点编码必有一位同时为1。,Cohen-Sutherland 算法结论,Cohen-Sutherland 算法,判别方法：将线段两端点的编码逐位取逻辑“或”，若结果为零，则该线段必为完全可见，应保留；将线段两端点的编码逐位取逻辑“与”，若结果非零，则该线段必为完全不可见，应舍弃；否则，这一线段可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口边界的一个交点，根据交点位置，也赋予四位二进制编码，并对分割后的线段重复进行检查，直到全部线段均被舍弃或被保留为止,实现本算法时，不必把线段与每条窗口边界依次求交，只要按左右下上的顺序检测到端点的编码不为0，才把线段与对应的窗口边界求交。,Cohen-Sutherland 算法 求交,若编码 00010，端点与左边界有交点；若编码 00100，端点与右边界有交点；若编码 01000，端点与下边界有交点；若编码 10000，端点与上边界有交点；,线段与窗口边界交点,（1）线段的标准方程,（2）线段的标准方程与窗口边界方程联立,例：求出线段P1P2（P1（x1，y1），P2（x2，y2）与直线x=a的交点。,（y2-y1)(x-x1)-(x2-x1)(y-y1)=0,Cohen-Sutherland 算法,线段的端点编码,Cohen-Sutherland 算法,例：Cohen-Sutherland算法裁剪线段AB，其中A(3,3)，B(-2,-1)，裁剪窗口WXl=0，WXr=2，WYb=0，WYt=2。要求写出每一步的取点的坐标值。,AB在窗口ABCD裁剪后的直线段的坐标为：（7/4，2）、（0，3/5）。,B,练习,1、图中ABCD为矩形窗口，P1P2为待裁剪线段。试用编码裁剪算法求出P1P2在窗口中的直线段坐标。已知：窗口及线段的坐标分别为A（3，1）、B（8，1）、C（8，6）、D（3，6）、P1（3，0）、P2（10，9）,P1P2在窗口ABCD裁剪后的直线段的坐标为（34/9，1）、（69/9，6）。,Cohen-Sutherland 算法,此方法直观而方便，速度也较快。由于采用逻辑运算，在某些高级语言中不便进行全部摒弃的判断只适合于那些仅在窗口同一侧(或左、或右、或上、或下)的线段，对于跨越3个区域的线段就不能一次做出判断而舍弃它们。要进行求交计算，涉及浮点数的运算。,只能快速排除d及e 不能快速排除d！,中点分割裁剪算法,基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。,中点分割裁剪算法-求线段与窗口的交点,采用中点分割方法，从P0出发找距离P0最近可见点先求出P0P1的中点Pm,若Pm在窗口内，用P0Pm代替P0P1；否则取PmP1代替P0P1。再对新的P0P1求中点Pm。重复上述过程，直到Pm到窗口边界的距离小于给定的控制常数，此时Pm收敛于交点。从P1出发找距离P1最近可见点采用上面类似方法。,中点分割裁剪算法,中点分割裁剪算法,例：图中ABCD为矩形窗口，P1P2为待裁剪线段。试用中点分割法求出P1的最近可见点，当中点到窗口边界的长度1时算法结束。已知：窗口及线段的坐标分别为A（3，1）、B（8，1）、C（8，6）、D（3，6）、P1（3，0）、P2（10，9）,中点分割裁剪算法,主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。,多边形裁剪,用直线段裁剪算法，可以吗？,G,H,多边形裁剪,新的问题：,不仅保持窗口内多边形的边界部分，而且要将窗口的有关部分按照一定的顺序插入多边形的保留边界之间，从而使裁剪后的多边形之间仍就保持封闭状态。,如何确定其边界？,多边形裁剪,关键：不仅在于求出新的顶点，删去界外顶点还在于形成正确的顶点序列,一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？,Sutherland-Hodgman算法,裁剪处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。,流水线过程(左上右下)：前边的结果是后边的输入。,亦称逐边裁剪算法,Sutherland-Hodgman算法,基本思想：每次用裁剪窗口的一条边界对要裁剪的多边形进行裁剪，把落在此边界外侧的多边形部分去掉，只保留内侧部分，形成一个新的多边形，并把它作为下一次待裁剪的多边形。对于矩形裁剪窗口的一条边界线，称窗口区域所在的一侧为内侧，另一侧为外侧。,明确一点:多边形用顶点序列表示，被窗口的一条边裁剪后，仍为多边形,裁剪的结果就是一系列的顶点,Sutherland-Hodgon裁剪算法,具体实现：首先把待裁剪多边形各顶点按照一定方向（通常为逆时针方向）有次序地组成顶点序列。然后依次用窗口的一条边界裁剪多边形，产生新的顶点序列。,如何确定新的顶点序列？,取决于多边形的各条边的两端点S、P与裁剪线的位置关系。,Sutherland-Hodgon裁剪算法,情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P,Sutherland-Hodgon裁剪算法,确定新顶点的算法 对于输入顶点序列中的每个顶点Pi，若处于裁剪边可见侧，则被加入新顶点序列，否则，该顶点被删除；若i 1，还要检测该顶点与其前一个顶点是否位于裁剪边的同侧，若不是，则还要求出裁剪边与Pi-1Pi的交点，将交点也加入新顶点序列；当最后一个顶点Pn检测完后，在检测该顶点与第一个顶点是否处于裁剪边两侧，是则求出交点加入新顶点序列。,Sutherland-Hodgon裁剪算法,例1：如下图所示，裁减窗口为正方形，采用逐边裁件算法，依次按左、下、右、上的顺序，用四条窗口边界裁减多边形ABCDE。试写出每条框口边界裁减后输出的新的多边形的顶点序列。,左边界裁减后：ABCD12下边界裁减后：4B56D123右边界裁减后：4B7D123上边界裁减后：4B789123,Sutherland-Hodgon裁剪算法,例2：使用Sutherland-Hodgon算法，以A（1,1），B（5,3），C（4,5），D（0,3）所围成的矩形作为窗口，对连接P1（-1,2）到P2（6,4）的线段进行裁剪。,方法：利用向量叉积确定两向量之间的位置关系。,向量叉积定义,两个向量u、v的叉积定义为：其中：n是一个与u和v均垂直的单位矢量。,方向与u,v所在平面垂直且满足右手螺旋定则。,向量叉积定义,右手螺旋定则:将右手拇指伸直,其余四指并拢指向u的方向,并沿 的计算方向弯向v,拇指所指的方向就是n的方向.,uv0，u在v的顺时针方向uv0，u在v的逆时针方向uv=0，u，v共线,向量叉积定义,i、j、k为直角坐标系的单位向量，满足等式ij=k，jk=i，ki=j，设：,等价于：,则：,用坐标表示式计算叉积,Sutherland-Hodgon裁剪算法,1、确定P1、P2与AB的关系,（1）表达出向量AB、AP1和AP2,AB=（5-1）i+（3-1）jAP1=（-1-1）i+（2-1）jAP2=（6-1）i+（4-1）j,（2）计算AB和AP1、AB和AP2的叉积,ABAP1=4*1+2*2=8；P1在AB的逆时针方向ABAP2=4*4-2*5=6；P2在AB的逆时针方向,算法输出P1P2。,Sutherland-Hodgon裁剪算法,2、确定P1、P2与BC的关系,（1）表达出向量BC、BP1和BP2,BC=（4-5）i+（5-3）jBP1=（-1-5）i+（2-3）jBP2=（6-5）i+（4-3）j,（2）计算BC和BP1、BC和BP2的叉积,BCBP1=-1*（-1）+2*6=13；P1在BC的逆时针方向BCBP2=-1*1-2*1=-3；P2在BC的顺时针方向,（3）计算BC所在直线与P1P2的交点P（75/16,29/8），输出P1、P,Sutherland-Hodgon裁剪算法,3、确定P1、P2与CD的关系,4、确定P1、P2与DA的关系,结论：裁剪线段为交点（75/16,29/8）和交点（5/16，39/18）确定的线段。,Sutherland-Hodgon裁剪算法,优点：裁剪算法采用流水线方式，适合硬件实现。可推广到任意凸多边形裁剪窗口,Sutherland-Hodgon裁剪算法,用Sutherland-Hodgeman算法对凹多边形的裁剪，可能出现如下图所示多余的连线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。,Weiler-Atherton裁剪算法,也称边界裁剪算法或双边裁剪法。算法的基本做法是：有时沿着多边形边的方向来处理顶点，有时沿着窗口的边界方向来处理，从而避免产生多余的连线。设被裁剪多边形和裁剪窗口都按顺时针确定排列方向。,从多边形的任一点出发，跟踪检测多边形的每一条线段，当线段与裁剪窗口边界相交（实交点）时：如果线段起点在窗口外部而终点在窗口内部，则求出交点，同时输出线段可见部分，继续沿多边形方向往下处理；如果线段起点在窗口内部而终点在窗口外部，则求出交点，输出线段可见部分。从此交点开始，沿着窗口边界方向往前检测，找到一个多边形与窗口边界的新交点后，输出由前交点到此新交点之间窗口边界上的线段，返回到前交点，再沿着多边形方向往下处理；直到处理完多边形的每一条边，回到起点为止。,Weiler-Atherton裁剪算法,Weiler-Atherton裁剪算法,Weiler-Atherton裁剪算法,练习：用Weiler-Atherton算法，从A点出发逆时针方向对多边形ABCDEF进行裁剪，画出裁剪结果图。,Weiler-Atherton裁剪算法,优点：裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。裁剪思想新颖，方法简洁，裁剪一次完成，与裁剪窗口 的边数无关。,3.5 视图变换,窗口-视区变换,窗口(Window)：在WC中定义的一个(矩形)区域，该区域内的对象将予以显示。视区(Viewport)：在DC中定义一个(矩形)区域,所有在窗口内的对象都将显示在该区域中。,窗口用来确定要显示的物体，视区确定实际显示图形。实际情况中，窗口与视区的大小往往不一样。如果要在视区正确地显示形体，必须将其从窗口变换到视区，此过程称为窗口-视区变换。,3.4 视图变换,为了使变换后的图形不变形,变换时要满足下列条件:1）X、Y方向进行相同的比例变换2）窗口在视区中占有最大的区域,对象在窗口中和在视区中有同样的相对位置。,3.4 视图变换,Xwmin,Xwmax,Ywmin,Ywmax,Yvmax,Yvmin,Xvmin,Xvmax,3.4 视图变换,（1）,3.4 视图变换,思考：前面讲的窗口视图变换时，假设窗口的边和坐标轴平行，如果窗口的边不和坐标轴平行呢？,A.先让窗口FGHI转-角，使它和FGHI重合。B.用(1)式进行计算,3.4 视图变换练习,假设在观察坐标系下窗口区的左下角坐标为（wxl=10,wyb=10）,右上角坐标为（wxr=50，wyt=50）。设备坐标系中视区的左下角坐标为（vxl=10,vyb=30）,右上角坐标为（vxr=50,vyt=90）。已知在窗口内有一点p(20,30),要将点p映射到视区内的点p,请问p点在设备坐标系中的坐标是多少？,3.4 视图变换练习,（1）将窗口左下角点（10,10）平移至观察坐标系的坐标原点，平移矢量为（-10，-10）；（2）针对坐标原点进行比例变换，使窗口的大小和视区相等。比例因子为：Sx=(50-10)/(50-10)=1;Sy=(90-30)/(50-10)=1.5（3）将窗口内的点映射到设备坐标系的视区中，再进行反平移，将视区的左下角点移回到设备坐标系中原来的位置（10，30），平移矢量为（10，30）。,3.4 视图变换练习,