Sign in to follow this  
Defrag

[Solved] Quaternions: Extrapolating a rotation based on previous samples

Recommended Posts

I'm currently making a networked game and I've got some basic dead-reckoning up and running. Every time the client receives a timestamped update from the server containing information about an object, the update data (position, velocity, orientation) is placed in that object's history list (with newest updates at the start). I'm using quaternions for my orientations. Anyway, objects carry on along a path defined by their last known position & velocity while I wait for newer updates. Now I'm attempting to perform a similar operation for the orientation of an object. I.e. I want to look at the second latest and latest orientations the server has sent me and extract a quaternion representing the difference between those angles. Anyway, that much is plain sailing (I think!). What is troubling me is that the server snapshots are arbitrarily spaced (as I'm not guaranteed to receive them) and my client application's frame time is also arbitrary. Basically, what I'm asking is: If I know that an object's server-confirmed orientation was q1 at t1 and q2 at t2 and the time difference between those snapshots was t2-t1 seconds, how do I determine what the rotation I need for the current frame is? I.e. I need to relate the angular difference between those two snapshots with the rotation this will produce for an arbitrary frame time (I'm assuming the rotation continues at the current speed to start with). Apologies if this is not terribly clear. Blunt version: I know object x rotated y amount over a period of z. My client has advanced w seconds since the last frame. Given this data, how do I extrapolate to find the rotation for this frame? Here's my initial stab at it up 'til finding the difference quaternion. I *think* my code is OK thus far, but please correct me if I've messed up. D3DX reverses quaternion multiplication so it always confuses me slightly. The spatial history structure just contains the position, velocity & orientation plus a client & server timestamp. In this case I'm just interested in the orientation & server timestamps.
void CNode::Predict( float fTimeDelta ) // fTimeDelta = time elapsed in seconds since last frame
{	
	....

	// angular estimates.  We need at least 2 items in the list to try this
	if( m_spatialHistoryList.size() > 1 )
	{			
		std::list< spatialHistory_t >::const_iterator i = m_spatialHistoryList.begin();
		
		// get the two most recent orientations as confirmed by the server
		spatialHistory_t shCurr = (*i);
		spatialHistory_t shOlder = (*++i);		
        
		// given two quaternions, q1 and q2, a quaternion representing the difference between each is
		// quatDiff = q1^-1 q2 where q1^-1 is the inverse.  Use conjugate instead since our quats are unit length.
		// Once we have this value, we have the difference for a given time period.
		D3DXQUATERNION rotationDelta, oldInverse;
		D3DXQuaternionConjugate( &oldInverse, &shOlder.sh.orientation );
		D3DXQuaternionMultiply( &rotationDelta, &oldInverse, &shCurr.sh.orientation );
                
		// get the length of time taken to move between these two orientations and convert MS to S
		DWORD dwTimeDeltaBetweenUpdates = shCurr.dwServerTimeStamp - shOlder.dwServerTimeStamp;
		float fSecsBetweenUpdates = (float)dwTimeDeltaBetweenUpdates * 0.001f;

		// We know the rotation difference and the time taken to travel between these two orientations
		// so now we need to work out what the equivalent rotation would be for the period fTimeDelta

// what now?


	}
}



I'm thinking that I need to work out the frame time as a fraction of the time between the last two updates, then exponentiate by this amount? Any help appreciated. [Edited by - Defrag on December 12, 2006 4:07:35 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Defrag
I'm thinking that I need to work out the frame time as a fraction of the time between the last two updates, then exponentiate by this amount? Any help appreciated.
I don't have much experience with networking, but what you describe sounds reasonable. In pseudocode, it might look something like this:
quaternion last_delta = quaternion_difference(
next_most_recent_sample,
most_recent_sample
);
quaternion delta = quaternion_exponentiate(
last_delta,
time_step / last_time_step
);
quaternion new_orientation = quaternion_concatenate(
current_orientation,
delta
);
I think this could also be re-arranged to take advantage of the slerp() function:
quaternion last_delta = quaternion_difference(
next_most_recent_sample,
most_recent_sample
);
quaternion target_orientation = quaternion_concatenate(
current_orientation,
last_delta
);
quaternion new_orientation = slerp(
current_orientation,
target_orientation,
time_step / last_time_step
);
I might have messed something up somewhere, but you might give one or the other of those a try and see what sort of results you get.

Share this post


Link to post
Share on other sites
I know you can use slerp (spherical linear interpolation) to smoothly interpolate between two quaternions. With regular lerp on points, when you let 't' go outside the usual [0,1] range you get extrapolated values that form a line, as expected. I'm wondering if the same property holds true for slerp. If it does, then all you'd have to do is slerp between q1 and q2 using the interpolating value (t-t1)/(t2-t1) with the current time being 't'.

Share this post


Link to post
Share on other sites
Thanks guys. I'm going to give the first suggestion a try as it more closely mirrors what I had in my head, so it should be easier to implement. Just need to figure out how to do the exponentiation now (I don't think D3DX provides a function to exponentiate) but I have a textbook to get the formula from.

I'll report back when I get it working (or bugger it up).

Share this post


Link to post
Share on other sites
Well, that was pretty much painless. It worked first time for my space ship which is controlled by the user. The server runs @ 20 fps, but the client runs as fast as I can render it -- it's smooth :).

My asteroids are really jerky but that's just because of a program logic conflict, I think (the asteroid's own update function is spinning it independently, so I'll have to sort out that later).

I'll move the exponentiation calculation (nabbed from the rather excellent 3D Math Primer for Graphics and Game Development) into its own little function, but here's the code:

// angular estimates.  We need at least 2 items in the list to try this
if( m_spatialHistoryList.size() > 1 )
{
std::list< spatialHistory_t >::const_iterator i = m_spatialHistoryList.begin();

// get the two most recent orientations as confirmed by the server
spatialHistory_t shCurr = (*i);
spatialHistory_t shOlder = (*++i);

// given two quaternions, q1 and q2, a quaternion representing the difference between each is
// quatDiff = q1^-1 q2 where q1^-1 is the inverse. Use conjugate instead since our quats are unit length.
// Once we have this value, we have the difference for a given time period.
D3DXQUATERNION rotationDelta, oldInverse;
D3DXQuaternionConjugate( &oldInverse, &shOlder.sh.orientation );
D3DXQuaternionMultiply( &rotationDelta, &oldInverse, &shCurr.sh.orientation );

// get the length of time taken to move between these two orientations and convert MS to S
DWORD dwTimeDeltaBetweenUpdates = shCurr.dwServerTimeStamp - shOlder.dwServerTimeStamp;
float fSecsBetweenUpdates = (float)dwTimeDeltaBetweenUpdates * 0.001f;

// We know the rotation difference and the time taken to travel between these two orientations
// so now we need to work out what the equivalent rotation would be for the period fTimeDelta

// Theory: Get the frame time as a fraction of the delta between the two confirmed updates
// then exponentiate the quaternion rotationDelta by this value like so:
// fExpVal = fTimeDelta / fSecsBetweenUpdates
// quaternion finalAngle = quaternionExponentiate( rotationDelta, fExpVal )

float fExpVal = fTimeDelta / fSecsBetweenUpdates;

if( fabs( rotationDelta.w ) < .9999f )
{
float fAlpha = acos( rotationDelta.w );
float fNewAlpha = fAlpha * fExpVal;
rotationDelta.w = cos( fNewAlpha );
float fMult = sin( fNewAlpha ) / sin( fAlpha );
rotationDelta.x *= fMult;
rotationDelta.y *= fMult;
rotationDelta.z *= fMult;
}

D3DXQuaternionMultiply( &m_spatial.orientation, &m_spatial.orientation, &rotationDelta );
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Defrag
Just need to figure out how to do the exponentiation now (I don't think D3DX provides a function to exponentiate)...
You might check out the function D3DXQuaternionToAxisAngle(), since essentially what you want to do is extract the axis and angle of rotation from a quaternion, scale the angle, and then construct a quaternion from the axis and the scaled angle.

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