Bezier Curve SDF Derivation

Hello friends, It's been almost a month since my last article. The main reason is that the derivation for this one really exceedeed my capabilities and there a a lack of relveant materials. making it ver challenging to digest. The highlights of this article include

• Friendly to beginners: It's been over a decade since I last used math. and my math level is basically thata of a middle school student. In hte process of understaning, I encountered many caued-and-effect explanations that were completely unclear to me. The reason for this that I had forgetten many formulas and theorems, or simply never know then. Through continuously consulting materials. I finnaly managed to write out the entire derivation prcoess. This article supplements a lot of this foundational knowledge. and I believe it will also be suitable for beginners, as I was one myself
• Consistent marker, symbols and variables: At first glance of sdf shader code, I couldn't understand how the code was working. Later when I found some meterials with the entire proof process, I still didn't understand it. A big part of the reason was the symbols in the code and in the mathematical formulas were completely different. In this article, the symbols for legends, proofs, and code are all the same.
• Proved: Using De Moivre's theorem and Fermat's lemma with diagrams, that the third root cannot be the minimum value.

Math References

Chain Rule for Differentiation

The chain rule is a fundamental rule in calculus for differentiating composite functions.

$$ \frac{d}{dx}f(g(x)) = f'(g(x)) \cdot g'(x) $$

Polynomial Differentiation

Polynomial differentiation is a basic concept in calculus,

$$ P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0 $$

Where $a_n, a_{n-1}, \ldots, a_1, a_0$ are constant coefficients, $n$ is the highest power and is a non-negative integer. The derivative of a polynomial function $P'(x)$ can be calculated using the following rules:

• Power rule: if $f(x) = x^n$ , where $n$ is any real number, then $f'(x) = n \cdot x^{n-1}$ .
• Constant rule: If $C$ is a constant, then the derivative of $f(x) = C$ is 0. That is $C' = 0$

Cubic Unit Roots

Cubic unit roots, also known as the cube roots of unity, are a special type of number in complex numbers that are solutions to the equation $x^3 = 1$.

$$ \begin{aligned} x_1 &= 1 \\ x_2 &= e^{\frac{i2\pi}{3}} = \cos{\frac{2\pi}{3}} + i\sin{\frac{2\pi}{3}} = -\frac{1}{2} + i\frac{\sqrt{3}}{2} \\ x_3 &= e^{\frac{i2\pi \cdot 2}{3}} = \cos{\frac{4\pi}{3}} + i\sin{\frac{4\pi}{3}} = -\frac{1}{2} - i\frac{\sqrt{3}}{2} \\ \end{aligned} $$

Triple Angle Formula

The triple angle formula is an important formula in trigonometry that relates the trigonometric values of a triple angle to the trigonometric values of a single angle.

$$ \cos(3A) = 4\cos^3 A - 3\cos A $$

Euler's Formula

The most beautiful formula in the world, it connects exponential operations of complex numbers with trigonometric functions

$$ e^{i\theta} = \cos{\theta} + i\sin{\theta} $$

De Moivre's Theorem

When we seek the $n^{th}$ root of a complex number $z$, the result can be expressed as

$$ z^{1/n} = r^{1/n} \left( \cos \left( \frac{\theta + 2k\pi}{n} \right) + i\sin \left( \frac{\theta + 2k\pi}{n} \right) \right), k = 0, 1, \ldots, n-1 $$

Cardano's Equation

An equation of the form $$ x^3 + px + q = 0 $$ which lacks a quadratic term, is known as the “Depressed form” or “Cardano's form.” Its roots are given by the following formula: $$ x = \sqrt[3]{-\frac{q}{2} + \sqrt{\left(\frac{q}{2}\right)^2 + \left(\frac{p}{3}\right)^3}} + \sqrt[3]{-\frac{q}{2} - \sqrt{\left(\frac{q}{2}\right)^2 + \left(\frac{p}{3}\right)^3}} $$

To use Cardano's equation, any cubic equation of the form $ax^3 + bx^2 + cx + d = 0$ needs to be first transformed into the depressed form through subsitution. This is usually done by replacing $x$ to eliminate the quadratic term from the orginal equation.

$$ x = y - \frac{b}{3a} $$

When using Cardano's method, we often encounter a quanity known as the Cardano's discriminant

$$ \Delta = \left(\frac{q}{2}\right)^2 + \left(\frac{p}{3}\right)^3 $$

This quantity tells us about the nature of the equation's roots:

• If $\Delta > 0$, then the equation has one real root and two complex roots.
• If $\Delta = 0$, then all roots are real, and at least two roots are equal.
• If $\Delta < 0$, then the equation has three distinct real roots.

Viète's Formulas

Viète's formulas, are a set of theorems about the relationship between the roots of a polynomial equation and its coefficients. These theorems hold for any polynomial equation with real or complex coefficients.

$$ a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0 = 0

\implies

\begin{cases} x_1 + x_2 + \dots + x_n = -\frac{a_{n-1}}{a_n} \ x_1x_2 + x_1x_3 + \dots + x_{n-1}x_n = \frac{a_{n-2}}{a_n} \ x_1x_2 \dots x_n = (-1)^n \frac{a_0}{a_n} \end{cases} $$

Fermat's Lemma

Fermat's Lemma is a fundamental result in calculus which states that: If a function $f$ has a local maximum or minimum at the point $x = c$, and if $f$ is differentiable at $x = c$, then $f'(c) = 0$. Fermat's Lemma merely provides a necessary condition for a differentiable function to have an extremum at a certain point. This means that some stationary points may not be extrema; they could be inflection points. To determine whether a stationary point is an extremum, and to further distinguish between maximum and minimum points, one needs to analyze the second derivative (if it exists). When the second derivative at that point is greater than zero, the point is a minimum; when less than zero, the point is a maximum. If the second derivative is zero, this test is inconclusive, and further investigation is required.

Derivation

Quadratic Bezier Curve Function

Bézier curves result from linear interpolation. If we know the distance between two points and want to find a new point 20% of the distance away from the first point (that is, 80% of the distance away from the second point), we can calculate it as follows:

$$ Given \begin{pmatrix} p1 = some point \\ p2 = other point \\ distance = (p2 - p1) \\ ratio = \cfrac{percentage}{100} \end{pmatrix}, \text{our new point =} p_1 + distance \cdot ratio $$

In a 2D coordinate system with points A, B, C, and variable t, where t's value ranges from $[0, 1]$, a quadratic Bézier curve is drawn. For any point p within the coordinates, find the shortest distance from p to this curve.

vec2 Bezier(vec2 a, vec2 b, vec2 c, float t) {
    return mix(mix(a, b, t), mix(b,c,t), t);
}

Also $$ mix(a, b, t) = a\cdot(1-t) + b\cdot t $$

In mathmatical formulas $$ \begin{aligned}

P(t) &= (1 - t)^2 \cdot A + 2 \cdot (1 - t) \cdot t \cdot B + t^2 \cdot C \ &=(1-2t+t^2) \cdot A + (2t - 2t^2) \cdot B + t^2 \cdot C \

let f(t) = P(t) - p
\implies f(t) &= (A-2B+C) \cdot t^2 + 2 \cdot (B-A) \cdot t + A-p \ \ let
\begin{cases} a=B-A \ b=A-2B+C \ c=2(B-A) = 2a \ d=A-p \end{cases} \implies f(t) &= b \cdot t^2 + c \cdot t + d

\end{aligned} $$

The Minimum Distance Is Found by Seeking the Extrema

Thus, the problem of the distance field for the Bézier curve becomes $$ what \ value \ t, the \ minimum \ value \ of \ |f(t)| $$

This problem is equivalent to

$$ what \ value \ t, the \ minimum \ value \ of \ f(t)^2 $$

Thus, it becomes a problem of finding the extremum, where the extremum must be point where derivative equals 0. Using the chain rule of differnetiation, it can be calculated as follows

$$ \frac{d}{dt}[f(t)]^2 = 2f(t) \cdot f'(t) $$

Applying basic polynomial differentiation

$$ \begin{aligned} 0 &= 2f(t) \cdot f'(t) \\ &= 2 \cdot (b \cdot t^2 + c \cdot t + d) \cdot (2b \cdot t + c) \\ &= b \cdot t^2 \cdot (2b \cdot t + c) + c \cdot t \cdot (2b \cdot t + c) + d \cdot (2b \cdot t + c) \\ &= (b \cdot t^2 \cdot 2b \cdot t) + (b \cdot t^2 \cdot c) + (c \cdot t \cdot 2b \cdot t) + (c \cdot t \cdot c) + (d \cdot 2b \cdot t) + (d \cdot c) \\ &= 2b^2 \cdot t^3 + bc \cdot t^2 + 2bc \cdot t^2 + c^2 \cdot t + 2bd \cdot t + dc \\ &= 2b^2 \cdot t^3 + 3bc \cdot t^2 + (c^2 + 2bd) \cdot t + dc \\ \end{aligned} $$

Finally, the problem becomes one of solving a cubic polynomial.

$$ g(t)=2b^2 \cdot t^3 + 3bc \cdot t^2 + (c^2 + 2bd) \cdot t + dc $$

Solving Cubic Polynomials with Cardarno's Formula

$$ \begin{aligned} 0 &= 2b^2 \cdot t^3 + 3bc \cdot t^2 + (c^2 + 2bd) \cdot t + dc \\ &=t^3 + \frac{3ab}{b^2} \cdot t^2 + \frac{2a^2 + bd}{b^2} \cdot t + \frac{da}{b^2} \end{aligned} $$

$$ let \ \ \begin{pmatrix} a_2 = \frac{3ab}{b^2} \\ a_1 = \frac{2a^2 + bd}{b^2} \\ a_0 = \frac{da}{b^2} \end{pmatrix} \implies x^3 + a_2x^2 + a_1x + a_0 = 0 $$

To find the turning points. take the second derivative and shift to zero location(change of variables) to eliminate the quadratic term.

$$ \begin{aligned} f(x)=x^3 + a_2x^2 + a_1x + a_0 &\implies f''(x) = 6x + 2a_2 =0 \ x\to x - \frac{a_2}{3} &\implies x^3 + (a_1-\frac{a_2^2}{3})x + (a_0 + \frac{a_2*(2a_2^2 - 9a_1)}{27}))= 0

\end{aligned}

$$

Using Cardano's formula variables $p$ and $q$

$$ let \begin{cases} p=a_1-\frac{a_2^2}{3} \\ q=a_0 + \frac{a_2*(2a_2^2 - 9a_1)}{27} \\ \end{cases} \implies x^3 = -3(\frac{p}3)x + 2(-\frac{q}2) \\ $$

$$ let \begin{cases} m = \frac{p}3 \\ n= -\frac{q}2 \\ \end{cases} \implies x^3 = -3mx + 2n \\ $$

$$

\begin{aligned} let \ x\to s+t &\implies x^3 = 3st(s+t) + s^3 + t^3 \ &\implies x^3 = 3st\cdot x + s^3 + t^3
\end{aligned}

$$

By comparing coefficients from Equations 1 and 2 as above,

$$ \begin{cases} s^3 \cdot t^3 = m^3 \ s^3 + t^3 = 2n
\end{cases} $$ According to Vieta's formulas, $s^3$ and $t^3$ are roots of the equation $x^2 - 2nx + m^3 = 0$, so we have

$$ \begin{cases} s^3 = n + \sqrt{n^2-m^3} \\ t^3 = n - \sqrt{n^2-m^3} \end{cases} $$

unfolding the equation gives us $$ x = s+t = \sqrt[3]{ n + \sqrt{n^2-m^3}} + \sqrt[3]{n - \sqrt{n^2-m^3}} $$ Applying the cubic roots of unity allows for full expansion

$$ \implies x= \begin{cases} \sqrt[3]{ n + \sqrt{n^2-m^3}} + \sqrt[3]{n - \sqrt{n^2-m^3}} \ \omega \sqrt[3]{ n + \sqrt{n^2-m^3}} + \omega^2\sqrt[3]{n - \sqrt{n^2-m^3}} \ \omega^2\sqrt[3]{ n + \sqrt{n^2-m^3}} + \omega \sqrt[3]{n - \sqrt{n^2-m^3}} \

\end{cases} \ \omega = e^{\frac{2\pi}{3}i} = -\frac12 + \frac{\sqrt{3}}{2}i $$

The issue with this solution is that it only becomes clear which roots are real after computing each formula in sequence.

Solving Cubic Polynomials by Trigonnometric Substitution

This method avoids the issues with square roots and uncertainty of real roots encountered in the previous method.

Using the triple angle formula, we have $$ \cos(3\theta) = 4\cos^3 \theta - 3\cos \theta $$ Similarly, this is a cubic equation, so if we have the following cubic equation, it can be inferred that

$$ 4x^3 - 3x - cos3\theta = 0 \implies x = cos\theta $$ Recalling our equation from the previous section

$$ x^3 = 3px + 2q
$$ If we make a substitution such that equation satisfies the triple angle formula, we can directly obtain the solution

$$ \begin{aligned} x = 2\sqrt{p} \ C &\implies 4C^3 - 3C = \frac{q}{p\sqrt{p}} = cos3\theta \ &\implies x = 2\sqrt{p} cos(\frac{\phi +2k\pi}{3}), \phi = arccos(\frac{q}{p\sqrt{p}}) , k = 0, 1, 2 \end{aligned} $$ This solution is the method used in code.

Solving Cubic Polynomials using Complex Plane Polar Coordinates

Returning to our equations

$$ \begin{cases} s^3 = q + \sqrt{q^2-p^3} \ t^3 = q - \sqrt{q^2-p^3} \end{cases} $$ Let's consider the situation with three real roots when $q^2 < p^3$. If $q^2 < p^3$, $s^3$ and $t^3$ are a pair of conjugate complex numbers

$$ s^3 = q + \sqrt{p^3 - q^2}i $$

The magnitude $r$ of $s^3$ is

$$ \sqrt{q^2 + p^3 - q^2} = p\sqrt[]{p} $$

Placing $s^3$ and $t^3$ into polar coordinates, we can get the following diagram:

• geogebra: https://www.geogebra.org/classic/jf4ckzek

Taking the cube root of $s^3$ and using the formula for De Moivre's Theorem $$ z^{1/3} = r^{1/3} \left( \cos \left( \frac{\phi + 2k\pi}{3} \right) + i\sin \left( \frac{\phi + 2k\pi}{3} \right) \right), \space k = 0, 1, \ldots, n-1 $$ Directly yielding the three solutions.

For the root 0 $$ x = s_0 + t_0 = 2RealPart(s_0) = 2\sqrt{p} \ \ cos(\phi/3) $$

By adding $s$ and $t$ in the polar coordinate complex plane as vectors, we arrive at the same solution as in the previous sections!!! Behind this actually lies the Euler's formula $$ x= 2\sqrt{p} \cos \left( \frac{\phi + 2k\pi}{3} \right) , \phi = arccos(\frac{q}{p\sqrt{p}}) \space k = 0, 1, 2 $$

Proving that the Minimum Value Can Only Be Between $t_0$ and $t_1$

Let's return to expressing the final roots in terms of $t$.

$$ \phi \in [0, \pi] \implies \frac{\phi}{3} = \theta \in [0, \frac{\pi}3] $$ geogebra: https://www.geogebra.org/classic/u8uuxw9u

For any $\theta \in [0, \frac{\pi}3]$, we have $$ cos(\theta+\frac{21\pi}{3}) < cos(\frac{\phi + 22\pi}{3})< cos(\frac{2*0\pi}{3}) \implies t_1 < t_2 < t_0 $$

Returning to the function of the quadratic bezier curve, we have

$$ \begin{aligned} f(t) &= b \cdot t^2 + c \cdot t + d \ \frac{d}{dt}[f(t)]^2 = g(t) &= 2b^2 \cdot t^3 + 3bc \cdot t^2 + (c^2 + 2bd) \cdot t + dc \ g'(t) &= 6b^2t^2 + 6bct + c^2 +2bd \end{aligned} $$

The extremal points of $f(t)^2$ must correspond to the three roots of the first derivative $g(t)=0$, namely $t_1$, $t_2$, $t_0$. If there are three real roots, there can only be the following two types of graphs.

geogebra: https://www.geogebra.org/classic/qdrdxycn

1. There are local maxima at $t_0$ and $t_1$, while $t_2$ is a local minimum.
2. There are local minima at $t_0$ and $t_1$, while $t_2$ is a local maximum.

The graphs of the second derivative $g'(t)$ for each of these two functions are as follows, opening upwards and downwards, respectively.

Given that $g'(t) = 6b^2t^2 + 6bct + c^2 +2bd$ Because $6t^2 &gt; 0$, Therefore the graph of the function opens upwards, and we have $$ t_1 < t_2 < t_0 $$ From observing the graph, we can deduce that $$ g'(t_2) < max(g'(t_0), g'(t_1)) \tag{1} $$ Assuming we are in situation 1, where there are local maxima at $t_0$ and $t_1$, while $t_2$ is a local minimum. Then, according to Fermat's lemma, for a local maximum, the second derivative < 0, we have $$ g'(t_0) < 0 \ \ and \ \ g'(t_1) < 0 \tag{2} $$ For a local minimum, the second derivative > 0, we have $$ g'(t_2) > 0 \tag{3} $$ From inequalities (1) and (2), we can deduce that

$$ g'(t_2) < max(g'(t_0), g'(t_1)) < 0 \tag{4} $$ Inequalities (3) and (4) contradict each other, thus situation 1 does not exist.

Therefore, the closest distance from the Bézier curve must be at the root either $t_0$ or $t_1$.

$$ Q.E.D. $$