The Scanline Sweeper: A Glyph Rendering Algorithm

**TL;DR:** This article introduces a new algorithm for real-time glyph rendering in GPU shaders — the Scanline Scanner. It performs continuous coverage estimation based on the analytic representation of glyph curves, reducing memory usage while preserving anti-aliasing quality, and supports arbitrary scaling, rotation, and perspective transformations. ## Algorithm Overview This algorithm aims to address the shortcomings of traditional text rendering methods (such as texture sampling, signed distance fields, and ray tracing) in terms of memory, quality, or versatility. It starts directly from the analytic representation of glyphs (quadratic Bézier curves) and generates anti-aliased glyphs by calculating per-pixel curve scanline coverage, without the need for pre-rasterization or high-resolution textures. Preprocessing steps (curve monotonicization, splitting) are performed offline. At runtime, only simple mathematical operations are executed in pixel/compute shaders. ## Preprocessing Stage 1. **Convert Cubic Bézier to Quadratic Bézier** Modern fonts (e.g., TrueType) use quadratic Bézier curves, while newer formats (e.g., OpenType) use cubic Bézier curves. For the latter, the algorithm decomposes them into one or more quadratic Bézier approximations to ensure all curves are unified into quadratic form. 2. **Upgrade Line Segments to Quadratic Bézier** Straight line segments in contours are essentially first-order Bézier curves. To simplify shader implementation, they are promoted to quadratic Bézier curves (i.e., control points are collinear). 3. **Remove Strictly Horizontal Line Segments** Strictly horizontal line segments do not contribute to coverage calculation and are discarded. 4. **Make All Curves Monotonic in X and Y** A quadratic Bézier curve may have inflection points (extrema) in the X or Y direction. By solving the derivative (quadratic equation), the t values (within [0,1]) are found to split the curve at the inflection points, making each sub-segment monotonic. This step splits a curve into at most three segments, ensuring simple and efficient subsequent scanline calculations. ## Core Algorithm: Scanline Scanner Within each pixel, a rectangular window (i.e., the pixel's coverage area) is defined. The algorithm iterates through all preprocessed curve segments, processing only those that intersect the window. ### Coverage Calculation For each intersecting curve, its direction (upward or downward) is encoded as a contribution sign to the coverage: - **Upward-moving curves**: Increase coverage (glyph interior is to the right) - **Downward-moving curves**: Decrease coverage The curve then "scans" the window horizontally: starting from the intersection point of the curve with the left edge of the window, up to the right edge (or the end of the curve), the area below the curve (for upward) or above the curve (for downward) is calculated. The coverage percentage is then computed based on the total window area. The scanline boundaries are determined by the intersection points of the window's top and bottom edges with the curve. The scanning process accumulates coverage until the curve ends. The final coverage direction (positive or negative) of the window determines whether the pixel is filled by the glyph. ### Examples - **Simple Full Coverage**: An upward curve covers the entire window, contributing 100%. - **Partial Coverage**: An upward curve ends in the middle of the window, covering only half the area. - **Cancellation**: The window is outside the glyph; upward and downward curve scans cancel each other out, resulting in 0% coverage. - **Complex Case**: The window overlaps with two curves of opposite directions simultaneously, correctly calculating the net coverage (e.g., 61%). The algorithm repeats this process for all pixels, producing high-quality anti-aliased glyphs. ## Key Mathematical Knowledge - **Quadratic Bézier Evaluation**: `Q(t) = (1-t)^2 * A + 2(1-t)t * B + t^2 * C`, expressible as a standard quadratic form. - **Solving for Inflection Points**: The derivative `Q'(t) = 0` yields t values for extrema in X and Y directions, used for curve monotonicization. - **Curve Splitting**: Using De Casteljau's algorithm, evaluating the curve naturally yields the control points of the sub-curves without additional computation. - **Intersection Calculation**: Computing intersections between monotonic curves and horizontal/vertical lines can be efficiently done by solving a quadratic equation; the shader only needs to compute the discriminant and select the valid root. ## Comparison with Other Methods | Method | Memory | Quality | Versatility | |--------|--------|---------|-------------| | Texture Sampling | High (requires high-res textures) | Depends on pixel alignment | Poor (rotation/perspective artifacts) | | Signed Distance Field | Lower (can reuse low-res) | Blurry edges, detail loss | Better (supports transformations, but memory limits font scope) | | Ray Tracing | Low (only curve data needed) | High | High (arbitrary transformations) but numerically complex | | Scanline Scanner | Low (same as ray tracing) | High (continuous coverage) | High (direct analytic rendering, supports extreme perspective) | ## Implementation Tips All preprocessing steps are performed offline, and the results are uploaded to the GPU as buffers. The shader only needs to perform the following for each pixel window: - Iterate through the list of preprocessed curve segments - For each intersecting curve, calculate the scanline area contribution - Accumulate all contributions to obtain the final coverage Since curves are monotonic, intersection calculations can be simplified to solving quadratic equations; area calculations reduce to trapezoid or triangle area formulas, which is very efficient. --- Source: https://youtu.be/B9bztU1sTFA