#### Archived

This topic is now archived and is closed to further replies.

# cubic spline interpolation/extrapolation

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

## Recommended Posts

Before I begin to explain, I just want to say I've searched through the forum and haven't found any information to solve this problem. I have read previous posts that seem to be the same problem I'm having, but no good explainations (if any) as to why the problem is occuring and how to solve it. I'm using cubic splines to smoothly move from position to position in my network game. I'm using it on ball position updates for a testing ground (knowing that cubic splines aren't helping much due to the linear nature of ball movement), which will result in use throughout the game on all other moving objects (goalies, players, etc.). I have everything setup _almost_ correctly. The ball moves along the correct path, but jitters back a forth a small amount (say 10 pixels or so) along the path of its current position from its last position. I'm sending updates from the server to the client every 100ms. I've tested using values of 250ms and 50ms with various results. The higher the update frequency (50ms), the more jitters I seem to notice, with less jitters noticable with a lower frequency (250ms). This leads me to believe the problem is somewhere in the handling of new position update packets. The creating of the spline to be more precise. This is really only a guess at the moment. code I'm using when recieving a new position update packet:
double newx = (double)(update->ballx + ( newmx * (double)(gClient->peers[0].roundTripTime / 2) / (double)1000.0) );
double newy = (double)(update->bally + ( newmy * (double)(gClient->peers[0].roundTripTime / 2) / (double)1000.0) );

ball.newx = newx;
ball.newy = newy;
ball.newmx = newmx;
ball.newmy = newmy;

double distance = sqrt(pow(ball.x - newx, 2) + pow(ball.y - newy, 2));

// threshold check
if(distance > BALLSPEED[gSettings.BallSpeed] * 24){
ball.x = newx;
ball.y = newy;

for(int i = 0; i < 4; i ++){
ball.spline.x = ball.x;
ball.spline[i].y = ball.y;
}

} else {
ball.spline[0].x = ball.x;
ball.spline[0].y = ball.y;
ball.spline[1].x = ball.x + ( ball.mx * (double)((double)gServerUpdateMS / (double)1000.0) );
ball.spline[1].y = ball.y + ( ball.my * (double)((double)gServerUpdateMS / (double)1000.0) );
ball.spline[2].x = newx;
ball.spline[2].y = newy;
ball.spline[3].x = newx + ( newmx * (double)((double)gServerUpdateMS / (double)1000.0) );
ball.spline[3].y = newy + ( newmy * (double)((double)gServerUpdateMS / (double)1000.0) );

}

gLastUpdateTick = timeGetTime();

code I'm using each frame to update the ball render position
struct DPOINT {
double x;
double y;
};

double delta = (double)(timeGetTime() - gLastUpdateTick) / (double)1000.0;

if(delta <= (double)((double)gServerUpdateMS / (double)1000.0)){
// still following spline path
DPOINT pos = GetSplinePos(ball.spline, (delta / ((double)gServerUpdateMS / (double)1000.0)));

ball.x = pos.x;
ball.y = pos.y;

} else {
// fall back off dead reckoning
ball.x = ball.newx + (ball.newmx * delta);
ball.y = ball.newy + (ball.newmy * delta);

}

This is a great thread I have read and where most of the implementation has come from: http://www.gamedev.net/community/forums/topic.asp?topic_id=39162 -Brad [edited by - bmm on February 28, 2004 4:20:20 PM]

##### Share on other sites
I neglected to mention a few things. I'm using the free ENet network library which continual updates a roundTripTime variable often. As you can see, I'm using this to predict where the current ball position is on the client (taken in consideration for half the round trip for the data to get to the client from the server). The average ping times I've been testing with have been between 20ms and 30ms.

[edited by - bmm on February 27, 2004 4:35:37 PM]

##### Share on other sites
Well there will always be a large descrepancy between the predicted position of the ball and the incoming positions due to the lack of a synchronizing function.

Even though your using 1/2 ping, it can fluxate between 20-30 ms due to network load or cpu load. So just using 1/2 ping your ball may be +- 10 ms from where it might be.

If the ball was moving say 100 pixels/ sec, thats .1 pixel per ms. It will jitter +- 1 pixel per update. As you can see the faster the speed the more larger the jitter and the more often the update rate, the more often the jitter.

From my exp, you'll see about a standard deviation of pings of 1/3 of the users roundtrip ping. So at 60 ms ping you will see about +- 20 ms, so not only do they get more lag, but they also will get a larger jitter effect, a double whammy!

To get true smoothing you can do 2 things. Interpolate the incoming predicted position to the current position over time, or use a better synchonrization algorithim, like NTP.

There has been many dissucsions of both methods on this group, just look through the archive, for timming synchronzition.

edit: I should also note, that even though your reporting 20-30 ms for ping, your internal update rate has a large impact upon the effective latency. The effective latency is taking into account the natural update rate of your simulation and also the methods in which you recive data (async,blocking,threaded etc).

So even though your getting 20-30 ms from Enet, your effective latency could be 100+ ms, if your updating your simulation at 10x/sec. That or the packet could be sitting on the queue too long before its processed adding more effective latency.

Well Good Luck!

-ddn

[edited by - ddn3 on February 28, 2004 8:59:25 PM]

##### Share on other sites
I''m implementing a performance timer class (QueryPerformanceCounter) to replace timeGetTime both in my project and the ENet network library that I use (actually, ENet uses GetTickCount, which is even worse) in hopes of gaining atleast 10ms resolution and more accurate ping times for use with the syncing. I''ve looked for some sample NTP or SNTP client examples, but haven''t had any success finding anything yet.

##### Share on other sites
check this out:
http://www.mine-control.com/zack/timesync/timesync.html

##### Share on other sites
rookie:
The ENet library already does that for me.

I've done a lot more testing and now I think the problem is with transitioning from spline to spline each update. I slowed down the simulation to 1 update per second and drew the control points on the screen for reference. Whenever it recieves an update the new spline is setup correctly, and the ball starts moving on it's spline path (the path generated for the next second) but slows to a stop half way through the path and then precedes to jump to the start of the new spline when the new update packet arrives. This is why I'm getting the jitters, but I still can't figure out what I'm doing wrong. I really don't think it has anything todo with latency, because I'm testing it on the same machine and the ball slows to a stop exactly half way through the spline path (by that I mean the actually stop point is the half-way point, not when the ball begins to slow down).

[edited by - bmm on February 29, 2004 7:30:56 AM]

##### Share on other sites
Hmm so the object stops at the midway point of the spline? So extrapalting that you update the client every 100 ms, and splines are driven the time, at 50ms the object is only at 1/2 the predicted point.

Are you taking into account the speed of the object and factoring that in to distanced traveled? You should be aware the spline equation doesn''t produce equally spaced points for a given linear incrementing value of time. You will have to use an incremental algorithim to find the true position of an object given a linear velocity. I suspect that is the problem.

Good Luck!

Man that thread brings up some old memories

-ddn

##### Share on other sites
I understand what you are saying, but how would I go about implementing "an incremental algorithim to find the true position of an object given a linear velocity". I thought about altering the delta variable that gets passed to the spline function in order to account for the objects speed so it returns the correct position along the spline, but after rereading what you said again, it doesn't sound like this is how I should be doing it. Maybe I am misunderstanding what you are saying. Even if it is the delta variable I should be adjusting, I don't understand the math behind adjusting the delta variable to account for the objects speed. Could you open up the door to the light a little more.

[edited by - bmm on February 29, 2004 12:27:32 AM]

##### Share on other sites
I''ll have to get back 2 you on this bmm. It''s not difficult to calcuate the length of the spline using the iterative approach. Basically you divide the spline in half and recursively do that until your satistfied.

For your purposes though, you need to break the spline into equal subdivisions, you would use the above alogorithim to subdivide the spline. Though you would want to cache this calcuation to avoid recomputing the subdivisions again and again. However after reading all the evidence, I suspect its another problem, unfortunatly im very busy this week, I''ll look into it more on the weekends.

Good Luck!

-ddn

##### Share on other sites
What do you have in mind for other possibilities to the cause of the problem? After reading your last reply I thought immediately "that has to be it!". I thought about how the spline knows nothing about the velocity of an object. It's just given 4 points and spits out an end point based on the time given between t0 and t1. This assumes a constant velocity, which is not the case. The ball, in this example, will always be accererating, decelerating, or stopped.

Your last post kind of confused me so I'll wait till this weekend and hopefully you can help me squash this problem once and for all.

[edited by - bmm on March 3, 2004 4:20:22 PM]

1. 1
2. 2
Rutin
20
3. 3
khawk
18
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633762
• Total Posts
3013727
×