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 performance reasons, some of these calculations can be cached for each line.
The fill algorithm described in this article is as follows:
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:
\(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}\)
\(\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}\)
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}\)
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}\)
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}\)
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}\)
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}\)
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\).
\(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\)
\(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\)
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.
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.
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.
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.