哈尔滨工业大学计算机科学与技术学院：《计算机图形学》第5章 图形变换与裁剪（三）（苏小红）

第五章 图形变换与救剪(三) 计算机学院 苏小红

1 第五章 图形变换与裁剪（三） 计算机学院 苏小红

二维裁剪 1直线段裁剪 直接求交算法 Cohen- Sutherland算法 中点分割裁剪算法 梁友栋 Basky算法 2多边形裁剪 Sutherland_ Hodgman算法 Weiler-Atherton算法

2 二维裁剪 1 直线段裁剪 直接求交算法 Cohen-Sutherland算法 中点分割裁剪算法 梁友栋-Basky算法 2 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Atherton算法

直线段裁剪(1/15) ·裁剪的目的 a判断图形元素是否在裁剪窗口之内并找出其位于内部的部分 裁剪处理的基础 图元关于窗口内外关系的判别 图元与窗口的求交 ·裁剪、覆盖

3 直线段裁剪(1/15) 裁剪的目的 ◼ 判断图形元素是否在裁剪窗口之内并找出其位于内部的部分 裁剪处理的基础 ◼ 图元关于窗口内外关系的判别 ◼ 图元与窗口的求交 裁剪、覆盖

直线段裁剪(2/15) 裁剪窗口 矩形、圆形、一般多边形 被裁剪对象 线段、多边形、曲线、字符 ·裁剪的策略 先裁剪,后变换 先变换,后裁剪 ·裁剪算法的核心问题 效率

4 直线段裁剪(2/15) 裁剪窗口 ◼ 矩形、圆形、一般多边形 被裁剪对象 ◼ 线段、多边形、曲线、字符 裁剪的策略 ◼ 先裁剪，后变换 ◼ 先变换，后裁剪 裁剪算法的核心问题 ◼ 效率

直线段裁剪(3/15) 点裁剪 n点(x,y)在窗口内的充分必要条件是: xmn≤x≤xmax ymin<y≤ymax 问题:对于任何多边形窗口,如何判别?

5 直线段裁剪(3/15) 点裁剪 ◼ 点(x, y)在窗口内的充分必要条件是： 问题：对于任何多边形窗口，如何判别？ x min  x  x max y min  y  y max

直线段裁剪(4/15) 假定条件 a矩形裁剪窗口:[xmin,xmax] XImin,ymax] 待裁剪线段:P(xy)P(x2y) 任何平面线段相对于凸多边形窗口进行裁剪后?

6 直线段裁剪(4/15) 假定条件 ◼ 矩形裁剪窗口：[xmin,xmax]X[ymin,ymax] ◼ 待裁剪线段： 任何平面线段相对于凸多边形窗口进行裁剪后？ P x y P x y 0 0 0 1 1 1 ( , ) ( , )

直线段裁剪(5/15) 待裁剪线段和窗口的关系 完全落在窗口内 完全落在窗口外 部分在内,部分在外 H E ymin Xmin Xm ax

7 直线段裁剪(5/15) 待裁剪线段和窗口的关系 ◼ 完全落在窗口内 ◼ 完全落在窗口外 ◼ 部分在内，部分在外

直线段裁剪(6/15) 为提高效率,算法设计时应考虑: 1.快速判断情形(1)2) 2.设法减少情形(3)求交次数和每次求交时所需的计算量

8 直线段裁剪(6/15) 为提高效率，算法设计时应考虑： 1. 快速判断情形(1)(2)； 2. 设法减少情形(3)求交次数和每次求交时所需的计算量

直线段栽剪(7/15) Cohen-Sutherland算法(编码算法) 算法步骤 第一步判别线段两端点是否都落在窗口内,如果是, 则线段完全可见;否则进入第二步; 第二步判别线段是否为显然不可见,如果是,则裁 剪结束;否则进行第三步; 第三步求线段与窗口边延长线的交点,这个交点将 线段分为两段,其中一段显然不可见,丢弃。 对余下的另一段重新进行第一步,第二步判断, 直至结束 裁剪过程是递归的

9 Cohen-Sutherland 算法 (编码算法) 算法步骤： 第一步 判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步； 第二步 判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步 ； 第三步 求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。 对余下的另一段重新进行第一步，第二步判断， 直至结束 裁剪过程是递归的。 直线段裁剪(7/15)

直线段裁剪(8/15) Cohen-Sutherland算法 特点 对显然不可见线段的快速判别 编码方法: 由窗口四条边所在直线把二维平面分成9个区域,每个区域赋予一个四 位编码,CCcC,上下右左; vmaX lyxmax 1当x< x min ymin 01011010 0110 0 else 0 else min Xm ax

10 特点： ◼ 对显然不可见线段的快速判别 编码方法： ◼ 由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四 位编码，CtCbCrCl，上下右左；     = else y y Ct 0 1 当 max     = else x x Cr 0 1 当 max     = else x x Cl 0 1 当 min     = else y y Cb 0 1 当 min Cohen-Sutherland 算法 直线段裁剪(8/15)