第5章 图形变换与裁剪3.ppt

第五章图形变换与裁剪(三)
计算机学院
苏小红
1
二维裁剪
1 直线段裁剪
直接求交算法
Cohen-Sutherland算法
中点分割裁剪算法
梁友栋-Basky算法
2 多边形裁剪
Sutlerland_Hodgman算法
Weiler-Atherton算法
2
直线段裁剪(1/15)
裁剪的目的
判断图形元素是否在裁剪窗口之内并找出其位于内部的部分
裁剪处理的基础
图元关于窗口内外关系的判别
图元与窗口的求交
裁剪、覆盖
3
直线段裁剪(2/15)
裁剪窗口
矩形、圆形、一般多边形
被裁剪对象
线段、多边形、曲线、字符
裁剪的策略
先裁剪,后变换
先变换,后裁剪
裁剪算法的核心问题
效率
4
直线段裁剪(3/15)
点裁剪
点(x, y)在窗口内的充分必要条件是:

问题:对于任何多边形窗口,如何判别?
5
直线段裁剪(4/15)
假定条件
矩形裁剪窗口:[xmin,xmax]X[ymin,ymax]
待裁剪线段:
任何平面线段相对于凸多边形窗口进行裁剪后?
6
直线段裁剪(5/15)
待裁剪线段和窗口的关系
完全落在窗口内
完全落在窗口外
部分在内,部分在外
7
直线段裁剪(6/15)
为提高效率,算法设计时应考虑:
1. 快速判断情形(1)(2);
2. 设法减少情形(3)求交次数和每次求交时所需的计算量
8
Cohen-Sutherland 算法(编码算法)
算法步骤:
第一步判别线段两端点是否都落在窗口内,如果是,
则线段完全可见;否则进入第二步;
第二步判别线段是否为显然不可见,如果是,则裁
剪结束;否则进行第三步;
第三步求线段与窗口边延长线的交点,这个交点将
线段分为两段,其中一段显然不可见,丢弃。
对余下的另一段重新进行第一步,第二步判断,
直至结束
裁剪过程是递归的。
直线段裁剪(7/15)
9
特点:
对显然不可见线段的快速判别
编码方法:
由窗口四条边所在直线把二维平面分成9个区域,每个区域赋予一个四位编码, CtCbCrCl,上下右左;
Cohen-Sutherland 算法
直线段裁剪(8/15)
10