Sign in to follow this  
BeanDog

Cubic splines [SOLVED]

Recommended Posts

I've implemented a basic version of cubic splines to "defeat lag" according to the article on this site. To select my 4 points and calculate the constants that represent the spline, I do the following:
//My current location
m_v[0] = m_vOldLocation;
//My location in 1 second, using old data.
m_v[1] = m_vOldLocation + m_vOldSpeed;
//My new location one second before fTimeToArrive seconds pass.
m_v[2] = m_vLocation + m_vSpeed*fTimeToArrive - m_vSpeed;
//My new location after fTimeToArrive seconds.
m_v[3] = m_vLocation + m_vSpeed*fTimeToArrive;

m_fA = m_v[3] - 3*m_v[2] + 3*m_v[1] - m_v[0];
m_fB = 3*m_v[2] - 6*m_v[1] + 3*m_v[0];
m_fC = 3*m_v[1] - 3*m_v[0];
m_fD = m_v[0];
The problem is that the splines have undesirable results. The article stated that this is how the 4 points were supposed to be calculated (I'm ignoring acceleration for now).
Quote:
Coordinate 1 = Starting position Coordinate 2 = Position after 1 second using starting velocity Coordinate 3 = Position after 1 second using reversed ending velocity = Coordinate 4 - Ending velocity Coordinate 4 = Ending position
The problem occurs when m_vOldLocation == m_vLocation and m_vOldSpeed==m_vSpeed. Under such circumstances, the client is already on track to be in the same place the server will be after fTimeToArrive seconds pass. So the spline ought to provide a near-linear interpolation between m_vOldLocation and m_vLocation. Instead, I get a spline that goes way ahead of the server position, then way behind, then eventually arrives in the correct place. What am I doing wrong? ~BenDilts( void ); [Edited by - BeanDog on October 8, 2005 10:13:36 AM]

Share this post


Link to post
Share on other sites
The article is either incomplete or you're missing some implementation. The formula for a cubic spline is:

f(t) = b0B30(t) + b1B31(t) + b2B32(t) + b3B33(t)

Where B3n are Bernstein polynomials such that:

B30(t) = (1 - t)3
B31(t) = 3t(1 - t)2
B32(t) = 3t2(1 - t)
B33(t) = t3


And bn are your control points. The article was correct about generating b1 and b2, which are your second and third control points, however multiply your velocity by 1/3 before adding it to b0 and subtracting it from b3 to get b1 and b2, respectively. This is because the derivative at the endpoints is three times the difference between the endpoints and their adjacent control points, or in other words:

p'0 = 3(b1 - b0)
p'1 = 3(b3 - b2)

b1 = b0 + (p'0/3)
b2 = b3 - (p'1/3)

Share this post


Link to post
Share on other sites
I really appreciate your reply. It almost fixed the problem. I multiplied not by 1/3, but by fTimeToArrive/3. I'm not sure of the mathematical details of why this works great, but it does. Any ideas for a mathematical explanation?

Edit: I'm assuming in my code that the time variable in the final spline equation ranges from 0 to 1, regardless of the actual time taken to traverse the spline. I could also fix this by changing the range of that variable.



~BenDilts( void );

[Edited by - BeanDog on October 7, 2005 11:55:35 PM]

Share this post


Link to post
Share on other sites
It's really implementation-dependent. As long as you have the correct Bernstein polynomials, then you can chose anything for your control points and it will always start at b0 and end at b3 with a range of [0,1] for time. The endpoint derivative requirement is really used if you're connecting multiple cubic splines together to form one long curve. In that case, the curve simply looks the most natural if all the cubic splines adhere to that restriction. But otherwise you're free to manipulate them in any way that best suits your needs.

You say you almost fixed the problem. What exactly isn't working for you?

Share this post


Link to post
Share on other sites
Sorry for my vague second post, Zipster. Multiplying by 1/3 almost fixed my problem. Multiplying by fTimeToArrive/3 completely fixed my problem.

Thanks!



~BenDilts( void );

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