1,哈尔滨工业大学计算机学院 苏小红,第五章 图形变换与裁剪,2,二维裁剪,1 直线段裁剪 直接求交算法 Cohen-Sutherland算法中点分割裁剪算法梁友栋-Basky算法 2 多边形裁剪Sutlerland_Hodgman算法Weiler-Atherton算法,3,直线段裁剪(1/15),裁剪的目的 判断图形元素是否在裁剪窗口之内并找出其位于内部的部分 裁剪处理的基础 图元关于窗口内外关系的判别 图元与窗口的求交 裁剪、覆盖,4,直线段裁剪(2/15),裁剪窗口 矩形、圆形、一般多边形 被裁剪对象 线段、多边形、曲线、字符 裁剪的策略 先裁剪，后变换 先变换，后裁剪 裁剪算法的核心问题 效率,5,直线段裁剪(3/15),点裁剪 点(x, y)在窗口内的充分必要条件是：问题：对于任何多边形窗口，如何判别？,6,直线段裁剪(4/15),假定条件 矩形裁剪窗口：xmin,xmaxXymin,ymax 待裁剪线段： 任何平面线段相对于凸多边形窗口进行裁剪后？,7,直线段裁剪(5/15),待裁剪线段和窗口的关系 完全落在窗口内 完全落在窗口外 部分在内，部分在外,8,直线段裁剪(6/15),为提高效率，算法设计时应考虑：1. 快速判断情形(1)(2)； 2. 设法减少情形(3)求交次数和每次求交时所需的计算量,9,Cohen-Sutherland 算法 (编码算法),算法步骤： 第一步 判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步； 第二步 判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步 ； 第三步 求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束,裁剪过程是递归的。,直线段裁剪(7/15),10,特点： 对显然不可见线段的快速判别 编码方法： 由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码， CtCbCrCl，上下右左；,Cohen-Sutherland 算法,直线段裁剪(8/15),11,端点编码： 定义为它所在区域的编码 结论： 当线段的两个端点的编码的逻辑“与”非零时 ，显然不可见,Cohen-Sutherland 算法,直线段裁剪(9/15),12,求交测试顺序固定(左上右下） 最坏情形，线段求交四次。,对于那些非完全可见、又非完全不可见的线段，需要 求交，求交前先测试与窗口哪条边所在直线有交？ (按序判断端点编码中各位的值ClCtCrCb）,Cohen-Sutherland 算法,直线段裁剪(10/15),13,1）特点：用编码方法可快速判断线段-完全可见和显然不可见。2）特别适用二种场合：大窗口场合窗口特别小的场合,Cohen-Sutherland 算法的特点,直线段裁剪(11/15),14,中点分割法,基本思想： 从P0点出发找出距P0最近的可见点 从P1点出发找出距P1最近的可见点 不断地在中点处将线段一分为二，对每段线段重复Cohen-Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止 取中点Pm=(P1+P2)/2。,直线段裁剪(12/15),15,Liang-Barsky裁剪算法,直线L与区域的交：当Q为空集时，线段AB不可能在窗口中有可见线段。 当Q不为空集时，Q可看成是一个一维窗口,直线段裁剪(13/15),基本思想： 把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段。,16,Liang-Barsky裁剪算法,直线段裁剪(14/15),存在可见线段的充要条件不为空集,向x轴投影，就得到可见线段上点的坐标的变化范围为,左端点,右端点,17,Liang-Barsky裁剪算法,AB有可见部分的充分必要条件也可表示为,直线段裁剪(15/15),18,多边形裁剪-1/2,用直线段裁剪算法，可以吗？ 新的问题：,边界不再封闭，需要用窗口边界的恰当部分来封闭它,19,分裂为几个多边形,多边形裁剪-2/2,关键： 不仅在于求出新的顶点，删去界外顶点 还在于形成正确的顶点序列,20,Sutherland-Hodgman算法-1/4,分割处理策略： 将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。 流水线过程(左上右下)：左边的结果是右边的开始。,亦称逐边裁剪算法,21,Sutherland-Hodgman算法-2/4,内侧空间与外侧空间 多边形的边与半空间的关系,22,Sutherland-Hodgman算法-3/4,裁剪结果的顶点构成： 裁剪边内侧的原顶点； 多边形的边与裁剪边的交点。 顺序连接。,优点： 裁剪算法采用流水线方式，适合硬件实现。 可推广到任意凸多边形裁剪窗口,23,Sutherland-Hodgman算法-4/4 存在的问题,逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？,逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这几个多边形沿边框产生多余的线段？,24,Weiler-Atherton算法-1/6,裁剪窗口为任意多边形（凸、凹、带内环）的情况主多边形：被裁剪多边形，记为SP 裁剪多边形：裁剪窗口，记为CP,25,约定： SP与CP均用它们顶点的环形链表定义 外边界取顺时针方向 内边界取逆时针方向,Weiler-Atherton算法-2/6,26,SP和CP把二维平面分成两部分。 内裁剪：SPCP 外裁剪：SP-CP,Weiler-Atherton算法-3/6,裁剪结果区域的边界由SP的部分边界和CP的部分边界两部分构成，并且在交点处边界发生交替，即由SP的边界转至CP的边界，或由CP的边界转至SP的边界,27,Weiler-Atherton算法-4/6,主多边形与裁剪多边形交点成对出现 分为如下两类：进点：主多边形边界由此进入裁剪多边形内 出点：主多边形边界由此离开裁剪多边形区域.,28,Weiler-Atherton算法-5/6,主多边形表,裁剪多边形表,S1,S2,I1,S3,S4,S5,S6,I2,I3,I4,I5,I6,I7,I8,C1,C2,I3,I4,C4,I8,I1,I2,I5,C3,I5,I6,S1,I7,C1,开始,结束,29,Weiler-Atherton算法-6/6,主多边形表,裁剪多边形表,S1,S2,I1,I4,S4,S6,I5,I2,I3,S3,S1,S5,S7,I6,S8,I7,I8,S5,C1,C2,C3,C4,I4,I5,I1,I8,C1,C5,C5,C6,I2,I3,I6,C7,C8,I7,算法裁剪后所生成的多边形为I1I2I7I8I1和I3I4I5I6I3,裁剪多边形,主多边形,开始,开始,结束,结束,