Skip to main content
GameDev.net gamedev.net
🔒 Locked 🎮 Unity

Spline interpolation, Bezier / Hermite

Started by uglybdavis Mar 13, 2019 at 8:54 PM 8 replies 5.4k views
Original Post
uglybdavis
uglybdavis

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....

alvaro
alvaro

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.

taby
taby

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];
}
	
JohnnyCode
JohnnyCode
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 :(

alvaro
alvaro
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?


JohnnyCode
JohnnyCode
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!


JohnnyCode
JohnnyCode

Correction, in the end I combine them like this

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

JohnnyCode
JohnnyCode

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

fleabay
fleabay

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)


🙂🙂🙂🙂🙂<←The tone posse, ready for action.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.