I wrote an application in C# which controls a camera through a 3D environment.
At the moment the camera follows a path which is defined as an array of points, where each point is defined as: x, y, z & rotation for each axis (everything is a float)
The camera position between those points are computed by linear interpolation every frame.
Because this leads to very clunky movement, I want to implement cubic spline interpolation instead.
There are many different algorithms, but so far I set my eyes on the following, since those feel "more correct", which means they don't overshoot:
- Piecewise Cubic Hermite Interpolating Polynomial (PCHIP)
- Modified Akima piecewise cubic Hermite interpolation (MAKIMA)
My biggest problem is, that I am absolutely not a mathematician and I can't read and understand the gibberish found online for their definitions, so I need help translating it into code.
Constraints for the implementation
- Algorithm should use either PCHIP or MAKIMA (I am open for other "correct" approaches though)
- Interpolated values must be a function of time (t from 0 to {points.Length})
- Must run for 3D points, not only 2D
- Should not contain any external libraries if possible
Libraries
I have checked the following, but they either don't support 3D points, or interpolation by time (and aren't intuitive to use either... not even talking about the license here):
Here is a small code stump which I came up with to demonstrate what I am looking for:
static float[,] points = new float[,] {
{10, 10, 10},
{35, 5, 25},
{15, 30, 15}
};
static int numberOfPoints = points.Length / 3; // dividing for each stored float value per point: only x, y, z for simplification
static void Main()
{
List<float[]> pointsWithInterpolation = new(); // holding both known and interpolated points
float stepSize = 0.1f; // step size for t
for (int i = 0; i < numberOfPoints - 1; i++)
{ // loop for each spline segment
pointsWithInterpolation.Add(new float[] { points[i, 0], points[i, 1], points[i, 2] }); // add an allready known point to the list
for (float t = stepSize; t < 1f; t += stepSize)
{ // should run (1 / {stepSize} - 2) times
float[] interpolatedPoint = Interpolate(i + t);
pointsWithInterpolation.Add(interpolatedPoint); // add an interpolated point to the list
}
if (i == numberOfPoints - 1)
{ // add the very last point if we have finished the last segment
pointsWithInterpolation.Add(new float[] { points[i + 1, 0], points[i + 1, 1], points[i + 1, 2] }); // add an allready known point to the list
}
}
}
private static float[] Interpolate(float t)
{
// point indexes
int p1 = (int)t;
int p2 = p1 + 1;
int p0 = p1 == 0 ? 0 : p1 - 1; // if there are no previous point, set it to the first one
int p3 = p2 == numberOfPoints - 1 ? p2 : p2 + 1; // if there are no following points, set it to the last one
float x0 = points[p0, 0];
float x1 = points[p1, 0];
float x2 = points[p2, 0];
float x3 = points[p3, 0];
float y0 = points[p0, 1];
float y1 = points[p1, 1];
float y2 = points[p2, 1];
float y3 = points[p3, 1];
float z0 = points[p0, 2];
float z1 = points[p1, 2];
float z2 = points[p2, 2];
float z3 = points[p3, 2];
float x, y, z;
/* black magic hocus pocus happening here
x = ???;
y = ???;
z = ???;
*/
float[] point = new float[] { x, y, z };
return point;
}
So the question is: what is the formula for solving for x/y/z (the formula should be the same for each variable, but they use different variables).
Yes I know, this results in a constant number of interpolated points between the "real" ones, even if the distance of segments widely varies - I will tackle the issue of constant speed separately.
If I am not mistaken, every interpolation between p1 and p2 needs 4 values, so I set p0 equal to p1 for the very first segment and p3 equal to p2 for the last one to make up for non-existant points.
I haven't performance optimized the code, so I (hopefully) make it more clear/easy to understand what I try to do.
Of course I would also be thankful for code in other languages, as long as it fulfils the implementation constraints and doesn't use functions which aren't available in C# (and also no assembler please lmao)
