计算机图形学教程（第5版 微课版）课件 第5章 图形变换与裁剪

第五章

图形变换与裁剪计算机学院苏小红二维图形的显示流程计算机学院苏小红5.1窗口视图变换

1.窗口和视图区用户坐标系（worldcoordinatesystem，简称WC）设备坐标系（devicecoordinatesystem，简称DC）窗口区（window）视图区（viewport）计算机学院苏小红2.窗口到视图区的变换窗口区与视图区间的映射关系：窗口区中的任一点(xw,yw)

与视图区中的任一点(xv,yv)存在如下对应关系：（5-1）（5-2）XwOwWxlWxrYwWybWyt窗口(xw,yw)YuXuOuVxlVxrVybVyt视图区(xv,yv)窗口与视图区的对应关系计算机学院苏小红

（5-3）（5-4）由式（5-1）和式（5-2）可分别解得：令有（5-5）

（5-6）

计算机学院苏小红5.2二维图形几何变换5.2.1二维图形几何变换的原理二维图形由点或直线段组成直线段可由其端点坐标定义二维图形的几何变换：对点或对直线段端点的变换计算机学院苏小红1.平移变换（translation）平行于x轴的方向上的移动量平行于y轴的方向上的移动量

5.2.2几种典型的二维图形几何变换xy平移变换（5-7）（5-8）计算机学院苏小红平行于x轴的方向上的缩放量平行于y轴的方向上的缩放量2.比例变换（scale）指相对于原点的比例变换

yx相对于原点的比例变换相对于重心的比例变换yx重心（5-10）（5-9）计算机学院苏小红比例变换的性质当时，变换前的图形与变换后的图形相似当时，图形将放大，并远离坐标原点当时，图形将缩小，并靠近坐标原点当时，图形将发生畸变计算机学院苏小红3.旋转变换（rotation）

点P绕原点逆时针转θ度角（设逆时针旋转方向为正方向）（5-11）（5-12）将式（5-11）代入式（5-12）得：（5-13）（5-14）yx旋转变换计算机学院苏小红5.2.3齐次坐标（homogeneouscoordinates）技术

1.齐次坐标技术的引入平移、比例和旋转等变换的组合变换处理形式不统一，将很难把它们级联在一起。

2.变换具有统一表示形式的优点便于变换合成便于硬件实现3.齐次坐标技术的基本思想

把一个n维空间中的几何问题转换到n+1维空间中解决。计算机学院苏小红4.齐次坐标表示齐次坐标表示不是唯一的

有n个分量的向量有n+1个分量的向量哑元或标量因子规格化的齐次坐标计算机学院苏小红5.基本几何变换的齐次坐标表示

平移变换

比例变换旋转变换：6.无穷远点或无穷远区域的齐次坐标表示

时，齐次坐标表示一个n维的无穷远点逆时针为正

计算机学院苏小红5.2.3常用的二维几何变换

1.对称变换（symmetry）（反射变换或镜像变换）（1）相对于y轴对称（2）相对于x轴对称oyx对称变换（1）yxo对称变换（2）计算机学院苏小红（3）相对于原点对称（即中心对称）（4）相对于直线y=x对称oxy对称变换（3）xyoy=x对称变换（4）计算机学院苏小红（5）相对于直线y=-x对称xyoy=-x对称变换（5）计算机学院苏小红2.错切变换（shear）（1）沿x轴方向关于y轴错切将图形上关于y轴的平行线沿x方向推成θ角的倾斜线，而保持y坐标不变。△x

错切变换（1）yx计算机学院苏小红（2）沿y轴方向关于x轴错切将图形上关于x轴的平行线沿y方向推成Ψ角的倾斜线，而保持x坐标不变。

错切变换（2）yx△y计算机学院苏小红问题：如何实现复杂变换？变换分解变换合成5.3.3二维组合变换计算机学院苏小红1.相对于任意点（x0,y0）的比例变换对任意点比例变换的步骤：（1）平移变换（2）相对于原点的比例变换（3）平移变换

当（x0,y0）为图形重心的坐标时，这种变换实现的是相对于重心的比例变换。计算机学院苏小红令任意点比例变换示意图平移平移比例则有计算机学院苏小红2.绕任意点（x0,y0）的旋转变换绕任意点旋转变换的步骤：（1）平移变换（2）对图形绕原点进行旋转变换（3）平移变换

θ(x2,y2)(x3,y3)(x0,y0)θOxy(x1,y1)(x4,y4)相对于任意点(x0,y0)的旋转变换计算机学院苏小红任意点旋转变换示意图平移平移旋转令则有计算机学院苏小红变换的结果与变换的顺序有关（矩阵乘法不可交换）变换的固定坐标系模式相对于同一个固定坐标系先调用的变换先执行，后调用的变换后执行计算机学院苏小红三维几何变换（1/7）三维齐次坐标(x,y,z)点对应的齐次坐标为标准齐次坐标(x,y,z,1)右手坐标系

xyz计算机学院苏小红三维几何变换（2/7）平移变换

放缩变换计算机学院苏小红三维几何变换（3/7）旋转变换:右手螺旋方向为正绕x轴yxyzz’y’zoox轴指向纸外绕轴旋转角计算机学院苏小红三维几何变换（4/7）绕z轴绕y轴计算机学院苏小红三维几何变换（5/7）对称变换关于坐标平面xy的对称变换计算机学院苏小红三维几何变换错切变换zyxzyxzyxzyxzyxzyx三维错切变换沿z含x错切沿z含y错切沿y含x错切沿y含z错切沿x含y错切

沿x含z错切计算机学院苏小红三维几何变换（7/7）三维变换的一般形式哈尔滨工业大学计算机学院苏小红32第五章

图形变换与裁剪

投影变换计算机学院苏小红33基本内容1三维图形的基本问题平面几何投影平行投影透视投影34三维图形的基本问题（1/5）显示器屏幕、绘图纸等是二维的显示对象是三维的解决方法----投影三维显示设备正在研制中1.在二维屏幕上如何显示三维物体？35三维图形的基本问题（2/5）2.如何表示三维物体？二维形体的表示----直线段,折线,曲线段,多边形区域二维形体的输入----简单（图形显示设备与形体的维数一致）三维形体的表示----空间直线段、折线、曲线段、多边形、曲面片三维形体的输入、运算、有效性保证----困难解决方法----各种用于形体表示的理论、模型、方法36三维图形的基本问题（3/5）3.如何反映遮挡关系？物体之间或物体的不同部分之间存在相互遮挡关系遮挡关系是空间位置关系的重要组成部分解决方法----消除隐藏面与隐藏线37三维图形的基本问题（4/5）何谓真实感图形？逼真的示意的人们观察现实世界产生的真实感来源于空间位置关系----近大远小的透视关系和遮挡关系光线传播引起的物体表面颜色的自然分布解决方法建立光照明模型开发真实感图形绘制方法4.如何产生真实感图形38三维图形的基本问题（5/5）三维图形的基本研究内容投影三维形体的表示消除隐藏面与隐藏线建立光照明模型、研究真实感图形绘制方法39照像机模型与投影

如何投影?生活中的类比--如何拍摄景物？拍摄过程选景取景--裁剪对焦—参考点按快门--成像移动方式移动景物移动照相机两个坐标系平面几何投影（1/17）40投影—照相机模型选定投影类型

设置投影参数–拍摄方向、距离等三维裁剪

–取景投影和显示

–成像简单的三维图形显示流程图二平面几何投影（2/17）41平面几何投影及其分类

投影将n维的点变换成小于n维的点

将3维的点变换成小于3维的点投影中心(COP:CenterofProjection)视觉系统—观察点、视点电影放映机—光源投影面不经过投影中心平面--照相机底片曲面—球幕电影,视网膜平面几何投影（3/17）42平面几何投影（4/17）投影线从投影中心向物体上各点发出的射线

直线—光线曲线—喷绘平面几何投影

投影面是平面投影线为直线投影变换投影过程投影的数学表示43平面几何投影（5/17）投影分类投影中心与投影平面之间的距离为无限

投影中心与投影平面之间的距离为有限

44平面几何投影（6/17）透视投影平行投影45平面几何投影（7/17）平行投影

投影中心与投影平面之间的距离为无限是透视投影的极限状态投影方向投影平面46平面几何投影（8/17）正投影与斜投影正平行投影斜平行投影47平面几何投影（9/17）三视图：正视图、侧视图和俯视图

yzx主视图俯视图侧视图图3一个直角棱台的三视图48解决：投影平面不垂直于任何一个坐标轴——正轴测投影

yxz图5正轴测投影平面的定义投影方程：平面几何投影（10/17）49120°120°120°(a)正等轴测yzx投影平面三个单位向量将投影成三个长度相等的平面向量，即三根坐标轴有相同的变形系数正方体的正等轴测投影

平面几何投影（11/17）50正方体的正轴测投影(c)正三轴测yzx投影平面(b)正二轴测投影平面yzx平面几何投影（12/17）51透视投影投影中心与投影平面之间的距离为有限参数：投影方向，距离例子：室内白炽灯的投影，视觉系统特点：产生近大远小的视觉效果，由它产生的图形深度感强，看起来更加真实。平面几何投影（13/17）52

透视投影投影方程yxz投影中心dx’y’P’Pyxz投影平面一点透视平面几何投影（14/17）53灭点的个数?灭点：不平行于投影平面的平行线，经过透视投影之后相交于一点，称为灭点.yxzz轴灭点图7正方体的一点透视及其灭点空间平行线可认为是相交于无穷远点，灭点可以看成是无穷远点经透视投影后得到的点灭点的位置?无穷远点灭点平面几何投影（15/17）54一点透视两点透视三点透视主灭点:平行于坐标轴的平行线产生的灭点。一点透视两点透视三点透视主灭点的个数由什么决定?平面几何投影（16/17）55平面几何投影（17/17）56第五章图形变换与裁剪（三）

5.5二维线段裁剪苏小红计算机科学与技术学院哈尔滨工业大学575.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法梁友栋-Barsky算法2多边形裁剪

Sutherland_Hodgman算法

Weiler-Atherton算法

581.直线段裁剪(1/18)裁剪（clipping）的目的判断图形元素是否在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交裁剪与覆盖的区别591.直线段裁剪(2/18)裁剪窗口矩形、圆形、一般多边形被裁剪对象线段、多边形、曲线、字符设计裁剪算法的核心问题效率高，速度快601.直线段裁剪(3/18)把直线当作点的集合，逐点裁剪点(x,y)在窗口内的充分必要条件是：

问题：极其费时，精度不高。611.直线段裁剪(4/18)把直线当作一个整体来裁剪矩形裁剪窗口：

[xmin，xmax]

[ymin，ymax]待裁剪线段：前提：任何平面线段在凸多边形窗口进行裁剪后，落在窗口内的线段不会多于1条。621.直线段裁剪(5/18)待裁剪线段和窗口的关系完全落在窗口内,完全落在窗口外,部分在内，部分在外.635.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法梁友栋-Barsky算法64直接求交算法直线与窗口边都写成参数形式，求参数值。1.直线段裁剪(6/18)655.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法梁友栋-Barsky算法66Cohen-Sutherland算法1.直线段裁剪(7/18)为提高效率，该算法强调：快速判断情形(1)(2)；减少情形(3)的求交次数和求交所需的计算量。待裁剪线段和窗口的关系完全落在窗口内,完全落在窗口外,部分在内，部分在外.67Cohen-Sutherland算法算法步骤：判别线段两端点是否都落在窗口内，如果是，则线段完全可见，转至第4步；判别线段是否为显然不可见，如果是，则裁剪结束，转至第4步；求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第1步处理，结束裁剪过程是递归的。1.直线段裁剪(8/18)68关键问题：如何快速判别完全可见和完全不可见线段？解决方法——编码：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；Cohen-Sutherland

算法1.直线段裁剪(9/18)11100000011100000011100000011100000069端点编码：定义为它所在区域的编码快速判断“完全不可见”

线段两端点编码的逻辑“与”运算结果非零

，则完全不可见。Cohen-Sutherland算法1.直线段裁剪(10/18)所以也称为编码裁剪算法70逐个端点判断其编码ClCtCrCb中各位是否为“1”，若是，则需求交。最坏情形：线段求交四次。对于那些部分可见又部分不可见的线段，需要求交，求交前先测试与窗口哪条边所在直线有交？Cohen-Sutherland算法1.直线段裁剪(11/18)71

1）特点：用编码方法可快速判断线段-——

完全可见或完全不可见。

2）特别适用两种场合：大窗口场合；窗口特别小的场合（如：光标拾取图形时，光标看作小的裁剪窗口）1.直线段裁剪(12/18)Cohen-Sutherland算法725.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法

中点分割裁剪算法梁友栋-Barsky算法73中点分割法基本思想：利用对分搜索思想搜索交点从P1点出发找出距P1最近的可见点从P2点出发找出距P2最近的可见点不断地在中点处将线段一分为二，对每段线段重复Cohen-Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止取中点Pm=(P1+P2)/2。P2P1从P1点出发找距P1最近的可见点PmP1用P1Pm代替P1P2P2P2用PmP2代替P1P2PmP11.直线段裁剪(13/18)741.直线段裁剪(13/18)优点：算法原理和编码裁剪是一致的，不同之处在于用移位运算代替求交计算适合硬件实现中点分割法755.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法

梁友栋-Barsky算法76Liang-Barsky裁剪算法

P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分1.直线段裁剪(14/18)基本思想：把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段77Liang-Barsky裁剪算法

直线L与区域的交：1.直线段裁剪(15/18)P4P1P3P2ymaxyminxminxmaxRTSULABP4P1P3P2ymaxyminxminxmaxRTSULAB当Q为空集时，线段AB不可能在窗口中有可见线段。当Q不为空集时，Q可看成是一个一维窗口

78存在可见线段的充要条件即不为空集。1.直线段裁剪(16/18)P4P1P3P2ymaxyminxminxmaxRTSULABP4P1P3P2ymaxyminxminxmaxRTSULAB当Q为空集时，线段AB不可能在窗口中有可见线段。当Q不为空集时，Q可看成是一个一维窗口。

79Liang-Barsky裁剪算法

1.直线段裁剪(17/18)向x轴投影，得到可见线段端点的x坐标变化范围

左端点x坐标右端点x坐标RS,AB,TU三条线段的交集的端点坐标等价于求三条线段的左端点的最大值，右端点的最小值

y坐标可由将x坐标代入直线方程计算得到P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分URTS80Liang-Barsky裁剪算法AB有可见部分的充要条件也可表示为1.直线段裁剪(18/18)P4P1P3P2ymaxyminxminxmaxRTSULABAS是一维窗口TS中的可见部分URTS815.5二维线段裁剪1直线段裁剪

直接求交算法

Cohen-Sutherland算法中点分割裁剪算法梁友栋-Barsky算法2多边形裁剪

Sutherland_Hodgman算法

Weiler-Atherton算法

822.多边形裁剪（Ploygonclipping）-1/3错觉：多边形裁剪是直线段裁剪的组合？新的问题：图1因丢失顶点信息而去法确定裁剪区域ABAB图2原来封闭的多边形变成了孤立的线段边界不再封闭，需要用窗口边界的恰当部分来封闭它8312123(a)(b)(c)AB裁剪后的多边形顶点形成的几种情况分裂为几个多边形2.多边形裁剪-2/384关键：不仅在于求出新的顶点，删去界外顶点还在于形成正确的顶点序列常用算法

Sutherland_Hodgman算法

Weiler-Atherton算法

2.多边形裁剪-3/385Sutherland-Hodgman算法-1/4分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：左边的结果是右边的开始。亦称逐边裁剪算法86Sutherland-Hodgman算法-2/4内侧空间与外侧空间多边形的边与半空间的关系

线段与当前裁剪边的位置关系可见一侧窗口(a)输出Pi+1当前裁剪边Pi+1Pi可见一侧窗口(a)无输出当前裁剪边Pi+1Pi可见一侧窗口(a)输出I当前裁剪边Pi+1Pi可见一侧窗口(a)输出I和Pi+1当前裁剪边Pi+1PiII87Sutherland-Hodgman算法-3/4裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点。顺序连接。几点说明：裁剪算法采用流水线方式，适合硬件实现。可推广到任意凸多边形裁剪窗口88Sutherland-Hodgman算法-4/4

存在的问题逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？

逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这几个多边形沿边框产生多余的线段？图6逐边裁剪法对凹多边形裁剪时可能出现的问题321876954103217654108932174108956原图对左边裁对顶边裁32174108956对右边裁对底边裁Demo89Weiler-Atherton算法-1/7裁剪窗口为任意多边形（凸、凹、带内环）的情况：主多边形：被裁剪多边形，记为SP裁剪多边形：裁剪窗口，记为CP90约定：SP与CP均用它们顶点的环形链表定义外边界取顺时针方向内边界取逆时针方向使得沿多边形的边走动，其右边为多边形的内部。Weiler-Atherton算法-2/7C2C1C3C4C8C7C5C6I1I8I2I3I4I5I6I791SP和CP把二维平面分成两部分。内裁剪：SP∩CP外裁剪：SP-CPWeiler-Atherton算法-3/7