Jump to content
  • Advertisement
Sign in to follow this  
ramirofages

Hermite splines linear interpolation

This topic is 522 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, yesterday I implemented hermite splines with multiple waypoints for my camera movement, but I've noticed that when passing throught each point, the velocity slows down a little. I suppose that is related to the basis functions of the hermite, where they tend to smooth out at the start and end points.

Is it possible to change the interpolation so it uses linear velocity instead of a smoothed one? While maintaining the nice rounded curves that they generate.

 

To be clear, I'm incrementing the interpolator variable (t) in a linear way, but slows down a little when reaching the endpoints.

 

Cheers

Share this post


Link to post
Share on other sites
Advertisement

but I've noticed that when passing throught each point, the velocity slows down a little.

 
This is because near the knot there is more change in the tangent direction and less change in velocity.
Even if you would be able to move along the spline with constant velocity the result would appear less smooth at knots, so probably you would not be happy either.
(I'm pretty sure there is no closed form solution to this and you would need to use some iterative method)
 
Maybe it's better you use a bezier spline because it gives you more control but you need to calculate the 'handles' (You might know this from photoshop paths os vector illustration tools).
 
E.g. you have an array of waypoints, one way to do this for my example code is:
 
cp1 = waypont; // left knot
cp4 = waypont[i+1]; // right knot
cp2 = cp1 + (waypont[i+1] - waypont[i-1]) / 6; // left knot + left handle
cp3 = cp4 - (waypont[i+2] - waypont) / 6; // right knot + right handle
 
For each knot you endup having two handles, and if they have opposite direction but equal length the spline is C2 continuous.
The length defines the velocity at the knot, direction can be any, so you have better controll than with hermite or catmull rom etc.
 
 
 
 
    void EvaluateBezier4 (float &pos, float &tang, const float cp1, const float cp2, const float cp3, const float cp4, const float t)
    {
        float u = 1.0f - t;        
    
        float vvv = u*u*u;
        float vvu = u*u*t*3;
        float vuu = u*t*t*3;
        float uuu = t*t*t;
    
        pos =  vvv * cp1;
        pos += vvu * cp2;
        pos += vuu * cp3;
        pos += uuu * cp4;

        vvv = -3*u*u;
        vvu = -6*u*t + 3*u*u;
        vuu =  6*u*t - 3*t*t;
        uuu =  3*t*t;

        tang =  vvv * cp1;
        tang += vvu * cp2;
        tang += vuu * cp3;
        tang += uuu * cp4;
    }
Edit: If the distance between your waypoints varies widely, you may want to use a second 1D spline where the distances are used as controlpoints
(I mostly use catmull rom for this, eventually subdivding the controlpoints once so you have values at the knots AND the centers of each segment).
The output shall be used as a factor of how much you increase t for the other waypoint spline.

This makes velocity more (but never exactly) constant.
 
inline float CatmullRom1D (const float tF, const float k0, const float k1, const float k2, const float k3) 
	{
		float sF = 1.0f - tF;

		float g0 = k2 - k0;
		float g1 = k3 - k1;
		float gL = g0 * sF + g1 * tF;
		float x0 = k1 + (gL + g0) * tF * 0.25f;
		float x1 = k2 - (gL + g1) * sF * 0.25f;

		float tI = tF * tF * (3.0f - 2.0f*tF); // cubic
		return x0 * (1.0f - tI) + x1 * tI;
	}

	float CatmullRom1D (const float tSpline, const int numKnots, const float *knots, int const stride = 1) // clamps indices in range
	{
		float tW = tSpline * float(numKnots);
		float ftW = floor (tW);
		float tF = tW - ftW;

		int i1 = (int) ftW;
		int i2 = i1 + 1;
		int i3 = i1 + 2;
		int i0 = i1 - 1;

		if (i0 < 0) i0 = 0;
		if (i1 < 0) i1 = 0;
		if (i2 < 0) i2 = 0;
		if (i3 < 0) i3 = 0;

		if (i0 >= numKnots) i0 = numKnots-1;
		if (i1 >= numKnots) i1 = numKnots-1;
		if (i2 >= numKnots) i2 = numKnots-1;
		if (i3 >= numKnots) i3 = numKnots-1;

		return CatmullRom1D (tF, knots[i0*stride], knots[i1*stride], knots[i2*stride], knots[i3*stride]);
	}
Edited by JoeJ

Share this post


Link to post
Share on other sites

 

but I've noticed that when passing throught each point, the velocity slows down a little.

 
This is because near the knot there is more change in the tangent direction and less change in velocity.
Even if you would be able to move along the spline with constant velocity the result would appear less smooth at knots, so probably you would not be happy either.
(I'm pretty sure there is no closed form solution to this and you would need to use some iterative method)
 
Maybe it's better you use a bezier spline because it gives you more control but you need to calculate the 'handles' (You might know this from photoshop paths os vector illustration tools).
 
E.g. you have an array of waypoints, one way to do this for my example code is:
 
cp1 = waypont; // left knot
cp4 = waypont[i+1]; // right knot
cp2 = cp1 + (waypont[i+1] - waypont[i-1]) / 6; // left knot + left handle
cp3 = cp4 - (waypont[i+2] - waypont) / 6; // right knot + right handle
 
For each knot you endup having two handles, and if they have opposite direction but equal length the spline is C2 continuous.
The length defines the velocity at the knot, direction can be any, so you have better controll than with hermite or catmull rom etc.
 
 
 
 
    void EvaluateBezier4 (float &pos, float &tang, const float cp1, const float cp2, const float cp3, const float cp4, const float t)
    {
        float u = 1.0f - t;        
    
        float vvv = u*u*u;
        float vvu = u*u*t*3;
        float vuu = u*t*t*3;
        float uuu = t*t*t;
    
        pos =  vvv * cp1;
        pos += vvu * cp2;
        pos += vuu * cp3;
        pos += uuu * cp4;

        vvv = -3*u*u;
        vvu = -6*u*t + 3*u*u;
        vuu =  6*u*t - 3*t*t;
        uuu =  3*t*t;

        tang =  vvv * cp1;
        tang += vvu * cp2;
        tang += vuu * cp3;
        tang += uuu * cp4;
    }
Edit: If the distance between your waypoints varies widely, you may want to use a second 1D spline where the distances are used as controlpoints
(I mostly use catmull rom for this, eventually subdivding the controlpoints once so you have values at the knots AND the centers of each segment).
The output shall be used as a factor of how much you increase t for the other waypoint spline.

This makes velocity more (but never exactly) constant.
 
inline float CatmullRom1D (const float tF, const float k0, const float k1, const float k2, const float k3) 
	{
		float sF = 1.0f - tF;

		float g0 = k2 - k0;
		float g1 = k3 - k1;
		float gL = g0 * sF + g1 * tF;
		float x0 = k1 + (gL + g0) * tF * 0.25f;
		float x1 = k2 - (gL + g1) * sF * 0.25f;

		float tI = tF * tF * (3.0f - 2.0f*tF); // cubic
		return x0 * (1.0f - tI) + x1 * tI;
	}

	float CatmullRom1D (const float tSpline, const int numKnots, const float *knots, int const stride = 1) // clamps indices in range
	{
		float tW = tSpline * float(numKnots);
		float ftW = floor (tW);
		float tF = tW - ftW;

		int i1 = (int) ftW;
		int i2 = i1 + 1;
		int i3 = i1 + 2;
		int i0 = i1 - 1;

		if (i0 < 0) i0 = 0;
		if (i1 < 0) i1 = 0;
		if (i2 < 0) i2 = 0;
		if (i3 < 0) i3 = 0;

		if (i0 >= numKnots) i0 = numKnots-1;
		if (i1 >= numKnots) i1 = numKnots-1;
		if (i2 >= numKnots) i2 = numKnots-1;
		if (i3 >= numKnots) i3 = numKnots-1;

		return CatmullRom1D (tF, knots[i0*stride], knots[i1*stride], knots[i2*stride], knots[i3*stride]);
	}

Thank you so much for the detailed explanation and source code, will try to implement it then! Cheers

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!