Jump to content
  • Advertisement
uglybdavis

Spline interpolation, Bezier / Hermite

Recommended Posts

When looking at bezier curves, it's easy to understand them intuitively as a few lerps between points. And they are fairly trivial to implement this way.

Vector3 SampleCurve(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, float t) {
	Vector3 q0 = Lerp(p0, p1, t);
	Vector3 q1 = Lerp(p1, p2, t);
	Vector3 q2 = Lerp(p3, p3, t);
	
	Vector3 r0 = Lerp(q0, q1, t);
	Vevtor3 r1 = Lerp(q1, q2, t);

	return Lerp(r0, r1, t);
}

From what i gather, the above is called de Casteljau's method.

However, you could also evaluate them using the bezier basis functions:

p = (1-t)^3 *P0 + 3*t*(1-t)^2*P1 + 3*t^2*(1-t)*P2 + t^3*P3 

Which is a lot less intuitive, but at least i can find some nice graphics to explain how the functions work:

300px-Bezier_basis.svg.png

 

When looking at cubic hermite splines, the only info i seem to find online is the less than intuitive basis funtions:

300px-HermiteBasis.svg.png

Implemented with some less than intuitive code:

float Hermite(float t, float p0, float m0, float p1, float m1) {
	float tt = t * t;
	float ttt = t * t * t;

	return 
		(2.0f * ttt - 3.0f * tt + 1.0f) * p0 +
		(ttt - 2.0f * tt + t) * m0 +
		(-2.0f * ttt + 3.0f * tt) * p1 +
		(ttt - tt) * m1;
}

Is there an intuitive, easy to explain way of interpolating cubic hermite splines similar to that of bezier curves? Maybe it's not just a few lerps, but it would really help to know if there is a way to explain this that doesn't involve having to look at the graph of basis functions....

Share this post


Link to post
Share on other sites
Advertisement

You specify a few features of the function:

  • the value at 0 (p0),
  • the value at 1 (p1),
  • the slope at 0 (m0),
  • the slope at 1 (m1).

The spline you get is the most natural curve (there is a precise statement of what that means) that satisfies those constraints.

I find them easier to understand than Bezier curves, actually.

Share this post


Link to post
Share on other sites
Posted (edited)

You get lost in the complexity, until out of the fog arises the general solution. One is best off remembering that the difference between two points is a vector.

// https://stackoverflow.com/questions/785097/how-do-i-implement-a-bézier-curve-in-c
vector_4 getBezierPoint(vector<vector_4> points, float t)
{
    int i = points.size() - 1;
	
    while (i > 0)
    {
        for (int k = 0; k < i; k++)
        {
            points[k].x += t * (points[k + 1].x - points[k].x);
            points[k].y += t * (points[k + 1].y - points[k].y);
            points[k].z += t * (points[k + 1].z - points[k].z);
            points[k].w += t * (points[k + 1].w - points[k].w);
        }

		i--;
    }
	
    return points[0];
}
	
Edited by taby

Share this post


Link to post
Share on other sites
On 3/13/2019 at 11:31 PM, alvaro said:

You specify a few features of the function:

  • the value at 0 (p0),
  • the value at 1 (p1),
  • the slope at 0 (m0),
  • the slope at 1 (m1).

The spline you get is the most natural curve (there is a precise statement of what that means) that satisfies those constraints.

I find them easier to understand than Bezier curves, actually.

Is there a way to functionaly extrapolate 0-1 value so that gains between p0 and p1 are linear? When I implemented it , p0 starts at zero motion, and slows down to zero motion at p1, no matter what the surroudning slopes dictate as derived from surrounding frames :(

Share this post


Link to post
Share on other sites
2 hours ago, JohnnyCode said:

Is there a way to functionaly extrapolate 0-1 value so that gains between p0 and p1 are linear? When I implemented it , p0 starts at zero motion, and slows down to zero motion at p1, no matter what the surroudning slopes dictate as derived from surrounding frames :(

You implemented it wrong... Could you show us what you did?

 

Share this post


Link to post
Share on other sites
Posted (edited)
On 3/15/2019 at 9:04 AM, alvaro said:

You implemented it wrong... Could you show us what you did?

I first make a cubic spline from four frames like this

  float x1 = (1.0 - weight) * (1.0 - weight) * (1.0 - weight);
    float x2 = 3.0 * weight * (1.0 - weight) * (1.0 - weight);
    float x3 = 3.0*weight*weight*(1.0-weight);
     float x4 = weight * weight * weight;

I then just linearily would combine those four scalars with the four vectors. But I instead follow like this, I derivate the cubic spline on 1/3 point and 2/3point coresponding to encapsulating frames like this:

 float deriv1 = 0.3333333;
    float x1d = -3.0 * (1.0 - deriv1) * (1.0 - deriv1);
    float x2d = 3.0 * (deriv1 - 1.0) * (3.0 * deriv1 - 1.0);
    float x3d = 6.0 * deriv1 - 9.0 * deriv1 * deriv1;
    float x4d = 3.0 * deriv1 * deriv1;

    float deriv2 = 0.6666666;
    float y1d = -3.0 * (1.0 - deriv2) * (1.0 - deriv2);
    float y2d = 3.0 * (deriv2 - 1.0) * (3.0 * deriv2 - 1.0);
    float y3d = 6.0 * deriv2 - 9.0 * deriv2 * deriv2;
    float y4d = 3.0 * deriv2 * deriv2;

I then take those 8 scalaras and combine all frame vectors with x1d-x4d and combine all frame vectors with y1d-y4d. I then send those two vectors as the two slopes along with encapsulating frame vectors to this Cubic Hermite Spline

  float x1 = 2.0 * weight * weight * weight - 3.0 * weight * weight + 1.0;
    float x2 = weight * weight * weight - 2.0 * weight * weight + weight;
    float x3 = -2.0 * weight * weight * weight + 3.0 * weight * weight;
    float x4 = weight * weight * weight - weight * weight;

And combine them like this

x1*slope1+x2*encapsulatingframevector1+x3*slope2+x4*encapsulatingframevector2

The weight going from zero to one it gives me start-stop motion between the two frames.

Thanks!

 

Edited by JohnnyCode
serious corrections

Share this post


Link to post
Share on other sites

Correction, in the end I combine them like this

x1*encapsulatingframevector1+x2*slope1+x3*encapsulatingframevector2 +x4*slope2

Share this post


Link to post
Share on other sites

And by better observation I have a feeling it is actualy working, does it seem all correct as it is?

Share this post


Link to post
Share on other sites
Posted (edited)

Check out this video at 34:22. I would recommend watching the whole video, it is awesome! (it says Unity but it is generally applicable)

 

Edited by fleabay

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!