3.2 裁剪：Cohen-Sutherland 与 Liang-Barsky

3.2 裁剪：Cohen-Sutherland 与 Liang-Barsky

本节摘要：屏幕外的几何不值得光栅化，裁剪（clipping）在"翻译成像素"之前把窗外部分剔除，既是正确性要求（防止越界写内存），也是性能优化（少画就是赚）。本节手推 Cohen-Sutherland 的区域编码法与 Liang-Barsky 的参数区间法，比较两者在"大量线段快速剔除"与"求精确交点"上的分工，并引出三维裁剪的预告。承接 3.1 的图元生成，为 3.3 变换后的落格做守门。

学习目标

阅读完本节，你应当能够：

1. 写出 Cohen-Sutherland 的 4 位 outcode 编码，用它快速剔除窗外线段
2. 手推线段与窗口边界的交点公式，完成线段的逐步收缩
3. 用 Liang-Barsky 的参数不等式组一次解出可见区间
4. 说明两种算法各自适合的场景与三维推广形式

核心问题

光栅化器只认窗口内的整数坐标。若线段端点在窗外，直接光栅化会写出帧缓冲边界之外——在软渲染器里是数组越界崩溃，在硬件里是撕裂内存保护。所以必须先裁剪：把几何精确修剪到窗口范围内，窗外部分丢弃。

裁剪看似只是"求交点"，规模却是瓶颈：一帧几十万个图元，绝大多数要么完全在内、要么完全在外，真正压着窗口边的只是少数。好的裁剪算法要能对两个大类做几乎零成本的快速判断——这正是 Cohen-Sutherland 编码法的设计出发点。

Cohen-Sutherland：给空间分区编号

把平面按窗口四条边分成 9 个区域，每个区域一个 4 位二进制码，从高到低依次表示：上、下、右、左。

outcode 规则（窗口为 x∈[xmin,xmax], y∈[ymin,ymax]）：
  bit0 左: x < xmin      bit1 右: x > xmax
  bit2 下: y < ymin      bit3 上: y > ymax
  完全在窗口内: outcode = 0000
​

两条线段各带一个 outcode，判断只需位运算：

LEFT, RIGHT, BOTTOM, TOP = 1, 2, 4, 8

def compute_outcode(x, y, xmin, ymin, xmax, ymax):
    code = 0
    if x < xmin: code |= LEFT
    elif x > xmax: code |= RIGHT
    if y < ymin: code |= BOTTOM
    elif y > ymax: code |= TOP
    return code

def cohen_sutherland_clip(p0, p1, box):
    # 返回裁剪后的两端点，或 None 表示完全不可见
    xmin, ymin, xmax, ymax = box
    x0, y0 = p0; x1, y1 = p1
    c0 = compute_outcode(x0, y0, xmin, ymin, xmax, ymax)
    c1 = compute_outcode(x1, y1, xmin, ymin, xmax, ymax)
    while True:
        if not (c0 | c1):            # 两端都在内：完全可见
            return (x0, y0), (x1, y1)
        if c0 & c1:                  # 同在某一外侧：完全不可见
            return None
        c = c0 if c0 else c1         # 挑窗外的一端处理
        if c & TOP:
            x = x0 + (x1-x0)*(ymax-y0)/(y1-y0); y = ymax
        elif c & BOTTOM:
            x = x0 + (x1-x0)*(ymin-y0)/(y1-y0); y = ymin
        elif c & RIGHT:
            y = y0 + (y1-y0)*(xmax-x0)/(x1-x0); x = xmax
        else:
            y = y0 + (y1-y0)*(xmin-x0)/(x1-x0); x = xmin
        if c == c0: x0, y0, c0 = x, y, compute_outcode(x, y, xmin, ymin, xmax, ymax)
        else:       x1, y1, c1 = x, y, compute_outcode(x, y, xmin, ymin, xmax, ymax)

print(cohen_sutherland_clip((-2, 1), (8, 5), (0, 0, 4, 4)))
# 输出: ((0.0, 2.0), (4.0, 4.0))  两端各被裁到左边界与上边界
​

算法循环最多四次（每轮至少把一个端点推入窗口或推出存在）。位运算快速分类是它的灵魂：c0 & c1 非零说明两端同侧窗外，一票否决；这在海量图元剔除时极其高效。

Liang-Barsky：让参数自己说话

另一条思路：把线段写成参数形式 P(t) = P0 + t(P1−P0)，t∈[0,1]。窗口四条边各是一个不等式约束，问题变成求满足全部约束的 t 区间：

对每条边的不等式统一写成：t·(p_k) ≤ q_k
  左边界:  -(dx) t ≤ x0 - xmin
  右边界:  ( dx) t ≤ xmax - x0
  下边界:  -(dy) t ≤ y0 - ymin
  上边界:  ( dy) t ≤ ymax - y0
​

def liang_barsky_clip(p0, p1, box):
    # 用参数区间 [t0,t1] 求可见段
    xmin, ymin, xmax, ymax = box
    x0, y0 = p0; x1, y1 = p1
    dx, dy = x1-x0, y1-y0
    t0, t1 = 0.0, 1.0
    for p, q in ((-dx, x0-xmin), (dx, xmax-x0), (-dy, y0-ymin), (dy, ymax-y0)):
        if p == 0 and q < 0:
            return None                     # 平行于边且在窗外
        r = q / p
        if p < 0:                           # 进入边界，抬 t0
            t0 = max(t0, r)
        elif p > 0:                         # 离开边界，压 t1
            t1 = min(t1, r)
    if t0 > t1:
        return None
    return ((x0+t0*dx, y0+t0*dy), (x0+t1*dx, y0+t1*dy))

print(liang_barsky_clip((-2, 1), (8, 5), (0, 0, 4, 4)))
# 输出: ((0.0, 2.0), (4.0, 4.0))  与 Cohen-Sutherland 结果一致
​

p<0 代表线段"正进入"该边内侧，抬下界；p>0 代表"将离开"，压上界。一次遍历同时完成快速剔除与精确求交，没有循环重试。

两种算法的取舍

我的偏好：批量剔除阶段用 outcode 预筛（几乎白送），真正需要交点的少数线段再交给 Liang-Barsky 求精。两者搭配，是工程里的常见组合。

三维的情形完全同构：窗口换成视锥体（或更便于硬件处理的规则包围盒），4 条边变 6 个面。第 4 章会看到，投影矩阵故意把可见区域扭成一个立方体，正是为了让裁剪从"算锥体交点"简化成"比较坐标绝对值是否小于 w"——硬件管线在齐次裁剪空间里做这件事，效率是设计出来的。

⚠️ 常见坑：裁剪顶点属性（颜色、纹理坐标）时，交点属性必须按同一参数 t 线性插值同步生成，只裁坐标不裁属性，纹理会在窗口边缘错位拉伸。

本节要点回顾

• 裁剪是守门员：既是防越界的正确性要求，也是剔除浪费的性能优化
• outcode 位运算快速分类：同侧一票否决，多数图元零成本出局
• 参数区间法一次到位：Liang-Barsky 把裁剪变成不等式组求交
• 两种算法互补：预筛用编码、求精用参数
• 属性要跟着 t 走：交点属性插值遗漏是纹理错位的常见根因

图元能画也能裁了，3.3 节给这套体系装上引擎：用矩阵把图形搬到任何位置。