The Scanline Sweeper: A Glyph Rendering Algorithm

TL;DR: 本文介绍一种在GPU着色器中实时渲染字形的新算法——扫描线扫描器，它基于字形曲线的分析表示进行连续覆盖率估计，在保留抗锯齿质量的同时降低内存占用，并支持任意缩放、旋转和透视变换。 ## 算法概览 该算法旨在解决传统文本渲染方法（如纹理采样、符号距离场和光线追踪）在内存、质量或通用性上的短板。它直接从字形的分析表示（二次贝塞尔曲线）出发，通过逐像素计算曲线扫描线覆盖率来生成抗锯齿字形，无需预先光栅化或高分辨率纹理。 预处理工作（曲线单调化、分割）在离线阶段完成，运行时只需在像素/计算着色器中执行简单的数学运算。 ## 预处理阶段 1. **将三次贝塞尔转换为二次贝塞尔** 现代字体（如TrueType）使用二次贝塞尔，而较新格式（如OpenType）使用三次贝塞尔。对于后者，算法将其分解为一个或多个二次贝塞尔近似，以确保所有曲线统一为二次形式。 2. **将线性段升级为二次贝塞尔** 轮廓中的直线段本质是一阶贝塞尔，为了简化着色器实现，它们被提升为二次贝塞尔（即控制点共线）。 3. **去除严格水平线段** 严格水平的线段对覆盖率计算无贡献，被舍弃。 4. **使所有曲线在X和Y方向上单调** 一条二次贝塞尔可能在X或Y方向上有拐点（极值点）。通过求解导数（二次方程），找到t值（在[0,1]内），将曲线在拐点处分割，使每个子段均为单调。这一步骤最多将一条曲线分成三段，确保后续扫描线计算简单高效。 ## 核心算法：扫描线扫描器 在每个像素内，定义一个矩形窗口（即像素的覆盖区域）。算法遍历预处理后的所有曲线段，仅处理与窗口相交的段。 ### 覆盖率计算 对于每条相交的曲线，将其方向（向上或向下）编码为对覆盖率的贡献符号： - **向上移动**的曲线：增加覆盖率（字形内部在右侧） - **向下移动**的曲线：减少覆盖率 然后，曲线沿水平方向“扫描”窗口：从曲线与窗口左边缘相交点开始，到右边缘（或曲线结束）为止，计算曲线下方（向上移动）或上方（向下移动）的面积，并基于窗口总面积计算覆盖率百分比。 扫描线边界由窗口上下边缘与曲线的交点确定。扫描过程逐步累积覆盖率，直到曲线结束。窗口最终的覆盖方向（正或负）决定了该像素是否被字形填充。 ### 举例说明 - **简单完全覆盖**：一条向上曲线覆盖整个窗口，贡献100%。 - **部分覆盖**：一条向上曲线在窗口中间结束，只覆盖一半面积。 - **抵消**：窗口位于字形外部，向上和向下曲线扫描相互抵消，最终覆盖率为0%。 - **复杂情况**：窗口同时与两条相反方向的曲线重叠，正确计算净覆盖率（如61%）。 算法重复该过程对所有像素，得到高质量抗锯齿字形。 ## 关键数学知识 - **二次贝塞尔求值**：`Q(t) = (1-t)^2 * A + 2(1-t)t * B + t^2 * C`，可写为标准二次形式。 - **拐点求解**：导数`Q'(t) = 0`给出X和Y方向的极值t值，用于曲线单调化。 - **曲线分割**：利用De Casteljau算法，求值过程中自然得到子曲线的控制点，无需额外计算。 - **交点计算**：单调曲线与水平/垂直线的交点可通过解二次方程高效获得，着色器中只需计算判别式并选取有效根。 ## 与其他方法的对比 | 方法 | 内存 | 质量 | 通用性 | |------|------|------|--------| | 纹理采样 | 高（需高分辨率纹理） | 依赖像素对齐 | 差（旋转/透视伪影） | | 符号距离场 | 较低（可复用低分辨率） | 边缘模糊，细节丢失 | 较好（支持变换，但内存限制字体范围） | | 光线追踪 | 低（仅需曲线数据） | 高 | 高（任意变换）但数值稳定性复杂 | | 扫描线扫描器 | 低（同光线追踪） | 高（连续覆盖率） | 高（直接分析渲染，支持极端透视） | ## 实现提示 所有预处理步骤在离线阶段完成，结果上传到GPU作为缓冲区。着色器中只需对每个像素窗口执行以下操作： - 遍历预处理后的曲线段列表 - 对每条相交曲线计算扫描线面积贡献 - 累加所有贡献，得出最终覆盖率 由于曲线已单调，交点计算可简化为二次方程求根；面积计算退化为梯形或三角形面积公式，十分高效。 --- Source：https://youtu.be/B9bztU1sTFA