为提高效率，算法设计时应考虑： (一）快速判断情形(1)(2)； (二) 设法减少情形(3)求交次数和每次求交时所需的计 算量。
2020/10/18
计算机科学与技术学院
8
➢ 实交点是直线段与窗口矩形边界的交点。 ➢ 虚交点则是直线段与窗口矩形边界延长线或直线
段的延长线与窗口矩形边界的交点。
A
实交点
(xmax,ymax )
xm in xxmax
yminyymax
➢ 裁剪窗口（Xmin，Xmax，Ymin，Ymax）
是世界坐标系的窗口边界或视区边界
➢ 应用举例
(xmin,ymin )
➢ 爆炸场景或海面泡沫的显示
➢ 问题：对于任何多边形窗口，如何判别？
2020/10/18
计算机科学与技术学院
4
直线段裁剪
➢ 包含性测试
若线段满足：xl≤x1≤ xr, yb≤y1≤ yt,则线段的始点在0 区，也即线段可见段的起点为：
xs = x1 , ys= y1
2020/10/18
计算机科学与技术学院
13
➢求交点，并判断 I. 若x1＜xl,则：
线段的起点坐标可能 位于3区、4区、5区。
3
4 (x1,y1)
而新起点的坐标可能在 直线y= yb和线段的交点上 直线y= yt和线段的交点上 直线x= xl和线段的交点上
➢ 待裁剪线段：18
计算机科学与技术学院
5
直线段裁剪
➢ 待裁剪线段和窗口的关系
（1）完全落在窗口内，线段完全可见 （2）完全落在窗口外，显然不可见 （3）与窗口边界相交，线段至少有一端点在窗口之外，但非
显然不可见
2020/10/18
计算机科学与技术学院
5 xl
2020/10/18
计算机科学与技术学院
1
6
yt
(x2,y2)
0
7
yb
2
8
xr
14
第一种情况：
xsx 1(yby1)x (2x 1)/( y2y1) ysyb
此时，若xl≤xs≤ xr 则(xs ys)为有效新起点。
第二种情况：
xsx1(yt y1)x (2x1)/( y2y1) ysyt
10
直接求交算法
直线与窗口边 都写成参数形 式，求参数值。
2020/10/18
计算机科学与技术学院
11
矢量裁剪法
➢ 算法思想
先从线段的一个端点出发进行判断或进行求交运算，所得交点 坐标保存在（xs，ys）中，然后再从线段的另一个端点出 发用前面的判断及其求交运算求得交点坐标（x，y），最后 只输出两个交点间的线段。
位于6区、7区、8区。
4
而新起点的坐标可能在 直线y= yb和线段的交点上 直线y= yt和线段的交点上 直线x= xr和线段的交点上
5 xl
1
6
yt
0
7 (x1,y1)
yb
2
8
xr
2020/10/18
计算机科学与技术学院
16
第一种情况： x ys s x y1 b(yby1)x (2x1)/(y2y1) 此时，若xl≤xs≤ xr 则(xs ys)为有效新起点。
6
要确定一条直线段上位于窗口内的可见段，只 须求出它的两个位于窗口内的可见端点即可。 ➢ 算法的基本思想
把所有的直线按照它和窗口的关系分类，不同 的直线使用不同的处理方法确定其可见部分。
2020/10/18
计算机科学与技术学院
7
直线裁剪算法的主要步骤： 首先将不需要裁剪的直线挑出，并删去其中在窗外的 直线； 其次，对其余直线，逐条与窗框求交点，并将窗外部 分删去
二维图形的裁剪优秀课件
二维裁剪
➢ 识别图形在指定区域内和区域外的部分的过程称为裁剪算法， 简称裁剪（clipping）
➢ 二维窗口是投影平面上的一个矩形。一般来说，这个矩形的边 和投影平面上的坐标轴平行，图形在窗口内的部分被显示出来， 窗口外的部分被裁剪掉了。平面上的图形受该矩形的裁剪称为 二维裁剪。
第二种情况： x ys s x y1 t (yt y1)x (2x1)/(y2y1) 此时，若xl≤xs≤ xr 则(xs ys)为有效新起点。
实交点 H
I 虚交点
G
F
窗口
虚交点 JD
实交点
E
B
虚交点
C
图6-25 实交点与虚交点
2020/10/18
计算机科学与技术学院
9
直线的剪裁算法
直接求交算法
矢量裁剪法
Cohen-Sutherland算法
中点分割算法
梁友栋－Barsky算法
2020/10/18
Nicholl-Lee-Nicholl算法
计算机科学与技术学院
➢ 用窗口的四条边界的直线将窗口分为9个区。
3
1
6
yt
(x2,y2)
4
0
7
(x1,y1)
yb
5
2
8
2020/10/18
x x 计算机科学与技术学院
l
r
12
➢ 排斥性测试
若线段满足下述四个条件之一时：
max(x1,x2)≤xl min(x1,x2)≥xr max(y1,y2)≤yb min(y1,y2)≥yt 则线段必定位于窗口之外，无输出线段。
此时，若xl≤xs≤ xr 则(xs ys)为有效新起点。
第三种情况：xxl
yyl (y1y0)x (l x0)/x (1x0)
此时，若yb≤ys≤ yt 则(xs ys)为有效新起点。
三种情况都不满足，则此线段不在窗口区内。
2020/10/18
计算机科学与技术学院
15
II. 若x1>xr
3
线段的起点坐标可能
2020/10/18
计算机科学与技术学院
2
➢ 裁剪的应用
➢ 从定义的场景中抽取用于观察的部分
➢ 在三维视图中识别出可见面
➢ 防止线段或对象的边界混淆
➢ 用实体造型来创建对象
➢ 显示多窗口的环境
➢ 允许选择图形的一部分来进行拷贝、移动或删除等绘图操作
➢ 裁剪算法类型
➢ 图形裁剪与窗口——视图变换的先后
➢ 窗口边界裁剪 ➢ 视区边界裁剪
➢ 图形生成与裁剪先后
➢ 先生成后裁剪
➢ 先裁剪后生成
2020/10/18
计算机科学与技术学院
3
点的裁剪
➢ 图形裁剪中的最基本的问题。
➢ 假设裁剪窗口为一个在标准位置的矩形，即边与坐标轴平行的
矩形，由上（y=ymin）、下（y=ymax）、左（x=xmin）、右
（x=xmax）四条边描述。 ➢ 点(x, y)在窗口内的充分必要条件是：
➢ 直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过 折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。
➢ 裁剪的目的
判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分
➢ 裁剪处理的基础
➢ 图元关于窗口内外关系的判别 ➢ 图元与窗口的求交
➢ 假定条件
➢ 矩形裁剪窗口：[xmin,xmax]X[ymin,ymax]