图形的几何变换及裁剪.ppt

第四章图形的几何变换及裁剪,4.1概述为了使被显示的对象数字化，通常是采用适当的坐标系来描述被处理的对象。图形和数字之间的联系也就是通过坐标建立起来的。因此，所谓图形的几何变换实质上就是图形的坐标变换。,一.几种坐标系,1.世界坐标系(WorldCoordinates)为了描述被处理的对象，要在对象所在的空间中定义一个坐标系，这个坐标系的长度单位和坐标轴的方向要适合对被处理对象的描述，这个坐标系通常就称之为世界坐标系或用户坐标系。世界坐标系一般采用右手三维笛卡儿坐标系。,x,y,z,o,2.观察坐标系(ViewCoordinates)产生三维物体的视图，必须规定观察点(视点)和观察方向。好比照相时选择拍摄的位置和方向。左手笛卡儿坐标系(上图)：观察坐标系的原点通常设置在观察点(视点)，Z轴作为观察方向。右手笛卡儿坐标系：视点确定在Z轴上的某一个位置，Z轴仍为观察方向(下图)。,x,y,z,o,x,y,z,o,视点,视点,3.设备坐标系(DeviceCoordinates)与图形设备相关连的坐标系叫设备坐标系。例如，显示器以分辨率确定坐标单位，原点在左下角或左上角；绘图机绘图平面以绘图精度确定坐标单位，原点一般在左下角。4.规格化设备坐标系(NormalDeviceCoordinates)为了使图形处理过程做到与设备无关，通常采用一种虚拟设备的方法来处理，也就是图形处理的结果是按照一种虚拟设备的坐标规定来输出的。这种设备坐标规定为0X1，0Y1，这种坐标系称之为规格化设备坐标系。,窗口：为选择图形的局部而设置的一个区域，一般采用矩形。其作用类似于照相机的取景器。视图区：在图形输出设备上定义的用于输出图形的区域，一般也采用矩形。窗口视图区变换：在窗口和视图区确定以后，找出两者之间的坐标对应关系，以便实现两者之间的映射。,二.窗口视图区变换,x,y,o,W(窗口),x,y,o,V(视图区),wxL,wxR,wyB,wyT,vxL,vxR,vyB,vyT,(wx,wy),(vx,vy),vxvxLwxwxL由两图的比例关系：vxRvxLwxRwxLvyvyBwywyBvyTvyBwyTwyB可得：vxRvxLwxRwxLvyTvyBwyTwyB,=,=,vx=,(wxwxL)+vxL,vy=,(wywyB)+vyB,若视图区为规格化设备坐标，即：vxRvxL=1；vyTvyB=1vxL=0；vyB=0则：wxwxLwxRwxLwywyBwyTwyB然后，再从规格化设备坐标映射到具体的物理设备坐标中。注意：当视图区和窗口在x方向和y方向上的伸缩比不同时，图形映射后会发生畸变。,vx=,vy=,x,y,o,1,1,V(视图区),规格化设备坐标,窗口视图二维变换过程,建立物体的WC,变换到VC,在VC空间进行裁剪,投影到NDC,变换到DC,在图形设备上输出,三.图形变换的特点图形变换就是改变图形的几何关系，即改变图形顶点的坐标，但图形的拓扑关系不变。最基本的图形变换可以分别用矩阵形式表示为：平移变换PPTmTmMxMyMx、My分别为X方向和Y方向的平移量。比例变换PPTsSx00SySx、Sy分别表示比例因子。旋转变换PPTrcossin-sincos0时为逆时针旋转0时为顺时针旋转,Ts,Tr,四.齐次坐标从形式上来说，用一个有n+1个分量的向量去表示一个有n个分量的向量的方法称为齐次坐标表示。例如二维平面上的点(x，y)的齐次坐标表示为(hx，hy，h)，h是任一不为0的比例系数。给定一个点的齐次坐标表示:(x，y，h)，该点的二维笛卡儿直角坐标：(x/h，y/h)。同样，对于一个三维空间的向量(x，y，z)，它在四维空间中对应的向量即齐次坐标为(xh，yh，zh，h)，其中h0。齐次坐标的概念可以推广到n维空间的向量。齐次坐标的表示不是唯一的，通常当h=1时，称为规格化齐次坐标。,4.2二维图形变换采用齐次坐标可将二维图形变换表示成如下形式：ab0cd0lm1P*=PM二维变换矩阵中：abcdlm是对图形进行平移变换,x*y*1=xy1,变换后的顶点坐标,变换前的顶点坐标,二维变换矩阵,是对图形进行缩放、旋转、对称、错切等变换。,二维图形变换中要注意的几个问题：1.旋转变换中角度正负的确定：逆时针旋转为正，顺时针旋转为负。2.对称变换是相对于：X轴、Y轴、坐标原点、直线y=x和直线y=x3.弄清错切变换前后的关系：沿X轴方向关于Y的错切-y坐标不变，而x坐标与原坐标值(x,y)及变换矩阵中的c有关，即x*=x+cy沿Y轴方向关于X的错切-x坐标不变，而y坐标与原坐标值(x,y)及变换矩阵中的b有关，即y*=y+bx并且，当c(或b)0时，图形沿X(或Y)正向错切；当c(或b)0时，图形沿X(或Y)负向错切。,4.二维图形的级联(组合)变换对于复杂的图形变换，需要通过若干个变换矩阵的级联才能实现。这里特别要注意的是矩阵级联的顺序，由于矩阵的乘法运算不适用交换率，因此矩阵级联的顺序不同所得到的变换结果也不相同。例如：对任意直线的对称变换（直线方程为Ax+By+C=0）,x,y,o,x,y,o,x,y,o,100T1=010C/A01,cossin0T2=sincos0001,x,y,o,x,y,o,x,y,o,100T3=0-10001,cossin0T4=sincos0001,100T5=010C/A01,组合变换矩阵为：,cos2sin20T=T1T2T3T4T5=sin2cos20(cos2-1)C/Asin2*C/A1,原图形上的任意一点P(x,y)对该直线的对称变换都可用下式实现：x*y*1=xy1T,4.3三维图形变换三维变换矩阵可表示为：abcpdefqghirlmns其中：abcdef产生比例、错切、镜象和旋转等基本变换。ghilmn产生沿x、y、z三轴方向上的平移变换。pq产生透视变换。rs产生等比例缩放变换。,T=,三维图形变换中要注意的几个问题：1.在三维图形的比例变换中，经常会采用s来实现整体的比例变换。当|s|1时，三维图形整体等比例缩小。2.三维图形的对称变换是相对于各个坐标平面进行的。3.三维图形的旋转变换是指绕坐标轴的旋转。在采用右手坐标系的情况下，图形绕坐标轴逆时针旋转时，转角为正(拇指指向坐标轴的方向，其余四指指向旋转方向)，顺时针旋转为负。4.三维图形的级联(组合)变换对于复杂的三维图形变换，也需要通过若干个变换矩阵的级联才能实现。特别要注意的是变换的方法和矩阵级联的顺序。,4.5二维图形的裁剪一.二维线段裁剪方法规则的二维裁剪窗口(矩形)。线段相对于该窗口的情况:线段全部位于窗口的内部（A）线段全部位于窗口外部（B、C）线段的中间部分在窗口内，而二端点在窗口外部（D）线段的一端在窗口内，而另一端在窗口外（E）由上图可知，点位于裁剪窗口之内的条件是：xLxxRyByyT,x=xL,x=xR,y=yB,y=yT,A,B,C,D,E,1.IvanSutherland算法(编码裁剪法)IvanSutherland算法也称Sutherland-Cohen算法。其核心思想是：分区编码和线段分割。分区编码方法：以x=xL、x=xR、y=yT、y=yB将图形区域划分成九个部分。采用四位编码表示端点所处的位置：第一位为“1”时，表示点在y=yT的上方；第二位为“1”时，表示点在y=yB的下方；第三位为“1”时，表示点在x=xR的右方；第四位为“1”时，表示点在x=xL的左方。,x=xL,x=xR,y=yB,y=yT,0000,0001,0010,1000,0100,1001,1010,0101,0110,算法步骤：1确定线段二端点P1和P2的代码值C1和C2（经一系列的判断p1（x1，y1），p2（x2，y2）和xR、xL、yT、yB的比较，分别给代码中的各位赋值）。2对线段的端点进行检测若线段全部在窗口内(c1=0且c2=0)画线若线段全部在窗口外(c1andc20)退出否则(c10orc20且c1andc2=0)要对线段进行分割，关键是求与窗口四边的交点(利用直线的两点式方程)。交点求出后，要对其重新编码，并继续判断。,例图：,P1,P2,C1=0001,C2=0000,P1,P2,C1=0100,C2=0100,P1,P2,C1=0101,C2=1010,P1,P2,A,B,C,D,C1=0000,C2=0000,2.中点分割算法算法的思路：采用与前相似的线段端点编码和相应的检查方法，先判定完全可见线段和显然不可见线段。否则，将线段分割成相等的两段，然后对每一小段重复上述的检查，直至找到每段与窗口边界的交点或分割小段的长度充分小，可以视为一点时为止。实际上，这相当于采用对分查找法求交，分割次数最多不超过线段端点的表示精度。,图例：,P1,P2,Pm1,算法中的关键点：求离p1最近的可见点。（离p2最近的可见点与此类似）新求得的端点必需重新编码（可采用子程序）。线段的可见否均由端点的编码状态确定（可采用子程序）。特点：避免了复杂的乘除运算；可采用并行算法。,3.Liang(梁友栋)-Barsky算法算法的基本思想：从A、B和P1三点中找出最靠近P2的点(P1)，从C、D和P2三点中找出最靠近P1的点(C)，则P1C就是P1P2线段上的可见部分。将被裁剪的线段P1P2表示成参数方程形式：xx1xt其中xx2x1yy1ytyy2y1,x,y,xL,xR,yB,yT,P1,P2,A,B,C,D,(0t1),另外，把窗口的四条边分成二类：始边和终边。当x0(或y0)时称xxL(或yyB)为始边，xxR(或yyT)为终边。当x0(或y0)时称xxL(或yyB)为终边，xxR(或yyT)为始边。求出P1P2和二条始边的交点的参数t1和t1令t1max(t1，t1，0)则t1即为A、B、P1三点中最靠近P2的点的参数。求出P1P2和二条终边的交点的参数t2和t2令t2min(t2，t2，1)则t2即为C、D、P2三点中最靠近P1的点的参数。当t2t1时，方程(1)中参数tt1,t2的线段就是P1P2的可见部分。当t1t2时，整个线段为不可见。,二.字符裁剪方法1.字符的表示方法点阵字符每个字符用一个位图(掩膜)来表示，其大小由位图的尺寸来确定，如79，916，1624等。,1111000,0100100,0100100,0111000,0100000,0100000,0100000,1110000,0000000,P在字库的表示,P的显示结果,矢量字符选一个正方形网格，作为字符的局部坐标空间，网格的大小可选1616，3232，6464等。每个字符由构成它的笔画组成，每个笔画又由其两端确定。每个端点保存它的坐标值及连线标志。,x,y,o,p1,p2,p3,p4,p5,p6,63,63,字符的编码,x1y10,x2y21,x3y30,x4y41,x5y50,x6y61,1,0表示不连线,1表示连线,字符结束标志,特点：除用直线段表示笔画外，还可采用二次三次曲线段。对矢量字符的变换是对其端点进行图形的几何变换。,2.字符的裁剪简单裁剪方法：用点阵字符的掩膜或矢量字符的网格大小作为字符的包围框，若该包围框在窗口内，则显示字符；否则，不予显示。精确裁剪方法：对于点阵字符，判断组成其笔画的每个像素点是否位于窗口内。对于矢量字符，对组成其笔画的每条线段进行裁剪。,三.多边形的裁剪1Sutherland-Hodgman(S-H)算法思路：将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。实现方法：设置二个表输入顶点表(向量)用于存放被裁剪多边形的顶点p1pm。输出顶点表(线性链表)用于存放裁剪过程中及结果的顶点q1qn。输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。,具体操作：Pi若位于边界线的可见一侧，则Pi送输出顶点表Pi若位于边界线的不可见一侧，则将其舍弃。除第一个顶点外，还要检查每一个Pi和前一顶点Pi-1是否位于窗口边界的同一侧，若不在同一侧，则需计算出交点送输出顶点表。最后一个顶点Pn则还要与P1一起进行同样的检查。,p1,p2,p3,p4,p5,q1,q2,q3,q4,算法特点：算法中相对于各窗口边界的裁剪过程相同，且每次都是相对于前一次的结果进行处理。可采用递归算法，可不保留中间多边形的顶点，而节省数据的存储量，但递归会影响速度。,q5,q6,q7,q8,q1,q2,p3,q7,q8,q5,q6,q4,q3,裁剪前：裁剪后：输入顶点表：p1p2p3p4p5输入顶点表:不变输出顶点表：空输出顶点表:q3q1q2p3q7q8q5q6q4,2Weiler-Atherton（W-A）算法W-A算法可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多边形。被裁剪的多边形主多边形裁剪区域裁剪多边形思路：主多边形和裁剪多边形均用它们的顶点表来定义。各多边形的外部边界取顺时针方向，而其内部边界或孔取逆时针方向。主多边形和裁剪多边形的边界若相交，交点必定成对地出现，其中一个交点为主多边形边进入裁剪多边形内部时的交点（称进点），另一个交点则为离开时的交点（称出点）。这两类交点分别用进点表和出点表来存放。,c1,c2,c3,c4,s1,s2,s3,s4,s5,s6,s7,I1,I2,I3,I4,I5,I6,I7,I8,裁剪多边形,主多边形,主多边形裁剪多边形顶点表