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.