计算机图形学chap6 二维变换及二维观察.ppt

计算机图形学基础 华东理工大学计算机系 谢晓玲 2 第六章二维变换及二维观察 如何对二维图形进行方向 尺寸和形状方面的变换 如何进行二维观察 3 二维变换及二维观察 基本几何变换与基本概念二维图形几何变换的计算复合变换变换的性质 4 图形的几何变换平移 旋转 缩放 反射和错切变换的组合图形几何变换的目的改变图形的位置 方向 大小基本几何变换都是相对于坐标原点和坐标轴进行的几何变换 6 2基本几何变换 6 2齐次坐标 齐次坐标将一个原本是n维的向量用一个n 1维向量来表示 例如 向量 x1 x2 xn 的齐次坐标表示为 Hx1 Hx2 Hxn H 其中H是一个不为0的实数 H 1的齐次坐标称为规范化齐次坐标 反之 由点或向量的齐次坐标 Hx1 Hx2 Hxn H 求它的规范化齐次坐标 可根据如下公式求得x1 Hx1 H x2 Hx2 H xn Hxn H齐次坐标表示法的优点将平移 旋转 缩放等变换同统一的方式表示 6 齐次坐标表示就是用n 1维向量表示一个n维向量 规范化齐次坐标表示就是h 1的齐次坐标表示 基本几何变换 规范化齐次坐标 恒等变换平面图形的恒等变换保持原图形的大小 形状 位置不变 其变换矩阵为 7 2二维几何变换的齐次坐标表示 8 基本几何变换 平移变换 平移是指将p点沿直线路径从一个坐标位置移到另一个坐标位置的重定位过程 图6 1平移变换 100设 P x y 1 xy1010TxTy1令 T Tx Ty 100010TxTy1记 P P T Tx Ty Tx Ty称为平移矢量 基本几何变换 平移变换 10 比例变换是指对p点相对于坐标原点沿x方向放缩Sx倍 沿y方向放缩Sy倍 其中Sx和Sy称为比例系数 基本几何变换 比例变换 图6 2比例变换 Sx 2 Sy 3 11 矩阵形式 Sx00设 P x y 1 xy10Sy0001令 S Sx Sy Sx000Sy0001记 P P S Sx Sy Sx Sy称为比例系数 基本几何变换 比例变换 12 基本几何变换 比例变换 图6 3比例变换 13 整体比例变换 当S 1 图形整体缩小 当S 1 图形整体放大 基本几何变换 比例变换 14 二维旋转是指将p点绕坐标原点转动某个角度 逆时针为正 顺时针为负 得到新的点p 的重定位过程 x r cos r cos cos r sin sin x cos y sin y r sin r cos sin r sin cos x sin y cos 基本几何变换 旋转变换 图6 4旋转变换 15 矩阵形式 逆时针旋转 角cos sin 1设 P x y 1 xy1 sin cos 0001令 R cos sin 1 sin cos 0001记 P P R 基本几何变换 旋转变换 16 基本几何变换 二维变换矩阵 T1 ab比例 旋转 对称 错切等 cdT2 lm平移T3 p投影qT4 s整体比例 17 对称变换后的图形是原图形关于某一轴线或原点的镜像 基本几何变换 对称变换 18 基本几何变换 对称变换 19 1 关于x轴对称 基本几何变换 对称变换 图6 6关于x轴对称 20 2 关于y轴对称 图6 6关于y轴对称 基本几何变换 对称变换 21 3 关于原点对称 基本几何变换 对称变换 图6 6关于原点对称 22 4 关于y x轴对称 基本几何变换 对称变换 图6 6关于x y对称 23 5 关于y x轴对称 基本几何变换 对称变换 图6 6关于x y对称 24 错切变换 也称为剪切 错位变换 用于产生弹性物体的变形处理 基本几何变换 错切变换 图6 7错切变换 沿X方向关于Y轴的错切矩形p1p2p3p4沿X方向错切变换 得到矩形p1p2p3 p4 错切角 点 x y 变换为 x x y tan y y令 shx tan 记 x y 1 xy1100shx10001 基本几何变换 错切变换 沿Y方向关于X轴的错切矩形p1p2p3p4沿Y方向错切变换 得到矩形p1p2 p3 p4 错切角 点 x y 变换为 x x y y x tan 令 shy tan 记 x y 1 xy11shy0010001 基本几何变换 错切变换 沿两个方向的错切x x y tan y y x tan 令 shx tan shy tan 记 x y 1 xy11shy0shx10001 基本几何变换 错切变换 28 其变换矩阵为 1 沿x方向错切 b 0 2 沿y方向错切 c 0 3 两个方向错切 b 0 c 0 基本几何变换 错切变换 29 二维图形几何变换的计算 几何变换均可表示成P P T的形式 1 点的变换 30 2 直线的变换 二维图形几何变换的计算 31 3 多边形的变换 二维图形几何变换的计算 32 复合变换 图形作一次以上的几何变换 变换结果是每次变换矩阵的乘积 任何一复杂的几何变换都可以看作基本几何变换的组合形式 复合变换具有形式 P P T P T1 T2 T3 Tn P T1 T2 T3 Tn n 1 33 复合变换 二维复合平移 34 复合变换 二维复合比例 35 复合变换 二维复合旋转 36 复合变换 旋转变换等价于先比例后错切 或者先错切后比例 矩阵相乘是符合结合律 但不符合交换律 A B C A B C A B C A B B C在连续的同种变换的特殊情况下 矩阵相乘可以符合交换律 二次连续旋转 可以用任意顺序进行 连续的平移或连续的比例变换可以交换 两向相同 Sx Sy 的比例变换与旋转变换可以交换 复合变换 38 相对任一参考点的二维几何变换 相对某个参考点 xF yF 作二维几何变换 其变换过程为 1 平移 2 针对原点进行二维几何变换 3 反平移 相对于任一固定点的比例变换则 P P T xA yA S sx sy T xA yA 记 SA sx sy T xA yA S sx sy T xA yA 100sx00100 sx000100sy00100sy0 xA yA1001xAyA1xA 1 sx yA 1 sy 1 相对任一参考点的二维几何变换 围绕任一基准点的旋转变换则 P P T xA yA R T xA yA 记 RA T xA yA R T xA yA 100cos sin 0100010 sin cos 0010 xA yA1001xAyA1 cos sin 0 sin cos 0 xA 1 cos yAsin yA 1 cos xAsin 1 例1错切变换矩形P1P2P3P4沿X轴 Y轴双向错切 设 tan 2 tan 1100110100110010 210 010 210111001 1 11211 则P 1 11110 1 113 11 210331 1412119413411381 相对任一参考点的二维几何变换 例2组合变换平面图形变换举例设 P1P2P3的三个顶点分别为 P1 10 20 P2 20 20 P3 15 30 它绕点Q 5 25 逆时针方向旋转30 它的复合变换由如下三种变换组成 1 平移 使Q移到原点O 平移常量l 5 m 25 平移变换矩阵为 相对任一参考点的二维几何变换 1 平移 使Q移到原点O 平移常量l 5 m 25 平移变换矩阵为T1 平移变换后的 P 1P 2P 3 相对任一参考点的二维几何变换 2 绕原点逆时针旋转30 旋转变换矩阵为T2 旋转变换后的 P 1P 2P 3 y Q O x 相对任一参考点的二维几何变换 3 最后将Q点移回原来位置Q 5 25 平移变换矩阵为T3 旋转变换后的 P 1P 2P 3 相对任一参考点的二维几何变换 46 相对任意方向的二维几何变换 相对任意方向作二维几何变换 其变换的过程是 1 旋转变换 使任意方向与某个轴重合 2 针对坐标轴进行二维几何变换 3 反向旋转 回到原来的方向 图关于任意轴的对称变换 T1 平移 0 Ty 使L过坐标原点 图形A变换为A1 R1 旋转 使L与X轴重合 图形A1变换为A2 RFx 图形A2关于X轴的对称图形A3 R2 旋转 图形A3变换为A4 T2 平移 0 Ty 使L回到原来的位置 图形A4变换为A5 此时 A5是A关于L的对称图形 总的变换 T1 R1 RFx R2 T2 7 37 相对任意方向的二维几何变换 对任意直线的对称变换设 直线的方程为 ax by c 0则 在 两轴上的截距分别为 c a和 c b 直线的斜率为tg a b 1 让直线沿 轴方向平移c a 使其通过坐标系原点 变换矩阵为 100T1 010c a01 2 让直线绕坐标系原点旋转 角 使与 轴重合 变换矩阵为 cos sin 0T2 sin cos 0001 3 由于原直线已与 轴重合 于是对于直线的对称变换即为对于 轴的对称变换 变换矩阵为 100T3 0 10001 4 绕原点旋转 角 使直线恢复到原倾斜位置 变换矩阵为 cos sin 0T4 sin cos 0001 5 让直线沿 轴方向平移 c a 使其回到原来位置 变换矩阵为 100T5 010 c a01 综合以上的五步 对任意直线的对称变换过程为 x y 1 xy1 T1 T2 T3 T4 T5 xy1 T组合变换矩阵 为 cos2 sin2 0T sin2 cos2 0 c a cos2 1 c a sin2 1 55 相对任意方向的二维几何变换 例相对直线y x的反射变换T cos 45 sin 45 0100cos 45 sin 45 0 sin 45 cos 45 00 10 sin 45 c0s 45 0001001001 56 例将正方形ABCO各点沿下图所示的 0 0 1 1 方向进行拉伸 比例变换 结果为如图所示的 写出其变换矩阵和变换过程 复合变换 可能发生的变换 沿 0 0 到 1 1 的比例变换 图6 11沿固定方向拉伸 58 坐标系之间的变换 问题 已知XOY坐标系上的P xp yp 求P转换到X O Y 坐标系上的P x p y p 图6 9坐标系间的变换 59 图6 10坐标系间的变换的原理 坐标系之间的变换 分析 在xoy坐标系中有点p 其坐标与p点在x o y 坐标系下的坐标相等 opx o px opy o py 则p 点的坐标是p点变换到p 点的坐标 可以分两步进行 图6 14坐标系间的变换的步骤 于是 62 光栅变换 直接对帧缓存中象素点进行操作的变换称为光栅变换 光栅平移变换 图6 12光栅平移变换 63 90 180 和270 的光栅旋转变换 光栅变换 每行像素值颠倒 擦掉 每行像素次序颠倒 交换其行列 行的次序颠倒 图6 13光栅旋转变换 64 任意角度的光栅旋转变换 光栅变换 图6 14任意角度的光栅旋转变换像素A的亮度由区域1 2 3的亮度加权平均而得 65 光栅比例变换 进行区域的映射处理 光栅变换 图6 15光栅比例变换根据sx和sy的大小 取出对应于变换后图像中的一个像素点的原图中的相应像素区域 对其区域的像素点的亮度加权平均 得变换后像素的亮度 66 变换的性质 平移 比例 旋转 错切和反射等变换均是二维仿射变换的特例 反过来 任何常用的二维仿射变换总可以表示为这五种变换的复合 二维仿射变换是具有如下形式的二维坐标变换 67 仅包含旋转 平移和反射的仿射变换维持角度和长度的不变性 比例变换可改变图形的大小和形状 错切变换引起图形角度关系的改变 甚至导致图形发生畸变 变换的性质 68 二维观察 基本概念二维观察变换二维裁剪OpenGL中的二维观察 坐标系建模坐标系 MC ModelingCoordinateSystem 用户坐标系 WC WorldCoordinateSystem 直角坐标系 又称笛卡尔坐标系 坐标系极坐标系 观察坐标系 VC ViewingCoordinateSystem 规范化坐标系 NDC NormalizedCoordinateSystem 设备坐标系 DC DeviceCoordinateSystem 二维观察 坐标系1 建模坐标系 MC ModelingCoordinates 依据物体而建的局部坐标系 是直角右手坐标系 长度单位用户自定 取值范围整个实数域 2 世界坐标系 WC WorldCoordinates 又称用户坐标系 场景采用的坐标系 是直角右手坐标系 长度单位用户自定 取值范围整个实数域 二维观察 坐标系3 设备坐标系 DC DeviceCoordinates 依设备而定的坐标系 是二维直角坐标系 原点和轴的定义依设备不同而不同 长度单位是设备的步距 取值范围有限的整数 4 规格化设备坐标系 NDC NormalizedDeviceCoordinates 一种虚拟的坐标系 与具体设备无关 其取值范围在0 1之间 起到将WC与DC联系起来的作用 用户的绘图数据经过转换成NDC中的值 使得图形有了统一的设备空间 这对图形的统一处理 带来很大的方便 从而提高图形程序的可移植性 二维观察 坐标系MC WC NDC DC之间的转换图二维场景从模型坐标系到设备坐标系的变换序列 Xmc Ymc Xwc Ywc Xndc Yndc Xdc Ydc 二维观察 窗口在世界坐标系 WC 中 指定或选取一个矩形区域 Window 视区在规格化设备坐标系 NDC 或设备坐标系 DC 上 指定一个矩形区域 ViewPort 用于显示窗口内的图形 开窗口先将图形关于窗口进行裁剪 然后将裁剪后的保留在窗口内的图形 变换成显示器屏幕上指定视区内的图形 开窗变换也叫取景变换 它包括裁剪运算和窗口到视区的变换 二维观察 基本概念 74 要将窗口内的图形在视区中显示出来 必须经过将窗口到视区的变换 Window ViewportTransformation 处理 这种变换就是观察变换 ViewingTransformation 二维观察 基本概念 76 观察坐标系 ViewCoordinate 是依据窗口的方向和形状在用户坐标平面中定义的直角坐标系 规格化设备坐标系 NormalizedDeviceCoordinate 也是直角坐标系 它是将二维的设备坐标系规格化到 0 0 0 0 到 1 0 1 0 的坐标范围内形成的 二维观察 基本概念 77 引入了观察坐标系和规格化设备坐标系后 观察变换分为如下图所示的几个步骤 通常称为二维观察流程 二维观察 基本概念 图6 19二维观察流程 78 变焦距效果 二维观察 基本概念 图6 20变焦距效果 窗口变 视区不变 视区大小不变 当窗口变小 放大显示 当窗口变大 缩小显示 则产生焦距 又称变焦 缩放的效果 79 整体放缩效果 漫游效果视区大小不变 窗口大小不变 只改变窗口位置 则产生摇镜头 又称漫游 的效果 二维观察 基本概念 图6 21整体放缩效果 窗口不变 视区变 80 用户坐标系到观察坐标系的变换 用户坐标系到观察坐标系的变换分由两个变换步骤合成 平移 将观察坐标系原点移动到用户坐标系原点 81 旋转 绕原点旋转使两坐标系重合 用户坐标系到观察坐标系的变换 82 假设观察坐标系的原点在用户坐标系中的坐标为 x0 y0 观察坐标系与用户坐标系之间的夹角为 则变换矩阵为 用户坐标系到观察坐标系的变换 83 窗口到视区的变换 观察窗口左下角 xwl ywb 右上角 xwr ywt 视区左下角 xvl yvb 右上角 xvr yvt 图6 23窗口 视区变换示意图 要求画面相对比例保持不变 图窗口到视区的变换窗口内点 xw yw 映射到视区 xv yv 应满足 xw xwmin xwmax xwmin xv xvmin xvmax xvmin yw ywmin ywmax ywmin yv yvmin yvmax yvmin 窗口到视区的变换 Xv xvmax xvmin xwmax xwmin xw xwmin xvminyv yvmax yvmin ywmax ywmin yw ywmin yvmin简化 Xv A xw BYv C yw D其中 A xvmax xvmin xwmax xwmin B xvmin xwmin AC yvmax yvmin ywmax ywmin D yvmin ywmin C 窗口到视区的变换 86 将窗口内的点 xw yw 映射到相对应的视区内的点 xv yv 需进行以下步骤 将窗口左下角点移至用户系统系的坐标原点 平移矢量为 xwl ywb 针对原点进行比例变换 使窗口大小与视区相等 比例因子为 Sx xvr xvl xwr xwl Sy yvt yvb ywt ywb 3 进行反平移 使窗口与视区重合 平移矢量为 xvl yvb 窗口到视区的变换 窗口到视区的变换 NWC DC T1 xwl ywb S Sx Sy T2 xvl yvb A000C0BD1其中 A xvr xvl xwr xwl B xvl xwl AC yvt yvb ywt ywb D yvb ywb C 窗口到视区的变换 这里 A C称为比例因子 B D称为平移因子当A C 窗口到视区的映射 可以保持在X Y两方向有相同的比例 当A C 1 则保持图形变换前后大小保持不变 88 裁剪 在二维观察中 需要在观察坐标系下对窗口进行裁剪 即只保留窗口内的那部分图形 去掉窗口外的图形 假设窗口是标准矩形 即边与坐标轴平行的矩形 由上 y wyt 下 y wyb 左 x wxl 右 x wxr 四条边描述 点 x y 在窗口内 则满足 wxl x wxr wyb y wyt 89 二维直线段的裁剪 已知条件 1 窗口边界wxl wxr wyb wyt的坐标值 2 直线段端点p1p2的坐标值x1 y1 x2 y2 图6 24直线段与窗口的3种关系 图6 25直线段与窗口边界的2种交点实交点 直线段与窗口矩形边界的交点 虚交点 处于直线段延长线或窗口边界延长线上的交点 91 二维直线段的裁剪 直线裁剪的基本原理首先确定哪些直线全部保留或全部裁剪 对于部分裁剪的直线 应求出直线与窗口边界的交点 把从交点开始到边界外的部分裁剪掉 常用裁剪算法Cohen Sutherland裁剪算法 又称编码裁剪算法 中点分割算法参数化算法 Liang Barsky算法 基本思想对于每条线段P1P2分为三种情况处理分为三种情况处理 若P1P2完全在窗口内 则显示该线段P1P2简称 取 之 若P1P2明显在窗口外 则丢弃该线段 简称 弃 之 若线段不满足 取 或 弃 的条件 则在交点处把线段分为两段 其中一段完全在窗口外 可弃之 然后对另一段重复上述处理 Cohen Sutherland算法 93 Cohen Sutherland算法 编码对于任一端点 x y 根据其坐标所在的区域 赋予一个4位的二进制码D3D2D1D0 编码规则如下 1 若x wxl D0 1 否则D0 0 2 若x wxr D1 1 否则D1 0 3 若y wyb D2 1 否则D2 0 4 若y wyt D3 1 否则D3 0 95 1 判断裁剪一条线段时 先求出直线段端点p1和p2的编码code1和code2 然后 若code1 code2 0 表明p1和p2区域码都为0000 p1和p2完全在窗口内 则对直线段简取之 若code1 code2 0 表明p1和p2区域码至少在某一位上同为1 p1和p2完全在窗口外 则对直线段简弃之 Cohen Sutherland算法 96 2 求交若上述判断条件不成立 则需求出直线段与窗口边界的交点 通常检测P1 如果P1在窗口外 则从低到高的顺序检测P1的编码CODE1 根据值为1的编码位确定与P1P2求交的窗口边界 按左右上下边界情况求出交点代替p1 用新的P1P2重新计算 如果P1在窗口内 即编码为全0 则将P1和P2交换 继续求交 Cohen Sutherland算法 97 2 求交设 已知一条端点为 x1 y1 和 x2 y2 的直线 左边界 x xwl 右边界 x xwr 交点的计算 y y1 k x x1 上边界 y ywb 下边界 y ywt 交点的计算 x x1 y y1 k 其中 k y2 y1 x2 x1 Cohen Sutherland算法 计算线段P1 x1 y1 P2 x2 y2 与窗口边界的交点 其区域码分别为code1和code2 if code1 0 code code1 elsecode code2 if LEFT 这里 LEFT 0001 RIGHT 0010 BOTTOM 0100 TOP 1000 Cohen Sutherland算法 99 p2 p1 Cohen Sutherland算法 100 用编码方法实现了对完全可见和不可见直线段的快速接受和拒绝 求交过程复杂 有冗余计算 并且包含浮点运算 不利于硬件实现 Cohen Sutherland算法 101 中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点 中点分割算法 基本思想是Cohen Sutherland算法的改进 为了避免使用乘除法求直线段与窗口边界的交点 用不断对分线段的方法排斥线段在窗口外的部分 最后求出离线段端点最远的可见点 所谓可见点就是线段落在窗口内的点 若这两点存在 则这两点就是线段P1P2的可见线段端点 如图 A B分别为距p1 p2最近的可见点 Pm为p1p2中点 中点分割算法 首先对线段端点进行编码 并把线段与窗口的关系分为三种情况 线段P1P2全在窗口内 保留 线段P1P2完全在窗口外 不保留 线段和窗口有交 用中点分割的方法求出线段与窗口的交点 用中点分割的方法将线段等分为二段 作 处理 直至每条线段要么完全在窗口内 要么完全在窗口外为止 中点分割算法 求从P1出发寻找最远的可见点的步骤 设 线段的端点在窗口内称为可见点 其区域码为0000 测试P2是否在窗口内 若是 则P2就是离P1最远的可见点 结束 否则 进行下一步 对P1 P2的区域码作逻辑与 若结果不为0 表明P1 P2是在窗外同侧 线段P1P2全部不可见 弃之 结束 否则 进行下一步 3 取P1P2的中点Pm x1 x2 2 y1 y2 2 若Pm可见 则Pm代替P1 重复步骤 3 若Pm不可见 则需要判断Pm和P2的关系 如果Pm和P2在窗口的同侧外面 即Pm P2的区域码逻辑与不为0 则Pm代替P2 重复步骤 3 如果Pm和P2不在窗口的同侧外面 即Pm P2的区域码逻辑与为0 则Pm代替P1 重复步骤 3 4 一直进行到分点与线段端点距离达到分辨率精度为止 106 特点 主要计算过程只用到加法或位移运算 易于硬件实现 同时适合于并行计算 中点分割算法 107 Liang Barsky算法 Liang Barsky算法是直线段的基于矩形窗口的参数化裁剪方法 广义地讲 4条裁剪边界会与线段相交 有4个交点 108 设直线段的两个端点坐标分别为 x1 y1 和 x2 y2 其参数方程为 对于直线上一点 x y 若它在窗口内则有 Liang Barsky算法 令 则有 令 当qk 0 则线段起始点p1在该边界外部 不可见侧 当qk 0 则线段起始点P1在该边界内部 可见侧 当qk 0 则线段起始点P1在该边界上 当pk 0 则线段与该边界平行 p1和p2符号互斥 p3和p4符号互斥 当pk 0并且qk 0 则整条线段在该边界之外 k 1 2 3 4 分别对应左 右 下 上 pk0 上限组 线段从窗口边界延长线的内部延伸到外部 P1x2P3y2 P1 0 P2 0 P3 0 P4 0 例如 p1 p2 0 线段A F平行左右边界 线段A q1 0 完全在边界外 同理线段F q2 0 亦在边界外 Liang Barsky算法 图6 29直线段与窗口边界平行的情况 p3 p4 0 线段G L平行上下边界 线段G q4 0 完全在边界外 同理线段L q3 0 亦在边界外 设直线从 x1 y1 到 x2 y2 连线方向作正向且无限延伸 同时 窗口的各边界也无限延伸 pk0 上限组 线段从窗口边界延长线的内部延伸到外部 在有交的情况下 下限组分布在直线的起始点一侧 上限组分布在直线的终止点一侧 Liang Barsky算法 上限组的最大值和下限组的最小值分别对应于直线段在窗口内部分的端点 假定存在 Liang Barsky算法 P3 0 Umax P1 0 Umin Umin Umax Umax max 0 pk0 上限组 线段出去 P2 0 P2 0 P4 0 P3 0 P4 0 P1 0 Umax max 0 pk0 上限组 线段出去 P1 0 Umin Umax P2 0 P4 0 P3 0 当pk 0时 可以计算出线段与边界k的延长线的交点参数 u qk pk对于每条直线 都有4个交点参数u 通过比较 可以计算出一对参数umax和umin umax的值表示由线段从外到内遇到的矩形边界 p0 所决定 umin取1和qk pk值之中的最小值 即 umin min qk pk Pk 0 1 Liang Barsky算法 当p1 p2 0 则表明直线段平行于左右边界 如果 q1 0或q2 0 则线段完全在边界外 弃之 q1 0并且q2 0 则线段只与上下边界求交 计算 uk qk pk pk 0 k 3 4 当p3 p4 0 则表明直线段平行于上下边界 如果 q3 0或q4 0 则线段完全在边界外 弃之 q3 0并且q4 0 则线段只与左右边界求交 计算 uk qk pk pk 0 k 1 2 当pk 0 则计算出线段与边界k的延长线的交点参数 u qk pk pk 0 k 1 2 3 4 Liang Barsky算法 再分别计算 umax max 0 qk pk Pk0 1 根据umax umin 可以判断直线是如何裁剪的 如果umax umin 则线段完全落在裁剪窗口之外 弃之 若umax umin 则线段在窗口内 由参数umax umin计算出裁剪线段的端点 x1 x u y1 y u Liang Barsky算法 例 直线L1与4个边界延伸线的交点 直线L1方向与Pk取值如表所示 对于L1 umax umin 则线段L1被裁剪 对于L2 umax umin 则线段L2完全落在窗口之外 弃之 Liang Barsky算法 算法步骤 1 输入直线段的两端点坐标 x1 y1 和 x2 y2 以及窗口的四条边界坐标 wyt wyb wxl和wxr 2 若 x 0 则p1 p2 0 此时进一步判断是否满足q10且q2 0 则进一步计算umax和umin 算法转 5 3 若 y 0 则p3 p4 0 此时进一步判断是否满足q30且q2 0 则进一步计算umax和umin 算法转 5 4 若上述两条均不满足 则有pk 0 k 1 2 3 4 此时计算umax和umin 5 求得umax和umin后 进行判断 若umax umin 则直线段在窗口外 算法转 7 若umax umin 利用直线的参数方程求得直线段在窗口内的两端点坐标 6 利用直线的扫描转换算法绘制在窗口内的直线段 算法结束 voidLine Clipping floatx1 floaty1 floatx2 floaty2 rect pRect floatdx x2 x1 dy y2 y1 umax 0 0 umin 1 0 比较左 右边界 获得最大的umaxifClip Top dx x1 pRect xw xmin umax umin 左边界ifClip Top dx pRect xw xmax x1 umax umin 右边界 比较下 上边界 获得最小的uminifClip Top dy y1 pRect yw xmin umax umin 下边界ifClip Top dy pRect xw xman y1 umax umin 上边界line int x1 umax dx int y1 umax dy int x1 umin dx int y1 umin dy Liang Barsky算法 intClip Top floatp floatq float Liang Barsky算法 特点 每修改一次u1或u2只需要一次除法 在u1和u2确定后 直线与窗口的交点只需要计算一次 不足之处 只能应用于矩形窗口的情况 Liang Barsky算法 125 多边形的裁剪 多边形的裁剪结果应仍是多边形 即仍是一个封闭的线框图形 如果直接应用直线的裁剪方法 那么 在一般的情况下就不可能得到明确的结果 可能得到一系列不连接的直线段 如图所示 126 Sutherland Hodgeman多边形裁剪 基本思想 将多边形的边界作为一个整体 每次用窗口的一条边界对要裁剪的多边形进行裁剪 用部分窗口的边框线段去拼补留下的缺口 体现分而治之的思想 127 窗口的一条边以及延长线构成的裁剪线把平面分为两个区域 包含窗口区域的区域称为可见侧 不包含窗口区域的域为不可见侧 设 S为前一点 P为当前点 I为窗口边界内外两点连线与窗口边界的交点 则有4种情况 外 内内 内内 外外 外 Sutherland Hodgeman多边形裁剪 128 算法 逐边裁剪 为窗口各边界裁剪的多边形存储输入与输出顶点表 以左 右 底 顶边界裁剪流水线处理窗口各边界裁剪多边形 每次仅仅裁剪顶点 并且将裁剪后的顶点传输到下一边界的裁剪程序每次裁剪时 去掉边界不可见侧内的顶点 保留边界可见侧内的顶点和窗口边界内外两点连线与窗口边界的交点 Sutherland Hodgeman多边形裁剪 Sutherland Hodgeman多边形裁剪 适合凸多边形 对于凹多边形 只有一个输出顶点表 最后一个顶点总是连着第一个顶点 如图 Sutherland Hodgeman多边形裁剪 132 设 多边形按顺时针处理顶点 对于由外到内的顶点 沿多边形边界的方向 对于由内到外的顶点 按顺时针沿窗口边界的方向 Weiler Atherton多边形裁剪 结果生成二个多边形 133 设 多边形按顺时针处理顶点 且用户多边形定义为Ps 窗口矩形为Pw 算法从Ps的任一点出发 跟踪检测Ps的每一条边 当Ps与Pw相交时 实交点 按如下规则处理 1 若是由不可见侧进入可见侧 则输出可见直线段 转 3 Weiler Atherton多边形裁剪 134 2 若是由可见侧进入不可见侧 则从当前交点开始 沿窗口边界顺时针检测Pw的边 即用窗口的有效边界去裁剪Ps的边 找到Ps与Pw最靠近当前交点的另一交点 输出可见直线段和由当前交点到另一交点之间窗口边界上的线段 然后返回处理的当前交点 3 沿着Ps处理各条边 直到处理完Ps的每一条边 回到起点为止 Weiler Atherton多边形裁剪 下图示了Weiler Atherton算法裁剪凹多边形的过程和结果 设 被