二维变换及二维观察.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,二维变换及二维观察,说明：,h,可以取不同的值，所以同一点的齐次坐标不是唯一的。,（2,3）(1,1.5,0.5)(4,6,2)(6,9,3)等等。,普通坐标与齐次坐标的关系为“一对多”,由普通坐标,h,齐次坐标,由齐次坐标,h,普通坐标,当,h,=1时产生的齐次坐标称为“规格化坐标”，因为前,n,个坐标就是普通坐标系下的,n,维坐标。,不包含窗口区域的域为不可见侧。,当b=d=0,a=-1,e=1时，与y轴对称：,算法的基本思想是:从A,B和P0三点中找出最靠近P1的点(P0)。,当b=d=0,a=1,e=-1时，,可将图形变换表示为图形点集规范化次坐标矩阵与某一变换矩阵相乘的形式。,当b=d=0,a=e=-1时，与原点对称：,几何变换均可表示成P=P*T的形式,画当前的直线段p1p2。,否则，若code1&code20，对直线段可简弃之，结束；,(1)若是由不可见侧进入可见侧，则输出可见直线段，转(3)；,不仅裁线条，要处理好多边形的拓朴关系,P*(x*y*1),原图形关于某一轴线或原点的镜像。,90、180和270的光栅旋转变换：,确保p1在窗口外部：若p1在窗口内，则交换p1和p2的坐标值和编码。,虚交点：与窗口边界延长线的交点，,在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。,为窗口各边界裁剪的多边形存储输入与输出顶点表。,(x,y)点对应的齐次坐标为,(x,y)点对应的齐次坐标为三维空间的一条直线,规范化齐次坐标的作用：,可将图形变换表示为图形点集规范化次坐标矩阵与某一变换矩阵相乘的形式。,如：,几何变换,对图形的几何信息经过平移、比例、旋转等变换后产生新的图形，是图形在方向、尺寸和形状方面的变换。,二维变换矩阵,二维空间中某点的变换可以表示成点的齐次坐标与3阶的二维变换矩阵T,2D,相乘：,二维变换矩阵,6.2 基本几何变换,相对于坐标原点和坐标轴进行的几何变换。,平移变换,将p点沿直线路径从一个坐标位置移到另一个坐标位置的重定位过程。,平移是一种不产生变形而移动物体的刚体变换。,T,x,，T,y,称为,平移矢量,变换矩阵,例：已知点P（20，30），求平移（T,x,=20,T,y,=15）后的坐标。,比例变换,对p点相对于坐标原点沿x方向放缩S,x,倍，沿y方向放缩S,y,倍。其中S,x,和S,y,称为比例系数。,变换矩阵,以坐标原点为放缩参照点,旋转变换,将p点绕坐标原点转动某个角度（逆时针为正，顺时针为负）得到新的点p的重定位过程。,逆时针旋转角,(x,y),(x,y,),例：求P(2,1)逆时针旋转30,后的坐标。,当很小时，简化计算：,对称变换,原图形关于某一轴线或原点的镜像。,当,b,=,d,=0,a,=1,e,=-1时，,与,x,轴对称：,当,b,=,d,=0,a,=-1,e,=1时，与,y,轴对称：,当,b,=,d,=0,a,=,e,=-1时，与原点对称：,当,b,=,d,=1,a,=,e,=0时，与,y,=,x,对称：,当,b,=,d,=-1,a,=,e,=0时，与,y,=-,x,对称：,错切变换,也称为剪切、错位变换，用于产生弹性物体的变形处理。,1)当b=0时，图形的,y,坐标不变；,当c0：图形沿+,x,方向作错切位移。,当,c,0：图形沿+,y,方向作错切位移。,当b0：图形沿-,y,方向作错切位移。,二维图形几何变换的计算,几何变换均可表示成P=P*T的形式,1.点的变换,2.直线的变换,3.多边形的变换,4.曲线的变换,6.3 复合变换,图形作一次以上的几何变换，变换结果是每次的变换矩阵相乘。,任何一复杂的几何变换都可以看作基本几何变换的组合形式。,复合变换具有形式：,二维复合平移,P,(,x,y,),P,(,x,y,1),P,*(,x,*,y,*1),（,Tx,1,Ty,1）,（,Tx,2,Ty,2）,得到二维复合平移矩阵：,相加性,二维复合比例,P,(,x,y,),P,(,x,y,1),P,*(,x,*,y,*1),（S,x,1,S,y,1）,（S,x2,S,y2,）,二维复合比例矩阵：,相乘性,二维复合旋转,1,2,P,(,x,y,),P,(,x,y,1),P,*(,x,*,y,*1),二维复合旋转矩阵：,相加性,二维多种复合变换,例：将P(2,3)平移（Tx=5,Ty=6）后再比例(Sx=2,Sy=0.5)变换。,相对任一参考点的二维几何变换,相对某个参考点(x,F,y,F,)作二维几何变换，其变换过程为：,(分解成基本的几何变换）,(1)平移。,(2)针对原点进行二维几何变换。,(3)反平移。,例1.相对点(x,F,y,F,)的旋转变换,T(-X,F,-Y,F,)R()T(X,F,Y,F,),30,（1，1）,(2.5,1.5),(Xp,Yp),T(-1,-1)R(30,)T(1,1),例2.相对点(x,F,y,F,)的比例变换,T(-X,F,-Y,F,)S(S,x,S,y,)T(X,F,Y,F,),（1，1）,(2,1.5),(Xp,Yp),T(-1,-1)S(2,2.5)T(1,1),S,x,=2,S,y,相对任意方向的二维几何变换,相对任意方向作二维几何变换，其变换的过程是：,(1)旋转变换,(2)针对坐标轴进行二维几何变换；,(3)反向旋转,例3.,相对直线y=x的反射变换,将直线顺时针旋转,角：,图形关于,x,轴的反射变换：,(x,y),将(x,y)逆时针旋转,角：,(x,y),可得复合变换矩阵：,坐标系之间的变换,问题,：,可以分两步进行：,于是：,假定x,p,=3,y,p,=4,x0=1,y0=1,Q=30,则：,小结,1.任何几何变换都可以由齐次坐标向量与相应的变换矩阵相乘表示，不同的变换归结为寻找其相应的变换矩阵。,2.复合变换可以看成一系列基本几何变换的合成，将这一系列基本几何变换的变换矩阵相乘得到复合变换矩阵。,光栅变换,直接对帧缓存中象素点进行操作的变换。,光栅平移变换：,90、180和270的光栅旋转变换：,先颠倒每行像素值，,后交换行列,先颠倒每行像素值，,后颠倒行的次序,任意角度的光栅旋转变换：,光栅比例变换：,6.4 两维观察,基本概念,窗口（Window）,在用户坐标系中需要进行观察和处理的一个坐标区域。,视区（Viewport）,窗口映射到显示设备上的坐标区域。,要将窗口内的图形显示到视区中，必须经过将窗口到视区的变换（Window-Viewport Transformation）处理，这种变换称,观察变换,（Viewing Transformation）。,观察坐标系,依据窗口的方向和形状在用户坐标平面中定义的直角坐标系。,x用户,y,用,户,窗口,y,观,察,x,观,察,(a)观察坐标系,引入观察坐标系的目的：简化窗口到视区的变换。,规格化设备坐标：,将二维的设备坐标系规格化到（0.0，0.0）到（1.0，1.0）的坐标范围内形成的坐标系。,x用户,y,用,户,窗口,y,观,察,x,观,察,(a)观察坐标系,1,xNDC,y,N,D,C,视区,1,(b)规格化设备坐标系,引入规格化坐标系的目的：使观察变换独立于设备。,引入了观察坐标系和规格化设备坐标系后，观察变换分为如下图所示的几个步骤，通常称为,二维观察流程,。,二维观察流程的设置，为图形的观察提供了非常灵活的方式：,变焦距效果,整体放缩效果,漫游效果：通过移动窗口。,用户坐标系到观察坐标系的变换,由两个变换步骤合成：,将观察坐标系原点移到用户坐标系原点。,绕原点旋转使两坐标系重合。,窗口到视区的变换,要将窗口内的点（x,w,y,w,）映射到相对应的视区内的点（x,v,y,v,）需进行以下步骤：,将窗口左下角点移至观察坐标系的原点。,针对原点进行比例变换。,进行反平移。,6.5 裁剪,在二维观察中，需要在观察坐标系下对窗口进行裁剪，即只保留窗口内的那部分图形，去掉窗口外的图形。,假设窗口是标准矩形，即边与坐标轴平行的矩形。（wxl，wyt）（wxr，wyb）,点的裁剪,保留满足以下条件的点：,直线段的裁剪,假定直线段用p,1,(x,1,y,1,)p,2,(x,2,y,2,)表示。,直线段和剪裁窗口的可能关系：,完全落在窗口内,完全落在窗口外,与窗口边界相交,实交点,：与窗口边界的交点。,虚交点,：与窗口边界延长线的交点，,或延长线与窗口边界的交点。,Cohen-Sutherland算法,编码裁剪算法,基本思想：对每条直线段p,1,p,2,分三种情况处理：,直线段完全可见，“简取”之。,直线段完全不可见，“简弃”之。,直线段既非“简取”又非“简弃”，需对直线段按交点进行分段，分段后重复上述处理。,编码,：,对于任一端点(x,y)，根据其坐标所在的区域，赋予一个4位的二进制码D,3,D,2,D,1,D,0,。,编码规则如下：,若xwxr，则D,1,=1，否则D,1,=0；,若ywyt，则D,3,=1，否则D,3,=0。,裁剪：,裁剪一条线段时，先求出端点p,1,和p,2,的编码code1和code2，然后：,若code1|code2=0：,简取。,若code1&code20：,简弃。,否则：,求直线段与窗口边界的交点，弃外段。再对另一段重复进行上述处理,。,求交,：,假定直线的端点为(x,1,y,1,)和(x,2,y,2,),左、右边界交点的计算：,上、下边界交点的计算：,算法的步骤：,输入直线段的两端点坐标：p,1,(x,1,y,1,)、p,2,(x,2,y,2,)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。,对p,1,、p,2,进行编码：点p,1,的编码为code1，点p,2,的编码为code2。,若code1|code2=0，简取之，转；否则，若code1&code20，简弃之，转；当上述两条均不满足时，进行步骤。,确保p,1,在窗口外部：若p,1,在窗口内，则交换p,1,和p,2,的坐标值和编码。,按左、右、下、上的顺序求出直线段与窗口边界的交点，并用该交点的坐标值替换p,1,的坐标值。去掉p,1,s这一段。转。,画当前的直线段p,1,p,2,。,算法结束。,算法的特点：,对完全可见或完全不可见线段：快速。,特别适用于大窗口情况。,中点分割算法,基本思想：,当对直线段不能简取也不能简弃时，简单地把线段等分为二段，对两段重复前述测试处理，直至每条线段完全在窗口内或完全在窗口外。,算法的步骤：,输入直线段的两端点坐标：p,1,(x,1,y,1,)、p,2,(x,2,y,2,)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。,对p,1,、p,2,进行编码：点p,1,的编码为code1，点p,2,的编码为code2。,若code1|code2=0，简取之，保留端点坐标，转；否则，若code1&code20，简弃之，转；当上述两条均不满足时，进行步骤。,求出直线段的中点M，将p,1,M、p,2,M入栈,。,当栈不空时，从栈中弹出一条直线段，取为p,1,p,2,，转进行处理。否则，继续。,当栈为空时，合并保留的直线段端点，得到窗口内的直线段p,1,p,2,。画出当前的直线段p,1,p,2,，算法结束。,中点分割算法的核心思想是,通过二分逼近来确定直线段与窗口的交点,。,重新构造,算法步骤,：,若code1|code2=0，对直线段应简取之，结束；否则，若code1&code20，对直线段可简弃之，结束；当这两条均不满足时，进行步骤。,找出该直线段离窗口边界最远的点和该直线段的中点。,判中点是否在窗口内,：,若不在，则把中点和离窗口边界最远点构成的线段丢掉，以线段上的另一点和该中点再构成线段求其中点；如中点在窗口内，则又以中点和最远点构成线段，并求其中点，直到中点接近窗口边界，则该中点就是该线段落在窗口内的一个端点坐标。,如另一点在窗口内，则经,即确定了该线段在窗口内的部分。如另一点不在窗口内，则该点和所求出的在窗口上的那一点构成一条线段，重复步骤,，即可求出落在窗口内的另一点。,算法特点：,只用到加法和位移运算，便于用硬件实现。,梁友栋-Barsky算法,设要裁剪的线段是P,0,P,1,。P,0,P,1,和窗口边界交于A,B,C,D四点。算法的基本思想是:从A,B和P,0,三点中找出最靠近P,1,的点(P,0,)。从C,D和P,1,中找出最靠近P,0,的点(C)。那么P,0,C就是P,0,P,1,线段上的可见部分。,在用户坐标系中需要进行观察和处理的一个坐标区域。,直线段完全可见，“简取”之。,当b=d=0,a=1,e=-1时，,假定直线段用p1(x1,y1)p2(x2,y2)表示。,P(x y 1),否则，若code1&code20，对直线段可简弃之，结束；,求出P0P1与两条始边的交点参数t0,t1,令tL=max(t0,t1,0)，则tL即为三者中离p1最近的点的参数,若code1&code20：,几何变换均可表示成P=P*T的形式,窗口到视区的变换,否则，若code1&code20，对直线段可简弃之，结束；,90、180和270的光栅旋转变换：,相对任意方向的二维几何变换,Sutherland-Hodgeman多边形裁剪 逐边裁剪算法,当c0：图形沿-x方向作错切位移。,线段的参数表示:,x=x,0,+tx,y=y,0,+ty 0=t t,L,则可见线段区间,t,L,t,u,t,0,t,1,t,2,t,3,0,多边形的裁剪,问题的提出：,不仅裁线条，要处理好多边形的拓朴关系,Sutherland-Hodgeman多边形裁剪,逐边裁剪算法,基本思想,：每次用窗口的一条边对多边形进行裁剪。,算法实施策略：,为窗口各边界裁剪的多边形存储输入与输出顶点表。在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。,窗口的一条边以及延长线构成的裁剪线把平面分为两个区域，包含有窗口区域的一个域称为可见侧；不包含窗口区域的域为不可见侧。,沿着多边形依次处理顶点会遇到四种情况：,特点,：,适用于凸多边形，对凹多边形裁剪要作特殊处理。,Weiler-Atherton多边形裁剪,双边裁剪算法,假定按顺时针方向处理顶点，且将用户多边形定义为Ps，窗口矩形为Pw。算法从Ps的任一点出发，跟踪检测Ps的每一条边，当Ps与Pw相交时（实交点），按如下规则处理：,(1)若是由不可见侧进入可见侧，则输出可见直线段，转(3)；,(2)若是由可见侧进入不可见侧，则从当前交点开始，沿窗口边界顺时针检测Pw的边，即用窗口的有效边界去裁剪Ps的边，找到Ps与Pw最靠近当前交点的另一交点，输出可见直线段和由当前交点到另一交点之间窗口边界上的线段，然后返回处理的当前交点；,(3)沿着Ps处理各条边，直到处理完Ps的每一条边，回到起点为止。,下图示了Weiler-Atherton算法裁剪凹多边形的过程和结果。,谢谢观看！,