Major overhaul of the waypoint system

I recently created two threads exploring the mathematics and various issues behind interpolations. I’m creating this new thread as a guide to fixing these issues and getting Synfig to run in a more intuitive way. As a heads-up, I’ll be starting with the mathematics but by the end, I’ll have some pseudocode for you.

All interpolation in Synfig (except constant) is accomplished via cubic splines, curves that take the form
y(t) = At^3 + Bt^2 + Ct + D

Personally, I prefer thinking about this in the form of a differential equation. The equation y’’’’(t) = 0, where primes denote time derivatives, encodes the exact same information as the above definition. The reason this is useful is that it allows us to define our splines based on their boundary conditions. This is essentially what is going on even under the current version of Synfig, although it’s sort of broken at the moment.

Each waypoint sets a value to the spline and so two of our boundary conditions come “for free”. The two remaining boundary conditions typically (though not necessarily) arise from tangents.

For example, the ease in/out waypoint defines its tangent to be zero. If the ease waypoint is set at t=0, it corresponds to the boundary condition y’(0)=0. The last boundary condition would be set by the waypoint at the opposite end of the spline.

I’ve already argued that the linear waypoint is broken. Its current definition is effectively y’(0) = p2-p1, where p2-p1 is the difference in values at between the linear waypoint and its adjacent neighbor. Instead, I argue its definition should be y’’(0) = 0.

This would make it the only waypoint defined by its second derivative, which explains why Synfig doesn’t currently use this definition. Cubic Hermite splines, which are used to construct the splines, work really well with first derivatives, not so well with second derivatives. In this post, I’ll get around that problem by working directly with the coefficients, avoiding cubic Hermite splines.

Finally, the TCB spline is meant to give the user complete control over the tangents. Sadly, it’s sort of broken. My aim in this post is to fix all of the above and maybe add some new tools to use.

The boundary conditions are set by a 4x4 matrix. I’ll be using the coefficients A, B, C, and D as my variables, but if you prefer cubic Hermite splines, it’s not very difficult to change your basis, although I’d rather avoid them for what I’m trying to do. We also should work with normalized time, such that whatever time interval we’re concerned with covers the domain [0,1]. The values at the endpoints are set and so the first two rows of the matrix are always the same:

[0 0 0 1][A]   [p0]
[1 1 1 1][B]   [p1]
[       ][C] = [  ]
[       ][D]   [  ]

I’ve left the last two rows of the matrix and vector on the right hand side blank because they depend on the remaining two boundary conditions. Note that the top row already gives us D = p0 explicitly, so we can immediately reduce this to a 3x3 matrix and cut down on our work a bit, if desired.

Let’s cover all four simple cases involving ease and linear waypoints:
Ease left:
[0 0 1 0][.] = [0]

Linear left:
[0 1 0 0][.] = [0]

Ease right:
[3 2 1 0][.] = [0]

Linear right:
[3 1 0 0][.] = [0]

These definitions can be paired in four distinct ways with one left and one right boundary condition. For example, the matrix corresponding to a linear-ease pair of waypoints would be:

[0 0 0 1][A]   [p0]
[1 1 1 1][B]   [p1]
[0 1 0 0][C] = [ 0]
[3 2 1 0][D]   [ 0]

In fact, I see no reason why we can’t have three boundary conditions at one waypoint and one at the other, except that it would be confusing to the user. So let’s not do that.

The user should also be able to set the tangents of a new type of waypoint that I’ll just call “tangent”. In matrix form, this boundary condition becomes:
Tangent left:
[0 0 1 0][.] = [t1]

Tangent right:
[3 2 1 0][.] = [t2]

Note that when t1 or t2 is 0, this corresponds to the ease waypoint, as we would hope. Values t1 and/or t2 would be set by the user with handles or a dialogue box, as with the TCB spline. With a hypothetical new “tangent” waypoint, the user has complete control over cubic splines.

By the way, as long as I have your attention, let me also suggest a waypoint called “parabolic”, which corresponds with the boundary condition y’’’ = 0. Setting the third derivative to zero results in the same effect (A=0) regardless of which end of the spline you apply it to. This could be used as the left or right waypoint but not both, since it would leave the system underdetermined. I suggest if the user attempts two consecutive parabolic waypoints, Synfig instead kicks out an exception and just uses a linear spline to connect the two points. Here’s the corresponding boundary condition:
[1 0 0 0][.] = [0]

Currently, there’s no way to produce parabolic curves using waypoints except by either implementing a linear waypoint and integrating or calculating the tangents of the parabola and entering them manually into a TCB spline.

That’s what I’ve come up with so far. I also have an idea for a waypoint I call “super-linear” which would not only have zero second derivative in its proximity (as with the linear waypoint) but would also have continuous first derivative. The issues I’m running into are that such a waypoint would require fourth-degree polynomials and the boundary conditions of these polynomials would have to be “chained together” so they are no longer independent. This means inverting the matrix could be computationally intensive and might not even be stable. If we were to implement such a waypoint, I suggest that we restrict them so they can’t be used consecutively or no more than, say, two or three times in a row. I’m also having trouble getting the number of boundary conditons to match up with the number of unknowns.

All right, I know the developers here like programming more than math, so let me lay out my pseudocode. Keep in mind I’m not a programmer and I tend to make mistakes. This code would need to be debugged and cleaned up.

#include <matrix_algebra>  //I'm assuming there's some standard matrix operations package for C++.  Is it already loaded?
type_1 = first waypoint's type
type_2 = second waypoint's type
p1 = first waypoint's value
p2 = second waypoint's value

if type_1 == constant || type_2 == constant {
  (Handle constant waypoint case much as we do now.  Spline takes value p1 until time of second waypoint, at which point it's p2.)
elseif type_1 == parabola && type_2 == parabola{  //Handles parabola-parabola exception and produces a linear interpolation instead.
  D = p1  //There are a bunch of ways to handle this case.  I've just set the coefficients directly.
  C = p2-p1
  A = 0
  B = 0
else {
  BC_matrix[1] = [0 0 0 1]  //First row of the boundary conditions matrix.
  BC_matrix[2] = [1 1 1 1]  //Second row.

  BC_values[1] = [p1]  //This is the column vector on the right hand side of the equation.
  BC_values[2] = [p2]  //The first two rows are always p1 and p2.
  BC_values[3] = [0]
  BC_values[4] = [0]  //Most BCs set something equal to zero and it's good to have these default to 0 to handle exceptions.

  if type_1 == ease {
    BC_matrix[3] = [0 0 1 0]
  elseif type_1 == linear {
    BC_matrix[3] = [0 1 0 0]
  elseif type_1 == parabola {
    BC_matrix[3] = [1 0 0 0]
  elseif type_1 == tangent {
    BC_matrix[3] = [0 0 1 0]
    t1 = first waypoint's tangent  //The tangents might need to be multiplied/divided by the time interval.  I'm not sure...
    BC_values[3] = [t1]

  if type_2 == ease {
    BC_matrix[4] = [3 2 1 0]
  elseif type_2 == linear {
    BC_matrix[4] = [3 1 0 0]
  elseif type_2 == parabola {
    BC_matrix[4] = [1 0 0 0]
  elseif type_2 == tangent {
    BC_matrix[4] = [3 2 1 0]
    t2 = second waypoint's tangent  //The tangents might need to be multiplied/divided by the time interval.  I'm not sure...
    BC_values[4] = [t2]

  inverted = matrix_inverse(BC_matrix)  //Use whatever matrix inversion function is built into the package.
  coefficients_vector = inverted*BC_values  //Note that this is matrix multiplication.
  A = coefficients_vector[1]
  B = coefficients_vector[2]
  C = coefficients_vector[3]
  D = coefficients_vector[4]

// The above values work just fine if the splines are defined using normalized time.  Otherwise, we have to change them, as below:

t1 = time of first waypoint
t2 = time of second waypoint
delta_t = t2 - t1

A_new = 1/delta_t^3 * A
B_new = -3*t1/delta_t^3 * A + 1/delta_t^2 * B
C_new = 3*t1^2/delta_t^3 * A - 2*t1/delta_t^2 * B + 1/delta_t * C
D_new = -t1^3/delta_t^3 * A + t1^2/delta_t^2 * B - t1/delta_t * C + D

spline = A_new*t^3 + B_new*t^2 + C_new*t + D_new  //I'm pretty sure this line doesn't really belong here as the coefficients are instead fed into a different subroutine.

Please let me know if you’d like any clarification on anything I’ve written. I know overhauling the waypoint system is asking a lot, but I hope the effort I’ve put into this post is an indication of how much I believe this should be implemented. With my pseudocode as a guide, it might not even take too long to put together. I’m confident that if someone takes the time to make these changes, you’ll be really pleased with what pops out.

(phew, I made it)
Alright, if I’m understanding this correctly, it sounds like you’re aiming to add control handles to the waypoints in the graph editor so that they can be manipulated like splines on the canvas. I think that sounds like a great addition. It’s similar to what Blender has which works extremely well in my opinion.

If the parabola stuff becomes too troublesome then I suggest pushing it back to a later point on the hypothetical road map. It’s certainly valuable, but as an art focused program, most users aren’t too bothered that their cartoon bouncing ball is following a cubic arc instead of a parabolic one. That said, I would suggest to again mimic Blender when it comes to implementation. It’s parabolic option removes control options at the end point.

I’m not sure what your “super-linear” concept is going for. Could you describe a use case?

Finally, I’m not a programmer either, but coincidentally I have been studying Bezier/Hermite curves recently, so I’ll weigh in with what I’ve learned in regards to your code proposal. Take it with a big grain of salt though:

Cubic Hermite curves are defined by their boundary conditions which include the start point P0, end point P1, starting tangent u0, and ending tangent u1. Through some math wizardry, we can plug in the boundary conditions solve the original equation P(t) = At^3 + Bt^2 + Ct + D into the following form:
P(t) = P0*H0(t) + u1*H1(t) + P1*H2(t) + u1*H3(t)
where H_n are the Cubic Hermite Bases
H0 = (1 + 2t)(1 - t)^2
H1 = t(1 - t)^2
H2 = (t^2)(3 - 2t)
H3 = (-t^2)(1 - t)
This form is useful because it provides a single formula for defining any and all Cubic Hermite curves. Just plug in the 4 inputs and you have a curve. Additionally, the basic boundary conditions (linear, ease, tangent) can be handled by setting u0 and u1 appropriately.
I think my point here is that it may not be necessary to perform all of that matrix manipulation because there is already a closed form solution. The formula currently exists in the code in curve.h.
I apologize if I’m missing the intention behind some of your code. I admit that I am reaching out of my depth here.

First of all, thanks for reading my post! I was worried it would be buried.

Not necessarily. Tangents could be set manually via a pop-up much as the TCB parameters can be set currently. Of course, once boundary conditions are implemented as I propose above, it becomes trivial to add handles. (“Trivial” I say, still not a programmer, not the person who would have to go through the process of creating the damn thing.)

In my pseudocode above, adding parabolic waypoints is not substantially more difficult than any other changes. Also, a lot of my own uses of Synfig use parabolic splines, so maybe I’m a little biased. Of course, if for whatever reason they’re difficult to implement, the user can manually calculate the desired tangent.

I don’t have anything specific in mind, but I thought of it when thinking about the boundary conditions associated with linear waypoints. There is no constraint on linear waypoints-- currently or in my proposal-- that forces the derivative to agree on either side of the function. This means that linear waypoints introduce corners, which to me sounds rather “not-so-linear”. I wanted to propose something that would straighten them out so the derivatives agree on either side. Unfortunately, I think this makes the problem significantly more difficult and I can’t match up the number of boundary conditions with the number of variables, so I’m inclined to file it away as a fanciful idea that isn’t worth implementing. The user could still use a “tangent” waypoint and manually set the tangents equal on either side. The downside to this is that the second derivative would likely not vanish in the vicinity of the waypoint, which is what the linear waypoint is supposed to accomplish.

I am familiar with cubic Hermite splines and they are currently used in Synfig. Check back to the first post of this topic. Cubic Hermite splines are, as you say, great for setting the values and first derivatives of arbitrary splines. They are ill-suited, however, for specifying second or third derivatives, both of which I’ve done above.

Let’s work with a concrete example. Suppose we have a spline defined over normalized time (0<t<1) that takes the value 0 at the left end and 1 at the right end. Let’s say we also want the derivative to be zero at the right end and the second derivative to be zero at the left end. This last condition, concerning the second derivative, is one that can’t be handled easily by cubic Hermite splines. The boundary conditions with respect to the derivatives I’ve set correspond to a linear waypoint at the left end and an ease in/out waypoint at the right end, so this isn’t some abstract exercise.

We first have to take two derivatives of all our Hermite splines:
H0’’ = 12t - 6
H1’’ = 6t - 4
H2’’ = -12t + 6
H3’’ = 6t - 2

(I did those in my head. They might be wrong.)

We can still use H0, H2, and H3 to satisfy three of the boundary conditions, but H1’s coefficient remains unknown. In equation form, this is P(t) = 0*H0 + A*H1 + 1*H2 + 0*H3, where A is our unknown coefficient. The second derivative condition is then:
P’’(0) = 0 = A*H1’’ + H2’'
0 = -4A + 6
A = 3/2

Notice how the algebra is more extensive than usual for cubic Hermite splines. We can scale up or down this result for free, which is nice, but that amounts to programming in several different cases (i.e., how to handle tangent-tangent splines, tangent-linear splines, tangent-parabola splines, ease-parabola splines, etc…). All of this is equivalent to the same amount of work as is required to invert the matrix, as I’ve done in the pseudocode.

If you’d like, I can adjust my pseudocode to output coefficients of cubic Hermite splines. I promise it won’t really offer any advantages.