Fast calculation of the distance to cubic Bezier curves on the GPU

Summary

Bézier curves are a core building block of text and 2D shapes rendering. There are several approaches to rendering them, but one especially challenging problem, both mathematically and technically, is computing the distance to a Bézier curve. For quadratic curves (one control point), this is fairly accessible, but for cubic (two control points) we're going to see why it is so hard. A glyph from the Virgil font, composed of multiple Bézier curves Having this distance field opens up many rendering possibilities. It's hard, but it's possible; here is a live proof: Distance to a cubic Bézier curve In this visualization, I'm borrowing your device resources to compute the distance to the curve for every single pixel. The yellow points are the control points of the curve (in white) and the blue zone is a representation of the distance field. Note All the demos and code in this article are self-contained GLSL fragment shaders. Most of the code can be found in the article, but feel free to inspect the source code of any of these WebGL demo for the complete code. They can be run verbatim using ShaderWorkshop. The basic maths In a previous article, we explained that a Bézier curve can be expressed as a polynomial. In our case, a cubic polynomial: B_3(t) = \textbf{a}t^3 + \textbf{b}t^2 + \textbf{c}t + \textbf{d} Where a, b, c and d are the vector coefficients derived from the start (P_0), end (P_3), and control points (P_1, P_2) using the following formulas (you can refer to the previous article for details): \begin{aligned} \textbf{a} &= -P_0 + 3(P_1-P_2) + P_3 \\ \textbf{b} &= 3P_0 - 6P_1 + 3P_2 \\ \textbf{c} &= -3P_0 + 3P_1 \\ \textbf{d} &= P_0 \end{aligned} For a given point p in 2D space, the distance to that Bézier curve can be expressed as a length between our curve and p: \begin{aligned} d(t) &= ||B_3(t) - \textbf{p}|| \\ &= ||\textbf{a}t^3 + \textbf{b}t^2 + \textbf{c}t + \textbf{d} - \textbf{p}|| \end{aligned} Our goal is to find the t value where d(t) is the smallest....