第5章-二维变换和二维观察总结讲课讲稿.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第5章-二维变换和二维观察总结,5.1 图形变换预备知识,矢量,矢量和,5.1.1 矢量和矩阵,矢量的数乘,矢量的点积,性质,矢量的长度,单位矢量,矢量的夹角,矢量的叉积,矩阵,阶矩阵,n阶方阵,零矩阵,行向量与列向量,单位矩阵,矩阵的加法,矩阵的数乘,矩阵的乘法,矩阵的转置,矩阵的逆,矩阵的含义,矩阵：由mn个数按一定位置排列的一个,整体，简称mn矩阵。,A=,矩阵运算,加法,设A，B为两个具有相同行和列元素的矩阵,A+B=,数乘,kA=k*a,ij,|,i=1.m,j=1,.n,乘法,设A为32矩阵，B为23矩阵,C=A B=,C=C,mp,=A,m n,B,np,c,ij,=,a,ik,*b,kj,单位矩阵,在一矩阵中，其主对角线各元素a,ii,=1,其余皆为0的矩阵称为单位矩阵。n阶单位矩阵通常记作I,n,。A,m n,=A,m n,I,n,k=1,n,逆矩阵,若矩阵A存在AA,-1,=A,-1,A=I，则称A,-1,为A的逆矩阵,矩阵的转置,把矩阵A=(a,ij,),mn,的行和列互换而得到的nm矩阵称为A的转置矩阵,记作A,T,。,(A,T,),T,=A,(A+B),T,=A,T,+B,T,(aA),T,=aA,T,(AB),T,=B,T,A,T,当A为n阶矩阵，且A=A,T,，则,A是对称矩阵。,矩阵运算的基本性质,交换律与结合律师,A+B=B+A;,A+(B+C)=(A+B)+C,数乘的分配律及结合律,a(A+B)=aA+aB;,a(A B)=(aA)B=A(aB),(a+b)A=aA+bA,a(bA)=(ab)A,矩阵乘法的结合律及分配律,A(B C)=(A B)C,(A+B)C=A C+B C,C(A+B)=C A+C B,矩阵的乘法不适合交换律,所谓齐次坐标表示法就是由,n,+1维向量表示一个,n,维向量。如,n,维向量(,P,1,P,2,Pn,)表示为（,hP,1,hP,2,hPn,h,），其中,h,称为哑坐标。,1、,h,可以取不同的值，所以同一点的齐次坐标不是唯一的。,如普通坐标系下的点（2,3）变换为齐次坐标可以是(1,1.5,0.5)(4,6,2)(6,9,3)等等。,2、,普通坐标与齐次坐标的关系为“一对多”,由普通坐标,h,齐次坐标,由齐次坐标,h,普通坐标,3、,当,h,=1时产生的齐次坐标称为“规格化坐标”，因为前,n,个坐标就是普通坐标系下的,n,维坐标。,5.1.2 齐次坐标,(x,y)点对应的齐次坐标为,(x,y)点对应的齐次坐标为三维空间的一条直线,1.将各种变换用阶数统一的矩阵来表示。提供了用矩阵运算把二维、三维甚至高维空间上的一个点从一个坐标系变换到另一坐标系的有效方法。,2.便于表示无穷远点。,例如：（x,h,y,h,h)，令h等于0,3.,齐次坐标变换矩阵形式把直线变换成直线段，平面变换成平面，多边形变换成多边形，多面体变换成多面体。,4.,变换具有统一表示形式的优点,便于变换合成,便于硬件实现,齐次坐标的作用,图形变换是计算机图形学基础内容之一。,几何变换，投影变换，视窗变换,线性变换，属性不变，拓扑关系不变。,作用：,把用户坐标系与设备坐标系联系起来；,可由简单图形生成复杂图形；,可用二维图形表示三维形体；,动态显示。,5.1.3 图形变换,图形的几何变换,图形变换：对图形的几何信息经过几何变换后产生新的图形。,图形变换的两种形式：,1.图形不变，坐标系改变；,2.图形改变，坐标系不变。,我们所讨论的是针对坐标系的改变而讲的。,5.2 基本二维变换内容,图形变换预备知识,Basic transformation（基本变换）,Matrix representation（矩阵表示）,Composite transformation（复合变换）,Other 2D transformations（其他变换）,Transformation between Coordinate Systems,（坐标系间的变换）,Raster method of transformation（变换的光栅方法）,5.2 Basic Transformations基本变换,Def.,改变,对象,坐标描述,的变换称为几何变换，例如改变对象的方向、尺寸和形状。,Def.Geometric transformations alter coordinate descriptions of objects,such as changes in orientation,size and shape.,Types,Translation平移,Rotation旋转,Scaling变比,5,.2.1 2D 平移,Translation平移,Def.图形对象沿直线运动产生的变换,Parameters:,平移向量(t,x,t,y,),Formula:,x=x+t,x,y=y+t,y,x,y,P,P,矩阵表示,x x t,x,P=P=T=,y y t,y,P=P+T,x,y,P,P,50,100,50,100,(-20，20),30,80,70,120,x,y,x,y,Example,5,.2.2 2D 旋转,Rotation旋转,Def.图形对象沿圆弧路径运动产生的变换,Parameters,基准点(pivot)，坐标原点或任意点,旋转角,方向,约定：,逆时针,为正,x,y,(x,y),(x,y),r,x,y,(x,y),(x,y),r,(Xr,Yr),绕原点旋转,绕任意点旋转,Formula,针对坐标原点,x=x*cos,-y*sin,y=x*sin,+y*cos,如何得到上述公式?,针对任意点(x,r,y,r,)旋转的计算公式?,x,y,P,P,x=r*cos(+)=r*(cos*cos-sin*sin),=rcos*cos-rsin*sin=x*cos-y*sin,y=r*sin(+)=r*(cos*sin+sin*cos),=rcos*sin+rsin*cos=x*sin+y*cos,矩阵表示,x x,cos,-,sin,P=P=R=,y y sin,cos,P=R P,旋转也是一种不产生变形而移动对象的刚体变换。,Scaling变比,Def.,改变图形对象大小的变换,Parameters:变比因子(S,x,S,y,),基准点，方向,Formula:,针对坐标原点 针对固定参考点(x,f,y,f,),x=x*S,x,x=x,f,+(x-x,f,)*S,x,y=y*S,y,y=y,f,+(y-y,f,)*S,y,5,.2.3 2D 变比（缩放）,矩阵表示,x x s,x,0,P=P=S=,y y 0 s,y,P=S P,1,1,(2，1),1,2,x,y,x,y,1,Example,2D变比讨论,如果|S,x,|或|S,y,|大于1，则表示图形在X轴方向或Y轴方向放大；,如果|S,x,|或|S,y,|小于1，则表示图形在X轴方向或Y轴方向缩小；,如果|S,x,|=|S,y,|，则表示均匀缩放；,如果|S,x,|S,y,|，则表示差值缩放；,如果|S,x,|或|S,y,|等于1，则表示图形在X轴方向或Y轴方向不变；,如果S,x,或S,y,小于零，则表示图形在X轴方向或Y轴方向作镜面变换。,二维变换内容,图形变换预备知识,Basic transformation（基本变换）,Matrix representation（矩阵表示）,Composite transformation（复合变换）,Other 2D transformations（其他变换）,Transformation between Coordinate Systems,（坐标系间的变换）,Raster method of transformation（变换的光栅方法）,5,.2.4 2D 矩阵表示,在图形系统中，矩阵式实现变换的标准方法。,P,=P+T(平移);,P,=R,P(旋转);,P,=S,P,(变比);,对于平移、旋转和缩放变换，每个基本的变换都可表示为普通距阵形式：,P=M,1,*P+M,2,采用齐次坐标,(x,h,y,h,h)表示每个2D坐标位置(x,y),齐次坐标表示就是用n+1维向量表示n维向量。,P=M*P,5,.2.4 2D 矩阵表示,Point(x,y)-(x,h,y,h,h),-(x,y,1),T,2D graph-,3xn,基本变换参数-,3x3,2D 图形变换坐标计算：,P,最终坐标,=M,变换矩阵,*P,原坐标,平移变换,x 1 0 t,x,x,y=0 1 t,y,y,1 0 0 1 1,P=T(t,x,t,y,)*P,举例,旋转变换,x cos,-sin,0 x,y=sin,cos,0 y,1 0 0 1 1,P=R(,)*P,举例,变比变换,x s,x,0 0 x,y=0 s,y,0 y,1 0 0 1 1,P=S(s,x,s,y,)*P,注意：上述三种都是针对坐标原点和X/Y轴方向的。,举例,Basic transformation（基本变换）,Matrix representation（矩阵表示）,Composite transformation（复合变换）,Other 2D transformations（其他变换）,Transformation between Coordinate Systems,（坐标系间的变换）,Raster method of transformation（变换的光栅方法）,二维变换内容,5,.3 复合变换,进行一次以上的基本变换,复合变换,利用矩阵表示，就可通过计算单个变换的矩阵乘积，将任意顺序变换的矩阵建立为,组合变换矩阵,。,形成变换矩阵的乘积被称为矩阵的合并(concatenation)或复合(composition),5,.3 复合变换,Translations 连续平移,Rotations 连续旋转,Scalings 连续变比,General pivot-point transformations 通用基准点的变换,General Directions transformations 通用方向的变换,5,.3.1 Translations 连续平移,n个连续的平移向量(t,x1,t,y1,),(t,x2,t,y2,),(t,xn,t,yn,)被用于点P，那么最后的点坐标可计算为,P=T(t,xn,t,yn,)*T(t,x2,t,y2,)*T(t,x1,t,y1,)P,=,T(t,xn,t,yn,)*T(t,x2,t,y2,)*T(t,x1,t,y1,),P,计算时，可先计算两个平移变换矩阵的乘积,T(t,x2,t,y2,)T(t,x1,t,y1,)=T(t,x2,+t,x1,t,y2,+t,y1,),连续平移是可加的,平移变换,x 1 0 t,x,1 0 t,x1,y=0 1 t,y,0 1 t,y1,*P,1 0 0 1 0 0 1,1 0,t,x,+t,x1,P=0 1 t,y,+t,y1,*P,0 01,举例,5,.3.2 Rotations 连续旋转,应用于点P的n个连续旋转(,1,),(,2,).(,n,)，得到的点P的坐标可计算为,P=R(,n,)*R(,2,),R(,1,)P,=,R(,n,)*R(,2,)R(,1,),P,R(,2,)R(,1,)=R(,1,+,2,),则P的坐标可计算为 P=R(,1,+,2,)P,连续旋转是可加的.自己推导。,举例,5,.3.3 Scalings 连续变比,n个连续缩放操作S(s,x1,s,y1,),S(s,x2,s,y2,),S(s,xn,s,yn,)的变换距阵连接，产生的组合变换距阵,P,=S(s,xn,s,yn,)*S(s,x2,s,y2,)*S(s,x1,s,y1,)*P,S(s,x2,s,y2,)*S(s,x1,s,y1,)=S(s,x1,*s,x2,s,y1,*s,y1,),连续缩放操作是相乘的,，非叠加的，,自己推导,。,前三个基本变换是针对原点和X,Y轴的。,举例,5.3.4 通用基准点变换,Solution,平移使基准点移动到坐标原点(T),针对原点做指定变换(M),反向平移使基准点回到原始位置(T,-1,),Examples,Example1 针对固定点变比,x,y,(x,f,y,f,),y,x,x,y,x,y,1 0 x,f,0 1 y,f,0 0 1,s,x,0 0,0 s,y,0,0 0 1,1 0-x,f,0 1-y,f,0 0 1,Example2 针对固定点旋转,1 0 x,f,0 1 y,f,0 0 1,x,y,(x,f,y,f,),y,x,cos,-sin,0,sin,cos,0,0 0 1,1 0-x,f,0 1-y,f,0 0 1,x,y,x,y,5.3.5 通用方向变换,Solution,旋转对象使任意方向与坐标轴方向重合,针对坐标轴方向做指定变换,反向旋转使任意方向回到原方向,Example,x,y,S,2,S,1,Example,cos-45,sin-45 0,Sin-45 cos-45 0,0 0 1,1 0 0,0 2 0,0 0 1,x,y,S2,S1,x,y,1,1,S1=1,S2=2,=45,x,1,1,y,cos45,-sin45 0,sin45 cos45 0,0 0 1,3/2 1/2 0,1/2 3/2 0,0 0 1,M=,0 3/2 2 1/2,0 1/2 2 3/2,1 1 1 1,P=M*,0 1 1 0,0 0 1 1,1 1 1 1,=,x rs,xx,rs,xy,trs,x,x,y=rs,yx,rs,yy,trs,y,y,1 0 0 1 1,5.3.6 通用复合变换矩阵,Basic transformation（基本变换）,Matrix representation（矩阵表示）,Composite transformation（复合变换）,Other 2D transformations（其他变换）,Transformation between Coordinate Systems,（坐标系间的变换）,Raster method of transformation（变换的光栅方法）,二维变换内容,5,.3 2D 其他变换,Reflections反射(对称),Reflection about x-axis X轴反射,Reflection about y-axis Y轴反射,Reflection about(0,0)原点反射,Reflection about x=y 45度线反射,Shearing错切,shearing in x X方向错切,shearing in y Y方向错切,1,Reflection反射,about x-axis,1 0 0,0 -1 0,0 0 1,1,2,3,2,3,1,X轴坐标不变,Y轴坐标变反,about y-axis,-1 0 0,0 1 0,0 0 1,1,2,3,1,3,2,Y轴坐标不变,X轴坐标变反,about(0,0),-1 0 0,0 -1 0,0 0 1,1,2,3,1,3,2,X轴坐标变反,Y轴坐标变反,绕原点旋转180,About x=y,0 1 0,1 0 0,0 0 1,y=x,1,2,1,2,X,Y坐标互换位置,举例,2,shearing错切(X/Y方向的拉伸),1 SHx 0,0 1 0,0 0 1,x,y,1,1,2,3,(2,1),(3,1),x,y,1,1,SHx=2,(1,1),1 0 0,SHy 1 0,0 0 1,x,y,1,1,2,3,2,(1,3),(1,2),x,y,1,1,SHy=2,(1,1),举例,二维变换内容,Basic transformation（基本变换）,Matrix representation（矩阵表示）,Composite transformation（复合变换）,Other 2D transformations（其他变换）,Transformation between Coordinate Systems,（坐标系间的变换）,Raster method of transformation（变换的光栅方法）,坐标系间的变换,x,y,x,y,x0,y0,平移(x0,y0)到(0,0),旋转 轴x使与x轴重合,M=R(-,)*T(-x,0,-y,0,),x,y,x,y,x0,y0,y方向的单位矢量v=V/|V|=(v,x,v,y,),V顺旋90度获得x的单位矢量u=(v,y,-v,x,)=(u,x,u,y,),u,x,u,y,0,R=v,x,v,y,0,0 0 1,V,二维变换内容,Basic transformation（基本变换）,Matrix representation（矩阵表示）,Composite transformation（复合变换）,Other 2D transformations（其他变换）,Transformation between Coordinate Systems,（坐标系间的变换）,Raster method of transformation（变换的光栅方法）,二维观察内容,2D Viewing Pipeline（二维观察流程）,Clipping Window,Viewport,2D Clipping（二维裁剪）,Point clipping,Line clipping,Area clipping,Text clipping,5.4.1,2D Viewing Pipeline,Def.常规图形系统中，世界坐标系中指定的用于显示的坐标区域-,裁剪窗口,(,clipping,window,)或,窗口,(,window,),Def.显示设备上用于窗口映射的坐标区域-,视区、视口,(,viewport,),。,Def.通常，世界坐标系中部分场景映射到设备坐标系的过程-,观察(视图、视像)变换,。,世界坐标系,(,W,orld,C,oordinates),图形定义时所采用的坐标系，坐标的大小和尺寸由用户确定。,设备坐标系,(,D,evice,C,oordinates),与一个图形设备相关的坐标系叫设备坐标系。如显示器或打印机有它们自己的坐标系。,规范化坐标系,(,N,ormalized,C,oordinates),它是独立于具体物理设备的一种坐标系，其显示空间在X和Y方向上都是从0到1,坐标系,设备坐标系,x,y,v1,v2,v3,v4,视口,x,y,w1,w2,w3,w4,窗口,世界坐标系,1,1,1,绘图仪,其他输出设备,建模坐标,世界坐标,规范化坐标,设备坐标,窗口-视口变换,x,y,w,1,w,2,w,3,w,4,窗口,(x,w,y,w,),x,y,v,1,v,2,v,3,v,4,视口,(x,v,y,v,),保持视口与窗口中的对象具有同样的相对位置，必须满足,(X,w,-W,1,)/(W,2,-W,1,)=(X,v,-V,1,)/(V,2,-V,1,),(Y,w,-W,3,)/(W,4,-W,3,)=(Y,v,-V,3,)/(V,4,-V,3,),窗口-视口变换,X,v,=S,x,X,w,+t,x,Y,v,=S,y,Y,w,+t,y,缩放系数,S,x,=(V,2,-V,1,)/(W,2,-W,1,),S,y,=(V,4,-V,3,)/(W,4,-W,3,),平移参数,t,x,=(W,2,*V,1,-W,1,*V,2,)/(W,2,-W,1,),t,y,=(W,4,*V,3,-W,3,*V,4,)/(W,4,-W,3,),已知,w,1,=10,w,2,=20,w,3,=40,w,4,=80,v,1,=80,v,2,=110,v,3,=10,v,4,=130,窗口中一点P(15，60)，求视区中的映射点P,?,解：(15-10)/(20-10)=(x,v,-80)/(110-80),(60-40)/(80-40)=(y,v,-10)/(130-10),x,v,=95,y,v,=70,Example,二维观察内容,2D Viewing Pipeline（二维观察流程）,Clipping Window,Viewport,2D Clipping（二维裁剪）,Point clipping,Line clipping,Area clipping,Text clipping,5.4.4,2D,裁剪,裁剪定义Clipping,识别图形在指定区域内或区域外的过程-,裁剪,裁剪的时机,(1)针对窗口边界裁剪,(2)针对视区边界裁剪,裁剪类型,点裁剪,直线裁剪,多边形区域裁剪,曲线裁剪（自学）,文字裁剪,5.4.5,点的裁剪,点(x,y)如果满足下列不,等式则保留：,w1=x=w2,w3=y=w4,w1,w2,w3,w4,(x,y),5.4.6 直线段的裁剪,假定,直线段用p,1,(x,1,y,1,)p,2,(x,2,y,2,)表示。,直线段和剪裁窗口的可能关系：,完全落在窗口内,完全落在窗口外,与窗口边界相交,窗口,直线段与窗口的关系,A,B,C,D,E,F,H,G,I,J,实交点,是直线段与窗口,矩形边界的交点。,虚交点,则是直线段与窗,口矩形边界延长线或直,线段的延长线与窗口矩,形边界的交点。,窗口,实交点与虚交点,A,B,C,D,E,F,H,G,I,J,虚交点,实交点,实交点,实交点,虚交点,虚交点,Cohen-Sutherland直线裁剪算法,Liang梁友栋-Barsky直线裁剪算法,中点分割算法,Nicholl-Lee-Nicholl直线裁剪算法,Cyrus-Beck算法（自学）,直线段的裁剪算法,1.Cohen-Sutherland,直线裁剪算法,基本思想,：,直线由端点标识；,测试直线端点和窗口边界的关系以确定是否,需要计算交点,；,CS 编码方案,扩展窗口的边界将整个2,D,平面划分为9个区域,每个区域赋予一个4位编码,称为区域码,0000,0110,0100,0101,0010,0001,1001,1000,1010,上,下,右,左,w1,w2,w3,w4,编码规则,b,0,=1 iff x w2,b,2,=1 iff y w4,0000,0110,0100,0101,0010,0001,1001,1000,1010,上,下,右,左,w1,w2,w3,w4,算法描述,计算直线端点编码,c1 和 c2;,判断,c1,和,c2,均为0000，保留直线,c1&c2,不为零，同在某一边界外，删除该直线,c1,和,c2,不 均为0000,且,c1&c2,为零，需要进一步求解交点,以L,R,B,T 为序，将x=w1/w2或y=w3/w4带入直线方程，计算直线与窗口边界的交点，将交点和另一端点重复上述过程，直至线段保留或删除,CS线段裁剪算法 举例,P3,P4,1,0000,0110,0100,0101,0010,0001,1001,1000,1010,CS线段裁剪算法 举例,1,3,2,P,1,P,2,0000,0110,0100,0101,0010,0001,1001,1000,1010,算法的步骤,：,(1)输入直线段的两端点坐标：p,1,(x,1,y,1,)、p,2,(x,2,y,2,)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。,(2)对p,1,、p,2,进行编码：点p,1,的编码为code1，点p,2,的编码为code2。,(3)若code1|code2=0，对直线段应简取之，转(6)；否则，若code1&code20，对直线段可简弃之，转(7)；当上述两条均不满足时，进行步骤(4)。,(4)确保p,1,在窗口外部：若p,1,在窗口内，则交换p,1,和p,2,的坐标值和编码。,(5),按左、右、上、下的顺序求出直线段与窗口边界的交点,，并用该交点的坐标值替换p,1,的坐标值。,也即在交点s处把线段一分为二，并去掉p,1,s这一段。,考虑到p,1,是窗口外的一点，因此可以去掉p,1,s。用p,1,替代s转(2)。,(6)用直线扫描转换算法画出当前的直线段p,1,p,2,。,(7)算法结束,。,计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点,if(LEFT&code!=0),x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);,else if(RIGHT&code!=0),x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);,else if(BOTTOM&code!=0),y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);,else if(TOP&code!=0),y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);,程序实现,p1,p2,p3,p4,1,3,2,1,举例,。,程序流程图,优点,：简单，易于实现。,算法中求交点的次数决定了算法的,速度,，最坏要求交三次，反复循环。,在裁剪窗口非常大或非常小时效率很高。,CS线段裁剪算法小结,2,Liang-Barsky直线裁剪算法,思想：基于直线段参数方程分析的快速直线裁剪算法。,参数方程,直线两端点,P,1,(x,1,y,1,),P,2,(x,2,y,2,),x=x,1,+(x,2,-x,1,)u,y=y,1,+(y,2,-y,1,)u,0,u,1,已知直线端点：,起点,P,1,(x,1,y,1,),，终点,P,2,(x,2,y,2,),参数方程：,x=x,1,+(x,2,-x,1,)u,y=y,1,+(y,2,-y,1,)u,P,1,P,2,u1,LB,算法推导,如果直线在窗口内,则,w,1,x,1,+dx*u,w,2,w,3,y,1,+dy*u,w,4,统一表示为：,P,k,*u,Q,k,k=1,2,3,4,P,1,=-dx,Q,1,=x,1,-w,1,P,2,=dx,Q,2,=w,2,-x,1,P,3,=-dy,Q,3,=y,1,-w,3,P,4,=dy,Q,4,=w,4,-y,1,w1,w2,w3,w4,u,b,u,l,u,t,u,r,0,1,dx,dy,P1=-dx,Q1=x1-w1 P2=dx,Q2=w2-x1,P3=-dy,Q3=y1-w3 P4=dy,Q4=w4-y1,算法描述,计算 P,k,Q,k,k=14,P,k,=0，表示直线平行于窗口某边界,Qk=0，直线在窗口内，平行边界内,对 P,k,0的情形,用Q,k,/P,k,计算交点所对应的u值,对每条线计算参数u,1,&u,2,u,1,=Max(,Q,k,/P,k,|,P,k,0,U,1,),如果u1 u2,则直线在窗口外，否则计算交点坐标,x(u)=x1+dx*u,y(u)=y1+dy*u,LB线段裁剪算法 例1,已知线段的两个端点P,1,(3,4)，P,2,(8,2),窗口边界x=1,x=4,y=1,y=3,用LB算法对线段进行裁剪,线段的参数方程,x=3+5u,y=4-2u,P,1,=-5,Q1=2,R1=-2/5,P,2,=5,Q2=1,R2=1/5,P,3,=2,Q3=3,R3=3/2,P,4,=-2,Q4=-1,R4=1/2,u,1,=max(0,-2/5,1/2)=1/2,u,2,=min(1,1/5,3/2)=1/5,u,1,u,2,所以线段,全部被裁剪,线段的两个端点（-2，-1）和（1，1.5）,窗口边界x,1,=-1,x,2,=1,y,1,=-1,y,2,=1,LB线段裁剪算法 例2,x=3,y=2.5,p,1,=-3q,1,=-1 r,1,=1/3,p,2,=3q,2,=3r,2,=1,p,3,=-2.5q,3,=0r,3,=0,p,4,=2.5q,4,=2r,1,=4/5,对于p 0，u,2,=min1，1，4/5=4/5,则u,1,u,2,，则可见线段的端点坐标：,x=x,1,+u,1,x=-1,y=y,1,+u,1,y =-1/6,即(-1,-1/6),x=x,1,+u,2,x=2/5,y=y,1,+u,2,y,=1,即(2/5,1),void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT),float x1,y1,x2,y2,XL,XR,YB,YT;,float dx,dy,u1,u2;,tl=0;tu=1;dx=x2-x1;dy=y2-y1;,if(ClipT(-dx,x1-Xl,&u1,&u2),if(ClipT(dx,XR-x1,&u1,&u2),if(ClipT(-dy,y1-YB,&u1,&u2),if(ClipT(dy,YT-y1,&u1,&u2),displayline(x1+u1*dx,y1+u1*dy,x1+u2*dx,y1+u2*dy),return;,程序实现,bool ClipT(p,q,u1,u2),float p,q,*u1,*u2;,float r;,if(p*u2)return FALSE;,else if(r*u1),*u1=r;return TRUE;,。/下页,else if(p0),r=p/q;,if(r*u1)return FALSE;,else if(r*u2),*u2=r;return TRUE;,else if(q0)return FALSE;,return TRUE;,LB vs.CS,LB 效率高于 CS,因为减少了交点计算次数。参数u1 和 u2 的更新需要四次除法,交点坐标计算至多4次乘法。,Liang-Barsky和Cohen-Sutherland算法很容易扩展为三维裁剪算法,3 中点分割裁剪算法,基本思想：,与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况:,全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理。,对于第三种情况，用中点分割的方法求出线段与窗口的交点。,求线段与窗口的交点,A、B分别为距,P,0,、P,1,最近的可见点，,P,m,为P,0,P,1,中点,问：算法为什么可行？会不会无限循环、不断二分？,从 出发找最近可见点的方法,先求出 的中点,若 不是显然不可见的，并且 在窗口中有可见部分，则距 最近的可见点一定落在 上，所以用 代替 ；,否则取 代替,再对新的 求中点 。重复上述过程，直到 长度小于给定的控制常数为止，此时 收敛于交点。,从 出发找最近可见点采用上面类似方法。,中点分割算法的,核心思想,是,通过二分逼近来确定直线段与窗口的交点,。,举例,4 NLN直线裁剪算法,IDEA,通过在裁剪窗口周围创立,多个区域,，并在求交运算之前进行更多的区域测试，从而,避免,对直线段进行,多次剪裁,。,适用范围,仅仅适用于2D剪裁,算法步骤,从P,1,点向窗口的四个角点发出射线，这四条射线和窗口的四条边界直线一起将二维平面划分为更多的小区域。,线段端点P,1,的三种位置,Case 1,Case 2,Case 3A,Case 3B,P,2,位置?,比较直线段P,1,P,2,的斜率和剪裁区域边界的斜率.,y,t,-y,1,y,2,-y,1,y,t,-y,1,x,r,-x,1,x,2,-x,1,x,l,-x,1,交点计算,p2,裁剪类型,点裁剪,直线裁剪,多边形区域裁剪,曲线裁剪（自学）,文字裁剪,5.4.7,多边形的裁剪,问题的提出：,裁剪算法,Sutherland-Hodgman 算法,Weiler-Atherton 算法,多边形的裁剪算法,1.Sutherland-Hodgeman,多边形裁剪,基本思想：,以多边形,顶点,为初始集合,首先用窗口,左,边界剪裁多,边形，产生新的顶点序列。新的顶点集依次传给,右,边,界、,下,边界和,上,边界进行处理。SH算法最终输出定,义剪裁后的多边形边界的顶点序列。,输入：ABCDEFGH,A,B,C,D,E,F,G,H,输出：A12DEFGH,1,2,用左边界裁剪,A,D,G,H,1,用上边界裁剪,3,4,5,6,7,8,输入：A134D5678GH,输出：K34D56789IHJ,9,I,J,K,沿多边形依次处理顶点有四种情况,剪裁情况一,S out,P in;由外至内,输出 i和p,P,:second,output,S,IN,OUT,i,:first output,剪裁情况二,S&P both in；,由内至内,输出 P,Polygon,being,clipped,P,:output,Clip,boundary,S,IN,OUT,剪裁情况三,S in,P out,由内至外,输出 i,IN,OUT,S,i,output,P,剪裁情况四,S&P both out,由外至外,无顶点输出,(no output),P,S,IN,OUT,1,2,3,4,5,6,窗口左边界,Example,1,2,3,4,5,6,1,2,3,4,5,窗口左边界,1,2,3,4,5,6,1,2,3,4,5,窗口左边界,算法改进,只有当窗口的四个边界都确定一个点在窗口内时才加入到输出顶点表中,V1,V2,V3,V1,V2,V2,V3,问题,SH算法适用于凸多边形,多余线段,Weiler-Atherton 算法,2 Weiler-Atherton,多边形裁剪,算法思想：,通过修改多边形顶点处理顺序(考虑顶点处理方,向)，从而正确显示凹多边形。若顺时针处理多边形顶点，采,用下列规则：,对由外到内的顶点对，沿着,多边形边界,的方向；,对由内到外的顶点对，按顺时针沿,窗口边界,的方向。,Weiler算法适用于任意多边形裁剪区域,Weiler-Atherton,算法步骤,假定,按顺时针方向处理顶点，且将用户多边形定义为Ps，窗,口矩形为Pw。算法从Ps的任一点出发，跟踪检测Ps的每一条,边，当Ps与Pw相交时（实交点），按如下规则处理：,(1)若是由不可见侧进入可见侧，则输出可见直线段，转(3)；,(2)若是由可见侧进入不可见侧，则从当前交点开始，沿窗口边界顺时针检测Pw的边，即用窗口的有效边界去裁剪Ps的边，找到Ps与Pw最靠近当前交点的另一交点，输出可见直线段和由当前交点到另一交点之间窗口边界上的线段，然后返回处理的当前交点；,(3)沿着Ps处理各条边，直到处理完Ps的每一条边，回到起点为止。,下图示了Weiler-Atherton算法裁剪凹多边形的过程和结果。,A,B,C,D,E,C,E,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,Weiler-Atherton算法裁剪凹多边形,(a)裁剪前,(b)Weiler-Atherton算法的裁剪结果,返回,返回,5.4.8,其它裁剪,1.,曲线边界对象的裁剪,曲线边界对象与矩形窗口和多边形窗口的裁剪加速方法;,2.,文字裁剪,文字裁剪的策略包括几种：,串精度裁剪,字符精度裁剪,笔划、象素精度裁剪,3.,外部裁剪,保留落在裁剪区域外的图形部分、去掉裁剪区域内的所有图形，这种裁剪过程称为,外部裁剪,，也称,空白裁剪,。,字符裁剪,串精度,:,将包围字串的外接矩形对窗口作裁剪,字符精度,:,将包围字的外接矩形对窗口作裁剪,以及笔画象素精度,:,将笔划分解成直线段对窗口作裁剪,待裁剪字符串 串精度裁剪 字符精度裁剪 象素精度裁剪,例1：复合平移,求点,P,(,x,y,)经第一次平移变换（,Tx,1,Ty,1），第二次平移变换（,Tx,2,Ty,2）后的坐标,P,*（,x,*,y,*）,解：设点,P,(,x,y,1)经第一次平移变换后的坐标为,P,(,x,y,1)，则,经第二次平移变换后的坐标为,P,*(,x,*,y,*1),变换矩阵为,Tt,=,Tt,1,Tt,2,例2：多种复合组合,例:对一线段先放大2倍(即S,x,=S,y,=2)，再平移T,x,=10,T,y,=0。,解:设点(x,y)为线段上的任意一点,点(x,y)为点(x,y)放大后的坐标则:x,y,1=x,y,1 S,2,(2,2)设点(x,y)为点(x,y)经平移后的坐标为：x,y,1=x,y,1T,2,(10,0)则：x,y,1=x,y,1T,2,(10,0)=x,y,1S,2,(2,2)T,2,(10,0),令：M=