D 3D 2D 1D 0
0110
Cohen-Sutherland算法
裁剪一条线段时，先求出端点 p1 和 p2 的编码 code1 和 code2，然后： (1)若code1|code2=0，对直线段应“简取”之。 (2)若code1&code2≠0，对直线段可“简弃”之。
(3)若上述两条件均不成立。则需求出直线段与窗口边 界的交点。在交点处把线段一分为二，其中必有一段 完全在窗口外，可以弃之。再对另一段重复进行上述 处理，直到该线段完全被舍弃或者找到位于窗口内的 一段线段为止。
二维裁剪
直线段裁剪 • Cohen-Sutherland算法；
• • 中点算法 Nicholl-Lee-Nicholl算法
多边形裁剪
•
• Sutlerland_Hodgman算法 Weiler-Athenton算法
假设窗口是标准矩形，即边与坐标轴平行的矩 形，由上（y=yt）、下（y=yb）、左（x=xl）、 右（x=xr）四条边描述。
•如果线段平行于裁剪窗口的某两边界，则必有相应的 pk﹦0，如果还满足qk＜0，则线段的端点位于窗口外部， 即线段在窗口外，应该舍弃。如果qk≥0，线段在窗口内。 •当 pk ＜ 0 时，若直线与裁剪窗口第 k 条边界线相遇，则必 是从边界线外部延伸到内部。例如当p1 ＜0时，则x2＞x1, 直线必然从裁剪窗口的左边界线的外部进入内部，如下图 中的线段P1P2。 •当 pk ＞ 0 时，若直线与裁剪窗口第 k 条边界线相遇，则必 是从边界线的内部延伸到外部。例如p2 ＞0时，则x2＞x1, 直线必然从裁剪窗口的右边界线的内部进入外部 ,如下图 中的线段P3P4。
当pk不等于零时，可以计算出线段与第k条裁剪窗 口边界线的交点参数：
qk rk pk
根据定义，对于每条线段，pk中必有两个小于零，而另 两个大于零。 •对于小于零的pk，直线同第k条裁剪窗口边线是从外到 内相遇的，此时如果线段同第k条裁剪窗口边界线有交 点的话，是参数 u 从 0 变大时遇到的，这时计算出相应 的rk值，取0和各个rk值之中的最大值记为u1。 •对于大于零的pk，计算出相应的rk值，取1和各个rk值 之中的最小值记为u2。两个参数u1和u2定义了在裁剪窗 口内的线段部分。如果u1＞u2，则线段完全落在裁剪窗 口之外，应被舍弃。否则被裁剪线段可见部分的端点 由参数u1和u2计算出来。
– 可见一侧空间和不可见一侧空间 – 沿多边形依次处理顶点会遇到四种情况
当前裁剪边 可见一侧 Pi+1 Pi
窗口 当前裁剪边 当前裁剪边 当前裁剪边
可见一侧 Pi
可见一侧 Pi Pi+1
可见一侧
Pi+1 窗口
窗口 窗口
Pi+1
Pi
(a) 输出Pi+1
(a) 无输出
(a) 输出I
(a) 输出I和Pi+1
B
p1，p3小于0，决定u1(max)，取0与r1和r3中的大者，u1=1/4 p2，p4大于0，决定u2，取1与r2和r4中的小者，u2=3/4 两交点由u1，u2决定： 1 x x1 u( x2 x1 ) x1 ux 计算：(1) x 1 4 4 2 y y1 u( y2 y1 ) y1 uy 1 1 y 2 1 2 4 4 (2) 3 x 1 4 4 4 3 3 y 2 1 2 4 4
x x1 u( x2 x1 ) x1 ux y y1 u( y2 y1 ) y1 uy
0≤u≤1
坐标(x,y)表示直线上两端点之间的任一点。当u=0时，得 点P1，当u=1时，得点P2。线段的裁剪条件可以由下面的不 等式表示： Wxl≤x1﹢uΔ x≤Wxr Wyb≤y1﹢uΔ y≤Wyt 这四个不等式可以表示为： upk≤qk k=1,2,3,4 Δx=x2-x1; Δy=y2-y1; 其中，参数p,q定义为： p1﹦-Δ x, q1﹦x1﹣Wxl p2﹦Δ x, q2﹦Wxr﹣x1 p3﹦-Δ y, q3﹦y1﹣Wyb p4﹦Δ y, q4﹦Wyt﹣y1 下标 k=1,2,3,4 分别对应裁剪窗口的左、右、下、上四条 边界线。
Cohen-SutherLand算法
对于那些非完全可见、又非显然不可见的线段，需要 求交求交前先测试与窗口哪条边所在直线有交？(按序判 断端点编码中各位的值D4D3D2D1）
1001 1000 0000 窗口 1010
• 求交测试顺序固定 • 最坏情形，线段求交四 次。
0001
0010
0101
0100
通常粱友栋-Barsky算法比Cohen-Sutherland算法 更有效，因为需要计算的交点数目减少了。一次计算 就可以确定出线段的可见性及可见部分。这两种线段 裁剪算法都可以扩展为三维线段裁剪算法。
多边形裁剪
• 用直线段裁剪算法，可以吗？ • 新的问题：
A A B B
图1 因丢失顶点信息而去法确定裁剪区域
练习：试用 S-H 算法裁剪下图多边形，要求画出每 次裁剪对应的图形，并表明输入输出的顶点。
D(6,8)
y 6 E(1,5) 2
B(5,4)
0
A(4,1) 2 6
C(8,1) x
解：用左边界裁剪前后为：
D(6,8) y
6M(2,5.6) N(2,3.6) 2 0 A(4,1) 2 6 C(8,1) 0 x 2 C(8,1) 6 x D(6,8)
Cohen-Sutherland算法
基本思想：
对每条直线段p1(x1,y1)p2(x2,y2)分三步处理：
(1)判断点P1和P2是否完全在裁减窗口内，若是，直线段完全可见，“简取”之。
否则进入步骤（2）。 x1<xl and x1>xr x2<xl and x2>xr y1>yb and y1<yt
y 6 E(1,5) 2
B(5,4)
B(5,4)
A(4,1)
输入为：ABCDE
输出为：BCDMNA
2.如下图所示，裁减窗口为正方形，采用逐边裁件算法，依次按左、下、右、 上的顺序，用四条窗口边界裁减多边形ABCDE。试写出每条框口边界裁减 后输出的新的多边形的顶点序列。
答：左边界裁减后： ABCD12 下边界裁减后： 4B56D123 右边界裁减后： 4B7D123 上边界裁减后： 4B789123
• 消除C-S算法中多次求交的情况。 • 基本想法：对2D平面的更细的划分。
参数化线段裁剪算法
更快的线段裁剪算法基于线段的参数化方程的 分析，它是由粱友栋和Barsky提出的，也称为粱 友栋-Barsky线段裁剪算法。 设线段两端点坐标分别为 P1(x1,y1)和P2(x2,y2), 则其参数化直线方程可写成下列形式：
Cohen-Sutherland算法
特点： 对完全可见和不可见线段的快速判别。
编码方法：
由窗口四条边所在直线把二维平面分成 9个区域，每个区域赋予一个 4 位的二进制编码D4D3D2D1。编码规则如下: – 若x<xl，则D1=1，否则D1=0； – 若x>xr，则D2=1，否则D2=0； – 若y<yb，则D3=1, 否则D3=0； – 若y>yt，则D4=1，否则D4=0。
梁友栋线的裁剪算法例子 设：Wxl=2; Wxr=4; Wyb=2; Wyt=4 被裁剪线段的两端点：（1，2），（5，3） 计算：Δ x=5-1=4 Δ y=3-2=1 p1= -4，q1= -1 p2=4， q2=3 p3= -1，q3= 0 p4=1， q4=2
p1﹦-Δx, q1﹦x1﹣Wxl p2﹦Δx, q2﹦Wxr﹣x1 p3﹦-Δy, q3﹦y1﹣Wyb p4﹦Δy, q4﹦Wyt﹣y1 A
图2 原来封闭的多边形变成了孤立的线段
• 关键：
– 求出新的顶点，删去界外顶点 – 形成正确的顶点序列
Sutherland-Hodgman算法
• 分割处理策略：将多边形关于矩形窗口的裁剪分解为多边
形关于窗口四边所在直线的裁剪。
• 流水线过程(左上右下)：左边的结果是右边的开始。
亦称逐边裁剪算法
Sutherland-Hodgman算法
y yt
yb
xl
xr
x
点的裁剪
对于任意一点P(x,y),若满足下列不等式
xl x xr , 且yb y yt
则点 P 在矩形窗口内；否则，点 P 在 矩形窗口外。
y yt P(x,y) yb
xl
xr
x
直线段的裁剪
• 直线段和剪裁窗口的可能关系：
(1) 完全落在窗口内
(2) 完全落在窗口外 为提高效率，算法设计时应考虑： (3) 与窗口边界相交 (一）快速判断情形(1)(2)； (二) 设法减少情形(3)求交次数和每次求交时所需的计 算量。
中点分割算法 基本思想： 当对直线段不能简取也不能简弃时，简单地把线段等 分为二段，对两段重复上述测试处理，直至每条线段 完全在窗口内或完全在窗口外。
例
p1
×
p5

p1
p4ቤተ መጻሕፍቲ ባይዱ


p6
×
p7
p3
×
p2
p2
中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点。
Nicholl-Lee-Nicholl算法
线段与当前裁剪边的位置关系
Sutherland-Hodgman算法
• 裁剪结果的顶点构成：裁剪边内侧的原顶点；多
边形的边与裁剪边 的交点。
• 顺序连接。
几点说明： 裁剪算法采用流水线方式， 适合硬件实现。 可推广到任意凸多边形裁剪 窗口
例子：对多边形ABCDEFGH进行裁剪
A
G B