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

1、第四章第四章 图形的几何变换及裁剪图形的几何变换及裁剪4.1 概述 为了使被显示的对象数字化，通常是采用适当的坐标系坐标系来描述被处理的对象。图形和数字之间的联系也就是通过坐标建立起来的。因此，所谓图形的几何变换实质上就是图形的坐标变换。一一.几种坐标系几种坐标系1.世界坐标系(World Coordinates)为了描述被处理的对象，要在对象所在的空间中定义一个坐标系，这个坐标系的长度单位和坐标轴的方向要适合对被处理对象的描述，这个坐标系通常就称之为世界坐标系或用户坐标系。世界坐标系一般采用右手三维笛卡儿坐标系。xyzo 2.观察坐标系(View Coordinates)产生三维物体的视图，

2、必须规定观察点(视点)和观察方向。好比照相时选择拍摄的位置和方向。左手笛卡儿坐标系(上图)：观察坐标系的原点通常设置在观察点(视点)，Z轴作为观察方向。右手笛卡儿坐标系：视点确定在Z轴上的某一个位置，Z轴仍为观察方向(下图)。xyzoxyzo视点视点 3.设备坐标系(Device Coordinates)与图形设备相关连的坐标系叫设备坐标系。例如，显示器以分辨率确定坐标单位，原点在左下角或左上角；绘图机绘图平面以绘图精度确定坐标单位，原点一般在左下角。4.规格化设备坐标系(Normal Device Coordinates)为了使图形处理过程做到与设备无关，通常采用一种虚拟设备的方法来处理，也

3、就是图形处理的结果是按照一种虚拟设备的坐标规定来输出的。这种设备坐标规定为0X1，0Y1，这种坐标系称之为规格化设备坐标系。窗口窗口：为选择图形的局部而设置的一个区域，一般采用矩形。其作用类似于照相机的取景器。视图区视图区：在图形输出设备上定义的用于输出图形的区域，一 般也采用矩形。窗口窗口视图区变换视图区变换：在窗口和视图区确定以后，找出两者 之间的坐标对应关系，以便实现两者之间的映射。二二.窗口窗口视图区变换视图区变换xyoW(窗口)xyoV(视图区)wxLwxRwyBwyTvxLvxRvyBvyT(wx,wy)(vx,vy)vx vxL wx wxL 由两图的比例关系：vxR vxL w

4、xR wxL vy vyB wy wyB vyT vyB wyT wyB可得：vxR vxL wxR wxL vyT vyB wyT wyB=vx=(wx wxL)+vxLvy=(wy wyB)+vyB若视图区为规格化设备坐标，即：vxR vxL=1 ；vyT vyB=1 vxL=0 ；vyB=0 则：wx wxL wxR wxL wy wyB wyT wyB然后，再从规格化设备坐标映射到具体的物理设备坐标中。注意：当视图区和窗口在 x 方向和 y 方向上的伸缩比不同时，图形映射后会发生畸变。vx=vy=xyo11V(视图区)规格化设备坐标窗口窗口视图二维变换过程视图二维变换过程建立物体的 W

5、C变换到 VC在VC空间 进行裁剪投影到 NDC变换到 DC在图形设备上输出三三.图形变换的特点图形变换的特点 图形变换就是改变图形的几何关系，即改变图形顶点的坐标，但图形的拓扑关系不变。最基本的图形变换可以分别用矩阵形式表示为：平移变换 PPTm TmMx My Mx、My分别为X方 向和Y方向的平移量。比例变换 PPTs Sx 0 0 Sy Sx、Sy分别表示比例因子。旋转变换 PPTr cos sin -sin cos 0时为逆时针旋转 0时为顺时针旋转Ts Tr四四.齐次坐标齐次坐标 从形式上来说，用一个有n+1个分量的向量去表示一个有n个分量的向量的方法称为齐次坐标表示。例如二维平面

6、上的点(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 二维图形变换二维图形变换 采用齐次坐标可将二维图形变换表示成如下形式：a b 0 c d 0 l m 1 P*=P M二维变换矩阵中：a b c d l m 是对图形进行平移变换 x*y*1 =

7、x y 1 变换后的顶点坐标变换前的顶点坐标二维变换矩阵是对图形进行缩放、旋转、对称、错切等变换。二维图形变换中要注意的几个问题：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)正向错切

8、；当 c(或 b)0 时，图形沿 X(或 Y)负向错切。4.二维图形的级联(组合)变换 对于复杂的图形变换，需要通过若干个变换矩阵的级联才能实现。这里特别要注意的是矩阵级联的顺序矩阵级联的顺序，由于矩阵的乘法运算不适用交换率，因此矩阵级联的顺序不同所得到的变换结果也不相同。例如例如：对任意直线的对称变换（直线方程为 Ax+By+C=0）xyoxyoxyo 1 0 0 T1=0 1 0 C/A 0 1 cos sin 0T2=sin cos 0 0 0 1xyoxyoxyo 1 0 0T3=0 -1 0 0 0 1 cos sin 0T4=sin cos 0 0 0 1 1 0 0 T5=0 1

9、 0 C/A 0 1组合变换矩阵为：cos2 sin2 0T=T1T2T3T4T5=sin2 cos2 0 (cos2-1)C/A sin2*C/A 1 原图形上的任意一点 P(x,y)对该直线的对称变换都可用下式实现：x*y*1=x y 1T4.3 三维图形变换三维图形变换三维变换矩阵可表示为：a b c p d e f q g h i r l m n s 其中：a b c d e f 产生比例、错切、镜象和旋转等基本变换。g h i l m n 产生沿x、y、z三轴方向上的平移变换。p q 产生透视变换。r s 产生等比例缩放变换。T=三维图形变换中要注意的几个问题：1.在三维图形的比例变

10、换中，经常会采用 s 来实现整体的比例变换。当|s|1 时，三维图形整体等比例缩小。2.三维图形的对称变换是相对于各个坐标平面进行的。3.三维图形的旋转变换是指绕坐标轴的旋转。在采用右手坐标系的情况下，图形绕坐标轴逆时针旋转时，转角为正(拇指指向坐标轴的方向，其余四指指向旋转方向)，顺时针旋转为负。4.三维图形的级联(组合)变换 对于复杂的三维图形变换，也需要通过若干个变换矩阵的级联才能实现。特别要注意的是变换的方法变换的方法和矩阵级联的顺序。矩阵级联的顺序。4.5 二维图形的裁剪二维图形的裁剪 一一.二维线段裁剪方法二维线段裁剪方法 规则的二维裁剪窗口(矩形)。线段相对于该窗口的情况:线段全

11、部位于窗口的内部（A）线段全部位于窗口外部（B、C）线段的中间部分在窗口内，而二端点在窗口外部（D）线段的一端在窗口内，而另一端在窗口外（E）由上图可知，点位于裁剪窗口之内的条件是：xL x xR yB y yTx=xLx=xRy=yBy=yTABCDE1.Ivan Sutherland1.Ivan Sutherland算法算法(编码裁剪法编码裁剪法)Ivan Sutherland算法也称Sutherland-Cohen算法。其核心思想是：分区编码分区编码和线段分割线段分割。分区编码方法：以x=xL、x=xR、y=yT、y=yB将图形区域划分成九个部分。采用四位编码表示端点所处的位置：第一位为

12、“1”时，表示点在y=yT的上方；第二位为“1”时，表示点在y=yB的下方；第三位为“1”时，表示点在x=xR的右方；第四位为“1”时，表示点在x=xL的左方。x=xLx=xRy=yBy=yT000000010010100001001001101001010110算法步骤：算法步骤：1确定线段二端点P1和P2的代码值C1和C2（经一系列的判断 p1（x1，y1），p2（x2，y2）和xR、xL、yT、yB的比较，分别给代码中的各位赋值）。2对线段的端点进行检测 若线段全部在窗口内(c1=0 且c2=0)画线 若线段全部在窗口外(c1 and c2 0)退出 否则(c10 or c20 且 c1

13、 and c2=0)要对线段进行分割，关键是求与窗口四边的交点(利用直线的两点式方程)。交点求出后，要对其重新编码，并继续判断。例图：P1P2C1=0001C2=0000P1P2C1=0100C2=0100P1P2C1=0101C2=1010P1P2ABCDC1=0000C2=00002.中点分割算法中点分割算法算法的思路：采用与前相似的线段端点编码和相应的检查方法，先判定完全可见线段和显然不可见线段。否则，将线段分割成相等的两段，然后对每一小段重复上述的检查，直至找到每段与窗口边界的交点或分割小段的长度充分小，可以视为一点时为止。实际上，这相当于采用对分查找法求交，分割次数最多不超过线段端点

14、的表示精度。图例：P1P2Pm1算法中的关键点：算法中的关键点：求离p1最近的可见点。（离p2 最近的可见点与此类似）新求得的端点必需重新编码（可采用子程序）。线段的可见否均由端点的编码状态确定（可采用子程序）。特点特点：避免了复杂的乘除运算；可采用并行算法。3.Liang(梁友栋梁友栋)-Barsky 算法算法算法的基本思想：从A、B和 P1三点中找出最靠近 P2 的点(P1)，从C、D和 P2三点中找出最靠近 P1的点(C)，则 P1C 就是 P1P2 线段上的可见部分。将被裁剪的线段 P1P2 表示成参数方程形式：xx1xt 其中 xx2x1 yy1yt yy2y1xyxLxRyByTP

15、1P2ABCD(0 t 1)另外，把窗口的四条边分成二类：始边和终边。当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时，整个线段为不可见。二二.字符

16、裁剪方法字符裁剪方法1.字符的表示方法 点阵字符点阵字符每个字符用一个位图(掩膜)来表示，其大小由位图的尺寸来确定，如 7 9，9 16，16 24 等。1 1 1 1 0 0 0 0 1 0 0 1 0 00 1 0 0 1 0 00 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 01 1 1 0 0 0 0 0 0 0 0 0 0 0P在字库的表示P的显示结果 矢量字符矢量字符 选一个正方形网格网格，作为字符的局部坐标局部坐标空间，网格的大小可选16 16，32 32，64 64等。每个字符由构成它的笔画笔画组成，每个笔画又由其两端

17、确定。每个端点端点保存它的坐标值坐标值及连线标志连线标志。xyop1p2p3p4p5p66363字符的编码x1 y1 0 x2 y2 1x3 y3 0 x4 y4 1x5 y5 0 x6 y6 1 10表示不连线1表示连线字符结束标志特点特点：除用直线段表示笔画外，还可采用二次三次曲线段。对矢量字符的变换是对其端点进行图形的几何变换。2.字符的裁剪 简单裁剪方法：用点阵字符的掩膜或矢量字符的网格大小作为字符的包围框，若该包围框在窗口内，则显示字符；否则，不予显示。精确裁剪方法：对于点阵字符，判断组成其笔画的每个像素点是否位于窗口内。对于矢量字符，对组成其笔画的每条线段进行裁剪。三三.多边形的裁

18、剪多边形的裁剪1Sutherland-Hodgman(S-H)算法 思路思路：将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。实现方法实现方法：设置二个表 输入顶点表(向量)用于存放被裁剪多边形的顶点p1pm。输出顶点表(线性链表)用于存放裁剪过程中及结果的顶 点 q1qn。输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时 针或逆时针方向。相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行 裁剪。具体操作具体操作：Pi 若位于边界线的可见一侧，则 Pi 送输出顶点表 Pi 若位于边界线的不可见一侧，则将其舍弃。除第一个

19、顶点外，还要检查每一个 Pi 和前一顶点 Pi-1是否位于窗口边界的同一侧，若不在同一侧，则需计算出交点送输出顶点表。最后一个顶点 Pn则还要与 P1 一起进行同样的检查。p1p2p3p4p5q1q2q3q4算法特点算法特点：算法中相对于各窗口边界的裁剪过程相同，且每次都是相对于前一次的结果进行处理。可采用递归递归算法，可不保留中间多边形的顶点，而节省数据的存储量，但递归会影响速度。q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前：裁剪后：输入顶点表：p1p2p3p4p5 输入顶点表:不变输出顶点表：空 输出顶点表:q3q1q2p3q7q8q5q6q42 2WeilerWeiler-

20、Atherton-Atherton（W-AW-A）算法）算法 W-A算法可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多边形。被裁剪的多边形主多边形主多边形 裁剪区域裁剪多边形裁剪多边形思路思路：主多边形和裁剪多边形均用它们的顶点表来定义。各多边形的外部边界取顺时针方向，而其内部边界或孔取逆时针方向。主多边形和裁剪多边形的边界若相交，交点必定成对地出现，其中一个交点为主多边形边进入裁剪多边形内部时的交点（称进点），另一个交点则为离开时的交点（称出点）。这两类交点分别用进点表进点表和出点表出点表来存放。c1c2c3c4s1s2s3s4s5s6s7I1I2I3I4I5I6I7I8裁剪多边形主多

21、边形主多边形 裁剪多边形 顶点表 顶点表 s1 c1 I1 I8 I2 I1 s2 c2 I3 I2 s3 I3 I4 c3 s4 I4 I5 I5 I6 c4 s5 I6 I7 I7 s6 c1 I8 s7 s1起点算法算法：分别建立主多边形和裁剪多边形的顶点表 求出主多边形与裁剪多边形的交点（进点和出点）并分别建立进点表和出点表 将交点加入各顶点表中 if 进点表为空 then finish1 取一进点作为始点2 跟踪主多边形顶点表，直至发现下一交点，复制这一段主多边形顶点到内表中 根据交点处指针，转到裁剪多边形顶点表中的相应位置跟踪裁剪多边形顶点表，直至发现下一交点，复制这一段裁剪多边形顶点到内表中 if 该交点不是起始点 then 2 if 进点表中还有未遍历到的交点 then 13 finish