Now Loading..

2D Cubic Bézier Curves as Interpolation Functions

Last updated 2024- 5-22, 7:39: 3 A.M. UTC+00:00

Re: The F-Curve Enigma

A Common Solution

The Problem Statement is simple: we are given two keyframes and we would like to interpolate between them, whilst granting enough control to the artist to control the interpolation function.

Hermite

This short writeup is prompted by a discussion from CH FR about pathological keyframe tangent behavior in Autograph

I am unsure about the rationale behind choosing a "1D Hermite" solution over a de-facto industry standard. The use of 2D Cubic Bézier curve is robust, tried-and-true, and performant.

Regardless, here is an interactive demo for 2D Hermite interpolation.

The Common Solution is to somehow use a parametric 2D Cubic Bézier curve to specify the function, as it is already widely used for vector graphics. It is necessary that we subject such a curve to some constraints for this use case, in order to obtain a well-defined function (that only associate a single one \(y\)-value to any \(x\)-value in range). Here is an interactive demo:

Improvement on de Casteljau

De Casteljau's algorithm is the way Bézier curves are usually drawn. A new method has been proposed this year that is more efficient. It is remarkable that progress has been made on such an old, and simple too, subject.

Unknown Area (未 知 の エ リ ア)

The equation for the parametric curve \(C:[0,1] \to \mathbb R ^2\) is simple, too. Given four points \(P_0 = (x_0, y_0), P_1 = (x_1, y_1), P_2 = (x_2, y_2), P_3 = (x_3, y_3) \in \mathbb R ^2\): $$\begin{align*} C(t) &= \sum_{i=0}^3 \binom{3}{i} t^{i} \left(1-t\right)^{3-i} P_i \\ &= t^3P_3+3t^2\left(1-t\right)P_2+3t\left(1-t\right)^2PX_1+\left(1-t\right)^3P_0 \end{align*}$$

In our context of discussion, the \(x\)-axis represents time (usually in frame number or in seconds), and the \(y\)-axis represents the desired value. We can now restate the problem: Consider the component functions \(C=(C_x, C_y)\), we would like to have \(C_x: [0,1] \to \mathbb R\) be injective, in addition to \(C\) itself being injective. Notice that the latter implies the former, while the former does not imply the latter -- because a loop necessarily has points that have the same \(x\)-coordinates; so the former is a stronger condition.

Here are two results from calculus that will come in very handy:

The simple constraints used in applications such as Blender, Cinema 4D, After Effects are the following:

The goal of this writeup is to investigate why this works (with a surprise at the end!).

In effect, the two tangents or handles (\(P_1,P_2\)) are bound to be between the the first and last points (\(C(0)=P_0, C(1)=P_3\)).

The following result is immediate, and by design of the Bézier interpolation:

Theorem 1. The entire curve (the image of \(C: [0,1] \to \mathbb R^2 \)) is contained within the convex hull of \({P_0,P_1,P_2,P_3}\).

Proof The coefficient functions sum to \(1\) by the binomial theorem: $$\begin{align*} t^3+3t^2\left(1-t\right)+3t\left(1-t\right)^2+\left(1-t\right)^3 &= \sum_{i=0}^3 \binom{3}{i} t^{i} \left(1-t\right)^{3-i} \\ &= (t + (1 - t))^3 \\ &= 1 \end{align*}$$ And as such automatically every \(C(t)\) is a convex combination of \({P_0,P_1,P_2,P_3}\). And thus it is in the convex hull by definition. \(\blacksquare\)

In practical applications, this means that the curve may never extend before \(P_0\) or past \(P_3\) in time, when constraint 2 is applied. In other words, the image of \(C_x\) is contained within \([x_0, x_3]\) (to see this, notice that the convex hull is always contained within the bounding box).

Theorem 2. Suppose \(C\) is subject to constraint 1. Then the component function \(C_x:[0,1] \to [x_0,x_3]\) is injective if \(C\) satisfies constraint 2.

Proof As in here, we can expand \(C_x\) out explicitly in \(t\)-monomials:

$$\begin{align*}C_x (t) = & (-x_0 + 3x_1- 3x_2 + x_3)t^3 + (3x_0 - 6x_1 + 3x_2)t^2 +\\ &(-3x_0 + 3x_1)t + x_0\end{align*}$$

Without loss of generality, we may assume first that \(P_0 = (0,0), P_3 = (1,1)\) (other bezier curves satisfying constraint 1 can be transformed into such by scaling and translation, without changing the nature of the curve). So then we get: $$\begin{align*}C_x (t) &= (3x_1- 3x_2 + 1)t^3 + (- 6x_1 + 3x_2)t^2 + 3x_1t \end{align*}$$ whose derivative is: $$\begin{align*}C_x' (t) &= 3(3x_1- 3x_2 + 1)t^2 + 2(- 6x_1 + 3x_2)t + 3x_1 \end{align*}$$

By (Result from calculus 1), if we want \(C_x\) to be injective, it is also strictly monotonic. Thus by (Result from calculus 2), \(C_x'\) here must be positive or negative over \([0,1]\), save for at most two points, being the roots of \(C_x'\). We know there are at most two because \(C_x'\) is a quadratic. Further its graph is a parabola. We consider the three possible cases under which the above can be true:

The first situation correspond to a discriminant \(\Delta = 0\), and the second corresponds to \(\Delta < 0\). We will deal with those two cases first, since we see that \(C_x'\) has discriminant $$\Delta = (2(- 6x_1 + 3x_2))^2 - 4\cdot3(3x_1- 3x_2 + 1)\cdot3x_1$$ Since we are only interested in the sign of \(\Delta\): $$\begin{align*}\frac{\Delta}{12} &= ((- 2x_1 + x_2))^2 - (3x_1- 3x_2 + 1)x_1\\ &= 4x_1^2 + x_2^2 - 4x_1x_2 - 3x_1^2 + 3x_1x_2 - x_1\\ &= x_1^2 + x_2^2 - x_1x_2 - x_1\end{align*}$$

Thus for the first two cases, we find that we require \(x_1^2 + x_2^2 - x_1x_2 - x_1 \leq 0 \). This results in the following plot in the parameter space where the \(x\)-axis represents \(x_1\) and the \(y\)-axis represents \(x_2\).

Isn't this amazing? It's an ellipse that includes values outside \([0,1] \times [0,1]\)!

We can look at the last case now where \(\Delta > 0\), this case is not as interesting, and contains a lot of hairy symbol pushing. Using the quadratic formula, we obtain expressions for the two roots. We will save the details and proceed to plot the area in the parameter space where at least one root of \(C_x'\) falls in \((0,1)\) (so that the unshaded area is the desired area):

This just traces out the square where \(0\leq x_1\leq1\) and \(0\leq x_2\leq1\) in addition to the ellipse before, we notice that this square (not including parts of the ellipse extending past it) is the exactly the area prescribed if we follow constraints 1 and 2. \(\blacksquare\)

Here I provide an interactive demo where you can drag the curve tangents, with a view of the parameter space on the right. The curve is suitable as an interpolation function so long as the point in the parameter space is within the shaded area. You can confirm yourself that you really can't get a curve in your app (Blender, AE, etc) in the demo here where the \(x_1,x_2\) parameter point lives outside the square and into the two elliptically-bounded regions. (Notice that the \(y\)-coordinates carry no effect on whether the curve describes a function.)

So, yes! You can pull your keyframe tangents past the opposite keyframes, and you may be fine (as long as its not too much)!

Conclusion

I don't claim to know where the practice of clamping handles along contraints 1 and 2 originated. But I assume it's all heuristics, as it was done for Blender. It's certainly a good one at that, as it's proven to be effective. Nonetheless, I think it's still kinda fun to figure out why effective heuristics work!