⊕ Code: LuxxxLucy/seiler-interpolation-experiments ⊕ Note that this is the third blog in the Bezielogue series on Bezier curves. Previous ones:
1. Bezielogue 1 cubic fitting
2. Bezielogue 2 split and merge.

TL;DR We introduce Seiler interpolation, a relatively new way for evaluating curves. Compared to the usual algorithm, Seiler interpolation uses half the number of linear interpolations (lerps) with the precomputed Seiler Points. This brings optimization opportunities, as we show in the later part of the post, that with it we can easily make the fastest glyph rasterizer. This comes with caveats, by fastest I mean it beats the main competitor fontdue, the current fastest glyph rasterizer. As shown later in the post, the experimental superraster rasterizer tackles only curve evaluation, part of the entire rasterization process and is far from being a complete implementation, and other than curve evaluation using Seiler interpolation, we have a large gap (as well as optimization opportunities) to fill. See more in discussion and future steps.I will dedicate another blog for that while keeping this post mainly about the Seiler interpolation. Stay tuned.

TOC:

1. We will start with the usual Bernstein parameterization using de Casteljau and then introduce the Seiler Interpolation, the main point is that it uses fewer linear interpolations (lerps) with pre-computed Seiler Points. It reduces the number of lerps from 6 to 3 and evaluation depths from 3 to 2.
2. Seiler Interpolation within the context of commonly used font glyph formats.
3. Breakdown of the computation
4. Making a glyph rasterizer, superraster, and how much faster it is than fontdue.
5. Discussion and future steps.

Introduction & Background

A cubic Bezier curve is defined by four control points :

(1)

We will also refer to it as the Bernstein parameterization as it uses Bernstein polynomials as the blending functions mapping into a point on the curve. ⊕ Paul de Casteljau, Citroen, 1959.

(2)

In the previous post Bezielogue 2: split and merge, we introduced how to use de Casteljau’s algorithm to split a curve at (see Figure 1). Evaluating a point is essentially the same procedure. In order to evaluate the point at , we will need to do 6 lerps. A linear interpolation (lerp) between two points and at parameter is defined as

Each step takes neighbouring points of the previous step and interpolates between them at the same . Note that the depth of the computation is 3, that is we cannot parallelize all 6 lerps; we can do at least by 3 sequential steps even with parallelism, we will need to evaluate and then and finally .

In 2020, Larry Seiler Lin, Seiler and Yuksel, Hardware Adaptive High-Order Interpolation for Real-Time Graphics, HPG 2021. came up with the idea that we can perform the same evaluation with only 3 lerps if we are allowed to precompute two auxiliary points. Cem Yuksel Cem Yuksel, Seiler’s Interpolation for Evaluating Polynomial Curves, SIGGRAPH 2024 Talks. presented a SIGGRAPH talk in 2024 and coined it Seiler’s interpolation. Recently this year (2026), Anas and Wolfe Anas and Wolfe, A Texture Lookup Approach to Bezier Curve Evaluation on the GPU, 2026. showed that these three lerps can be done by a GPU texture unit when it filters a 2 by 2 texture, so the whole evaluation collapses into one texture read in GPU. Though for this blog, we are scoped to mainly focus on the CPU side of things.

Here we introduce the idea of Seiler interpolation.

Seiler Interpolation: formulation

Seiler Interpolation is an idea that given the original parameterization , we can use 2 precomputed Seiler points to get as the new parameterization for evaluating the curve. (See Figure 2). From now on we start introducing the formulation as well as showcasing that this is just a change of basis and thus is analytically equivalent.

The idea of Seiler interpolation starts with an observation. Given the Bernstein parameterization we can first connect and and draw the point of .

We can subtract the from Equation 1, and get :

(3)

⊕ The end terms factor because and . Every term then carries the factor , as the two roots promised.

We observe becomes a cubic polynomial in with roots at and .

We denote , so

is linear w.r.t , in other words is a linear function of .

(4)

and we then can represent .

Putting the pieces back together,

(5)

and so

(6)

To further simplify it, note that holds for any weight , so with , and , we have

We can further simplify the second argument of the lerp as:

We here arrived at the two Seiler points, denote and we have:

(7)

Assume the two Seiler points are available, the curve now can be represented as , we now can evaluate the curve using only 3 lerps at depth of 2.

(8)

We can make sure that this evaluation is analytically correct, with sympy for symbolic checking:

from sympy import symbols, expand
t, p0, p1, p2, p3 = symbols("t p0 p1 p2 p3")
u = 1 - t
lerp = lambda a, b, w: (1 - w) * a + w * b
bezier = u**3*p0 + 3*u**2*t*p1 + 3*u*t**2*p2 + t**3*p3
s1, s2 = 3*p1 - p0 - p3, 3*p2 - p0 - p3
seiler = lerp(lerp(p0, p3, t), lerp(s1, s2, t), u*t)
print(expand(bezier - seiler))  # 0

⊕ There is a different formulation that has the same shape of 3 lerps but fewer multiplies from Yuksel: First compute the offset points and , then . Significance: precomputing is cheap as we will pay the cost of loading/parsing the curve from disk format anyway, and saving the lerps from 6 to 3 and the depth from 3 to 2 has a massive implication in the evaluation, the depth reduction is the basic we can do, so computation-wise, that alone by theory would roughly give us performance boost. (but of course that is to say the end to end performance would be like that as the evaluation is not the entire computation, say, for the entire rasterization process)

Moving to higher degrees

The same idea can be pushed further to higher degrees. For a curve of degree , ⊕ Yuksel gives closed-form difference terms up to degree 5.

In general Seiler’s interpolation enables us to evaluate with lerps for degree , out of which are independent and can be parallelized.

Compared to that, for de Casteljau, lerps are needed.

Curves in a font file

Even though we started our formulation with , the Bernstein parameterization, it would be unsurprising if I told you that in real fonts the data is not organized nicely as that cubic parameterization.

In order to save file size, while a font is compiled, it instead mainly stores the point coordinates without repetition with minimal info to determine the Bezier curve and leaves the “implied” points not being stored in the data.

We discuss two main formats: TrueType glyf and OpenType CFF.

TrueType glyf format In TrueType, a glyph is stored as a glyf entry in a data table. Its form is

1. a list of contours
2. a contour is a list of points with for the two-dimension coordinate deltas (position relative to the previous point) and an on flag indicating it is a control point (off the curve) or not (on the curve).

⊕ OpenType spec, glyf table, simple glyph description: “Bit 0: If set, the point is on the curve; otherwise, it is off the curve.” Coordinates stored are int16 or uint8 deltas “relative to previous point”.

The rule is simple: an off point between two on points is the middle control point of a quadratic, two consecutive on points make a straight line, and two off points imply an on point at their midpoint. Apple, TrueType Reference Manual, chapter 1: the tangency point “is not strictly needed to define the curve because its existence [is] implied and its location can be reconstructed from the data given by the other points.”

The implied point is a deliberate choice and heavily used for further compacting the size. For example, the a letter in Roboto Regular has two contours with 20 on points, 21 off points, and 9 implied points. Throughout the 567 simple glyphs, Roboto Regular has 8,591 on points and 5,321 off points, and 2,541 of the off points are followed by another off point, so about half of the quadratic endpoints are implied and never explicitly defined in the raw data we read from disk.

OpenType CFF format An OpenType CFF table chooses to store each glyph as a Type 2 charstring defined with a small domain specific language (DSL): rmoveto, rlineto, rrcurveto, and shorthand forms such as hvcurveto. Adobe, The Type 2 Charstring Format, Technical Note 5177.

One thing about CFF is that in CFF all curves are by default cubic. In Exo2 Regular, the CFF entry draws letter a with 10 cubics and 10 lines, letter o with 8 cubics.

A font parser such as ttf-parser would read data of those formats and turn them into a unified intermediate format with four operations: move, line, quadratic, cubic, with absolute coordinates. This is what most rasterizers consume as input. ⊕ Though the rasterizer superraster we wrote skips that step, as we can get the end and Seiler points directly from the stored deltas.

Opportunities

Now we start thinking about what this reduced number of lerps and reduced depth, offered by Seiler interpolation, implies for a new rasterizer implementation that is faster.

First, the basic correctness criteria is not broken. As in the new Seiler formulation, the curve parameterization simply changes a basis without loss. So the new parameterization carries the same information as , evaluates the same curve and takes the same memory.

Second, the depth of the pipeline that must be sequentially executed drops from 3 to 2.

Third, the two inner lerps do not depend on each other, so inside each depth step, we can parallelize this computation. Using SIMD, we can take and to produce both and in one instruction.

Fourth, we can further scale up by batching for . Evaluating a curve requires evaluating at many values of . These are additional opportunities we can take with parallelism. The rasterizer superraster is built on this.

Breakdown the computation

Now let us break down the computation in finer grain detail.

Computation per point

For evaluating one point on a Cubic Bezier, the computation of different evaluation method can be broken down as: ⊕ Credit: this is inspired by Yuksel’s work and methodology that counts multiplies and adds for each method in dimensions. ⊕ Horner’s form: with precomputed from the control points. Three fused multiply-adds per dimension.

If we are using an idealistic sequential tape-based Turing machine, the simplest polynomial form would win at fewest count of ops, followed by Seiler’s interpolation, and then de Casteljau would be the worst.

But Seiler interpolation provides opportunities for parallelism as well as less depth of sequential steps.

Making a glyph rasterizer superraster

Rasterizing a glyph means turning an outline of Bezier segments into a small anti-aliased coverage mask. Here we look at three rasterizers that get used for text: Skia’s scan converter, FreeType’s smooth rasterizer, and fontdue. ⊕ Skia: src/core/SkEdge.cpp
FreeType: src/smooth/ftgrays.c
fontdue: src/math.rs and src/raster.rs.

Skia converts each cubic edge to polynomial form and walks it by forward differencing in fixed point. The number of steps is with chosen from how far each inner control point sits from the curve at and , capped at 64 steps.

FreeType keeps the cubic in Bezier form and splits it at with de Casteljau, which at the midpoint is only adds and shifts (12 adds, 10 shifts per split in 2D). It splits until a flatness test passes, then draws the chord.

fontdue first flattens every curve once, at font load time, at a reference size of 40 pixels, into a list of line segments with their per-line constants (nudges, , ) packed into 128-bit SIMD registers. Rasterizing at any size later is a scale and offset of the stored lines followed by a signed-area accumulation into a float buffer and one prefix-sum pass. Lines are sorted into vertical lines and general lines so that the vertical ones take a cheaper loop in the sweep line algorithm.

In these methods, curve evaluation is at most 5 to 10 percent of the computation. My rough guess, have not really profiled that. If we just replace that tiny evaluation of curve in these methods with Seiler interpolation, it would gain us nothing.

So my decision is to make it rather a new approach and do with a simple and almost brute algorithm. Instead of all those algorithms, I opt for a simple algorithm that just evaluates at arbitrary to a precision that is acceptable and accurate. ⊕ This is a rather brutal idea. The prototype superraster is just 4 to 5 hundred lines of code.

We just load the font with the segments, and for each segment, we run evaluations with SIMD and produce the edges of contours. For each edge we add its signed area to a float buffer per pixel just like the scheme of font-rs and fontdue. And then we turn the areas into coverage by a running sum along the buffer.

We use the same benchmark as fontdue with its two listed Exo2 fonts (one in TrueType and one in CFF) and “Sphinx of black quartz, judge my vow.” as the text to render under default size of 40 pixels. ⊕ We set accuracy tolerance 0.035 px, so that the mean error is at or below fontdue’s error.

The main results. At the same size as fontdue, superraster is 1.35 to 1.4 times faster than fontdue, at a third of its error. And as the size increases, superraster would become even faster.

The gap also grows with the pixel size (Figure 5). Note that the time axis is log-scaled. At 200 px this is about 2 times faster than fontdue.

We are also getting less error than fontdue (Figure 6).

Discussion and future steps

We here in this post introduced the Seiler Interpolation and initial prototypes using that to make a fast rasterizer.

Seiler interpolation provides us with 3 lerps against 6 and depth 2 against 3, but rasterizer is in fact much more than curve evaluation. There are other parts of rasterization aside from evaluation that are very important in the end to end performance.

We do show that a straight implementation using Seiler interpolation can make evaluation very cheap, making it able to drop the load-time cache and still being able to be faster.

There are however, some other aspects we can look at:

Performance

Rasterization is more than curve evaluation, and careful implementation and algorithm is needed for the rest part of the rasterization process.

Nowadays we are having increasingly multi-core systems and with strong capabilities from the CPU. Most of the algorithms in rasterization were invented a long time ago where single thread simple code was the main paradigm. It is therefore perhaps time to not just focus on what we can do on curve evaluation, but rather taking a more pragmatic look at what the modern hardware can offer and how we can introduce algorithms and implementations that are more suited on modern hardware.

We could in principle provide a more profile and trace-based analysis of the entire procedure and start from there.

Maybe this is also a good opportunity for the Bitter Lesson Rich Sutton, The Bitter Lesson, 2019. pilled review of the methods.

Memory

Although we talked so far exclusively about computation, in modern systems, the data fetching from disk and memory would be much more important as that introduces real cost with a large constant. But luckily for Seiler interpolation we do not add any more data in terms of bytes we need to load. So we at least did not introduce any penalties.

It is better to derive implementations that we would do less of data fetching and do more work per data fetching.

Different formulation

The idea of Seiler interpolation in the end is simply a term-rewriting process and find that a particular variant of the formulation exposes better properties computationally.

Given all we have in modern term rewriting systems, such as e-graph and egg, it is perhaps possible to provide a real search over the possible variants and figure out the best ones.

Aside from Cubic, the font file format naturally provides a more high-degree version of curves, in these higher-degree cases, a more efficient way to evaluate curves might turn out to provide more potential performance boost.

Numeric accuracy and adaptive evaluation

which is also a very practical concern for curve evaluation in the rasterization process.

The case for GPU

The advancement from Seiler interpolation is more prominent in the context of GPU.

On a GPU all the computation breakdowns are different, because there is a piece of hardware texture unit that does lerps for free: It takes a coordinate, reads the neighbouring texels, and returns their bilinear (or trilinear) blend outside the shader core. Seiler’s three lerps are exactly a bilinear blend, so one texture read would just automatically do that for us. Anas and Wolfe, A Texture Lookup Approach to Bézier Curve Evaluation on the GPU, Journal of Computer Graphics Techniques, vol. 15, no. 2, 2026. Preprint: arXiv:2603.15447. This is implemented in a consumer GPU and gets quite good results for the curve evaluation running on top of millions of points. And this comes in a way like we can the computation (multiply-add) for free.

Rasterizer

As mentioned early, the rasterizer is merely a prototype, I will work on this with another dedicated post.