计算机图形学chap6二维变换及二维观察ppt课件.ppt

计算机图形学基础,华东理工大学计算机系 谢晓玲,2,第六章 二维变换及二维观察,如何对二维图形进行方向、尺寸和形状方面的变换。如何进行二维观察。,3,二维变换及二维观察,基本几何变换与基本概念二维图形几何变换的计算复合变换变换的性质,4,图形的几何变换平移、旋转、缩放、反射和错切变换的组合图形几何变换的目的改变图形的位置、方向、大小基本几何变换 都是相对于坐标原点和坐标轴进行的几何变换。,6.2 基本几何变换,6.2 齐次坐标,齐次坐标 将一个原本是n维的向量用一个n+1维向量来表示。例如：向量(x1, x2, , xn)的齐次坐标表示为(Hx1, Hx2, , Hxn, H), 其中H是一个不为0的实数。H=1的齐次坐标称为规范化齐次坐标；反之：由点或向量的齐次坐标(Hx1, Hx2, , Hxn, H)，求它的规范化齐次坐标, 可根据如下公式求得x1= Hx1/H,x2= Hx2/H, xn= Hxn/H齐次坐标表示法的优点将平移、旋转、缩放等变换同统一的方式表示,6,齐次坐标表示就是用n+1维向量表示一个n维向量。,规范化齐次坐标表示就是h=1的齐次坐标表示。,基本几何变换规范化齐次坐标,恒等变换平面图形的恒等变换保持原图形的大小、形状、位置不变, 其变换矩阵为：,7.2 二维几何变换的齐次坐标表示,8,基本几何变换平移变换,平移是指将p点沿直线路径从一个坐标位置移到另一个坐标位置的重定位过程。,图6-1 平移变换,1 0 0 设：P= x y 1 = x y 1 0 1 0 Tx Ty 1 令：T(Tx,Ty)= 1 0 0 0 1 0 Tx Ty 1 记：P=P*T(Tx,Ty) Tx，Ty称为平移矢量。,基本几何变换平移变换,10,比例变换是指对p点相对于坐标原点沿x方向放缩Sx倍，沿y方向放缩Sy倍。其中Sx和Sy称为比例系数。,基本几何变换比例变换,图6-2 比例变换(Sx=2,Sy=3),11,矩阵形式： Sx 0 0 设：P= x y 1 = x y 1 0 Sy 0 0 0 1 令：S(Sx,Sy)= Sx 0 0 0 Sy 0 0 0 1 记：P=P*S(Sx,Sy) Sx，Sy称为比例系数。,基本几何变换比例变换,12,基本几何变换比例变换,图6-3 比例变换,13,整体比例变换：当S1，图形整体缩小；当S1，图形整体放大。,基本几何变换比例变换,14,二维旋转是指将p点绕坐标原点转动某个角度（逆时针为正，顺时针为负）得到新的点p的重定位过程。x =rcos(+) =rcoscos-rsinsin =xcos-ysin y =rsin(+) =rcossin+rsincos =xsin+ycos,基本几何变换旋转变换,图6-4 旋转变换,15,矩阵形式：逆时针旋转角 cos sin 1 设：P= x y 1 = x y 1 - sin cos 0 0 0 1 令：R()= cos sin 1 - sin cos 0 0 0 1 记：P=P*R(),基本几何变换旋转变换,16,基本几何变换二维变换矩阵,T1= a b 比例、旋转、对称、错切等； c dT2= l m 平移T3= p 投影 qT4= s 整体比例,17,对称变换后的图形是原图形关于某一轴线或原点的镜像。,基本几何变换对称变换,18,基本几何变换对称变换,19,(1)关于x轴对称,基本几何变换对称变换,图6-6 关于x轴对称,20,(2)关于y轴对称,图6-6 关于y轴对称,基本几何变换对称变换,21,(3)关于原点对称,基本几何变换对称变换,图6-6 关于原点对称,22,(4)关于y=x轴对称,基本几何变换对称变换,图6-6 关于xy对称,23,(5)关于y=-x轴对称,基本几何变换对称变换,图6-6 关于xy对称,24,错切变换，也称为剪切、错位变换，用于产生弹性物体的变形处理。,基本几何变换错切变换,图6-7 错切变换,沿X方向关于Y轴的错切 矩形p1p2p3p4沿X方向错切变换，得到矩形p1p2p3p4， 错切角，点(x,y)变换为： x=x+y*tan()，y=y令：shx=tan() 记：x y 1 = x y 1 1 0 0 shx 1 0 0 0 1,基本几何变换错切变换,沿Y方向关于X轴的错切 矩形p1p2p3p4沿Y方向错切变换，得到矩形p1p2p3p4,错切角，点(x,y)变换为： x=x，y=y+x*tan()令：shy=tan() 记：x y 1 = x y 1 1 shy 0 0 1 0 0 0 1,基本几何变换错切变换,沿两个方向的错切 x=x+y*tan() y=y+x*tan() 令： shx=tan() 、shy=tan() 记：x y 1 = x y 1 1 shy 0 shx 1 0 0 0 1,基本几何变换错切变换,28,其变换矩阵为：,(1)沿x方向错切：b=0(2)沿y方向错切：c=0(3)两个方向错切：b0，c0,基本几何变换错切变换,29,二维图形几何变换的计算,几何变换均可表示成P=P*T的形式。1. 点的变换,30,2. 直线的变换,二维图形几何变换的计算,31,3. 多边形的变换,二维图形几何变换的计算,32,复合变换,图形作一次以上的几何变换，变换结果是每次变换矩阵的乘积。任何一复杂的几何变换都可以看作基本几何变换的组合形式。复合变换具有形式：P=PT=P(T1T2T3Tn) =P T1T2T3Tn(n1),33,复合变换二维复合平移,34,复合变换二维复合比例,35,复合变换二维复合旋转,36,复合变换,旋转变换等价于先比例后错切，或者先错切后比例。,矩阵相乘是符合结合律，但不符合交换律。ABC=(AB)C= A(BC)ABBC在连续的同种变换的特殊情况下，矩阵相乘可以符合交换律。二次连续旋转，可以用任意顺序进行；连续的平移或连续的比例变换可以交换；两向相同（Sx=Sy）的比例变换与旋转变换可以交换。,复合变换,38,相对任一参考点的二维几何变换,相对某个参考点(xF,yF)作二维几何变换，其变换过程为：(1) 平移；(2) 针对原点进行二维几何变换；(3) 反平移。,相对于任一固定点的比例变换则： P=PT(-xA,-yA)S(sx,sy)T(xA,yA)记：SA(sx,sy)= T(-xA,-yA)S(sx,sy)T(xA,yA) = 1 0 0 sx 0 0 1 0 0 = sx 0 0 0 1 0 0 sy 0 0 1 0 0 sy 0 -xA -yA 1 0 0 1 xA yA 1 xA(1-sx) yA(1-sy) 1,相对任一参考点的二维几何变换,围绕任一基准点的旋转变换则： P=PT(-xA,-yA)R()T(xA,yA)记：RA()= T(-xA,-yA)R()T(xA,yA) = 1 0 0 cos sin 0 1 0 0 0 1 0 -sin cos 0 0 1 0 -xA -yA 1 0 0 1 xA yA 1= cos sin 0 -sin cos 0 xA(1-cos)+yA sin yA(1-cos)-xAsin 1,例1 错切变换 矩形P1P2P3P4沿X轴、Y轴双向错切。设：tan()=2,tan()=1 1 0 0 1 1 0 1 0 0 1 1 00 1 02 1 0 0 1 0 =2 1 0 1 1 1 0 0 1 -1-1 1 2 1 1,则P= -1 -1 1 1 1 0 = -1 -1 1 3 -1 1 2 1 0 3 3 1 -1 4 1 2 1 1 9 4 1 3 4 1 13 8 1,相对任一参考点的二维几何变换,例2 组合变换平面图形变换举例 设P1P2P3的三个顶点分别为：P1(10,20), P2(20,20), P3(15,30), 它绕点Q(5,25)逆时针方向旋转30。它的复合变换由如下三种变换组成: (1) 平移，使Q移到原点O, 平移常量l=-5, m=-25, 平移变换矩阵为：,相对任一参考点的二维几何变换,(1) 平移，使Q移到原点O, 平移常量l=-5, m=-25, 平移变换矩阵为T1 ，平移变换后的P1P2P3。,相对任一参考点的二维几何变换,(2) 绕原点逆时针旋转30，旋转变换矩阵为T2 ，旋转变换后的P1P2P3。,y,Q,O,x,相对任一参考点的二维几何变换,(3) 最后将Q点移回原来位置Q(5,25), 平移变换矩阵为T3 ，旋转变换后的P*1P*2P*3 。,相对任一参考点的二维几何变换,46,相对任意方向的二维几何变换,相对任意方向作二维几何变换，其变换的过程是：(1) 旋转变换，使任意方向与某个轴重合； (2) 针对坐标轴进行二维几何变换；(3) 反向旋转，回到原来的方向。,图 关于任意轴的对称变换T1：平移(0,-Ty)，使L过坐标原点，图形A变换为A1R1：旋转-，使L与X轴重合，图形A1变换为A2RFx：图形A2关于X轴的对称图形A3R2：旋转，图形A3变换为A4T2：平移（0,Ty)，使L回到原来的位置，图形A4变换为A5，此时，A5是A关于L的对称图形。总的变换： T1R1RFxR2T2 (7.37),相对任意方向的二维几何变换,对任意直线的对称变换 设：直线的方程为：ax + by + c = 0则：在、两轴上的截距分别为-c/a和-c/b； 直线的斜率为tg= -a/b 。,(1)让直线沿轴方向平移c/a，使其通过坐标系原点。变换矩阵为： 1 0 0 T1= 0 1 0 c/a 0 1,(2)让直线绕坐标系原点旋转-角，使与轴重合。变换矩阵为： cos -sin 0 T2= sin cos 0 0 0 1,(3) 由于原直线已与轴重合，于是对于直线的对称变换即为对于轴的对称变换。变换矩阵为： 1 0 0 T3= 0 -1 0 0 0 1,(4)绕原点旋转角，使直线恢复到原倾斜位置。变换矩阵为： cos sin 0 T4= -sin cos 0 0 0 1,(5)让直线沿轴方向平移-c/a，使其回到原来位置。变换矩阵为： 1 0 0 T5= 0 1 0 -c/a 0 1,综合以上的五步，对任意直线的对称变换过程为：x* y* 1 = x y 1T1T2T3T4T5 = x y 1T组合变换矩阵为：cos2 sin2 0T = sin2 - cos2 0 (c/a)(cos2 -1) (c/a) sin2 1,55,相对任意方向的二维几何变换,例 相对直线y=x的反射变换T= cos(-45) sin(-45) 0 1 0 0 cos(45) sin(45) 0 -sin(-45) cos(-45) 0 0 -1 0 sin(45) c0s(45) 0 0 0 1 0 0 1 0 0 1,56,例 将正方形ABCO各点沿下图所示的(0,0)(1,1)方向进行拉伸（比例变换），结果为如图所示的，写出其变换矩阵和变换过程。,复合变换,可能发生的变换：沿（0，0）到（1，1）的比例变换,图6-11 沿固定方向拉伸,58,坐标系之间的变换,问题：已知XOY坐标系上的P(xp,yp)，求P转换到XOY坐标系上的P(xp,yp)。,图6-9 坐标系间的变换,59,图6-10 坐标系间的变换的原理,坐标系之间的变换,分析：在xoy坐标系中有点p*，其坐标与p点在xoy坐标系下的坐标相等：opx*=opx;opy*=opy;则p*点的坐标是p点变换到p点的坐标。,可以分两步进行：,图6-14 坐标系间的变换的步骤,于是：,62,光栅变换,直接对帧缓存中象素点进行操作的变换称为光栅变换。光栅平移变换：,图6-12 光栅平移变换,63,90、180和270的光栅旋转变换：,光栅变换,每行像素值颠倒擦掉；每行像素次序颠倒；交换其行列。 行的次序颠倒。图6-13 光栅旋转变换,64,任意角度的光栅旋转变换：,光栅变换,图6-14 任意角度的光栅旋转变换 像素A的亮度由区域1、2、3的亮度加权平均而得。,65,光栅比例变换：进行区域的映射处理。,光栅变换,图6-15 光栅比例变换 根据sx和sy的大小，取出对应于变换后图像中的一个像素点的原图中的相应像素区域，对其区域的像素点的亮度加权平均，得变换后像素的亮度。,66,变换的性质,平移、比例、旋转、错切和反射等变换均是二维仿射变换的特例，反过来，任何常用的二维仿射变换总可以表示为这五种变换的复合。,二维仿射变换是具有如下形式的二维坐标变换：,67,仅包含旋转、平移和反射的仿射变换维持角度和长度的不变性；比例变换可改变图形的大小和形状；错切变换引起图形角度关系的改变，甚至导致图形发生畸变。,变换的性质,68,二维观察,基本概念二维观察变换二维裁剪OpenGL中的二维观察,坐标系 建模坐标系(MC,Modeling Coordinate System) 用户坐标系(WC,World Coordinate System)直角坐标系(又称笛卡尔坐标系)坐标系极坐标系 观察坐标系(VC,Viewing Coordinate System) 规范化坐标系(NDC,Normalized Coordinate System) 设备坐标系(DC,Device Coordinate System),二维观察,坐标系1. 建模坐标系(MC,Modeling Coordinates) 依据物体而建的局部坐标系，是直角右手坐标系，长度单位用户自定，取值范围整个实数域。2. 世界坐标系(WC,World Coordinates) 又称用户坐标系，场景采用的坐标系，是直角右手坐标系，长度单位用户自定，取值范围整个实数域。,二维观察,坐标系3. 设备坐标系(DC,Device Coordinates) 依设备而定的坐标系，是二维直角坐标系，原点和轴的定义依设备不同而不同，长度单位是设备的步距，取值范围有限的整数。4. 规格化设备坐标系(NDC,Normalized Device Coordinates) 一种虚拟的坐标系，与具体设备无关，其取值范围在01之间，起到将WC与DC联系起来的作用。 用户的绘图数据经过转换成NDC中的值, 使得图形有了统一的设备空间。 这对图形的统一处理, 带来很大的方便, 从而提高图形程序的可移植性。,二维观察,坐标系 MC、WC、NDC、DC之间的转换 图 二维场景从模型坐标系到设备坐标系的变换序列(Xmc,Ymc)-(Xwc,Ywc)-(Xndc,Yndc)-(Xdc,Ydc),二维观察,窗口 在世界坐标系(WC)中，指定或选取一个矩形区域(Window)视区 在规格化设备坐标系(NDC)或设备坐标系(DC)上，指定一个矩形区域(ViewPort)，用于显示窗口内的图形。开窗口 先将图形关于窗口进行裁剪，然后将裁剪后的保留在窗口内的图形, 变换成显示器屏幕上指定视区内的图形。 开窗变换也叫取景变换，它包括裁剪运算和窗口到视区的变换。,二维观察基本概念,74,要将窗口内的图形在视区中显示出来，必须经过将窗口到视区的变换（Window-Viewport Transformation）处理，这种变换就是观察变换（Viewing Transformation）。,二维观察基本概念,76,观察坐标系(View Coordinate)是依据窗口的方向和形状在用户坐标平面中定义的直角坐标系。规格化设备坐标系(Normalized Device Coordinate)也是直角坐标系，它是将二维的设备坐标系规格化到（0.0，0.0）到（1.0，1.0）的坐标范围内形成的。,二维观察基本概念,77,引入了观察坐标系和规格化设备坐标系后，观察变换分为如下图所示的几个步骤，通常称为二维观察流程。,二维观察基本概念,图6-19 二维观察流程,78,变焦距效果,二维观察基本概念,图6-20 变焦距效果（窗口变、视区不变） 视区大小不变，当窗口变小，放大显示；当窗口变大，缩小显示，则产生焦距（又称变焦）缩放的效果；,79,整体放缩效果,漫游效果 视区大小不变，窗口大小不变，只改变窗口位置，则产生摇镜头（又称漫游）的效果。,二维观察基本概念,图6-21 整体放缩效果（窗口不变、视区变）,80,用户坐标系到观察坐标系的变换,用户坐标系到观察坐标系的变换分由两个变换步骤合成：平移：将观察坐标系原点移动到用户坐标系原点；,81,旋转：绕原点旋转使两坐标系重合,用户坐标系到观察坐标系的变换,82,假设观察坐标系的原点在用户坐标系中的坐标为(x0,y0)，观察坐标系与用户坐标系之间的夹角为，则变换矩阵为：,用户坐标系到观察坐标系的变换,83,窗口到视区的变换,观察窗口左下角(xwl,ywb)，右上角(xwr,ywt)。视区左下角(xvl,yvb)，右上角(xvr,yvt)。,图6.23 窗口-视区变换示意图,要求画面相对比例保持不变。图 窗口到视区的变换窗口内点(xw,yw)映射到视区(xv,yv)，应满足：(xw xwmin) /(xwmax xwmin)=(xv xvmin) /(xvmax xvmin) (yw ywmin) /(ywmax ywmin)=(yv yvmin) /(yvmax yvmin),窗口到视区的变换,Xv= (xvmax xvmin) /(xwmax xwmin)* (xw xwmin) + xvminyv= (yvmax yvmin) /(ywmax ywmin)* (yw ywmin) + yvmin简化： Xv= Axw +B Yv= Cyw +D 其中：A= (xvmax xvmin) /(xwmax xwmin) B=xvmin xwmin A C= (yvmax yvmin) /(ywmax ywmin) D=yvmin ywmin C,窗口到视区的变换,86,将窗口内的点（xw,yw）映射到相对应的视区内的点（xv,yv）需进行以下步骤：将窗口左下角点移至用户系统系的坐标原点，平移矢量为(-xwl,-ywb)；针对原点进行比例变换，使窗口大小与视区相等，比例因子为：Sx=(xvr-xvl)/(xwr-xwl) Sy=(yvt-yvb)/(ywt-ywb)(3)进行反平移，使窗口与视区重合，平移矢量为(-xvl,-yvb)。,窗口到视区的变换,窗口到视区的变换：NWC-DC=T1(-xwl,-ywb)S(Sx,Sy)T2 (-xvl,-yvb)= A 0 0 0 C 0 B D 1其中：A= (xvr-xvl)/(xwr-xwl) B=xvl xwlA C= (yvt-yvb)/(ywt-ywb) D=yvb ywb C,窗口到视区的变换,这里：A、C称为比例因子，B、D称为平移因子当A=C，窗口到视区的映射，可以保持在X、Y两方向有相同的比例；当A=C=1，则保持图形变换前后大小保持不变。,88,裁剪,在二维观察中，需要在观察坐标系下对窗口进行裁剪，即只保留窗口内的那部分图形，去掉窗口外的图形。假设窗口是标准矩形，即边与坐标轴平行的矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）四条边描述。点(x,y)在窗口内，则满足：wxlxwxr、wybywyt。,89,二维直线段的裁剪,已知条件：（1）窗口边界wxl，wxr，wyb，wyt的坐标值；（2）直线段端点p1p2的坐标值x1,y1,x2,y2。,图6.24 直线段与窗口的3种关系,图6.25 直线段与窗口边界的2种交点实交点：直线段与窗口矩形边界的交点;虚交点：处于直线段延长线或窗口边界延长线上的交点。,91,二维直线段的裁剪,直线裁剪的基本原理首先确定哪些直线全部保留或全部裁剪；对于部分裁剪的直线，应求出直线与窗口边界的交点；把从交点开始到边界外的部分裁剪掉。常用裁剪算法Cohen-Sutherland裁剪算法(又称编码裁剪算法)中点分割算法参数化算法(Liang-Barsky算法),基本思想 对于每条线段P1P2分为三种情况处理分为三种情况处理:若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。若线段不满足“取”或 “弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。,Cohen-Sutherland算法,93,Cohen-Sutherland算法,编码 对于任一端点(x,y)，根据其坐标所在的区域，赋予一个4位的二进制码D3D2D1D0。 编码规则如下：,（1）若xwxl，D0=1，否则D0=0；,（2）若xwxr，D1=1，否则D1=0；,（3）若ywyb，D2=1，否则D2=0；,（4）若ywyt，D3=1，否则D3=0。,95,（1）判断 裁剪一条线段时，先求出直线段端点p1和p2的编码code1和code2，然后：若code1|code2=0，表明p1和p2区域码都为0000，p1和p2完全在窗口内，则对直线段简取之；若code1&code20，表明p1和p2区域码至少在某一位上同为1，p1和p2完全在窗口外，则对直线段简弃之；,Cohen-Sutherland算法,96,（2）求交 若上述判断条件不成立，则需求出直线段与窗口边界的交点。 通常检测P1，如果P1在窗口外，则从低到高的顺序检测P1的编码CODE1，根据值为1的编码位确定与P1P2求交的窗口边界，按左右上下边界情况求出交点代替p1，用新的P1P2重新计算；如果P1在窗口内（即编码为全0），则将P1和P2交换，继续求交。,Cohen-Sutherland算法,97,（2）求交 设：已知一条端点为(x1,y1)和(x2,y2)的直线：左边界（x=xwl）、右边界（x=xwr）交点的计算：y = y1 + k(x - x1)；上边界（y=ywb）、下边界（y=ywt）交点的计算：x = x1 + (y-y1)/k；其中，k（y2-y1）/（x2-x1）。,Cohen-Sutherland算法,计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点，其区域码分别为code1和code2。 if(code1!=0)code=code1;else code=code2;if(LEFT这里：LEFT=0001、RIGHT=0010、BOTTOM=0100、TOP=1000,Cohen-Sutherland算法,99,p2,p1,Cohen-Sutherland算法,100,用编码方法实现了对完全可见和不可见直线段的快速接受和拒绝；求交过程复杂，有冗余计算，并且包含浮点运算，不利于硬件实现。,Cohen-Sutherland算法,101,中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点。,中点分割算法,基本思想 是Cohen-Sutherland算法的改进，为了避免使用乘除法求直线段与窗口边界的交点，用不断对分线段的方法排斥线段在窗口外的部分，最后求出离线段端点最远的可见点(所谓可见点就是线段落在窗口内的点)，若这两点存在，则这两点就是线段P1P2的可见线段端点。,如图：A、B分别为距p1、p2最近的可见点，Pm为p1p2中点。,中点分割算法,首先对线段端点进行编码，并把线段与窗口的关系分为三种情况: 线段P1P2全在窗口内，保留；线段P1P2完全在窗口外，不保留；线段和窗口有交，用中点分割的方法求出线段与窗口的交点。用中点分割的方法 将线段等分为二段，作、处理。直至每条线段要么完全在窗口内，要么完全在窗口外为止。,中点分割算法,求从P1出发寻找最远的可见点的步骤：设：线段的端点在窗口内称为可见点，其区域码为0000 。测试P2是否在窗口内。若是, 则P2就是离P1最远的可见点, 结束; 否则, 进行下一步。对P1、P2的区域码作逻辑与，若结果不为0，表明P1、P2是在窗外同侧,线段P1P2全部不可见, 弃之，结束；否则, 进行下一步。,（3）取P1P2的中点Pm(x1+x2)/2,(y1+y2)/2), 若Pm可见，则Pm代替P1，重复步骤(3)；若Pm不可见, 则需要判断Pm和P2的关系：如果Pm和P2在窗口的同侧外面（即Pm、P2的区域码逻辑与不为0），则Pm代替P2，重复步骤(3)；如果Pm和P2不在窗口的同侧外面（即Pm、P2的区域码逻辑与为0），则Pm代替P1，重复步骤(3);（4）一直进行到分点与线段端点距离达到分辨率精度为止。,106,特点：主要计算过程只用到加法或位移运算，易于硬件实现，同时适合于并行计算。,中点分割算法,107,Liang-Barsky算法,LiangBarsky算法是直线段的基于矩形窗口的参数化裁剪方法。,广义地讲：4条裁剪边界会与线段相交，有4个交点。,108,设直线段的两个端点坐标分别为(x1, y1)和(x2, y2)，其参数方程为：,对于直线上一点（x,y）,若它在窗口内则有：,Liang-Barsky算法,令,则有,令,当qk0，则线段起始点p1在该边界外部（不可见侧）；当qk0，则线段起始点P1在该边界内部（可见侧）。当qk=0，则线段起始点P1在该边界上；当pk=0，则线段与该边界平行；p1和p2符号互斥；p3和p4符号互斥；当pk=0并且qk0 ，则整条线段在该边界之外。(k=1,2,3,4，分别对应左、右、下、上),k0(上限组),线段从窗口边界延长线的内部延伸到外部。,P1x2P3y2,P10,P20,P30,P40,例如：,1=p2=0，线段AF平行左右边界；线段A(q10)完全在边界外；同理线段F(q20)亦在边界外。,Liang-Barsky算法,图6.29 直线段与窗口边界平行的情况,3=p4=0，线段GL平行上下边界；线段G(q40)完全在边界外；同理线段L(q30)亦在边界外。,设直线从(x1,y1)到(x2,y2)连线方向作正向且无限延伸，同时，窗口的各边界也无限延伸。pk0(上限组),线段从窗口边界延长线的内部延伸到外部。,在有交的情况下，下限组分布在直线的起始点一侧，上限组分布在直线的终止点一侧。,Liang-Barsky算法,上限组的最大值和下限组的最小值分别对应于直线段在窗口内部分的端点（假定存在）。,Liang-Barsky算法,P30,Umax,P10,Umin,Umin,Umax,Umax=max(0,pk0|上限组，线段出去),P20,P20,P40,P30,P40,P10,Umax=max(0,pk0|上限组，线段出去),P10,Umin,Umax,P20,P40,P30,当pk0时, 可以计算出线段与边界k的延长线的交点参数：u=qk/pk 对于每条直线，都有4个交点参数u，通过比较，可以计算出一对参数umax和umin：umax的值表示由线段从外到内遇到的矩形边界（p0）所决定。umin取1和qk/pk值之中的最小值，即： umin =min(qk/pk|Pk0,1),Liang-Barsky算法,当p1=p2=0，则表明直线段平行于左右边界，如果：q10或q20，则线段完全在边界外，弃之；q10并且q20，则线段只与上下边界求交， 计算：uk=qk/pk(pk0,k=3,4)。当p3=p4=0，则表明直线段平行于上下边界，如果：q30或q40，则线段完全在边界外，弃之；q30并且q40，则线段只与左右边界求交， 计算：uk=qk/pk(pk0,k=1,2)。当pk0，则计算出线段与边界k的延长线的交点参数：u=qk/pk (pk0,k=1,2,3,4)。,Liang-Barsky算法,再分别计算：umax =max(0,qk/pk|Pk0,1)根据umax, umin,可以判断直线是如何裁剪的：如果umaxumin，则线段完全落在裁剪窗口之外，弃之。若umaxumin，则线段在窗口内，由参数umax，umin计算出裁剪线段的端点(x1+x*u,y1+y*u)。,Liang-Barsky算法,例：直线L1与4个边界延伸线的交点，直线L1方向与Pk取值如表所示：对于L1, umaxumin ，则线段L1被裁剪； 对于L2, umaxumin ，则线段L2完全落在窗口之外，弃之。,Liang-Barsky算法,算法步骤：(1)输入直线段的两端点坐标：(x1,y1)和(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。(2)若x=0，则p1=p2=0。此时进一步判断是否满足q10且q20，则进一步计算umax和umin。算法转(5)。(3)若y=0，则p3=p4=0。此时进一步判断是否满足q30且q20，则进一步计算umax和umin。算法转(5)。(4)若上述两条均不满足，则有pk0（k=1,2,3,4）。此时计算umax和umin。(5)求得umax和umin后，进行判断：若umaxumin，则直线段在窗口外，算法转(7)。若umaxumin，利用直线的参数方程求得直线段在窗口内的两端点坐标。(6)利用直线的扫描转换算法绘制在窗口内的直线段。算法结束。,void Line_Clipping(float x1, float y1, float x2, float y2,rect *pRect)float dx=x2-x1,dy=y2-y1,umax=0.0,umin=1.0; /比较左、右边界，获得最大的umax if Clip_Top(-dx,x1- pRect-xw_xmin,umax,umin) /左边界 if Clip_Top(dx,pRect-xw_xmax-x1, umax,umin)/右边界 /比较下、上边界，获得最小的umin if Clip_Top(-dy,y1- pRect-yw_xmin, umax,umin)/下边界if Clip_Top(dy,pRect-xw_xman-y1, umax,umin)/上边界 line(int)(x1+umax*dx),(int)(y1+umax*dy),(int)(x1+umin*dx),(int)(y1+umin*dy);,Liang-Barsky算法,int Clip_Top(float p,float q,float ,Liang-Barsky算法,特点：每修改一次u1或u2只需要一次除法；在u1和u2确定后，直线与窗口的交点只需要计算一次；不足之处，只能应用于矩形窗口的情况。,Liang-Barsky算法,125,多边形的裁剪,多边形的裁剪结果应仍是多边形，即仍是一个封闭的线框图形。如果直接应用直线的裁剪方法，那么，在一般的情况下就不可能得到明确的结果。可能得到一系列不连接的直线段，如图所示。,126,Sutherland-Hodgeman多边形裁剪,基本思想：将多边形的边界作为一个整体，每次用窗口的一条边界对要裁剪的多边形进行裁剪，用部分窗口的边框线段去拼补留下的缺口，体现分而治之的思想。,127,窗口的一条边以及延长线构成的裁剪线把平面分为两个区域，包含窗口区域的区域称为可见侧；不包含窗口区域的域为不可见侧。设：S为前一点；P为当前点，I为窗口边界内外两点连线与窗口边界的交点。则有4种情况： 外-内 内-内 内-外 外-外,Sutherland-Hodgeman多边形裁剪,128,算法（逐边裁剪）：为窗口各边界裁剪的多边形存储输入与输出顶点表。以左、右、底、顶边界裁剪流水线处理窗口各边界裁剪多边形，每次仅仅裁剪顶点，并且将裁剪后的顶点传输到下一边界的裁剪程序每次裁剪时，去掉边界不可见侧内的顶点，保留边界可见侧内的顶点和窗口边界内外两点连线与窗口边界的交点。,Sutherland-Hodgeman多边形裁剪,Sutherland-Hodgeman多边形裁剪,适合凸多边形，对于凹多边形，只有一个输出顶点表，最后一个顶点总是连着第一个顶点，如图：,Sutherland-Hodgeman多边形裁剪,132,设：多边形按顺时针处理顶点：对于由外到内的顶点，沿多边形边界的方向；对于由内到外的顶点，按顺时针沿窗口边界的方向。,Weiler-Atherton多边形裁剪,结果生成二个多边形,133,设：多边形按顺时针处理顶点，且用户多边形定义为Ps，窗口矩形为Pw。 算法从Ps的任一点出发，跟踪检测Ps的每一条边，当Ps与Pw相交时（实交点），按如下规则处理： (1)若是由不可见侧进入可见侧，则输出可见直线段，转(3)；,Weiler-Atherton多边形裁剪,134,(2)若是由可见侧进入不可见侧，则从当前交点开始，沿窗口边界顺时针检测Pw的边，即用窗口的有效边界去裁剪Ps的边，找到Ps与Pw最靠近当前交点的另一交点，输出可见直线段和由当前交点到另一交点之间窗口边界上的线段，然后返回处理的当前交点；(3)沿着Ps处理各条边，直到处理完Ps的每一条边，回到起点为止。,Weiler-Atherton多边形裁剪,下图示了Weiler-Atherton算法裁剪凹多边形的过程和结果。,设：被裁剪的多边形为主多边形；裁剪区域为裁剪多边形，二者均用顶点环形表定义。例如：,Weiler-Atherton多边形裁剪,主多边形和裁剪多边形的边界可以相交，也可以不相交。 若它们相交，则交点必成对出现（进点，出点）。,主多边形的边离开裁剪多边形内部时的交点,主多边形的边进入裁剪多边形内部时的交点,Weiler-Atherton多边形裁剪,基本思想：算法从进入交点开始，沿主多边形的外部边界逆时针方向向前跟踪，直至找到它与裁剪多边形的一个交点为止。在交点处改变方向，开始沿裁剪多边形的外部边界逆时针方向向前跟踪，直至找到它与主多边形的一个交点为止。再改变方向，再次沿主多边形的外部边界逆时针方向向前跟踪，继续上述过程，直至到达算法起始点位置为止。适合任意凸或凹的多边形的裁剪。,Weiler-Atherton多边形裁剪,主多边形：P0,P1,P2,P3,P4,P5,P6,P7裁减多边形： Q0,Q1,Q2,Q3,Q4,Q5 q0,q1,q2,q3交点：I1,I2,I3,I4,I5,I6,I7,I8,Weiler-Atherton多边形裁剪,Weiler-Atherton裁剪算法步骤建立主多边形和裁剪多边形的顶点表（外：逆时针；内：顺时针）；求主多边形和裁剪多边形的交点，并将这些交点按顺时针插入到两多边形的顶点表中，在两多边形顶点表中的相同交点间建立双向指针；,Weiler-Atherton多边形裁剪,裁剪：如果存在没有被跟踪过的交点，则执行以下步骤：a）建立空的裁剪结果多边形的顶点表；b）选取任一个没有被跟踪过的交点为起点，将其输出到裁剪结果多边形的顶点表；c）如果该交点是进点，则跟踪主多边形边界；否则跟踪裁剪多边形边界；d）跟踪多边形边界，每遇到多边形顶点，将其输出到裁剪结果多边形的顶点表中，直至遇到新的交点；e）将该交点输出到裁剪结果多边形的顶点表中，并通过链接该交点的双向指针，改变跟踪方向；f）重复d）、e），直至回到起点为止。,Weiler-Atherton多边形裁剪,图 Weiler-Atherton裁剪算法,图 Weiler-Atherton算法的裁剪过程,143,2. 文字裁剪文字裁剪的策略包括几种：串精度裁剪字符精度裁剪笔划、象素精度裁剪3. 外部裁剪保留落在裁剪区域外的图形部分、去掉裁剪区域内的所有图形，这种裁剪过程称为外部裁剪，也称空白裁剪。,其他裁剪,144,6.6 OpenGL中的二维观察,指定矩阵堆栈指定裁剪窗口指定视区,145,指定矩阵堆栈,指定当前操作的是投影矩阵堆栈glMatrixMode(GL_PROJECTION);初始化，即指定当前操作的矩阵堆栈的栈顶元素为单位矩阵。 glLoadIdentity()；,146,指定裁剪窗口,定义二维裁剪窗口gluOtho2D(xwmin, xwmax, ywmin, ywmax);其中，双精度浮点数xwmin, xwmax, ywmin, ywmax分别对应裁剪窗口的左、右、下、上四条边界。默认的裁剪窗口，四条边界分别为：wxl=-1.0，wxr=1.0，wyt=-1.0，wyb=1.0。,147,指定裁剪窗口,指定视区glViewPort(xvmin，yvmin， vpWidth，vpHeighht)；xvmin和yvmin指定了对应于屏幕上显示窗口中的矩形视区的左下角坐标，单