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

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.

• 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 Bézier curves

The polynomial forms of Bézier 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}$$

$$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}$$

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$$

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