图形变换及裁剪

1、哈尔滨工业大学计算机学院唐好选2022年年2月月10日日图形变换与裁剪1.窗口和视图区窗口和视图区用户坐标系用户坐标系（world coordinate system，简称WCS）设备坐标系设备坐标系（device coordinate system，简称DCS）窗口区窗口区（window）视图区视图区（viewport） 窗口区与视图区间的映射关系： 窗口区中的任一点(x w , y w) 与视图区中的任一点(x v , y v) 存在如下对应关系：xlxrxlxrxlwxlvwwvvwxvxybytybytybwybvwwvvwyvy（5-1）（5-2）X wO wW x lW x rY

2、wW y bW y t窗口(x w , y w)Y vX vO uV x lV x rV y bV y t视图区(x v , y v)xlxlwxlxrxlxrvvwxwwvvx)(ybybwybytybytvvwywwvvy)(（5-3）（5-4）由式（5-1）和式（5-2）可分别解得：令xlxrxlxrwwvvaybytybytwwvvbxlxlxlxrxlxrvwwwvvcybybybytybytvwwwvvd有baxxwvdcyywv（5-5） （5-6） 5.2.1 二维图形几何变换的原理 二维图形由点或直线段组成 直线段可由其端点坐标定义 二维图形的几何变换：对点或对直线段端点的变

3、换yxP yxP平行于x轴的方向上的移动量平行于y轴的方向上的移动量 xT yT 5.2.2几种典型的二维图形几何变换xxTyPPyT平移变换yxTyyTxx几何关系（5-7）yxTTyxyx矩阵形式（5-8）平行于x轴的方向上的缩放量平行于y轴的方向上的缩放量xSyS指相对于原点的比例变换 yx相对于原点原点的比例变换相对于重心重心的比例变换yx重心yxSSyxyx00 矩阵形式（5-10）yxSyySxx几何关系（5-9）比例变换的性质当 时，变换前的图形与变换后的图形相似 当 时，图形将放大，并远离坐标原点 当 时，图形将缩小，并靠近坐标原点当 时，图形将发生畸变 10yxSSyxSS

4、1yxSSyxSS 1yxSSyxSS 点P绕原点逆时针转角（设逆时针旋转方向为正方向）cossinsincos)sin(sinsincoscos)cos(rrryrrrx（5-12）cossinsincosyxyyxx将式（5-11）代入式（5-12）得：（5-13）sincos ryrx（5-11）几何关系（5-14） cossinsincos yxyx矩阵形式PPyx旋转变换 1.齐次坐标技术的引入齐次坐标技术的引入 平移、比例和旋转等变换的组合变换 处理形式不统一，将很难把它们级联在一起。 2.变换具有统一表示形式的优点变换具有统一表示形式的优点 便于变换合成 便于硬件实现 3.齐次坐

5、标技术的基本思想齐次坐标技术的基本思想 把一个n维空间中的几何问题转换到n+1维空间中解决 齐次坐标表示不是唯一的),.,(21nxxx)/,.,/,/(21nxxx ),.,(21nxxx有n个分量的向量),.,(21nxxx有n+1个分量的向量1规格化的齐次坐标 平移变换 101000111yxTTyxyx 100000011yxSSyxyx 1000cossin0sincos11yxyx 比例变换 旋转变换：时，齐次坐标 表示一个n维的无穷远点 0),.,(21nxxx 1.对称变换对称变换（symmetry）（反射变换或镜像变换） （1）相对于y轴对称yyxx关系几何 11000100

6、01 11yxyxyx形式矩阵oyx对称变换（1）yxo对称变换（2）（2）相对于x轴对称yyxx关系几何 1100010001 11yxyxyx形式矩阵（3）相对于原点对称（即中心对称）（4）相对于直线y=x对称yyxx 1100010001 11yxyxyx关系几何形式矩阵形式矩阵关系几何xyyx 110000101011xyyxyxoxy对称变换（3）xyoy=x对称变换（4）（5）相对于直线y=-x对称xyyx几何关系 110000101011xyyxyx矩阵形式xyoy=-x对称变换（5）（1）沿 x 轴方向关于 y 轴错切 将图形上关于y轴的平行线沿x方向推成角的 倾斜线，而保持y

7、坐标不变。x 错切变换（1）yxayyctgx 有ctga 令yyayxx yyxxx 几何关系11000100111yayxayxyx矩阵形式（2）沿 y 轴方向关于 x 轴错切 将图形上关于x轴的平行线沿y方向推成角的倾斜线，而保持x坐标不变。 x 错切变换（2）yy 11000100111ybxxbyxyx矩阵形式几何关系yyyxx bxxctgyctgb 令bxyyxx 1.相对于任意点（相对于任意点（x0 , y0）的比例变换）的比例变换 对任意点比例变换的步骤： （1）平移变换 （2）相对于原点的比例变换 （3）平移变换 当（x0 , y0）为图形重心的坐标时，这种变换实现的是相对

8、于重心的比例变换。 1010001001yxT1000000yxSSS1010001002yxT 1000000 112233yxSSyxyx 1010001 11001122yxyxyx 1010001 11003344yxyxyx任意点比例变换示意图平移 111yx平移比例 21STTT TyxSTTyxyxyx 1 111112111442.绕任意点（绕任意点（x0 , y0）的旋转变换）的旋转变换 绕任意点旋转变换的步骤： （1）平移变换 （2）对图形绕原点进行旋转变换 （3）平移变换 (x2,y2)(x3,y3)(x0,y0)Oxy(x1,y1)(x4,y4)相对于任意点(x0,y0

9、)的旋转变换 1000cossin0sincos 112233yxyx 1010001 11001122yxyxyx 1010001 11003344yxyxyx任意点旋转变换示意图平移 100yx平移旋转1010001001yxT1000cossin0sincos R1010001002yxT 21RTTT TyxRTTyxyxyx 1 11111211144三维齐次坐标三维齐次坐标(x,y,z)点对应的齐次坐标为点对应的齐次坐标为标准齐次坐标标准齐次坐标(x,y,z,1)右手坐标系右手坐标系),(hzyxhhh0,hhzzhyyhxxhhhxyz平移变换平移变换 1010000100001

10、zyxTTTT放缩变换放缩变换1000000000000zyxsssS 旋转变换旋转变换:右手螺旋方向为正右手螺旋方向为正 绕绕x轴轴100000000001cossinsincos)(xRyxyzzyzoox轴指向纸外10000001000cossinsincos)(yR 绕绕y轴轴zyzxxzxooy轴指向纸外 绕绕z轴轴100001000000cossinsincos)(zRxzxyyxyooz轴指向纸外错切变换错切变换zyxzyxzyxzyxzyxzyx三维错切变换沿z含x错切沿z含y错切沿y含x错切沿y含z错切沿x含y错切 沿x含z错切三维变换的一般形式三维变换的一般形式旋转、比例、

11、错切、对称平移透视投影总体比例44434241343332312423222114131211aaaaaaaaaaaaaaaaA1 三维图形的基本问题 n 平面几何投影 n 平行投影2 透视投影显示器屏幕、绘图纸等是二维的显示对象是三维的解决方法-投影1. 在二维屏幕上如何显示三维物体？在二维屏幕上如何显示三维物体？2. 如何表示三维物体？如何表示三维物体？三维形体的表示-空间直线段、曲线段、多边形、曲面片三维形体的输入、运算、有效性保证-困难解决方法-各种用于形体表示的理论、模型、方法3. 如何反映遮挡关系？如何反映遮挡关系？物体之间或物体的不同部分之间存在相互遮挡关系解决方法-消除隐藏面与

12、隐藏线何谓真实感图形？真实感来源于透视关系和遮挡关系光线传播引起的物体表面颜色的自然分布解决方法建立光照明模型真实感图形绘制4. 如何产生真实感图形如何产生真实感图形三维图形的基本研究内容投影三维形体的表示消除隐藏面与隐藏线1. 建立光照明模型、研究真实感图形绘制方法 如何投影? 生活中的类比-如何拍摄景物？拍摄过程选景取景-裁剪对焦参考点按快门-成像移动方式移动景物移动照相机投影照相机模型选定投影类型 设置投影参数 拍摄方向、距离等三维裁剪 取景投影和显示 成像平面几何投影及其分类 投影将n维的点变换成小于n维的点 将3维的点变换成小于3维的点投影中心观察点、视点投影面不经过投影中心投影线从

13、投影中心向物体上各点发出的射线 平面几何投影 投影面是平面投影线为直线 投影变换投影过程投影的数学表示 投影分类透视投影透视投影平行投影平行投影平行投影 投影中心与投影平面之间的距离为无限投影方向投影方向投影平面投影平面正投影与斜投影正平行投影正平行投影斜平行投影斜平行投影 三视图：正视图、侧视图和俯视图 yx主视图俯视图侧视图一个直角棱台的三视图z 1000010000000001vTyx主视图一个直角棱台的三视图z正视图侧视图yx侧视图一个直角棱台的三视图z100010000100001100001000090cos90sin0090sin90cos1000010000100000LwxT

14、俯视图 yx俯视图一个直角棱台的三视图z10001000010000110000)90cos()90sin(00)90sin()90cos(000011000000000100001phzT从三视图很难想象出实际物体的空间形状解决：投影平面不垂直于任何一个坐标轴正轴测投影正轴测投影 yxz图5 正轴测投影平面的定义10000cossin00sincos0000110000cos0sin00100sin0cosxyyxRRR10000coscossincossin0sincos00cossinsinsincos1000000000100001yxRT100000sincossin00cos000

15、sinsincos Tzyxzyx11 投影方程：120 120120(a) 正等轴测 y z x投影平面三个单位向量将投影成三个长度相等的平面向量，即三根坐标轴有相同的变形系数 Tzyxx.10011.10sinsincosTzyxy.10101.10cos0Tzyxz.11001 .10sincossin100000sincossin00cos000sinsincosT(c)正三轴测yzx投影平面(b)正二轴测投影平面 y z x透视投影 投影中心与投影平面之间的距离为有限 参数：投影方向，距离 例子：室内白炽灯的投影，视觉系统特点：产生近大远小的视觉效果，由它产生的图形深度感强，看起来更

16、加真实。透视投影投影方程yxz投影中心dxyPPyxz投影平面一点透视dr/1dzxdzxdx)|(|dzydzydy)|(|1)/(dzxx1)/(dzyy100010000100001rT11111rzzrzyrzxzyx灭点的个数灭点的个数?灭点：不平行于投影平面的平行线，经过透视投影之后相交于一点，称为灭点.yxzz轴灭点正方体的一点透视及其灭点正方体的一点透视及其灭点空间平行线可认为是相交于无穷远点，空间平行线可认为是相交于无穷远点，灭点可以看成是无穷远点经透视投影后得到的点灭点可以看成是无穷远点经透视投影后得到的点 rrHzyx1001000100001000010100 1/10

17、01rzyx灭点的位置灭点的位置?一点透视两点透视三点透视主灭点:平行于坐标轴的平行线产生的灭点。 一点透视 两点透视 三点透视主灭点的个数由什么决定主灭点的个数由什么决定?1 直线段裁剪直接求交算法Cohen-Sutherland算法 中点分割裁剪算法 梁友栋-Basky算法2 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Atherton算法 裁剪的目的判断图形元素是否在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交裁剪、覆盖裁剪窗口裁剪窗口矩形、圆形、一般多边形矩形、圆形、一般多边形被裁剪对象被裁剪对象线段、多边形、曲线、

18、字符线段、多边形、曲线、字符裁剪的策略裁剪的策略先裁剪，后变换，可避免对窗口外的图形进行变先裁剪，后变换，可避免对窗口外的图形进行变换，效率较高换，效率较高先变换，后裁剪先变换，后裁剪裁剪算法的核心问题裁剪算法的核心问题效率效率点裁剪点裁剪 点点(x, y)在窗口内的充分必要条件是：在窗口内的充分必要条件是： 问题：对于任意多边形窗口，如何判别？问题：对于任意多边形窗口，如何判别？maxminxxxmaxminyyy假定条件矩形裁剪窗口：xmin,xmaxymin,ymax待裁剪线段：任何平面线段相对于凸多边形窗口进行裁剪后落在窗口内的线段不会多于一条PxyP xy000111(,)(,)待裁

19、剪线段和窗口的关系待裁剪线段和窗口的关系 （1）完全落在窗口内）完全落在窗口内（2）完全落在窗口外）完全落在窗口外（3）部分在内，部分在外）部分在内，部分在外为提高效率，算法设计时应考虑：为提高效率，算法设计时应考虑：1. 快速判断情形快速判断情形(1)(2)；2. 设法减少情形设法减少情形(3)求交次数和每次求交时求交次数和每次求交时所需的计算量所需的计算量算法步骤：算法步骤：第一步第一步 判别线段两端点是否都落在窗口内，如果是，判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步；则线段完全可见；否则进入第二步；第二步第二步 判别线段是否为显然不可见，如果是，则裁判别线

20、段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步剪结束；否则进行第三步 ；第三步第三步 求线段与窗口边延长线的交点，这个交点将求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。对余下的另线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束一段重新进行第一步，第二步判断，直至结束 裁剪过程是递归的。裁剪过程是递归的。elseyyCt01max当elsexxCr01max当elsexxCl01min当elseyyCb01min当 特点：特点：对显然不可见线段的快速判别对显然不可见线段的快速判别 编码方法：编码方法：由窗口四

21、条边所在直线把二维平面分成由窗口四条边所在直线把二维平面分成9个区域，每个区域个区域，每个区域赋予一个四位编码，赋予一个四位编码， CtCbCrCl， 上下右左；上下右左；端点编码：端点编码：定义为它所在区域的编码定义为它所在区域的编码结论：结论：当线段的两个端点的编码的逻辑当线段的两个端点的编码的逻辑“与与”非零时非零时 ，显然不可见，显然不可见 100000010010000001001001010101101010窗口bca 求交测试顺序固定求交测试顺序固定(左上右下）左上右下） 最坏情形，线段求交四次。最坏情形，线段求交四次。对于那些非完全可见、又非完全不可见的线段，需要求交，对于那些

22、非完全可见、又非完全不可见的线段，需要求交，求交前先测试与窗口哪条边所在直线有交？求交前先测试与窗口哪条边所在直线有交？(按序判断端点编按序判断端点编码中各位的值码中各位的值ClCtCrCb） 1）特点：用编码方法可快速判断线段特点：用编码方法可快速判断线段-完全可见和显然完全可见和显然不可见。不可见。 2）特别适用二种场合：）特别适用二种场合： 大窗口场合大窗口场合 窗口特别小的场合窗口特别小的场合 基本思想：基本思想： 从从P0点出发找出距点出发找出距P0最近的可见点最近的可见点 从从P1点出发找出距点出发找出距P1最近的可见点最近的可见点 不断地在中点处将线段一分为二，对每段线段重复不断

23、地在中点处将线段一分为二，对每段线段重复Cohen-Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止交点或分割子段的长度充分小可视为一点为止 取中点取中点Pm=(P1+P2)/2。P2P1 P2是离是离P1点最远的可见点点最远的可见点PmP1用用P1Pm代替代替P1P2P2P2用用PmP2代替代替P1P2PmP1 步骤： 步骤1：利用线段的端点编码判断P1P2是否完全在窗口内，若是，则画线段P1P2,裁剪过程结束；若不是，再判断是否完全在窗口外，若是，则无可见线段

24、输出，裁剪结束，否则转步骤2； 步骤2：固定P1，测试P2是否在窗口内，若是，则P2是离P1最远的可见点，返回，否则，转步骤3； 步骤3：将线段P1P2对分，求出中点Pm,编码判断线段PmP2是否全部在窗口外，若是，则舍弃PmP2,用P1Pm代替P1P2，若不是，则用PmP2代替P1P2； 步骤4：对新的P1P2重复步骤1-3，直到线段的长度小于给定的误差时为止，此时可认为在给定精度内求得离P1最远的可见点Pm; 步骤5：固定P2,再测P1,即将线段P1P2的端点对调，重复步骤1-3，找出离点P2最远的可见点Pm; 步骤6：画可见线段PmPm直线直线L与区域的交：与区域的交：当当Q为空集时，线

25、段为空集时，线段AB不可能在窗口中有可见线段。不可能在窗口中有可见线段。当当Q不为空集时，不为空集时，Q可看成是一个一维窗口可看成是一个一维窗口 P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口是一维窗口TS中的可见部分中的可见部分基本思想：基本思想： 把二维裁剪化为一维裁剪问题，并向把二维裁剪化为一维裁剪问题，并向x（或（或y）方向投影以决定可见线段。）方向投影以决定可见线段。Q,;,;,maxminmaxmin4321yyxxLPPPPL),;,(),;,(maxminmaxminyyLxxLTURSP4P1P3P2ymaxyminxminxmaxRTSULAB

26、AS是一维窗口是一维窗口TS中的可见部分中的可见部分存在可见线段的充要条件存在可见线段的充要条件 不为空集不为空集 向向x轴投影，就得到可见线段上点的坐标的变化范围为轴投影，就得到可见线段上点的坐标的变化范围为 TURSAB),max(),max(,min),min(),min(,maxmaxminUTBAUTBAxxxxxxxxxxx),max(),max(,min),min(),min(,maxmaxminUTBAUTBAxxxxxxxxxxxx左端点左端点右端点右端点AB有可见部分的充分必要条件也可表示为有可见部分的充分必要条件也可表示为 ),max(),max(,min),min(),

27、min(,maxmaxminUTBAUTBAxxxxxxxxxx),min(,maxminBAxxxL ),max(,minmaxBAxxxR RxxxxLRLUTUT),min(),max(用直线段裁剪算法，可以吗？用直线段裁剪算法，可以吗？新的问题新的问题：图图1 因丢失顶点信息而无法确定裁剪区域因丢失顶点信息而无法确定裁剪区域ABAB图图2 原来封闭的多边形变成了孤立的线段原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它边界不再封闭，需要用窗口边界的恰当部分来封闭它12123(a)(b)(c)AB图图3 裁剪后的多边形顶点形成的几种情况裁剪后的多边形顶点形成

28、的几种情况分裂为几个多边形分裂为几个多边形关键：关键：不仅在于求出新的顶点，删去界外顶点不仅在于求出新的顶点，删去界外顶点还在于形成正确的顶点序列还在于形成正确的顶点序列分割处理策略分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。在直线的裁剪。流水线过程流水线过程(左上右下左上右下)：左边的结果是右边的开始左边的结果是右边的开始。亦称逐边裁剪算法亦称逐边裁剪算法内侧空间与外侧空间内侧空间与外侧空间多边形的边与半空间的关系多边形的边与半空间的关系 线段与当前裁剪边的位置关系线段与当前裁剪边的位置关系可见一侧可见一

29、侧窗口窗口(a) 输出输出Pi+1当前裁剪边Pi+1Pi可见一侧可见一侧窗口窗口(a) 无输出无输出当前裁剪边Pi+1Pi可见一侧可见一侧窗口窗口(a) 输出输出I当前裁剪边Pi+1Pi可见一侧可见一侧窗口窗口(a) 输出输出I和和Pi+1当前裁剪边Pi+1Pi裁剪结果的顶点构成裁剪结果的顶点构成：裁剪边内侧的原顶点；裁剪边内侧的原顶点；多边形的边与裁剪边的交点。多边形的边与裁剪边的交点。顺序连接。顺序连接。优点：优点：裁剪算法采用流水线方式，适合硬件实现。裁剪算法采用流水线方式，适合硬件实现。可推广到任意凸多边形裁剪窗口可推广到任意凸多边形裁剪窗口逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这几逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这几个多边形沿边框产生多余的线段？个多边形沿边框产生多余的线