直线裁剪算法

前面我们讲了如何填充和变换二维图形，这篇文章来讲解如何对直线段进行裁剪——判断哪些部分在窗口内、哪些在窗口外，只保留该画的部分。

直线裁剪算法

基本概念

裁剪（Clipping） 是图形管线中的关键一步：给定一个矩形窗口和一条直线段，求出该线段位于窗口内的部分。

直线裁剪算法主要有两种分类方式：

按思想分类：

• 区域编码类（Region Code）——给点打标签，快速判断位置关系
• 参数方程类（Parametric）——用线段参数方程统一处理，使用最广泛
• 中点递归/分治类（Subdivision）——反复取中点逼近边界

按窗口形状分类：

• 矩形窗口裁剪（最常见）
• 任意凸多边形窗口裁剪
• 非凸窗口裁剪

下面按思想分类来介绍。

区域编码类

Cohen–Sutherland 算法

基本思想：把窗口周围划分成 9 个区域，每个点用一个 4 位二进制编码标记其位置。通过对线段两端点的编码做位运算，快速判断”全在内部”“全在外部”还是”需要裁剪”。

区域编码规则：

四位编码从左到右依次表示：上、下、右、左。某一位为 1 表示该点在对应边界之外。

1
2
3
4
5

1001 | 1000 | 1010
─────┼──────┼─────
0001 | 0000 | 0010     窗口中心区域为 0000
─────┼──────┼─────
0101 | 0100 | 0110

编码规则：

• 第1位（上）：
• 第2位（下）：
• 第3位（右）：
• 第4位（左）：

对线段两端点 、 编码后得到 code0 和 code1，有三种情况：

1. 完全接受

1

(code0 | code1) == 0

两端点都在窗口内（都为 0000），整条线段无需裁剪，直接保留。

2. 完全拒绝

1

(code0 & code1) != 0

两端点的编码在同一位上都是 1，说明线段完全在窗口的某一侧（比如两个端点都在左边），直接丢弃。

3. 部分可见

不满足上面两种情况时，线段跨越多条边界，需要逐条边界求交、更新端点、重新编码，直到满足情况 1 或 2。

裁剪过程（部分可见时）：

1
2
3
4
5

1. 选取编码中某一位为 1 的端点（说明该点在对应边界外）
2. 计算该端点所在边界与线段的交点
3. 用交点替换该端点
4. 重新对新端点编码
5. 返回步骤 1，直到完全接受或完全拒绝

当两端点某一位同时为 1 时（code0 & code1 != 0），线段完全在该边界之外，可以直接丢弃，省去了与该边界求交的计算。这是 Cohen-Sutherland 相比盲目求交算法的核心优势。

具体例子

设窗口：。

线段 ： → 。

第一步：编码

• ： → 左位为 1； 在范围内 → 下/上为 0； 没超过 → 右为 0。编码：0001（左）。
• ： → 右位为 1；其余为 0。编码：0010（右）。

第二步：判断状态

• code0 | code1 = 0001 | 0010 = 0011 ≠ 0 → 不是完全接受
• code0 & code1 = 0001 & 0010 = 0000 == 0 → 不是完全拒绝
• 结论：部分可见，需要裁剪。

第三步：逐边裁剪

的第 4 位（左）为 1，说明 在左边界之左。求 与左边界 的交点：

替换 为 。重新编码： 刚好在左边界上（不算在外面）， 在范围内 → 0000。

现在两端点编码：、。

的第 3 位（右）为 1，求 与右边界 的交点：

替换 为 。重新编码：0000。

此时 code0 | code1 = 0000 → 完全接受，算法结束。

裁剪后的线段： → 。

算法特点：

优点： - 思想直观，位运算极快 - 大量线段完全在内部或外部时效率很高

缺点： - 部分可见时可能逐边求多次交点 - 对于跨越多条边界的线段，每步都要重新编码

Nicholl–Lee–Nicholl（NLN）算法对 Cohen-Sutherland 做了优化，通过额外预判减少了求交次数，但实现复杂度显著提高，实际应用较少，在这里我们不做介绍。

参数方程类

这类算法把线段表示为参数方程，通过求”合法的参数区间”来裁剪，避免了逐点编码的反复试探。

Liang–Barsky 算法

这是唯一一个以中国人（梁友栋 & Barsky）命名的计算机图形学经典算法。

基本思想：不是反复求线段和窗口边界的交点再判断，而是一次性算出线段上”能被窗口看见”的参数区间 。

参数方程

线段 的参数形式：

是起点， 是终点。记 ，，则：

推导不等式

对四条窗口边界分别代入约束：

• 左边界： → →
• 右边界： → →
• 下边界： → →
• 上边界： → →

统一写成 的形式：

• 左：，
• 右：，
• 下：，
• 上：，

分析

对于每条边 ，不等式为 ：

• ：除以负数要变号 → 。 必须大于等于这个值才能满足约束，即点从这条边进入窗口。更新进入时间：

• ：直接除以正数 → 。 超出这个值就不满足约束了，即点从这条边离开窗口。更新离开时间：

• ：线段与该边界平行。此时 消失，需要单独判断 ：

  • 若 ，则 不成立 → 线段在窗口外 → 直接丢弃
  • 若 ，不等式恒成立 → 此边界不构成限制 → 忽略

算法步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

输入: 线段 P0(x0,y0), P1(x1,y1)  窗口: (xmin, ymin) ~ (xmax, ymax)

1. t_enter = 0,  t_leave = 1
2. 计算 Δx = x1 - x0,  Δy = y1 - y0
3. 对四条边界，分别取 p, q:
   左: p = -Δx,  q = x0 - xmin
   右: p =  Δx,  q = xmax - x0
   下: p = -Δy,  q = y0 - ymin
   上: p =  Δy,  q = ymax - y0

4. 对每条边:
   a) 若 p == 0 且 q < 0  →  trivially reject
   b) 若 p < 0  →  t_enter = max(t_enter, q/p)
   c) 若 p > 0  →  t_leave  = min(t_leave,  q/p)

5. 若 t_enter > t_leave  →  线段在窗口外，丢弃

6. 裁剪后线段:
   起点 = P0 + t_enter · (P1 - P0)
   终点 = P0 + t_leave  · (P1 - P0)

注意： 可能 < 0（线段起点已深入窗口内部）， 可能 > 1（终点在进入窗口前），这都不影响判断，只要 就有可见段。

具体例子（用同一个场景对比）

窗口：。

线段 ： → 。

，。

初始：，。

逐边处理：

逐边处理：

处理左边界：， （进入边） →

处理右边界：， （离开边） →

处理下边界：， （进入边） →

处理上边界：， （离开边） →

最终区间：。

→ 有可见段。

计算裁剪后端点：

裁剪后线段： → ，结果与 Cohen-Sutherland 一致。

Cyrus–Beck 算法

基本思想：Cyrus-Beck 是 Liang-Barsky 的推广。Liang-Barsky 用四条边的 、 处理矩形窗口，Cyrus-Beck 用每条边的内法向量和边上任意一点，把同一套框架推广到任意凸多边形窗口——三角形、五边形、乃至任意凸多边形。

整体思路与 Liang-Barsky 一致：遍历每条边，根据该边是”进入边”还是”离开边”，更新 区间。

推导

参数方程（记方向向量 ）：

窗口边的表示：对于凸多边形的第 条边，定义两个量：

• ：该边上的任意一点（通常取一个端点）
• ：该边的内法向量，指向窗口内部

核心条件：点 在凸多边形内部的充要条件是——对每一条边， 都在边的内侧：

将 代入：

展开：

解出交点参数 ：

进入 / 离开分类：系数 的符号决定不等号方向，从而决定该边是”进入边”还是”离开边”：

• （进入边）：除以正数不变号，得 ，给出下界——线段从此边进入窗口

• （离开边）：除以负数变号，得 ，给出上界——线段从此边离开窗口

• （平行）： 从不等式中消失。此时检查 ：

  • 若 ：线段整体在窗口外侧 → 直接丢弃
  • 若 ：该边不构成限制 → 忽略

算法步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输入: 线段 P0, P1，凸多边形窗口顶点序列 V[0..n-1]（逆时针排列）
输出: 裁剪后的线段（或空）

1. t_enter = 0,  t_leave = 1
2. D = P1 - P0
3. 对每条边 i (从 V[i] 到 V[(i+1) mod n]):
   a) Fi = V[i]
   b) 计算边方向 Ei = V[(i+1) mod n] - V[i]
   c) 计算内法向量 Ni = (-Ei.y, Ei.x)  （将边方向逆时针旋转 90°）
   d) dot_N_D = Ni · D
   e) 若 dot_N_D == 0:
        - 若 Ni · (P0 - Fi) < 0  →  线段在外侧，丢弃
        - 否则  →  忽略此边，continue
   f) t = Ni · (Fi - P0) / dot_N_D
   g) 若 dot_N_D > 0  →  t_enter = max(t_enter, t)   // 进入边
   h) 若 dot_N_D < 0  →  t_leave  = min(t_leave,  t)  // 离开边
4. 若 t_enter > t_leave  →  线段在窗口外，丢弃
5. 输出线段: P0 + t_enter · D  →  P0 + t_leave · D

具体例子

用与前两个算法相同的场景，但这次把窗口视为一个四边形的凸多边形（逆时针排列）。

窗口顶点： → → → 。

线段： → ，方向向量 。

初始：，。

逐边处理：

逐边处理：

处理 e0（）： - ，， - → 进入边 - - -

处理 e1（）： - ，， - → 离开边 - - -

处理 e2（）： - ，， - → 离开边 - - -

处理 e3（）： - ，， - → 进入边 - - -

各列的详细计算说明（以 e0 为例）：

• （逆时针旋转 90°，指向窗口内部即上方）
• → 进入边
• （实际上这条边不缩小 ）

最终区间：。

→ 有可见段：

裁剪后线段： → ，与前面两个算法结果一致。

与 Liang-Barsky 的关系

Cyrus-Beck 用在矩形窗口上时，四条边的 和 取值非常简单，代入后完全退化为 Liang-Barsky。

对应关系：Cyrus-Beck 的 （进入边）等价于 Liang-Barsky 的 （进入边），（离开边）等价于 （离开边），同一套逻辑。

Cyrus-Beck 的通用性在于：只需更换 和 的定义，就能处理任意凸多边形窗口。

中点递归/分治类

这一类算法不用参数方程，而是反复取线段中点来逼近窗口边界。

基本思路：

1. 对线段两端点编码（同 Cohen-Sutherland）
2. 若完全接受 → 保留；若完全拒绝 → 丢弃
3. 否则取线段中点 ，将线段一分为二
4. 对两段子线段递归执行步骤 1-3
5. 当线段长度小于某个阈值时停止

这种方法不需求交点，只需编码判断和中点计算（整数运算），在早期硬件上实现方便。但由于递归调用多，性能不如 Liang-Barsky，现代已较少使用。

总结对比

实际使用中，如果只需要矩形窗口裁剪，Liang-Barsky 是首选——一次遍历四条边，没有重复编码的开销，实现简洁高效。

这次的插图来自画师Chigu

图片地址：https://www.pixiv.net/artworks/69618131