第四章 图形的裁剪及几何变换.ppt

第四章图形的裁剪及几何变换 主要介绍二维几何变换窗口到视区的变换三维几何变换 以下几方面的内容 数学基础 矢量 矩阵及运算视窗变换二维几何变换三维几何变换投影变换 内容 变换的数学基础 矢量矢量和 变换的数学基础 矢量的数乘矢量的点积性质 变换的数学基础 矢量的长度单位矢量矢量的夹角矢量的叉积 变换的数学基础 矩阵阶矩阵n阶方阵零矩阵行向量与列向量单位矩阵矩阵的加法矩阵的数乘矩阵的乘法矩阵的转置矩阵的逆 矩阵的含义矩阵 由m n个数按一定位置排列的一个整体 简称m n矩阵 A 其中 aij称为矩阵A的第i行第j列元素 变换的数学基础 矩阵运算加法设A B为两个具有相同行和列元素的矩阵A B 数乘kA k aij i 1 m j 1 n 变换的数学基础 乘法设A为3 2矩阵 B为2 3矩阵C A B C Cm p Am n Bn pcij aik bkj单位矩阵在一矩阵中 其主对角线各元素aii 1 其余皆为0的矩阵称为单位矩阵 n阶单位矩阵通常记作In Am n Am n In k 1 n 变换的数学基础 逆矩阵若矩阵A存在A A 1 A 1 A I 则称A 1为A的逆矩阵矩阵的转置把矩阵A aij m n的行和列互换而得到的n m矩阵称为A的转置矩阵 记作AT AT T A A B T AT BT aA T aAT A B T BT AT当A为n阶矩阵 且A AT 则A是对称矩阵 变换的数学基础 矩阵运算的基本性质交换律与结合律师A B B A A B C A B C数乘的分配律及结合律a A B aA aB a A B aA B A aB a b A aA bAa bA ab A 变换的数学基础 矩阵乘法的结合律及分配律A B C A B C A B C A C B CC A B C A C B矩阵的乘法不适合交换律 变换的数学基础 所谓齐次坐标表示法就是由n 1维向量表示一个n维向量 如n维向量 P1 P2 Pn 表示为 hP1 hP2 hPn h 其中h称为哑坐标 1 h可以取不同的值 所以同一点的齐次坐标不是唯一的 如普通坐标系下的点 2 3 变换为齐次坐标可以是 1 1 5 0 5 4 6 2 6 9 3 等等 2 普通坐标与齐次坐标的关系为 一对多 由普通坐标 h 齐次坐标由齐次坐标 h 普通坐标3 当h 1时产生的齐次坐标称为 规格化坐标 因为前n个坐标就是普通坐标系下的n维坐标 齐次坐标 齐次坐标 x y 点对应的齐次坐标为 x y 点对应的齐次坐标为三维空间的一条直线 1 将各种变换用阶数统一的矩阵来表示 提供了用矩阵运算把二维 三维甚至高维空间上的一个点从一个坐标系变换到另一坐标系的有效方法 2 便于表示无穷远点 例如 x h y h h 令h等于03 齐次坐标变换矩阵形式把直线变换成直线段 平面变换成平面 多边形变换成多边形 多面体变换成多面体 4 变换具有统一表示形式的优点便于变换合成便于硬件实现 齐次坐标的作用 齐次坐标与二维变换的矩阵表示 1 4 为什么需要齐次坐标 多个变换作用于多个目标 变换合成 变换合成的问题 引入齐次坐标 变换的表示法统一 齐次坐标与二维变换的矩阵表示 2 4 齐次坐标定义 x y 点对应的齐次坐标为 x y 点对应的齐次坐标为三维空间的一条直线 齐次坐标与二维变换的矩阵表示 3 4 标准齐次坐标 x y 1 二维变换的矩阵表示平移变换旋转变换 齐次坐标与二维变换的矩阵表示 4 4 放缩变换变换具有统一表示形式的优点便于变换合成便于硬件实现 4 1窗口视图变换 用户域和窗口区1 用户域 程序员用来定义草图的整个自然空间 WD a人们所要描述的图形均在用户域中定义 b用户域是一个实数域 理论上是连续无限的 2 窗口区 用户指定的任一区域 W a窗口区W小于或等于用户域WDb小于用户域的窗口区W叫做用户域的子域 c窗口可以有多种类型 矩形窗口 圆形窗口 多边形窗口等等d窗口可以嵌套 即在第一层窗口中可再定义第二层窗口 在第I层窗口中可再定义第I 1层窗口等等 窗口视图变换 1 屏幕域 DC 设备输出图形的最大区域 是有限的整数域 如图形显示器分辨率为1024 768 DC 0 1023 0 767 2 视图区 任何小于或等于屏幕域的区域a视图区用设备坐标定义在屏幕域中b窗口区显示在视图区 需做窗口区到视图区的坐标转换 c视图区可以有多种类型 圆形 矩形 多边形等 d视图区也可以嵌套 窗口区和视图区的坐标变换 设窗口的四条边界WXL WXR WYB WYT视图的四条边界VXL VXR VYB VYT则用户坐标系下的点 即窗口内的一点 Xw Yw 对应屏幕视图区中的点 Xs Ys 其变换公式为 窗口区和视图区的坐标变换 简化为 1 当a c时 即x方向的变化与y方向的变化不同时 视图中的图形会有伸缩变化 图形变形 2 当a c 1 b d 0则Xs Xw Ys Yw 图形完全相同 思考 前面讲的窗口 视图变换时 假设窗口的边和坐标轴平行 如果窗口的边不和坐标轴平行呢 窗口区和视图区的坐标变换 A 先让窗口FGHI转 角 使它和FG H I 重合 B 用 1 式进行计算 4 2二维图形的裁剪 裁剪 确定图形中哪些部分落在显示区之内 哪些落在显示区之外 以便只显示落在显示区内的那部分图形 这个选择过程称为裁剪 图形裁剪算法 直接影响图形系统的效率 裁剪策略1 图形裁剪与窗视变换的先后 先变换后裁剪 裁后部分也变换 先裁剪后变换 可避免无效变换2 图形生成的裁剪的先后 先生成后裁剪 裁剪算法简单 先裁剪后生成 无效工作少但算法复杂 点的裁剪 图形裁剪中最基本的问题 假设窗口的左下角坐标为 xL yB 右上角坐标为 xR yT 对于给定点P x y 则P点在窗口内的条件是要满足下列不等式 xL x xR并且yB y yT否则 P点就在窗口外 问题 对于任何多边形窗口 如何判别 点的裁剪判断一点是否在裁剪框内 以决定是否可见 最简单的图形裁剪方法 把图形转换为点后 对点裁剪 缺点 太慢 不现实 不实用 线段的裁剪 如何高效地裁剪线段 线段与裁剪框的位置关系有三种情况 内 全显 外 全擦除 内 外 框内显外擦 算法任务 确定可见部分之两端点 1 矢量裁剪法 思想 以 A B 为始点判断或求交 Xs Ys 以 C D 为始点判断或求交 X Y 显示 Xs Ys X Y 即可 算法流程 见书113页 114页 直接求交算法 直线与窗口边都写成参数形式 求参数值 编码裁剪法 基本思想 对于每条线段P1P2分为三种情况处理 1 若P1P2完全在窗口内 则显示该线段P1P2 2 若P1P2明显在窗口外 则丢弃该线段 3 若线段不满足 1 或 2 的条件 则在交点处把线段分为两段 其中一段完全在窗口外 可弃之 然后对另一段重复上述处理 为快速判断 采用如下编码方法 实现方法 将窗口边线两边沿长 得到九个区域 每一个区域都用一个四位二进制数标识 直线的端点都按其所处区域赋予相应的区域码 用来标识出端点相对于裁剪矩形边界的位置 1001 0001 0101 1000 0000 0100 1010 0010 0110 A B C D 编码裁剪法 编码裁剪算法 将区域码的各位从右到左编号 则坐标区域与各位的关系为 上下右左XXXX任何位赋值为1 代表端点落在相应的位置上 否则该位为0 若端点在剪取矩形内 区域码为0000 如果端点落在矩形的左下角 则区域码为0101 编码裁剪算法 一旦给定所有的线段端点的区域码 就可以快速判断哪条直线完全在剪取窗口内 哪条直线完全在窗口外 所以得到一个规律 编码裁剪法 若P1P2完全在窗口内code1 0 且code2 0 则 取 若P1P2明显在窗口外code1 code2 0 则 弃 在交点处把线段分为两段 其中一段完全在窗口外 可弃之 然后对另一段重复上述处理 编码线段裁剪 编码裁剪法 如何判定应该与窗口的哪条边求交呢 编码中对应位为1的边 计算线段P1 x1 y1 P2 x2 y2 与窗口边界的交点if LEFT 具体算法见p201 编码裁剪法直线裁剪算法小结 本算法的优点在于简单 易于实现 他可以简单的描述为将直线在窗口左边的部分删去 按左 右 下 上的顺序依次进行 处理之后 剩余部分就是可见的了 在这个算法中求交点是很重要的 他决定了算法的速度 另外 本算法对于其他形状的窗口未必同样有效 特点 用编码方法可快速判断线段的完全可见和显然不可见 中点分割裁剪算法 基本思想 从P0点出发找出离P0最近的可见点 和从P1点出发找出离P1最近的可见点 这两个可见点的连线就是原线段的可见部分 与Cohen Sutherland算法一样首先对线段端点进行编码 并把线段与窗口的关系分为三种情况 对前两种情况 进行一样的处理 对于第三种情况 用中点分割的方法求出线段与窗口的交点 A B分别为距P0 P1最近的可见点 Pm为P0P1中点 中点分割算法 求线段与窗口的交点 从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm 若P0Pm不是显然不可见的 并且P0P1在窗口中有可见部分 则距P0最近的可见点一定落在P0Pm上 所以用P0Pm代替P0P1 否则取PmP1代替P0P1 再对新的P0P1求中点Pm 重复上述过程 直到PmP1长度小于给定的控制常数为止 此时Pm收敛于交点 从P1出发找距离P1最近可见点采用上面类似方法 中点分割裁剪算法 对分辩率为2N 2N的显示器 上述二分过程至多进行N次 主要过程只用到加法和除法运算 适合硬件实现 它可以用左右移位来代替乘除法 这样就大大加快了速度 中点分割裁剪算法 多边形裁剪 错觉 直线段裁剪的组合 新的问题 1 边界不再封闭 需要用窗口边界的恰当部分来封闭它 如何确定其边界 多边形裁剪 2 一个凹多边形可能被裁剪成几个小的多边形 如何确定这些小多边形的边界 多边形的裁剪 剪边 从任意顶点开始 按逆时针顺序 每次取一条边裁剪 得用线段的编码算法求出交点 直到出发点 在裁剪过程中 对所有点 原顶点 交点 排序 并给出边界点附上有关信息 IN OUT 连接 可见点 排序 边界值小者在前 同边界按逆序 连接 从序号1开始 步长为2 每次连接一对Qi Qi 1 边界点 排序 边界值小者在前 同边界则按逆时针序 连接 第i个出点与第i个入点连接 逐边裁剪法算法 分割处理策略 将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪 流水线过程 左上右下 前边的结果是后边的输入 逐边裁剪法算法 基本思想是一次用窗口的一条边裁剪多边形 考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分 可见一侧 不可见一侧多边形的各条边的两端点S P 它们与裁剪线的位置关系只有四种 逐边裁剪法算法 情况 1 仅输出顶点P 情况 2 输出0个顶点 情况 3 输出线段SP与裁剪线的交点I 情况 4 输出线段SP与裁剪线的交点I和终点P 逐边裁剪法算法框图 处理线段SP过程子框图 逐边裁剪法算法 上述算法仅用一条裁剪边对多边形进行裁剪 得到一个顶点序列 作为下一条裁剪边处理过程的输入 对于每一条裁剪边 算法框图同上 只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变 逐边裁剪法算法 思考 如何推广到任意凸多边形裁剪窗口 双边裁剪法算法 裁剪窗口为任意多边形 凸 凹 带内环 的情况 主多边形 被裁剪多边形 记为A裁剪多边形 裁剪窗口 记为B 双边裁剪法算法 多边形顶点的排列顺序 使多边形区域位于有向边的左侧 外环 逆时针 内环 顺时针主多边形和裁剪多边形把二维平面分成两部分 内裁剪 A B外裁剪 A B 裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成 并且在交点处边界发生交替 即由A的边界转至B的边界 或由B的边界转至A的边界 双边裁剪法算法 如果主多边形与裁剪多边形有交点 则交点成对出现 它们被分为如下两类 进点 主多边形边界由此进入裁剪多边形内如 I1 I3 I5 I7 I9 I11出点 主多边形边界由此离开裁剪多边形区域 如 I0 I2 I4 I6 I8 I10 双边裁剪法算法 1 建立主多边形和裁剪多边的顶点表 2 求主多边形和裁剪多边形的交点 并将这些交点按顺序插入两多边形的顶点表中 在两多边表形顶点表中的相同交点间建立双向指针 3 裁剪 如果存在没有被跟踪过的交点 执行以下步骤 双边裁剪法算法 双边裁剪法算法 交点的奇异情况处理1 与裁剪多边形的边重合的主多边形的边不参与求交点 2 对于顶点落在裁剪多边形的边上的主多边形的边 如果落在该裁剪边的内侧 将该顶点算作交点 而如果这条边落在该裁剪边的外侧 将该顶点不看作交点 图形裁剪 字符串的剪裁 字符串剪裁有三种可选择的方法 一 字符串的有或无剪裁 all or none tex 效果如图2 6 6 其算法思想是 根据字符串所含字符的个数 及字符的大小 间隔 轨迹 求出字符串的外包盒 box 以外包盒的边界极值与窗边极值比较而决定该字串的去留 字串有或无剪裁 图形裁剪 字符串的剪裁 字符串剪裁有三种可选择的方法 二 字符的有或无剪裁 all or none character 效果如图2 6 7 其算法思想是 1 先以字串box与窗边比较而决定字串的全删 全留或部分留 2 对部分留的字串中 逐个测量字符的box与窗边关系而决定该字符的去留 字符有或无剪裁 图形裁剪 字符串的剪裁 字符串剪裁有三种可选择的方法 三 字符的精密剪裁效果如图2 6 8 其算法思想是 1 用字串box与窗边相比较 决定字串的全删 全留或部分删 2 对部分留的字串中 逐个测量字符的box与窗边的关系 决定字符的全删 全留或部分删 3 对部分留的字符的每一笔划 用直线剪裁法对窗边进行剪裁 字符的精密剪裁 图形变换是计算机图形学基础内容之一 几何变换 投影变换 视窗变换线性变换 属性不变 拓扑关系不变 作用 把用户坐标系与设备坐标系联系起来 可由简单图形生成复杂图形 可用二维图形表示三维形体 动态显示 4 3二维图形几何变换的一般表示 二维图形的显示流程图 图形的几何变换 图形变换 对图形的几何信息经过几何变换后产生新的图形 图形变换的两种形式 1 图形不变 坐标系改变 2 图形改变 坐标系不变 我们所讨论的是针对坐标系的改变而讲的 二维图形的几何变换 设二维图形变换前坐标为 x y 1 变换后为 x y 1 1 二维变换矩阵注意 T2D可看作三个行向量 其中 100 表示x轴上的无穷远点 010 表示y轴上的无穷远点 001 表示原点 二维图形的几何变换 从变换功能上可把T2D分为四个子矩阵 二维基本变换 平移变换 平移变换平移变换只改变图形的位置 不改变图形的大小和形状 二维基本变换 比例变换 以坐标原点为放缩参照点当Sx Sy 1时 恒等比例变换当Sx Sy 1时 沿x y方向等比例放大 当Sx Sy 1时 沿x y方向等比例缩小当Sx Sy时 沿x y方向作非均匀的比例变换 图形变形 二维基本变换 对称变换 当b d 0 a 1 e 1时 x y 1 xy1 与y轴对称的反射变换 当b d 0 a 1 e 1时 x y 1 x y1 与x轴对称的反射变换 当b d 0 a e 1时 x y 1 x y1 与原点对称的反射变换 当b d 1 a e 0时 x y 1 yx1 与y x对称的反射变换 当b d 1 a e 0时 x y 1 y x1 与y x对称的反射变换 二维基本变换 旋转变换 注意 是逆时针旋转角度 x y x y 二维基本变换 错切变换 1 当d 0时 x y 1 x byy1 图形的y坐标不变 当b 0 图形沿 x方向作错切位移 ABCD A1B1C1D1当b 0 图形沿 x方向作错切位移 ABCD A2B2C2D2 二维基本变换 错切变换 2 当b 0时 x y 1 xdx y1 图形的x坐标不变 当d 0 图形沿 y方向作错切位移 ABCD A1B1C1D1当d 0 图形沿 y方向作错切位移 ABCD A2B2C2D2 二维基本变换 错切变换 3 当b 0且d 0时 x y 1 x bydx y1 图形沿x y两个方向作错切位移 错切变换引起图形角度关系的改变 甚至导致图形发生变形 复合变换 复合变换又称级联变换 指对图形做一次以上的几何变换 注意 任何一个线性变换都可以分解为上述几类变换 例1 复合平移 求点P x y 经第一次平移变换 Tx1 Ty1 第二次平移变换 Tx2 Ty2 后的坐标P x y 解 设点P x y 1 经第一次平移变换后的坐标为P x y 1 则经第二次平移变换后的坐标为P x y 1 变换矩阵为Tt Tt1 Tt2 例2 多种复合组合 例 对一线段先放大2倍 即Sx Sy 2 再平移Tx 10 Ty 0 解 设点 x y 为线段上的任意一点 点 x y 为点 x y 放大后的坐标则 设点 x y 为点 x y 经平移后的坐标为 x y 1 x y 1 T2 10 0 则 x y 1 x y 1 T2 10 0 x y 1 S2 2 2 T2 10 0 令 M S2 2 2 T2 10 0 则M即为组合变换 例3 旋转变换 对参考点F xf yf 做旋转变换 解 1 把旋转中心F xf yf 平移至坐标原点 即坐标系平移 xf yf 则2 进行旋转变换 例3 旋转变换 将坐标系平移回原来的原点因此 例4 任意的反射轴的反射变换 任一图形关于任意的反射轴y a bx的反射变换解 1 将坐标原点平移到 0 a 处 例4 任意的反射轴的反射变换 2 将反射轴 已平移后的直线 按顺时针方向旋转 角 使之与x轴重合3 图形关于x轴的反射变换4 将反射轴逆时针旋转 角 例4 任意的反射轴的反射变换 5 恢复反射轴的原始位置因此 平移物体使固定点与坐标原点重合对于坐标原点缩放用步骤1的反向平移将物体移回原始位置 例5 通用固定点缩放 例6 通用定向缩放 比例变换中的比例因子Sx Sy只能在x轴方向或y轴方向起作用 实际图形变换中 不仅是在x y方向变换 往往要求在任意方向进行比例变换 通过旋转变换和比例变换的组合 可以实现任意方向的比例变换 解 定义比例因子S1和S2 1 使S1和S2旋转 角后分别与x轴和y轴重合 2 进行比例变换 3 使S1和S2旋转 角 返回原始位置 通用定向缩放 如 图 a 为一单位正方形 对由 0 0 和 1 1 两点构成的对角线方向实施比例变换 1 2 三维几何变换 三维其次坐标 x y z 点对应的齐次坐标为标准齐次坐标 x y z 1 右手坐标系 三维几何变换 变换矩阵平移变换比例变换 三维变换矩阵 对称变换 在二维变换下 对称变换是以线和点为基准 在三维变换下 对称变换则是以面 线 点为基准的 对称于XOY平面 x y z 1 xy z1 xyz1 对称于YOZ平面 x y z 1 xyz1 xyz1 对称于XOZ平面 x y z 1 x yz1 xyz1 三维变换矩阵 旋转变换 绕X轴变换空间上的立体绕X轴旋转时 立体上各点的X坐标不变 只是Y Z坐标发生相应的变化 x xy cos y cos z sin z sin y sin z cos X Y Z y z y z Y Z O O y z y z Z 三维变换矩阵 旋转变换 矩阵表示为 遵循右手法则 即若 0 大拇指指向轴的方向 其它手指指的方向为旋转方向 三维变换矩阵 旋转变换 绕Y轴旋转此时 Y坐标不变 X Z坐标相应变化 x sin x cos z sin y yz cos z cos x sin X Y Z x z x z X Z O O Z 三维变换矩阵 旋转变换 矩阵表示为 三维变换矩阵 旋转变换 绕Z轴旋转此时 Z坐标不变 X Y坐标相应变化 x cos x cos y sin y sin x sin y cos z z X Y Z x y x y X Y O O 三维变换矩阵 旋转变换 矩阵表示为 绕任意轴的旋转变换 方法1 a 绕过原点的任意轴的旋转变换空间点