Filling closed Bézier paths

Take Vos
2019-10-02

In TTauri I am using the same path drawing algorithm for drawing general shapes and for drawing text. TrueType fonts use quadratic Bézier curves to create closed paths. OpenType may also use cubic Bézier curves. The algorithm discussed below makes it possible to quickly fill in closed paths.

Traditional fill algorithm

Traditionally the following algorithm is used for filling a closed Bézier path:

For performance reasons, some of these calculations can be cached for each line.

The fill algorithm described in this article

The fill algorithm described in this article is as follows:

Polynomial forms of Bezier curves

The polynomial forms of Bezier curves are useful because we can solve polynomial formulas relatively easily.

Here are the descriptions of the variables used in the formulas below:

Linear Bézier curve (line)

\(B(t)=(P_{2}-P_{1})t+P_{1}\)

Quadratic Bézier curve

\(B(t)=(P_{1}-2C+P_{2})t^{2}+2(C-P_{1})t+P_{1}\)

Cubic Bézier curve:

\(\begin{align} B(t) & = (-P_{1}+3C_{1}-3C_{2}+P_{2})t^{3}\\ & + (3P_{1}-6C_{1}+3C_{2})t^{2}\\ & + (-3P_{1}+3C_{1})t\\ & + P_{1}\\ \end{align}\)

Solving Polynomial functions

Linear

We can solve \(x\) for \(ax + b = 0\) by using the following function:

\(\operatorname{solveLinear}(a,b) = \begin{cases} \frac{-b}{a}, & \text{if } a\ne0\\ \in\mathbb{R}, & \text{if } a=0,b=0\\ \varnothing & \text{if } a=0,b\ne0\\ \end{cases}\)

Quadratic

We can solve \(x\) for \(ax^{2} + bx + c = 0\) by using the following function:

\(D = b^{2} - 4ac\)

\(\operatorname{solveQuadratic}(a,b,c) = \begin{cases} \frac{-b}{2a}, & \text{if } D = 0\\ \frac{-b - \sqrt{D}}{2a}, \frac{-b + \sqrt{D}}{2a} & \text{if } D > 0\\ \varnothing & \text{if } D < 0\\ \end{cases}\)

Cubic

To solve \(x\) for \(ax^{3} + bx^{2} + cx + d = 0\) we first need to convert the problem to a depressed cubic form \(w^{3} + pw + q = 0\). The depressed cubic form is much easier to deal with since the cubic component has no multiplier and there is no quadratic component.

\(p = \frac{3ac - b^{2}}{3a^{2}}\)

\(q = \frac{2b^{3} - 9abc + 27a^{2}d}{27a^{3}}\)

\(\operatorname{solveCubic}(a,b,c,d) = \operatorname{solveDepressedCubic}(p,q) - \frac{b}{3a}\)

Solve cubic function using the depressed cubic form

We can solve \(w\) for \(w^{3} + pw + q = 0\) using the following algorithm:

\(D = \frac{q^{2}}{4} + \frac{p^{3}}{27}\)

\(\begin{align} & \operatorname{solveDepressedCubic}(p,q) = \\ & \hspace{4em} \begin{cases} 0 & \text{if } p=0 \land q=0\\ \frac{3q}{p}, -\frac{3q}{2p} & \text{if } D=0 \land p \neq 0\\ \operatorname{solveCubicTrig}(p, q) & \text{if } D<0 \land p \neq 0\\ \operatorname{solveCubicCardano}(D) & \text{else} \end{cases}\end{align}\)

Solve value with Cardano

We solve a depressed cubic function using Cardano. We only use it to calculate only a single result, but technically we can use Cardano to return three results when using complex numbers.

\(\begin{align} \operatorname{solveCubicCardano}(D) = & \sqrt[3]{-\frac{1}{2}+\sqrt{D}}\\ + & \sqrt[3]{-\frac{1}{2}-\sqrt{D}}\\ \end{align}\)

Solve with trigonometry

When we need to return three results we solve a depressed cubic function using trigonometry because it is easier and faster than using Cardano with complex numbers.

\(U = \frac{1}{3}\arccos{(\frac{3q}{2p} \cdot \sqrt{-\frac{3}{p}})}\)

\(V = 2\sqrt{-\frac{1}{3}p}\)

\(\begin{align} \operatorname{solveCubicTrig}(p, q) = & V\cdot \cos{(U)},\\ & V\cdot\cos{(U-\frac{2}{3}\pi)},\\ & V\cdot\cos{(U-\frac{4}{3}\pi)}\\ \end{align}\)

Find intersections of a horizontal line with a Bézier curve

To to find the intersections of a horizontal line with a Bézier curve we need to first solve all \(t_{i}\) of the curve's polynomial form.

We can use the \(\operatorname{solve*}\) functions above. By filling in the \(y\) part of each (control-) point, and subtracting the line's \(y\) from the last component.

We can then fill in the curve's polynomial form with the \(x\) part of each (control-) point and the set of \(t_{i}\) results from the \(\operatorname{solve*}\) functions; when \(0 \leq t_{i} \leq 1\).

Linear

\(a = P_{2} - P_{1}\)

\(b = P_{1}\)

\(t_{1} = \operatorname{solveLinear}(a_{y}, b_{y} - y)\)

\(x_{i} = a_{x}t_{i} + b_{x} \hspace{4em} \text{when } 0 \leq t_{i} \leq 1\)

Quadratic

\(a = P_{1} - 2C + P_{2}\)

\(b = 2(C - P_{1})\)

\(c = P_{1}\)

\(t_{1}, t_{2} = \operatorname{solveQuadratic}(a_{y}, b_{y}, c_{y} - y)\)

\(x_{i} = a_{x}t_{i}^{2} + b_{x}t_{i} + c_{x} \hspace{4em} \text{when } 0 \leq t_{i} \leq 1\)

Cubic

\(a = -P_{1} + 3C_{1} - 3C_{2} + P_{2}\)

\(b = 3P_{1} - 6C_{1} + 3C_{2}\)

\(c = -3P_{1} + 3C_{1}\)

\(d = P_{1}\)

\(t_{1}, t_{2}, t_{3} = \operatorname{solveCubic}(a_{y}, b_{y}, c_{y}, d_{y} - y)\)

\(x_{i} = a_{x}t_{i}^{3} + b_{x}t_{i}^{2} + c_{x}t_{i} + d_{x} \hspace{4em} \text{when } 0 \leq t_{i} \leq 1\)

Observations

Horizontal Lines

Solving a horizontal line will result in an infinite number of \(t\) values. Only the start \(x_{t=0}\) and end \(x_{t=1}\) are needed since we are rendering horizontal spans that will match the horizontal line.

Horizontal line matches endpoint

In a closed path, the endpoint of one curve will be the start point of the next curve. When the line matches the height of such a start-/endpoint combination would therefor yield two equal results, even though for the complete path it should be a single point.

One way to solve this is to use only the half-open range \(0 \leq t < 1\) of each Bézier path.

Another way to solve this is by ignoring duplicate results.

Numerical instability

Compounding the above problems is numeric instability in the calculations. It may be best to use the computational cheapest methods to solve the above issues and when the total number of \(x\) results is odd to retry with a slightly different \(y\) value. Combined with supersampling over they y-axis this should reduce visual artifacts.

Antialiasing

The algorithm returns pixel-fractional spans. This makes it possible to accurately calculate pixel coverage on the x-axis. This means we only need to super-sample over the y-axis for anti-aliasing.