Sign in to follow this  
DarkDemon

Defeating lag with cubic splines

Recommended Posts

Hello,

I've recently been exploring different interpolation methods. I wanted to try out cubic spline interpolation based on the article written here: http://archive.gamedev.net/reference/articles/article914.asp

I've had a quick search around the forum and noticed quite a few other people have had problems with this article, it doesn't appear to be written very clearly, and I'm currently stuck trying to implement my own version in Java.

This post seems to post a near complete solution bar a few mistakes it seems but i'm still not clear on it.

http://www.gamedev.net/topic/473632-defeating-lag-with-cubic-splines---help-needed/


From the article I'm also wondering if Cord 3 and 4 should be flipped?

My current implementation is as follows, and a new position get updated every 200ms,
http://pastebin.com/Zz1ALBZP

Some debug data:
http://pastebin.com/8UQHQq2X

My interpolated positions always return 0, and I was wondering if anyone has any success implementing the article, and if anyone could clarify the co-ords that would be great.

Many thanks

Share this post


Link to post
Share on other sites
[font="Arial"][size="2"]Ok, so you have a problem with the bezier equation literally? Or are you talking about networking here. And trying to smooth things up?[/size] [size="2"]As for the equation, it's as simple as this:[/size]
[size="2"]t = Where you want to be on the curve, between 0 and 1.[/size]
[size="2"]p0 = starting point[/size]
[size="2"]p1, p2 = control points, see the images in the Wiki to understand control points: [url="http://en.wikipedia.org/wiki/B%C3%A9zier_curve"]http://en.wikipedia....C3%A9zier_curve[/url][/size]
[size="2"]p3 = destination point[/size]

[size="2"][code]
float invT = 1.0f - t;
pos = p0 * (invT * invT * invT) + p1 * 3 * t * (invT * invT) + p2 * 3 * (t * t) * invT + p3 * (t * t * t);
[/code][/size]

[size="2"]I will make it very rough, as it was [/size]slightly[size="2"] more complex than this in the Madballs game. With prediction and taking time into consideration.[/size]
[size="2"]So let say you have 2 positions with 2 velocity, I would create the control points this way:[/size]
[size="2"][code]
float distanceBetweenPoints = Vector3::Distance(pos1, pos2);
float controlPointLength = distanceBetweenPoints / 3;
Vector3 p0 = pos1;
Vector3 p1 = pos1 + vel1.Normalize() * controlPointLength;
Vector3 p2 = pos2 - vel2.Normalize() * controlPointLength; // Don't forget to negate here.
Vector3 p3 = pos2;
[/code][/size][/font]

Share this post


Link to post
Share on other sites
Thanks, you helped clarify a few queries I had.

In terms of progress I now have this.

[url="http://www.youtube.com/watch?v=SjRHyqvMTr8"]http://www.youtube.c...h?v=SjRHyqvMTr8[/url]

There is certainly smooth movement being applied, but I'm think I'm facing a similar issue that you mentioned in your own thread [url="http://www.gamedev.net/topic/401827-lag-reduction-using-cubic-spline-alias-bezier/"]http://www.gamedev.n...e-alias-bezier/[/url] ? unless I'm mistaken.

Any thoughts? It's probably something obvious I'm missing..


Source:
[url="http://pastebin.com/ZtNc9Fhj"]http://pastebin.com/ZtNc9Fhj[/url]

It's certainly very getting very close now.

Share this post


Link to post
Share on other sites
You'll see that if u plot out the individual points of the [font="Arial"][color="#1C2837"][size="2"]bezier curve for a fix iteration of t, that the points don't maintain a constant spacing. This leads to what your seeing, the non-linear velocity of the vehicle along the curve.. Since this doesn't reflect the true motion of the vehicle, you'll have to correct it. The ways I've seen this done is to actually solve the curve and iteratively walk down it, manually maintaining the velocity..[/size][/color][/font]
[font="Arial"][color="#1C2837"][size="2"]
[/size][/color][/font]
[font="Arial"][color="#1C2837"][size="2"]Good Luck![/size][/color][/font]
[font="Arial"][color="#1C2837"][size="2"]
[/size][/color][/font]
[font="Arial"][color="#1C2837"][size="2"]-ddn[/size][/color][/font]

Share this post


Link to post
Share on other sites
[quote name='Daivuk' timestamp='1303412698' post='4801330']
Can you show the bezier curve?
with the 4 control points. We will see right away if at least that part you got right.
[/quote]

You're right the points are clearly wrong.

[media]http://www.youtube.com/watch?v=UuE3U2CV_Co[/media]


Start and end points are in red and white points, and the velocities that make up the direction are in green.

Share this post


Link to post
Share on other sites
Hello all,

I did some further tweaking and altered the formula based on Daivuk's post.

[media]http://www.youtube.com/watch?v=83Z7b7Uue1U[/media]

Certainly much better, but this looks like standard linear motion?

As far as I can tell the points appear to be in the right place.

http://pastebin.com/gtCTxK6n

Share this post


Link to post
Share on other sites
Since you're trying to match positions and velocity tangents, you might want to use a [url="http://en.wikipedia.org/wiki/Cubic_Hermite_spline"]cubic Hermite spline[/url] instead. It's functionally equivalent but would fit your representation better.

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

Sign in to follow this