图形变换与裁剪3.ppt

第五章 图形变换与裁剪（三） 计算机学院 苏小红 二维裁剪 1 直线段裁剪 直接求交算法 Cohen-Sutherland算法 中点分割裁剪算法 梁友栋-Basky算法 2 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Atherton算法 直线段裁剪(1/15) 裁剪的目的 判断图形元素是否在裁剪窗口之内并找出其位于内部的部分 裁剪处理的基础 图元关于窗口内外关系的判别 图元与窗口的求交 裁剪、覆盖 直线段裁剪(2/15) 裁剪窗口 矩形、圆形、一般多边形 被裁剪对象 线段、多边形、曲线、字符 裁剪的策略 先裁剪，后变换 先变换，后裁剪 裁剪算法的核心问题 效率 直线段裁剪(3/15) 点裁剪 点(x, y)在窗口内的充分必要条件是： 问题：对于任何多边形窗口，如何判别？ 直线段裁剪(4/15) 假定条件 矩形裁剪窗口：[xmin,xmax]X[ymin,ymax] 待裁剪线段： 任何平面线段相对于凸多边形窗口进行裁剪后？ 直线段裁剪(5/15) 待裁剪线段和窗口的关系 完全落在窗口内 完全落在窗口外 部分在内，部分在外 直线段裁剪(6/15) Cohen-Sutherland 算法 (编码算法) 特点： 对显然不可见线段的快速判别 编码方法： 由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码， CtCbCrCl，上下右左； 端点编码： 定义为它所在区域的编码 结论： 当线段的两个端点的编码的逻辑“与”非零时 ，显然不可见 Cohen-Sutherland 算法 求交测试顺序固定(左上右下） 最坏情形，线段求交四次。 Cohen-Sutherland 算法的特点 中点分割法 基本思想： 从P0点出发找出距P0最近的可见点 从P1点出发找出距P1最近的可见点 不断地在中点处将线段一分为二，对每段线段重复Cohen-Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止 取中点Pm=(P1+P2)/2。 Liang-Barsky裁剪算法 直线L与区域的交： 当Q为空集时，线段AB不可能在窗口中有可见线段。 当Q不为空集时，Q可看成是一个一维窗口 Liang-Barsky裁剪算法 存在可见线段的充要条件 不为空集 Liang-Barsky裁剪算法 AB有可见部分的充分必要条件也可表示为 多边形裁剪-1/2 用直线段裁剪算法，可以吗？ 新的问题： Sutherland-Hodgman算法-1/4 分割处理策略： 将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。 流水线过程(左上右下)：左边的结果是右边的开始。 Sutherland-Hodgman算法-2/4 内侧空间与外侧空间 多边形的边与半空间的关系 Sutherland-Hodgman算法-3/4 裁剪结果的顶点构成： 裁剪边内侧的原顶点； 多边形的边与裁剪边的交点。 顺序连接。 Sutherland-Hodgman算法-4/4存在的问题 逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？ Weiler-Atherton算法-1/6 裁剪窗口为任意多边形（凸、凹、带内环）的情况 主多边形：被裁剪多边形，记为SP 裁剪多边形：裁剪窗口，记为CP Weiler-Atherton算法-2/6 约定： SP与CP均用它们顶点的环形链表定义 外边界取顺时针方向 内边界取逆时针方向 Weiler-Atherton算法-3/6 SP和CP把二维平面分成两部分。 内裁剪：SP∩CP 外裁剪：SP-CP Weiler-Atherton算法-4/6 主多边形与裁剪多边形交点成对出现 分为如下两类： 进点：主多边形边界由此进入裁剪多边形内 出点：主多边形边界由此 离开裁剪多边形区域. Weiler-Atherton算法-5/6 Weiler-Atherton算法-6/6 * * 为提高效率，算法设计时应考虑： 1. 快速判断情形(1)(2)； 2. 设法减少情形(3)求交次数和每次求交时所需的计算量 算法步骤： 第一步 判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步； 第二步 判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步 ； 第三步 求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。