# Defeating lag with cubic splines

## Recommended Posts

DarkDemon    122
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 on other sites
Daivuk    413
[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 on other sites
DarkDemon    122
Thanks, you helped clarify a few queries I had.

In terms of progress I now have this.

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 on other sites
Daivuk    413
Can you show the bezier curve?
with the 4 control points. We will see right away if at least that part you got right.

##### Share on other sites
ddn3    1610
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 on other sites
DarkDemon    122
[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.

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

##### Share on other sites
DarkDemon    122
Hello all,

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

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 on other sites
kdmiller3    178
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.