The Scanline Sweeper: A Glyph Rendering Algorithm [pdf]

The Scanline Sweeper: A Glyph Rendering Algorithm The Scanline Sweeper: A Glyph Rendering Algorithm Scuff3D Rook with Rook & Possum (v0.2) Abstract One fundamental building block of Bézier curve rasterization has historically been winding- number computation. Winding-number evaluation per-pixel or per-sample permits rasteri- zation on both the CPU and GPU, but presents implementation challenges due to the need for precise quadratic root-finding. Algorithm failures can result in large discrepancies in the computed coverage estimate for a pixel, and while solutions for these numerical failures exist, a different direction based on continuous coverage estimates is worth exploring. In this paper, I present the Scanline Sweeper, a distinct paradigm for Bézier curve raster- ization that estimates coverage analytically, without computing explicit winding numbers and without any tessellation. While the Scanline Sweeper uses quadratic root-finding, perturbations in the outcome only modestly perturb final coverage estimates, resulting in a numerically robust algorithm. Author’s disclaimer: This is a self-published preprint, not subject to a traditional peer-review, and not submitted to any academic journal. While the ideas here are original in the sense that I have not seen them elsewhere, my background is primarily in 3D graphics programming for AAA games, so it’s possible these ideas are already explored in an industry or domain unfamiliar to me. Errors will be corrected and amended versions will be posted as time permits. Citation: Scuff3D Rook, The Scanline Sweeper: A Glyph Rendering Algorithm, Rook & Possum, 2026. Rook & Possum 1/16 The Scanline Sweeper: A Glyph Rendering Algorithm 1. Introduction Rendering font glyphs in games and interactive applications predominantly relies on CPU rasteriza- tion. After rasterization is performed on the CPU, applications maintain a glyph cache to store texture fonts that are uploaded and sampled later on the GPU. Glyph cache maintenance is a tricky affair, since rasterization results can change based on glyph size and transform. Glyphs are expected to be positioned on pixel boundaries, and text anti-alias- ing artifacts are noticeable in UI engines that don’t snap glyphs to the pixel grid.

Rendering text in a 3D context with CPU-rasterized glyphs is impossible without objectionable aliasing artifacts, because the CPU rasterizer has no awareness of how the glyph will ultimately be projected on the display. To combat aliasing issues in 3D contexts, a pop- ular preprocessing step is to convert pre-rasterized glyphs into a signed-distance field (SDF) represen- tation. Sampling SDFs reduces aliasing by filtering distances on the GPU at sample time. However, the filtered result, while smooth, may no longer be an accurate representation of the original glyph shape. Multi-channel distance fields (MSDFs) combat this by reserving two additional channels of information to store distances to multiple edges, but even this technique cannot maintain accuracy when glyph shape complexity exceeds a certain threshold. Both SDF and MSDF representations increase the burden of glyph cache maintenance, due to the signed-dis- tance conversion requirement. More recently, it has become more popular to rasterize glyphs directly on the GPU from Bézier curve data. This approach is attractive for a few reasons: • A glyph cache is optional, and if maintained, cache entries are never invalidated due to changes in font size, DPI, or glyph transforms. • As with SVG images, Bézier rasterization is size and orientation-independent, and so is particu- larly suited for text rasterized in 3D. • Compared to signed-distance representations, Bézier rasterization preserves all sharp corners and edges at arbitrary levels of magnification. Bézier curve rasterization is the most versatile of the methods described so far, but pose several implementation challenges. Existing methods op- erate using the similar principles as CPU-based Bézier rasterizers. Namely, they operate by com- puting winding numbers for sub-pixel samples. Un- like CPU-based rasterizers, GPU-based rasterizers cannot leverage double-precision arithmetic units portably, nor is excessive Bézier curve subdivision practical on the GPU, so care is needed to properly handle singular events (e.g. curves starting from a sample point, curves tangent to a ray, curves passing through a sample point, etc.). Failures in correct winding number computation due to precision can cause a wide swing in the final result, with cata- strophic errors in the case of low sample counts.

1.1. Motivation The Scanline Sweeper was designed to retain all the benefits of GPU-based Bézier curve rasteriza- tion, but simplify implementation significantly by reducing the numerical-exactness burden. Similarly to existing Bézier curve rasterizers, the Scanline Sweeper operates on glyph curves directly on the GPU, but introduces a different paradigm for pixel coverage estimation. Instead of explicitly computing winding numbers for separate sub-pixel samples as a set of discrete events, the Scanline Sweeper integrates signed areas swept by each curve intersecting the scanline of interest. By remaining in a continuous domain as opposed to measuring discrete events, the sweeper sidesteps the issue of singular-event handling and numerical failure altogether. Implementation difficulty is, of course, subjec- tive, so I would like to remind the reader that the simplicity claimed in the approach described here is strictly in my own estimation. As this is the only algorithm I have implemented (in this family of GPU Bézier curve rasterizers), I also can’t make claims to how the performance of my approach compares to other approaches, except to say that at least on paper, I believe the Scanline Sweeper should certainly no worse, and likely better under various conditions. 2. Related Work The related work cited here is restricted to algo- rithms that permit a GPU-oriented implementation, specifically targeting games and other applications with similar interactivity requirements. In particu- lar, tessellation-based solutions which adaptively triangulate glyphs are not considered, in part be- Rook & Possum 2/16 The Scanline Sweeper: A Glyph Rendering Algorithm cause they impose impractical memory or runtime costs for games. 2.1. Texture fonts For traditional texture fonts, [Rougier 2013][1] pro- vides a useful survey of best-practices, including glyph-packing, texture quad placement, and gamma correction. In particular, Rougier suggests the usage of FreeType or STB’s TrueType rasterizer in con- junction with Harfbuzz or Pango to handle accurate glyph positions present in the GPOS subtable of an OpenType font file. Rougier argues that ahead-of- time rasterization is to be preferred as analytical- methods cannot reasonably respect font hinting and sub-pixel placement.

These recommendations bore more significant merit at the time (circa 2013) when low-resolution displays were far more prevalent, but may still be applicable for certain applications. 2.2. Signed-distance fonts As an extension to texture fonts, [Green 2007][2] uses a signed-distance representation to leverage hardware texture filtering units to anti-alias glyphs under minification, magnification, and perspective projections. The signed-distances sampled in the shader are used not only to fill in glyph outlines, but also to support various effects such as edge soften- ing, outlining, and drop-shadows. [Chlumský 2015][3] extends the previous SDF approach by storing signed distances to multiple edges in a multi-component SDF (MSDF). The MSDF is constructed such that the median of the three sampled distances in a shader recovers the closest edge. This method resolves situations of ambiguity in the single-channel SDF representation where the filtered distance is positive in regions of negative space near corners. 2.3. GPU Bézier Rasterizers [Dobbie 2016][4] introduces a vector texture which stores glyph curve data in a texture and performs root-finding to evaluate winding numbers for hor- izontal rays. To combat precision issues when horizontal rays intersect Bézier curves at glancing angles, [Dobbie 2016] suggests leveraging more rays per pixel and averaging the results, effectively com- bating precision issues with compute. Like [Dobbie 2016], [Lengyel 2017][5] leverages root-finding to render glyphs on the GPU from curve data embedded in textures. However, [Lengyel 2017] addresses precision problems by classifying Bézier curves into separate equivalence classes. For each class, the positive and negative roots are con- sidered differently to eliminate numerical failures endemic to the more straightforward root-finding approach. For example, several classes of curves may only increment the winding number, while other curves may only decrement the winding number, and so on. Anti-aliasing is proposed by super-sam- pling within each pixel in a cross-shape to reuse quadratic and linear coefficients in the quadratic solver, but the technique generalizes in the sense that the implementer is free to use any sample points needed.

Practitioners in the industry have implemented variations of this idea. Some useful references include [Osorio 2025][6] as well as [Lague 2024] [7]. Both citations mention difficulties encountered in tackling problems pertaining to floating-point precision, which while solvable with careful imple- mentation as demonstrated by [Lengyel 2017], is in large part what inspired this work. [Ellis et. al. 2019][8] propose an analytical quad- rature method to estimate pixel coverage, similar to this work. [Author’s note: this paper was commu- nicated to the author after the initial publication of this paper.] Area is estimated per-curve under a weak-perspective approximation which permits quadrature via x-aligned trapezoidal segments. To compute the sampling window, the authors derive a UV transformation that approximates rotation with shear in such a way that horizontal alignment is maintained. The authors also prescribe a method by which each trapezoid can be clipped to the sam- pled window. Compared to [Ellis et. al. 2019], the Scanline Sweeper avoids the need to clip against left-edges by relying on the Jordan Curve Theorem. Curve monotonicity is also leveraged in this algo- rithm to accelerate root finding and avoid needing to locate curve critical points. 3. Scanline Sweeper In the Scanline Sweeper, winding numbers do not play a role in the computation. Instead, each curve contributes a signed coverage estimate additively. Anti-aliasing is an implicit part of the algorithm, and as opposed to integrating the result across separate discrete sample points, the sweeper produces an anti-aliased result for a single rectangular window Rook & Possum 3/16 The Scanline Sweeper: A Glyph Rendering Algorithm of the glyph’s coordinate space. Linear combina- tions of these intermediate results may be combined to approximate a coverage estimate for more sophis- ticated footprints, but are not necessary for the algorithm to work. In this section, I’ll describe the algorithm in its most basic form to facilitate a perfectly serviceable initial implementation. Section 4 will touch on vari- ous ways to improve the performance and quality of the algorithm with only a modest amount of addi- tional effort.