图形学第四章

1、第第 四四 章章 图形的几何变换及裁剪图形的几何变换及裁剪 本本 章章 重重 点点 1. 二维图形的变换方法。 2.三维图形的变换方法。 3.二维线段的裁剪方法。 4.多边形的裁剪方法。 难点：难点： 1.二维图形的级联(组合)变换。 2.多边形的裁剪算法。4.1 概述 为了使被显示的对象数字化，通常是采用适当的坐标系坐标系耒描述被处理的对象。图形和数字之间的联系也就是通过坐标建立起来的。因此，所谓图形的几何变换实质上就是图形的坐标变换。 一一. .几种坐标系几种坐标系1. 世界坐标系(W World C Coordinates) 为了描述被处理的对象，要在对象所在的空间中定义一个坐标系，这个

2、坐标系的长度单位和坐标轴的方向要适合对被处理对象的描述，这个坐标系通常就称之为世界坐标系或用户坐标系。世界坐标系一般采用右手三维笛卡儿坐标系。xyzo 2. 观察坐标系(V View C Coordinates) 产生三维物体的视图，必须规定观察点(视点)和观察方向。 好比照相时选择拍摄的位置和方向。 左手笛卡儿坐标系(上图)：观察坐标系的原点通常设置在观察点(视点)，Z轴作为观察方向。 右手笛卡儿坐标系：视点确定在Z轴上的某一个位置，Z轴仍为观察方向(下图)。xyzo视点xyzo视点 3. 设备坐标系(D Device C Coordinates) 与图形设备相关连的坐标系叫设备坐标系。 例

3、如，显示器以分辨率确定坐标单位，原点在左下角或左上角；绘图机绘图平面以绘图精度确定坐标单位，原点一般在左下角。4. 规格化设备坐标系(N Normal D Device C Coordinates) 为了使图形处理过程做到与设备无关，通常采用一种虚拟设备的方法来处理，也就是图形处理的结果是按照一种虚拟设备的坐标规定耒输出的。这种设备坐标规定为0X1，0Y1，这种坐标系称之为规格化设备坐标系。二二. . 图形变换的过程图形变换的过程建立物体的 WC变换到 VC在VC空间 进行裁剪投影到 NDC变换到 DC在图形设备上输出三三. . 图形变换的特点图形变换的特点 图形变换就是改变图形的几何关系，即

4、改变图形顶点的坐标，但图形的拓扑关系不变。 最基本的图形变换可以分别用矩阵形式表示为：平移变换 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个分量的向量的方法称为齐次坐标表示。 例如二维平面上的点(x，y)的齐次坐标表示为(hx，hy， h)，h是任一不为0的比例系数。 给定一个点的齐次坐标表示 : (x，y，h)， 该点的

5、二维笛卡儿直角坐标： (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 = x y 1 变换后的顶点坐标变换前的顶点坐标二维变换矩阵是对图形进行缩放、旋转、对称、错切等变

6、换。 二维基本变换1.比例变换比例变换是让点的x,y坐标各乘以一个比例因子，其变换公式为： x = ax y = dy 因此，可令变换矩阵T为：T= ，则：X Y 1 = ax dy 1 = X Y 1 0000001ad0000001ad其中a，d分别为x，y方向上的比例因子(a，d0)。讨论： 若a = d = 1, 为恒等变换，即变换后点的坐标不变。若a = d1，则为等比变换，变换结果是图形等比例放大（a = d 1）或等比例缩小（a = d 0时沿+X向错切；c0时,沿+Y向错切；b 0 时，图形沿 X (或 Y )正向错切；当 c (或 b ) 0 时，图形沿 X (或 Y )负向

7、错切。 平面图形绕任意点P（Xp,Yp)旋转角，需要通过以下几个步骤来实现： 将旋转中心平移到原点，变换矩阵为： 例例1：绕任意点旋转变换4. 二维图形的级联(组合)变换 对于复杂的图形变换，需要通过若干个变换矩阵的级联才能实现。这里特别要注意的是矩阵级联的顺序矩阵级联的顺序，由于矩阵的乘法运算不适用交换率，因此矩阵级联的顺序不同所得到的变换结果也不相同。 T1 = 1010001ppyx 将图形绕坐标系原点旋转角，变换矩阵为： T2 = 1000cossin0sincos 将旋转中心平移回到原点的位置，变换矩阵为： T3 = 1010001ppyx因此，绕任意点P的旋转变换矩阵为： T =

8、T1 T2 T3 = 1010001ppyx1000cossin0sincos1010001ppyx相乘后得： T = 1)cos1 (sinsin)cos1 (0cossin0sincosppppyxyx显然，当xp=0，yp=0时，即为对原点的旋转变换。 例例2 2：对任意直线的对称变换（直线方程为 Ax + By + C = 0） 直线在X轴和Y轴上的截距分别为C/A和C/B，直线与X轴的夹角为， =arctg(A/B)。 xyoxyoxyo 1 0 0 T1 = 0 1 0 C/A 0 1 cos sin 0T2= sin cos 0 0 0 1yxyoxyoxo 1 0 0T3 =

9、0 -1 0 0 0 1 cos sin 0T4 = sin cos 0 0 0 1 1 0 0 T5= 0 1 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 4.3 三维图形变换三维图形变换三维变换矩阵可表示为： a b c p d e f q h i j r l m n s 其中： a b c d e f 产生比例、错切、镜象和旋转等基本变换。 h i j l m n 产生

10、沿x、y、z三轴方向上的平移变换。 p q 产生透视变换。 r s 产生等比例缩放变换。T = 三维基本变换矩阵左上角的33矩阵的主对角线上的元素a，e，j的作用是使物体产生比例变换。 比例变换矩阵为： T = 0000000000001aej 其中a，e，j分别为沿x，y，z轴方向的比例因子。 对点进行比例变换： x y z 1T = ax ey jz 1 = x y z 1 三维基本变换1. 比例变换 三维对称变换包括对原点、对坐标轴和对坐标平面的对称，常用的是对坐标平面的变换，我们对此加以讨论： 对xoy平面的对称变换 变换矩阵： 1000010000100001xoyT变换后点的坐标：

11、 x y z 1 = x y z 1 Txoy = x y z 1 对xoz平面的对称变换2. 对称变换变换矩阵为： 1000010000100001xozT变换后点的坐标： x y z 1 = x y z 1 Txoz = x y z 1 对yoz平面的对称变换 变换矩阵为： 1000010000100001yozT变换后点的坐标： x y z 1 = x y z 1Tyoz = x y z 1上述的对称变换结果如下图所示。上述的对称变换结果如下图所示。 ZXYZXYZXY分别对分别对XOYXOY（左）、（左）、XOZXOZ（中）和（中）和YOZYOZ（右）平面（右）平面的对称变换结果的对称

12、变换结果 错切变换是指三维立体沿x，y，z三个方向产生错切，错切变换是画斜轴测图的基础，其变换矩阵为： 1010100001bcdfhiT x y z 1T = x+dy+hz bx+y+iz cx+fy+z 1 = x y z 1 由变换结果看出，一个坐标的变化受另外两个坐标变化的影响。 沿x含y错切 3. 错切变换变换矩阵： ( )100010000100001x ydT错切变换： x y z 1Tx(y) = x+dy y z 1 = x y z 1 沿x含z错切 变换矩阵： x(z)10000100h0100001T错切变换： x y z 1Tx(z) = x+hz y z 1 = x

13、 y z 1 沿y含x错切 变换矩阵: ( )100010000100001y xbT错切变换： x y z 1Ty(x) = x y+bx z 1 = x y z 1 沿y含z错切 变换矩阵： ( )100001000100001y ziT错切变换： x y z 1Ty(z) = x y+iz z 1 = x y z 1 沿z含x错切 变换矩阵： z(x)100010000100001cT错切变换： x y z 1Tz(x) = x y z+cx 1 = x y z 1 沿z含y错切 变换矩阵： z(y)100001000100001fT错切变换： x y z 1Tz(y) = x y z+

14、fy 1 = x y z 1 与二维旋转变换类似，三维旋转变换可分为绕坐标轴旋转变换和绕任意轴的旋转变换。 三维旋转变换要比二维旋转变换复杂得多，但方法是相似的。三维旋转变换可以看作是三个二维旋转变换，且旋转轴分别为x，y，z轴。 绕x轴旋转角 变换矩阵为： 10000cossin00sincos00001T4. 旋转变换 绕y轴旋转角 变换矩阵为： cos0sin00100sin0cos00001T 绕z轴旋转角 变换矩阵为： cossin00sincos0000100001TZXYZYXXZY 物体分别绕x（左）、y（中）、z（右）轴旋转90变换结果 将空间一点（x，y，z）平移到一个新的

15、位置（x y z）的变换矩阵为： 1000010000101lmnT 变换后新点的坐标为： x y z 1 = x y z 1T = x+l y+m z+n 1其中：l，m，n分别为沿x，y，z方向上的平移量。 5. 平移变换三维图形变换中要注意的几个问题： 1.在三维图形的比例变换中，经常会采用 s 来实现整体的比例变换。当 |s| 1 时，三维图形整体等比例缩小。 2.三维图形的对称变换是相对于各个坐标平面进行的。 3.三维图形的旋转变换是指绕坐标轴的旋转。 在采用右手坐标系的情况下，图形绕坐标轴逆时针旋转时，转角为正 ( 拇指指向坐标轴的方向，其余四指指向旋转方向 )，顺时针旋转为负。

16、4.三维图形的级联(组合)变换 对于复杂的三维图形变换，也需要通过若干个变换矩阵的级联才能实现。特别要注意的是变换的方法变换的方法和矩阵级联的顺序。矩阵级联的顺序。例:绕任意轴旋转的问题。如图所示，设空间一般位置的旋转轴是AA， A的坐标是(xA，yA，zA)，A的坐标是(xA，yA，zA)，空间一点P(x，y，z)绕AA轴旋转角到P(x，y,z)，即： x y z 1 = x y z 1TAR TAR 为绕任意轴的旋转变换矩阵，它是由基本变换矩阵组合而成，我们的任务就是要构造矩阵TAR ，步骤如下： XZYOP AAP 将点P与旋转轴AA一直起作平移变换，使旋转轴AA过原点，A与原点重合，其

17、变换矩阵为： 10100001000011AAAtzyxTXZYOAA 令AA轴首先绕X轴逆时针旋转角，使其与XOZ平面共面，然后再绕Y轴顺时针旋转角，使其与Z轴重合，该变换矩阵为： 21000cos()0sin()00cossin001000sincos0sin()0cos()000010001rxyT 绕X轴旋转角 绕Y轴旋转角 其中，和角可通过旋转轴的两个端点的坐标计算得到。 XZYOAAA1000010000cossin00sincosz3rT 将P点绕Z轴（即AA轴）旋转角，变换矩阵为： 对步骤作逆变换，将AA旋转回到原来的位置，变换矩阵为： 4xcos( )0sin( )01000

18、01000cos()sin()0sin( )0cos( )00sin()cos()000010001ry T 对步骤作逆变换，将旋转轴平移回到原来的位置，变换矩阵为： 10100001000015AAAtzyxT上述五步连起来，便组成绕任意轴的旋转变换矩阵： trrrt5yz4z3xy21ARTTTTTT4.4 4.4 窗口窗口视图区变换视图区变换 窗口窗口：为选择图形的局部而设置的一个区域，一般采用矩形。其作用类似于照相机的取景器。 视图区视图区：在图形输出设备上定义的用于输出图形的区域，一般也采用矩形。 窗口窗口视图区变换视图区变换：在窗口和视图区确定以后，找出两者之间的坐标对应关系，以便

19、实现两者之间的映射。xyoW(窗口)xyoV(视图区)wxLwxRwyBwyTvxLvxRvyBvyT(wx,wy)(vx,vy) vx vxL wx wxL 由两图的比例关系： vxR vxL wxR 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

20、 wyT wyB然后，再从规格化设备坐标映射到具体的物理设备坐标中。注意：当视图区和窗口在 x 方向和 y 方向上的伸缩比不同时，图形映射后会发生畸变。vx =vy =xyo11V (视图区)规格化设备坐标4.5 4.5 二维图形的裁剪二维图形的裁剪 当用户在平面上定义一个窗口之后，要把窗口内的图形映像到视图区，而把窗口内部分和窗口外部分正确无误地分离开来，这种分离技术我们称之为“裁剪”。 既然裁剪技术要将一个图形窗口内的部分和窗口外的部分分离开来，那么裁剪必然包括两部分内容： 1. 图形上的点是否在窗口内的判断。 2. 求出图形与窗口边界的交点。 一一. . 二维线段裁剪方法二维线段裁剪方法

21、 规则的二维裁剪窗口(矩形)。 线段相对于该窗口的情况:线段全部位于窗口外部（B、C）线段全部位于窗口的内部（A）线段的中间部分在窗口内，而二端点在窗口外部（D）线段的一端在窗口内，而另一端在窗口外（E）由上图可知，点位于裁剪窗口之内的条件是： xL x xR yB y yT x=xLx=xRy=yBy=yTABCDE1. Ivan Sutherland1. Ivan Sutherland算法算法( (编码裁剪法编码裁剪法) ) Ivan Sutherland算法也称Sutherland-Cohen算法。 其核心思想是：分区编码分区编码和线段分割线段分割。 分区编码方法： 以x=xL、x=xR

22、、y=yT、y=yB将图形区域划分成九个部分。采用四位编码表示端点所处的位置：第一位为“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 and c2 0)

23、退出 若线段全部在窗口内(c1= 0 且c2 = 0)画线 否则(c10 or c20 且 c1 and c2 = 0)要对线段进行分割，关键是求与窗口四边的交点( 利用直线的两点式方程 )。交点求出后，要对其重新编码，并继续判断。例图：P1P2C1=0001C2=0000P1P2C1=0100C2=0100P1P2C1=0101C2=1010P1P2ABCDC1=0000C2=00002.中点分割算法中点分割算法算法的思路： 采用与前相似的线段端点编码和相应的检查方法，先判定完全不可见线段和完全可见线段。 否则，将线段分割成相等的两段，然后对每一小段重复上述的检查，直至找到每段与窗口边界的交

24、点或分割小段的长度充分小，可以视为一点时为止。 实际上，这相当于采用对分查找法求交，分割次数最多不超过线段端点的表示精度。 以找出直线段AB上离端点A最远的可见点a为例。(1)排斥性测试 测试直线段AB是否完全被排斥在窗口之外。如果是，则无输出线段，过程就此结束。否则，继续进行(2)。(2)包含性测试 测试B点是否包含在窗口之内。如果是，则B点就是离A点最远的可见点a，过程退出。如果B点没有被包含在窗口之内，那么继续执行(3)。(3)分割直线段AB于中点M，并判断。 若MB被完全排斥在窗口之外，那么便以线段AM为新的线段AB，并返回算法第(1)步重新开始测试。 若MB没有被完全排斥在窗口之外，

25、那么便以线段MB作为新的线段AB，然后返回算法第(1)步重新开始测试。 反复执行上述算法中的三步，直至找到离线段端点A最远的可见点a为止。 这个过程找到了距离端点A的最远的可见点a，而对直线段BA（把直线段的两个端点对调一下）实施同样的算法步骤，便可找到离端点B最远的可见点b。这样，处于窗口内的可见段的两个端点便确定了。AbBaM算法中的关键点：算法中的关键点： 求离端点最远的可见点。 新求得的端点必需重新编码（可采用子程序）。 线段的可见否均由端点的编码状态确定（可采用子程序）。特点特点：避免了复杂的乘除运算；可采用并行算法。3. Liang(Liang(梁友栋梁友栋)-Barsky )-B

26、arsky 算法算法算法的基本思想： 从A、B和 P1三点中找出最靠近P2 的点( P1)，从C、D和 P2三点中找出最靠近 P1的点(C )，则 P1C 就是 P1P2 线段上的可见部分。将被裁剪的线段 P1P2 表示成参数方程形式： xx1xt 其中 xx2x1 yy1yt yy2y1xyxLxRyByTP1P2ABCD( 0 t 1 ) 另外，把窗口的四条边分成二类：始边和终边。x0， xxL为始边， xxR为终边。y0，yyB为始边，yyT为终边。反之，x0， xxR为始边， xxL为终边。y0， yyT为始边，yyB为终边。求出P1P2和二条始边的交点的参数t1和t1令 t1max

27、(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的可见部分。当 t2 t1时，整个线段为不可见。xyxLxRyByTP1P2ABCD二二. . 字符裁剪方法字符裁剪方法1. 1. 字符的表示方法 点阵字符点阵字符每个字符用一个位图(掩膜) 来表示，其大小由位图的尺寸来确定，如 7 9，9 16，16 24 等。 1 1 1 1 0 0 0 0 1 0 0 1 0 00 1 0 0

28、 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等。每个字符由构成它的笔画笔画组成，每个笔画又由其两端确定。每个端端点点保存它的坐标值坐标值及连线标志连线标志。xyop1p2p3p4p5p66363字符的编码x1 y1 0 x2 y2 1x3 y3 0 x4 y4 1x5 y5 0 x6 y6 1 10表示不连线1表示连线

29、字符结束标志特点特点：除用直线段表示笔画外，还可采用二次三次曲线段。 对矢量字符的变换是对其端点进行图形的几何变换。2. 字符的裁剪 简单裁剪方法： 用点阵字符的掩膜或矢量字符的网格大小作为字符的包围框，若该包围框在窗口内，则显示字符；否则，不予显示。 精确裁剪方法： 对于点阵字符，判断组成其笔画的每个像素点是否位于窗口内。 对于矢量字符，对组成其笔画的每条线段进行裁剪。3 3多边形的裁剪多边形的裁剪 平面多边形是由若干直线段围成的平面封闭图形，因此裁剪后的结果仍应是一个多边形，即是封闭的图形，而且仍应保持原多边形各边的连接顺序。 对于多边形的裁剪要着重考虑下列问题：如何把多边形落在窗口边界上

30、的交点正确地、按序连接成裁剪后的多边形，其中包括决定窗口边界及拐角点地取舍。1Sutherland-Hodgman(S-H)算法 该算法的出发点是把一个解决复杂问题的全过程分解为几个简单过程。其中的每个简单过程仅仅是完成一个单边裁剪，所以每一个简单过程都是类似的重复，这样就使复杂问题的解决方法最终得到简化。思路思路：将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再用另一条边界进行裁剪，如此重复多次，便可得到最终结果。实现方法实现方法：设置二个表 输入顶点表(向量)用于存放被裁剪多边形的顶点p1-pm。 输出顶点表(线性链表)用于存放裁剪过程中及结果的顶 点 q1-qn。输入顶点

31、表中各顶点要求按一定顺序排列，一般可采用顺时 针或逆时针方向。相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行 裁剪。具体操作具体操作： 读入顶点Pi，除第一个顶点外，要检查每一个 Pi 和前一顶 点 Pi-1是否位于窗口边界的同一侧，若不在同一侧，则需计算出交点送输出顶点表。 Pi 若位于边界线的可见一侧，则 Pi 送输出顶点表 Pi 若位于边界线的不可见一侧，则将其舍弃。 最后一个顶点还要与第一个顶点一起进行同样的检查。p1p2p3p4p5q1q2q3q4p1p3p4p5q1q2p3p4p5q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前： 裁剪后：输入顶点表：p1p2p3p4p5 输入顶点表: 不变输出顶点表： 空 输出顶点表: q3q1q2p3q7q8q5q6q4算法特点算法特点： 算法中相对于各窗口边界的裁剪过程相同，且每次都是相对于前一次的结果进行处理。 可采用递归递归算法，可不保留中间多边形的顶点，而节省数据的存储量，但递归会影响速度。q3q4q1q2p3p4q5q6q3q4q1q2p3S-H算法流程图 单边裁剪开 始Pi