# 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 each pixel, cast a ray horizontally to the left into infinity.
- Count how many times the ray intersects with each Bézier curve in the path.
- Make the pixel opaque when the count is odd; transparent when even.

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:

- For each line, collect all \(x\) positions where the line intersects with each Bézier
curve in the path.
- Sort the list of collected \(x\) position ascending by value.
- Split the list of sorted \(x\) positions into pairs.
- For each pair make the pixels opaque between two \(x\) values; leave the other
pixels transparent.

## 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:

- \(P_{1}\) and \(P_{2}\) are the coordinates of the start and stop
points of a Bézier curve.
- \(C\) is the coordinate of the control point of a
quadratic Bézier curve.
\(C_{1}\) and \(C_{2}\) are the coordinates of the first and second
control points of a cubic Bézier curve.
- \(t\) is a value between 0.0 and 1.0, a distance between point \(P_{1}\)
and point \(P_{2}\) respectively on the Bézier curve. A value of \(t\)
below 0.0 or above 1.0 extrapolates the curve smoothly.
- \(B(t)\) is the coordinate of a point on the Bézier curve at the distance \(t\).

### 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.