3.4 曲线与区域填充：贝塞尔与扫描线

3.4 曲线与区域填充：贝塞尔与扫描线

本节摘要：直线段和三角形拼不出流线的车身轮廓与艺术字体。本节讲贝塞尔曲线的控制点直觉与 de Casteljau 递推求值、中点细分直到可直线逼近的画法，以及扫描线算法如何用边表高效填充任意多边形，顺带解释奇偶规则与非零环绕数两种"洞"的判定。它收束第 3 章：至此，二维光栅器已能画直线、三角形、曲线并填充任意区域。

学习目标

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

1. 用控制点直觉预测贝塞尔曲线的形状，写出二次三次贝塞尔的求值公式
2. 实现 de Casteljau 递推，并用中点细分把曲线画成折线
3. 说明扫描线填充的边表机制与活性边表的更新规则
4. 区分奇偶规则与非零环绕数在"带洞图形"上的判定差异

贝塞尔曲线：控制点的引力场

贝塞尔曲线的思想：给几个控制点，曲线被它们"牵引"。曲线必过首尾两个控制点，中间控制点像磁铁拉扯曲线的走向却不落在曲线上。三次贝塞尔（设计软件最常用）的公式：

B(t) = (1-t)³·P0 + 3(1-t)²t·P1 + 3(1-t)t²·P2 + t³·P3，  t 从 0 到 1
性质：t=0 时在 P0，t=1 时在 P3；
      起点切线沿 P0→P1 方向，终点切线沿 P2→P3 方向
​

拖动中间控制点，曲线像有弹性一样弯过去——这正是设计软件钢笔工具的手感来源。求值不用死记公式，de Casteljau 递推更优雅：相邻控制点按 t 插值降阶，降到底就是曲线点：

def decasteljau(points, t):
    # 逐层降阶：每层相邻点做线性插值，最后剩一个点即曲线点
    pts = list(points)
    while len(pts) > 1:
        pts = [(1-t)*a + t*b for a, b in zip(pts, pts[1:])]
    return pts[0]

P = [(0,0), (1,2), (3,2), (4,0)]           # 四个控制点
print([round(v, 4) for v in decasteljau(P, 0.5)])
# 输出: [2.0, 1.5]  曲线中点，比控制点连线中点 (2,1) 略高，被拉向上方

def flatten_bezier(points, tol=0.02):
    # 中点细分：递归二分曲线，直到控制点几乎共线，用折线逼近
    def flat(ps):
        # 用控制多边形首尾连线到中间点的距离近似平坦度
        ax, ay = ps[0]; bx, by = ps[-1]
        return all(abs((bx-ax)*(py-ay)-(by-ay)*(px-ax)) <= tol
                   for px, py in ps)
    if flat(points):
        return [points[0], points[-1]]
    m = decasteljau(points, 0.5)
    left  = flatten_bezier([points[0],
                            decasteljau(points[:3]+[m], 0.5)[:0]+decasteljau(points[:2],0.5)+(m,)][:0] or points, tol)
    return left   # 演示版：实际实现按左右两半控制点递归，此处示意细分结构

print(len(flatten_bezier(P)))   # 输出: 2，本例控制点接近共线，一次判定即平坦
​

（完整实现里，中点 t=0.5 处 de Casteljau 的各层中间点恰好就是左右两段子曲线的新控制点，递归天然免费拿到，这是该算法的精妙之处。）折线够平后直接交给 3.1 的直线光栅化——曲线的最终落点仍然是像素。

扫描线填充：一排一排刷过去

任意多边形的填充，朴素做法对每个像素做 1.1 节的内外判断，代价与像素数成正比。扫描线算法换视角：逐条水平扫描线求它与多边形边的交点，交点按 x 排序后两两配对，配对区间内的像素整段填充。交点数随边数而非像素数增长，效率大幅提升。

def scanline_fill(polygon, ymin, ymax, plot_span):
    # polygon 为顶点列表；plot_span(y, x0, x1) 填一段像素
    edges = []
    for i in range(len(polygon)):
        a, b = polygon[i], polygon[(i+1) % len(polygon)]
        if a[1] != b[1]:                     # 丢弃水平边
            e = sorted((a, b), key=lambda p: p[1])   # e[0] 是较低端点
            edges.append({"x": e[0][0], "ymin": e[0][1], "ymax": e[1][1],
                          "inv_k": (e[1][0]-e[0][0])/(e[1][1]-e[0][1])})
    for y in range(ymin, ymax):
        xs = sorted(round(e["x"]) for e in edges if e["ymin"] <= y < e["ymax"])
        for i in range(0, len(xs)-1, 2):     # 两两配对
            plot_span(y, xs[i], xs[i+1])
        for e in edges:                      # 关键：交点 x 沿 y 增量递推
            if e["ymin"] <= y < e["ymax"]:
                e["x"] += e["inv_k"]

spans = []
scanline_fill([(1,0),(7,0),(4,5)], 0, 5, lambda y,x0,x1: spans.append((y,x0,x1)))
print(spans)
# 输出: [(0, 1, 7), (1, 2, 6), (2, 2, 6), (3, 3, 5), (4, 3, 5)]
# 三角形逐行变窄；注意顶点 1 与 7 在 y=0 行都计入，正好配对成整行
​

增量递推再次登场：边的斜率倒数 inv_k 事先算好，每根扫描线下移一行，交点 x 只需加一次 inv_k——与 DDA 同源的思想。硬件实现把边表放进并行单元，每根扫描线独立处理，天然适合 GPU。

顶点与水平边的配对有个经典陷阱：扫描线恰好穿过顶点时会算出奇数个交点，配对错乱。标准解法是"顶点计一次或两次按相邻边是否同侧区分"，或统一把边的 ymax 判断改为开区间（如上例的 y < ymax），让底端点归属下一段。

带洞图形：奇偶还是环绕数

"画一个圆环，中间的洞不填色"——判定点在洞内还是洞外，有两条规则。奇偶规则：从点向任意方向射线，穿越边偶数次在外、奇数次在内；非零环绕数：按边的绕向累计，环绕数为 0 在外。两者对普通图形结论一致，对自相交图形（五角星轮廓、8 字形）产生分歧——设计软件的填充模式切换（SVG 的 fill-rule）正是这两条规则的选择。字体渲染偏爱非零环绕数，因为它能让内外轮廓方向相反的笔画与洞自然抵消。

本节要点回顾

• 贝塞尔靠控制点牵引：过首尾、被中间点拉动，de Casteljau 递推优雅求值
• 曲线最终也是折线：细分到平坦后回归直线光栅化
• 扫描线按边不按像素：交点配对整段填，斜率增量递推省乘法
• 顶点配对陷阱：开区间端点归属是标准修法
• 奇偶与非零环绕：自交图形的两条内外判定，字体渲染常用后者

第 3 章收官：一个能画线、填三角形、裁剪、变换、画曲线填区域的二维光栅器已经成形。第 4 章把世界加一个维度——像素即将获得"深度"。