9.2.1. Bézier Curves

9.2.1.1. Valentina Requirements

  • Quadratic Bézier curve
  • adjustment of the control points by pulling the curve (passing by a point)
  • curve - line intersection
  • curve - curve intersection

9.2.1.2. Definitions

A Bézier curve is defined by a set of control points \(\mathbf{P}_0\) through \(\mathbf{P}_n\), where \(n\) is called its order (\(n = 1\) for linear, 2 for quadratic, 3 for cubic etc.). The first and last control points are always the end points of the curve;

In the following \(0 \le t \le 1\) and \(u = 1 - t\)

9.2.1.3. Linear Bézier Curves

Given distinct points \(\mathbf{P}_0\) and \(\mathbf{P}_1\), a linear Bézier curve is simply a straight line between those two points. The curve is given by

\[\begin{split}\begin{align} \mathbf{B}(t) &= \mathbf{P}_0 + t (\mathbf{P}_1 - \mathbf{P}_0) \\[.5em] &= (1-t) \mathbf{P}_0 + t \mathbf{P}_1 \\[.5em] &= u \mathbf{P}_0 + t \mathbf{P}_1 \end{align}\end{split}\]

and is equivalent to linear interpolation.

9.2.1.4. Quadratic Bézier Curves

A quadratic Bézier curve is the path traced by the function \(\mathbf{B}(t)\), given points \(\mathbf{P}_0\), \(\mathbf{P}_1\), and \(\mathbf{P}_2\),

\[\begin{split}\begin{align} \mathbf{B}(t) &= (1-t)[(1-t) \mathbf{P}_0 + t \mathbf{P}_1] + t [(1-t) \mathbf{P}_1 + t \mathbf{P}_2] \\[.5em] &= u[u \mathbf{P}_0 + t \mathbf{P}_1] + t [u \mathbf{P}_1 + t \mathbf{P}_2] \end{align}\end{split}\]

which can be interpreted as the linear interpolant of corresponding points on the linear Bézier curves from \(\mathbf{P}_0\) to \(\mathbf{P}_1\) and from \(\mathbf{P}_1\) to \(\mathbf{P}_2\) respectively.

Rearranging the preceding equation yields:

\[\begin{split}\begin{align} \mathbf{B}(t) &= (1-t)^2 \mathbf{P}_0 + 2(1-t)t \mathbf{P}_1 + t^2 \mathbf{P}_2 \\[.5em] &= u^2 \mathbf{P}_0 + 2ut \mathbf{P}_1 + t^2 \mathbf{P}_2 \\[.5em] &= (\mathbf{P}_0 - 2\mathbf{P}_1 + \mathbf{P}_2) t^2 + 2(-\mathbf{P}_0 + \mathbf{P}_1) t + \mathbf{P}_0 \end{align}\end{split}\]

This can be written in a way that highlights the symmetry with respect to \(\mathbf{P}_1\):

\[\begin{split}\begin{align} \mathbf{B}(t) &= \mathbf{P}_1 + (1-t)^2 ( \mathbf{P}_0 - \mathbf{P}_1) + t^2 (\mathbf{P}_2 - \mathbf{P}_1) \\[.5em] &= \mathbf{P}_1 + u^2 ( \mathbf{P}_0 - \mathbf{P}_1) + t^2 (\mathbf{P}_2 - \mathbf{P}_1) \end{align}\end{split}\]

Which immediately gives the derivative of the Bézier curve with respect to t:

\[\begin{split}\begin{align} \mathbf{B}'(t) &= 2(1-t) (\mathbf{P}_1 - \mathbf{P}_0) + 2t (\mathbf{P}_2 - \mathbf{P}_1) \\[.5em] &= 2 (\mathbf{P}_1 - \mathbf{P}_0) + 2(\mathbf{P}_0 - 2\mathbf{P}_1 + \mathbf{P}_2) t \\[.5em] &= 2u (\mathbf{P}_1 - \mathbf{P}_0) + 2t (\mathbf{P}_2 - \mathbf{P}_1) \end{align}\end{split}\]

from which it can be concluded that the tangents to the curve at \(\mathbf{P}_0\) and \(\mathbf{P}_2\) intersect at \(\mathbf{P}_1\). As \(t\) increases from 0 to 1, the curve departs from \(\mathbf{P}_0\) in the direction of \(\mathbf{P}_1\), then bends to arrive at \(\mathbf{P}_2\) from the direction of \(\mathbf{P}_1\).

The second derivative of the Bézier curve with respect to \(t\) is

\[\mathbf{B}''(t) = 2 (\mathbf{P}_2 - 2 \mathbf{P}_1 + \mathbf{P}_0)\]

9.2.1.5. Cubic Bézier Curves

Four points \(\mathbf{P}_0\), \(\mathbf{P}_1\), \(\mathbf{P}_2\) and \(\mathbf{P}_3\) in the plane or in higher-dimensional space define a cubic Bézier curve. The curve starts at \(\mathbf{P}_0\) going toward \(\mathbf{P}_1\) and arrives at \(\mathbf{P}_3\) coming from the direction of \(\mathbf{P}_2\). Usually, it will not pass through \(\mathbf{P}_1\) or \(\mathbf{P}_2\); these points are only there to provide directional information. The distance between \(\mathbf{P}_1\) and \(\mathbf{P}_2\) determines “how far” and “how fast” the curve moves towards \(\mathbf{P}_1\) before turning towards \(\mathbf{P}_2\).

Writing \(\mathbf{B}_{\mathbf P_i,\mathbf P_j,\mathbf P_k}(t)\) for the quadratic Bézier curve defined by points \(\mathbf{P}_i\), \(\mathbf{P}_j\), and \(\mathbf{P}_k\), the cubic Bézier curve can be defined as an affine combination of two quadratic Bézier curves:

\[\mathbf{B}(t) = (1-t) \mathbf{B}_{\mathbf P_0,\mathbf P_1,\mathbf P_2}(t) + t \mathbf{B}_{\mathbf P_1,\mathbf P_2,\mathbf P_3}(t)\]

The explicit form of the curve is:

\[\begin{split}\begin{align} \mathbf{B}(t) &= (1-t)^3 \mathbf{P}_0 + 3(1-t)^2t \mathbf{P}_1 + 3(1-t)t^2 \mathbf{P}_2 + t^3\mathbf{P}_3 \\[.5em] &= u^3 \mathbf{P}_0 + 3u^2t \mathbf{P}_1 + 3ut^2 \mathbf{P}_2 + t^3\mathbf{P}_3 \\[.5em] &= (\mathbf{P}_3 - 3\mathbf{P}_2 + 3\mathbf{P}_1 - \mathbf{P}_0) t^3 + 3(\mathbf{P}_2 - 2\mathbf{P}_1 + \mathbf{P}_0) t^2 + 3(\mathbf{P}_1 - \mathbf{P}_0) t + \mathbf{P}_0 \end{align}\end{split}\]

For some choices of \(\mathbf{P}_1\) and \(\mathbf{P}_2\) the curve may intersect itself, or contain a cusp.

The derivative of the cubic Bézier curve with respect to \(t\) is

\[\begin{split}\begin{align} \mathbf{B}'(t) &= 3(1-t)^2 (\mathbf{P}_1 - \mathbf{P}_0) + 6(1-t)t (\mathbf{P}_2 - \mathbf{P}_1) + 3t^2 (\mathbf{P}_3 - \mathbf{P}_2) \\[.5em] &= 3u^2 (\mathbf{P}_1 - \mathbf{P}_0) + 6ut (\mathbf{P}_2 - \mathbf{P}_1) + 3t^2 (\mathbf{P}_3 - \mathbf{P}_2) \end{align}\end{split}\]

The second derivative of the Bézier curve with respect to \(t\) is

\[\begin{split}\begin{align} \mathbf{B}''(t) &= 6(1-t) (\mathbf{P}_2 - 2 \mathbf{P}_1 + \mathbf{P}_0) + 6t (\mathbf{P}_3 - 2 \mathbf{P}_2 + \mathbf{P}_1) \\[.5em] &= 6u (\mathbf{P}_2 - 2 \mathbf{P}_1 + \mathbf{P}_0) + 6t (\mathbf{P}_3 - 2 \mathbf{P}_2 + \mathbf{P}_1) \end{align}\end{split}\]

9.2.1.6. Recursive definition

A recursive definition for the Bézier curve of degree \(n\) expresses it as a point-to-point linear combination of a pair of corresponding points in two Bézier curves of degree \(n-1\).

Let \(\mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_n}\) denote the Bézier curve determined by any selection of points \(\mathbf{P}_0\), \(\mathbf{P}_1\), \(\ldots\), \(\mathbf{P}_{n-1}\).

The recursive definition is

\[\begin{split}\begin{align} \mathbf{B}_{\mathbf{P}_0}(t) &= \mathbf{P}_0 \\[1em] \mathbf{B}(t) &= \mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_n}(t) \\[.5em] &= (1-t) \mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_{n-1}}(t) + t \mathbf{B}_{\mathbf{P}_1\mathbf{P}_2\ldots\mathbf{P}_n}(t) \end{align}\end{split}\]

The formula can be expressed explicitly as follows:

\[\begin{split}\begin{align} \mathbf{B}(t) &= \sum_{i=0}^n b_{i,n}(t) \mathbf{P}_i \\[.5em] &= \sum_{i=0}^n {n\choose i}(1-t)^{n - i}t^i \mathbf{P}_i \\[.5em] &= (1-t)^n \mathbf{P}_0 + {n\choose 1}(1-t)^{n - 1}t \mathbf{P}_1 + \cdots + {n\choose n - 1}(1-t)t^{n - 1} \mathbf{P}_{n - 1} + t^n \mathbf{P}_n \end{align}\end{split}\]

where \(b_{i,n}(t)\) are the Bernstein basis polynomials of degree \(n\) and \(n \choose i\) are the binomial coefficients.

9.2.1.7. Degree elevation

A Bézier curve of degree \(n\) can be converted into a Bézier curve of degree \(n + 1\) with the same shape.

To do degree elevation, we use the equality

\[\mathbf{B}(t) = (1-t) \mathbf{B}(t) + t \mathbf{B}(t)\]

Each component \(\mathbf{b}_{i,n}(t) \mathbf{P}_i\) is multiplied by \((1-t)\) and \(t\), thus increasing a degree by one, without changing the value.

For arbitrary \(n\), we have

\[\begin{split}\begin{align} \mathbf{B}(t) &= (1-t) \sum_{i=0}^n \mathbf{b}_{i,n}(t) \mathbf{P}_i + t \sum_{i=0}^n \mathbf{b}_{i,n}(t) \mathbf{P}_i \\[.5em] &= \sum_{i=0}^n \frac{n + 1 - i}{n + 1} \mathbf{b}_{i, n + 1}(t) \mathbf{P}_i + \sum_{i=0}^n \frac{i + 1}{n + 1} \mathbf{b}_{i + 1, n + 1}(t) \mathbf{P}_i \\[.5em] &= \sum_{i=0}^{n + 1} \mathbf{b}_{i, n + 1}(t) \left(\frac{i}{n + 1} \mathbf{P}_{i - 1} + \frac{n + 1 - i}{n + 1} \mathbf{P}_i\right) \\[.5em] &= \sum_{i=0}^{n + 1} \mathbf{b}_{i, n + 1}(t) \mathbf{P'}_i \end{align}\end{split}\]

Therefore the new control points are

\[\mathbf{P'}_i = \frac{i}{n + 1} \mathbf{P}_{i - 1} + \frac{n + 1 - i}{n + 1} \mathbf{P}_i\]

It introduces two arbitrary points \(\mathbf{P}_{-1}\) and \(\mathbf{P}_{n+1}\) which are cancelled in \(\mathbf{P'}_i\).

Example for a quadratic Bézier curve:

\[\begin{split}\begin{align} \mathbf{P'}_0 &= \mathbf{P}_0 \\[.5em] \mathbf{P'}_1 &= \mathbf{P}_0 + \frac{2}{3} (\mathbf{P}_1 - \mathbf{P}_0) \\[.5em] \mathbf{P'}_1 &= \mathbf{P}_2 + \frac{2}{3} (\mathbf{P}_1 - \mathbf{P}_2) \\[.5em] \mathbf{P'}_2 &= \mathbf{P}_2 \end{align}\end{split}\]

9.2.1.8. Matrix Forms

\[\mathbf{B}(t) = \mathbf{Transformation} \; \mathbf{Control} \; \mathbf{Basis} \; \mathbf{T}(t)\]
\[\begin{split}\begin{align} \mathbf{B^2}(t) &= \mathbf{Tr} \begin{pmatrix} P_{1x} & P_{2x} & P_{3x} \\ P_{1y} & P_{2x} & P_{3x} \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & -2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ t \\ t^2 \end{pmatrix} \\[1em] \mathbf{B^3}(t) &= \mathbf{Tr} \begin{pmatrix} P_{1x} & P_{2x} & P_{3x} & P_{4x} \\ P_{1y} & P_{2x} & P_{3x} & P_{4x} \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & -3 & 3 & -1 \\ 0 & 3 & -6 & 3 \\ 0 & 0 & 3 & -3 \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ t \\ t^2 \\ t^3 \end{pmatrix} \end{align}\end{split}\]

9.2.1.9. Symbolic Calculation

>>> from sympy import *

>>> P0, P1, P2, P3, P, t = symbols('P0 P1 P2 P3 P t')

>>> B2 = (1-t)*((1-t)*P0 + t*P1) + t*((1-t)*P1 + t*P2)
>>> collect(expand(B2), t)
P0 + t**2*(P0 - 2*P1 + P2) + t*(-2*P0 + 2*P1)

>>> B2_012 = (1-t)*((1-t)*P0 + t*P1) + t*((1-t)*P1 + t*P2)
>>> B2_123 = (1-t)*((1-t)*P1 + t*P2) + t*((1-t)*P2 + t*P3)
>>> B3 = (1-t)*B2_012 + t*B2_123
>>> collect(expand(B3), t)
P0 + t**3*(-P0 + 3*P1 - 3*P2 + P3) + t**2*(3*P0 - 6*P1 + 3*P2) + t*(-3*P0 + 3*P1)

# Compute derivative
>>> B2p = collect(simplify(B2.diff(t)), t)
-2*P0 + 2*P1 + t*(2*P0 - 4*P1 + 2*P2)

>>> B3p = collect(simplify(B3.diff(t)), t)
-3*P0 + 3*P1 + t**2*(-3*P0 + 9*P1 - 9*P2 + 3*P3) + t*(6*P0 - 12*P1 + 6*P2)

9.2.1.10. Curve Length

Reference

The quadratic Bézier is

\[\mathbf{B}(t) = (1-t)^2 \mathbf{P}_0 + 2t(1-t) \mathbf{P}_1 + t^2 \mathbf{P}_2\]

The derivative is

\[\mathbf{B'}(t) = -2(1-t) \mathbf{P}_0 + (2-4t) \mathbf{P}_1 + 2t \mathbf{P}_2\]

The length of the curve for \(0 <= t <= 1\) is

\[\int_0^1 \sqrt{(x'(t))^2 + (y'(t))^2} dt\]

The integrand is of the form \(\sqrt{c t^2 + b t + a}\)

You have three separate cases: \(c = 0\), \(c > 0\), or \(c < 0\).

The case \(c = 0\) is easy.

For the case \(c > 0\), an antiderivative is

\[\frac{2ct + b}{4c} \sqrt{ct^2 + bt + a} + \frac{k}{2\sqrt{c}} \ln{\left(2\sqrt{c(ct^2 + bt + a)} + 2ct + b\right)}\]

For the case \(c < 0\), an antiderivative is

\[\frac{2ct + b}{4c} \sqrt{ct^2 + bt + a} - \frac{k}{2\sqrt{-c}} \arcsin{\frac{2ct + b}{\sqrt{-q}}}\]

where \(k = \frac{4c}{q}\) with \(q = 4ac - b^2\).

9.2.1.11. Determine the curve flatness

Reference

flatness is the maximum error allowed for the straight line to deviate from the curve.

Algorithm

We define the flatness of the curve as the argmax of the distance from the curve to the line passing by the start and stop point.

\(\mathrm{flatness} = argmax(d(t))\) for \(t \in [0, 1]\) where \(d(t) = \vert B(t) - L(t) \vert\)

The line equation is

\[L = (1-t) \mathbf{P}_0 + t \mathbf{P}_1\]

Let

\[\begin{split}\begin{align} U &= 3\mathbf{P}_1 - 2\mathbf{P}_0 - \mathbf{P}_3 \\[.5em] V &= 3\mathbf{P}_2 - \mathbf{P}_0 - 2\mathbf{P}_3 \end{align}\end{split}\]

The distance is

\[\begin{split}\begin{align} d(t) &= (1-t)^2 t \left(3\mathbf{P}_1 - 2\mathbf{P}_0 - \mathbf{P}_3\right) + (1-t) t^2 (3\mathbf{P}_2 - \mathbf{P}_0 - 2\mathbf{P}_3) \\[.5em] &= (1-t)^2 t u + (1-t) t^2 v \end{align}\end{split}\]

The square of the distance is

\[d(t)^2 = (1-t)^2 t^2 (((1-t) U_x + t V_x)^2 + ((1-t) U_y + t V_y)^2\]

From

\[\begin{split}\begin{align} argmax((1-t)^2 t^2) &= \frac{1}{16} \\[.5em] argmax((1-t) a + t b) &= argmax(a, b) \end{align}\end{split}\]

we can express a bound on the flatness

\[\mathrm{flatness}^2 = argmax(d(t)^2) \leq \frac{1}{16} (argmax(U_x^2, V_x^2) + argmax(U_y^2, V_y^2))\]

Thus an upper bound of \(16\,\mathrm{flatness}^2\) is

\[argmax(U_x^2, V_x^2) + argmax(U_y^2, V_y^2)\]

9.2.1.12. Intersection of Bézier Curve with a Line

Algorithm

  • Apply a transformation to the curve that maps the line onto the X-axis.
  • Then we only need to test the Y-values for a zero.

9.2.1.13. Closest Point

Reference

Let a point \(\mathbf{P}\) and the closest point \(\mathbf{B}(t)\) on the curve, we have this condition:

\[\begin{split}(\mathbf{P} - \mathbf{B}(t)) \cdot \mathbf{B}'(t) = 0 \\[.5em] \mathbf{P} \cdot \mathbf{B}'(t) - \mathbf{B}(t) \cdot \mathbf{B}'(t) = 0\end{split}\]

9.2.1.13.1. Quadratic Bézier Curve

Let

\[\begin{split}\begin{align} \mathbf{A} &= \mathbf{P}_1 - \mathbf{P}_0 \\[.5em] \mathbf{B} &= \mathbf{P}_2 - \mathbf{P}_1 -\mathbf{A} \\[.5em] \mathbf{M} &= \mathbf{P}_0 - \mathbf{P} \end{align}\end{split}\]

We have

\[\mathbf{B}'(t) = 2(\mathbf{A} + \mathbf{B} t)\]

The condition can be expressed as

\[\mathbf{B}^2 t^3 + 3\mathbf{A}\mathbf{B} t^2 + (2\mathbf{A}^2 + \mathbf{M}\mathbf{B}) t + \mathbf{M}\mathbf{A} = 0\]
>>> C = collect(expand((P*B2p - B2*B2p)/-2), t)
P*P0 - P*P1 - P0**2 + P0*P1 +
t**3 * (P0**2 - 4*P0*P1 + 2*P0*P2 + 4*P1**2 - 4*P1*P2 + P2**2) +
t**2 * (-3*P0**2 + 9*P0*P1 - 3*P0*P2 - 6*P1**2 + 3*P1*P2) +
t    * (-P*P0 + 2*P*P1 - P*P2 + 3*P0**2 - 6*P0*P1 + P0*P2 + 2*P1**2)
>>> A = P1 - P0
    B = P2 - P1 - A
    M = P0 - P
>>> C2 = B**2 * t**3 + 3*A*B * t**2 + (2*A**2 + M*B) * t + M*A
>>> expand(C - C2)
0

9.2.1.13.2. Cubic Bézier Curve

Let

\[\begin{split}\begin{align} n &= \mathbf{P}_3 - 3\mathbf{P}_2 + 3\mathbf{P}_1 - \mathbf{P}_0 \\[.5em] r &= 3(\mathbf{P}_2 - 2\mathbf{P}_1 + \mathbf{P}_0 \\[.5em] s &= 3(\mathbf{P}_1 - \mathbf{P}_0) \\[.5em] v &= \mathbf{P}_0 \end{align}\end{split}\]

We have

\[ \begin{align}\begin{aligned}\begin{split}\begin{align} \mathbf{B}^3(t) &= nt^3 + rt^2 + st + v \\[.5em] \mathbf{B}'(t) &= 3nt^2 + 2rt + s \end{align}\end{split}\\ .. n = P3 - 3*P2 + 3*P1 - P0 r = 3*(P2 - 2*P1 + P0 s = 3*(P1 - P0) v = P0\end{aligned}\end{align} \]
>>> n, r, s, v = symbols('n r s v')
>>> B3 = n*t**3 + r*t**2 + s*t + v
>>> B3p = simplify(B3.diff(t))
>>> C = collect(expand((P*B3p - B3*B3p)), t)
-3*n**2 * t**5 +
-5*n*r * t**4 +
-2*(2*n*s + r**2) * t**3 +
3*(P*n - n*v - r*s) * t**2 +
(2*P*r - 2*r*v - s**2) * t +
P*s - s*v