BezierInfo-2/components/sections/matrixsplit/content.en-GB.md

Splitting curves using matrices

Another way to split curves is to exploit the matrix representation of a Bézier curve. In the section on matrices, we saw that we can represent curves as matrix multiplications. Specifically, we saw these two forms for the quadratic and cubic curves respectively: (we'll reverse the Bézier coefficients vector for legibility)

[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

and

[ B(t) = \begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\ -3 & 3 & 0 & 0\ 3 & -6 & 3 & 0\ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix} ]

Let's say we want to split the curve at some point t = z, forming two new (obviously smaller) Bézier curves. To find the coordinates for these two Bézier curves, we can use the matrix representation and some linear algebra. First, we separate out the actual "point on the curve" information into a new matrix multiplication:

[ B(t) = \begin{bmatrix} 1 & (z \cdot t) & (z \cdot t)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

and

[ B(t) = \begin{bmatrix} 1 & (z \cdot t) & (z \cdot t)^2 & (z \cdot t)^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0 \ -3 & 3 & 0 & 0 \ 3 & -6 & 3 & 0 \ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix}

\begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\ 0 & z & 0 & 0\ 0 & 0 & z^2 & 0\ 0 & 0 & 0 & z^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0 \ -3 & 3 & 0 & 0 \ 3 & -6 & 3 & 0 \ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix} ]

If we could compact these matrices back to the form [t values] · [Bézier matrix] · [column matrix], with the first two staying the same, then that column matrix on the right would be the coordinates of a new Bézier curve that describes the first segment, from t = 0 to t = z. As it turns out, we can do this quite easily, by exploiting some simple rules of linear algebra (and if you don't care about the derivations, just skip to the end of the box for the results!).

Deriving new hull coordinates

Deriving the two segments upon splitting a curve takes a few steps, and the higher the curve order, the more work it is, so let's look at the quadratic curve first:

[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

[

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \underset{we\ turn\ this...}{\underbrace{\kern 2.25em Z \cdot M \kern 2.25em}} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

[

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \underset{...into\ this...}{\underbrace{ M \cdot M^{-1} \cdot Z \cdot M }} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

[

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \underset{...to\ get\ this!}{\underbrace{ \kern 1.25em \cdot \kern 1.25em Q \kern 1.25em \cdot \kern 1.25em}} \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

We can do this because [M · M^-1] is the identity matrix. It's a bit like multiplying something by x/x in calculus: it doesn't do anything to the function, but it does allow you to rewrite it to something that may be easier to work with, or can be broken up differently. In the same way, multiplying our matrix by [M · M^-1] has no effect on the total formula, but it does allow us to change the matrix sequence [something · M] to a sequence [M · something], and that makes a world of difference: if we know what [M^-1 · Z · M] is, we can apply that to our coordinates, and be left with a proper matrix representation of a quadratic Bézier curve (which is [T · M · P]), with a new set of coordinates that represent the curve from t = 0 to t = z. So let's get computing:

[ Q = M^{-1} \cdot Z \cdot M = \begin{bmatrix} 1 & 0 & 0 \ 1 & \frac{1}{2} & 0 \ 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix}

\begin{bmatrix} 1 & 0 & 0 \ -(z-1) & z & 0 \ (z - 1)^2 & -2 \cdot (z-1) \cdot z & z^2 \end{bmatrix} ]

Excellent! Now we can form our new quadratic curve:

[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot Q \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot \left ( Q \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]

[

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \left ( \begin{bmatrix} 1 & 0 & 0 \ -(z-1) & z & 0 \ (z - 1)^2 & -2 \cdot (z-1) \cdot z & z^2 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]

[

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ z \cdot P_2 - (z-1) \cdot P_1 \ z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z - 1)^2 \cdot P_1 \end{bmatrix} ]

Brilliant: if we want a subcurve from t = 0 to t = z, we can keep the first coordinate the same (which makes sense), our control point becomes a z-ratio mixture of the original control point and the start point, and the new end point is a mixture that looks oddly similar to a Bernstein polynomial of degree two. These new coordinates are actually really easy to compute directly!

Of course, that's only one of the two curves. Getting the section from t = z to t = 1 requires doing this again. We first observe that in the previous calculation, we actually evaluated the general interval [0,z]. We were able to write it down in a more simple form because of the zero, but what we actually evaluated, making the zero explicit, was:

[ B(t) = \begin{bmatrix} 1 & ( 0 + z \cdot t) & ( 0 + z \cdot t)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

[

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

If we want the interval [z,1], we will be evaluating this instead:

[ B(t) = \begin{bmatrix} 1 & ( z + (1-z) \cdot t) & ( z + (1-z) \cdot t)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

[

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & z & z^2 \ 0 & 1-z & 2 \cdot z \cdot (1-z) \ 0 & 0 & (1-z)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]

We're going to do the same trick of multiplying by the identity matrix, to turn [something · M] into [M · something]:

[ Q' = M^{-1} \cdot Z' \cdot M = \begin{bmatrix} 1 & 0 & 0 \ 1 & \frac{1}{2} & 0 \ 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & z & z^2 \ 0 & 1-z & 2 \cdot z \cdot (1-z) \ 0 & 0 & (1-z)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix}

\begin{bmatrix} (z-1)^2 & -2 \cdot z \cdot (z-1) & z^2 \ 0 & -(z-1) & z \ 0 & 0 & 1 \end{bmatrix} ]

So, our final second curve looks like:

[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot Q \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot \left ( Q' \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]

[

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \left ( \begin{bmatrix} (z-1)^2 & -2 \cdot z \cdot (z-1) & z^2 \ 0 & -(z-1) & z \ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]

[

\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z-1)^2 \cdot P_1 \ z \cdot P_3 - (z-1) \cdot P_2 \ P_3 \end{bmatrix} ]

Nice. We see the same thing as before: we can keep the last coordinate the same (which makes sense); our control point becomes a z-ratio mixture of the original control point and the end point, and the new start point is a mixture that looks oddly similar to a bernstein polynomial of degree two, except this time it uses (z-1) rather than (1-z). These new coordinates are also really easy to compute directly!

So, using linear algebra rather than de Casteljau's algorithm, we have determined that, for any quadratic curve split at some value t = z, we get two subcurves that are described as Bézier curves with simple-to-derive coordinates:

[ \begin{bmatrix} 1 & 0 & 0 \ -(z-1) & z & 0 \ (z - 1)^2 & -2 \cdot (z-1) \cdot z & z^2 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}

\begin{bmatrix} P_1 \ z \cdot P_2 - (z-1) \cdot P_1 \ z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z - 1)^2 \cdot P_1 \end{bmatrix} ]

and

[ \begin{bmatrix} (z-1)^2 & -2 \cdot z \cdot (z-1) & z^2 \ 0 & -(z-1) & z \ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}

\begin{bmatrix} z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z-1)^2 \cdot P_1 \ z \cdot P_3 - (z-1) \cdot P_2 \ P_3 \end{bmatrix} ]

We can do the same for cubic curves. However, I'll spare you the actual derivation (don't let that stop you from writing that out yourself, though) and simply show you the resulting new coordinate sets:

[ \begin{bmatrix} 1 & 0 & 0 & 0 \ -(z-1) & z & 0 & 0 \ (z-1)^2 & -2 \cdot (z-1) \cdot z & z^2 & 0 \ -(z-1)^3 & 3 \cdot (z-1)^2 \cdot z & -3 \cdot (z-1) \cdot z^2 & z^3 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix}

\begin{bmatrix} P_1 \ z \cdot P_2 - (z-1) \cdot P_1 \ z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z-1)^2 \cdot P_1 \ z^3 \cdot P_4 - 3 \cdot z^2 \cdot (z-1) \cdot P_3 + 3 \cdot z \cdot (z-1)^2 \cdot P_2 - (z-1)^3 \cdot P_1 \end{bmatrix} ]

and

[ \begin{bmatrix} -(z-1)^3 & 3 \cdot (z-1)^2 \cdot z & -3 \cdot (z-1) \cdot z^2 & z^3 \ 0 & (z-1)^2 & -2 \cdot (z-1) \cdot z & z^2 \ 0 & 0 & -(z-1) & z \ 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix}

\begin{bmatrix} z^3 \cdot P_4 - 3 \cdot z^2 \cdot (z-1) \cdot P_3 + 3 \cdot z \cdot (z-1)^2 \cdot P_2 - (z-1)^3 \cdot P_1 \ z^2 \cdot P_4 - 2 \cdot z \cdot (z-1) \cdot P_3 + (z-1)^2 \cdot P_2 \ z \cdot P_4 - (z-1) \cdot P_3 \ P_4 \end{bmatrix} ]

So, looking at our matrices, did we really need to compute the second segment matrix? No, we didn't. Actually having one segment's matrix means we implicitly have the other: push the values of each row in the matrix Q to the right, with zeroes getting pushed off the right edge and appearing back on the left, and then flip the matrix vertically. Presto, you just "calculated" Q'.

Implementing curve splitting this way requires less recursion, and is just straight arithmetic with cached values, so can be cheaper on systems where recursion is expensive. If you're doing computation with devices that are good at matrix multiplication, chopping up a Bézier curve with this method will be a lot faster than applying de Casteljau.