• Create Account

### #ActualL. Spiro

Posted 11 September 2013 - 10:00 PM

So the thing is, interpolation is almost unavoidable if you choose such technique, because even if your sampling frequency is too high, missmatches between the playback framerate and the framerate it was encoded with can cause artifacts.

Another issue worth mentioning is that high sampling frequency (i.e. 60fps) cause the memory consumption to skyrocket. A modestly detailed walk animation loop for a human rig with around 50 bones sampled @60fps can easily reach 20 MBs. And you won't get much more detail/quality than sampling at 15-30fps (for a videogame).
Also considering that computing power keeps improving (and animation is highly parallelizable) but memory bandwidth growth is stalled, if you're planning to have hundreds of animated objects in your scene, interpolating with relatively low sampling frequencies could give you much more performance than just preprocessing the whole thing at high framerates and playing it with no interpolation.

This is handled by adding a redundancy elimination after the sampling stage.
First you sample between key frames at a fixed rate as mentioned.

Then you go over every triplet of samples, for example froms 0, 1, and 2, and you interpolate between the end samples, checking for error on the middle sample.
In this case that means, interpolate between 0 and 2 and if it is close enough to 1, eliminate 1 and repeat for frames 0 and 3, again checking against 1.
If the interpolation between 0 and 2 is not close enough, 1 is left and the process is repeated for frames 1, 2, and 3.

This gives you the best trade-off between accuracy and memory, as well as run-time performance. You can often end up with fewer frames then were in the original data set while stilling being extremely accurate.

However I would contend with the suggestion that the whole matrices should be stored on each keyframe.
Everything should be track-based, and only the minimum number of tracks should be used. This increased performance greatly and avoids the main problem with storing whole matrices. If you store whole matrices at each keyframe you lose a lot of flexibility.  It’s easier to write the tool chain and the run-time, but you can’t mix tracks etc.  In my previous engine I stored whole matrices at each keyframe and then later made a tool that could allow you to throw custom motions into the mix, such as rotating around Y for some seconds etc.
I had to evaluate the whole transform matrix for the animation system and then overwrite the rotation based on the tool’s parameters, and not only was it quirky but it had bugs that were simply not possible to fix due to limitations with the matrix system.

By going fully track-based, you are only updating the parts that are actually animated, and tracks can be individually turned on and off to allow compliance with other systems.
Plus it is true to the way model authoring software works, and tracks can then be used to animate anything, not just position, scale, rotation, etc.  The same track system can be used to animate lights turning on/off, changes in colors, changes in camera settings, etc.
Tracks are really the way to go.

Here is code for loading a track from the Autodesk® FBX® SDK and extracting the minimum number of keyframes needed.
	/**
* Loads data from an FBX animation curve.
*
* \param _pfacCurve The curve from which to load keyframes.
* \param _pfnNode The node effected by this track.
* \param _ui32Attribute The attribute of that node affected by this track.
* \return Returns true if there are no memory failures.
*/
LSBOOL LSE_CALL CAnimationTrack::Load( FbxAnimCurve * _pfacCurve, FbxNode * _pfnNode, LSUINT32 _ui32Attribute ) {
SetAttributes( _pfnNode, _ui32Attribute );

LSUINT32 ui32Total = _pfacCurve->KeyGetCount();
static const FbxTime::EMode emModes[] = {
FbxTime::eFrames96,
FbxTime::eFrames60,
FbxTime::eFrames48,
FbxTime::eFrames30,
FbxTime::eFrames24,
};
LSUINT32 ui32FrameMode = 0UL;
if ( ui32Total ) {
while ( ui32FrameMode < LSE_ELEMENTS( emModes ) ) {
// Count how many entries we will add.
FbxTime ftTotalTime = _pfacCurve->KeyGetTime( ui32Total - 1UL ) - _pfacCurve->KeyGetTime( 0UL );
// We sample at 48 frames per second.
FbxLongLong fllFrames = ftTotalTime.GetFrameCount( emModes[ui32FrameMode] );
if ( ui32Total + fllFrames >= 0x0000000100000000ULL ) {
// Too many frames!  Holy crazy!  Try to sample at the next-lower resolution.
++ui32FrameMode;
continue;
}

m_sKeyFrames.AllocateAtLeast( static_cast<LSUINT32>(ui32Total + fllFrames) );
// Evaluate at the actual key times.
int iIndex = 0;
for ( LSUINT32 I = 0UL; I < ui32Total; ++I ) {
if ( !SetKeyFrame( _pfacCurve->KeyGetTime( I ), _pfacCurve->Evaluate( _pfacCurve->KeyGetTime( I ), &iIndex ) ) ) {
return false;
}
}
// Extra evaluation between key times.
iIndex = 0;
FbxTime ftFrameTime;
for ( FbxLongLong I = 0ULL; I < fllFrames; ++I ) {
ftFrameTime.SetFrame( I, emModes[ui32FrameMode] );
FbxTime ftCurTime = _pfacCurve->KeyGetTime( 0UL ) + ftFrameTime;
if ( !SetKeyFrame( ftCurTime, _pfacCurve->Evaluate( ftCurTime, &iIndex ) ) ) {
return false;
}
}

// Now simplify.
LSUINT32 ui32Eliminated = 0UL;
for ( LSUINT32 ui32Start = 0UL; m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL; ++ui32Start ) {
const LSUINT32 ui32End = ui32Start + 2UL;
while ( m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL ) {
// Try to remove the key between ui32Start and ui32End.
LSDOUBLE dSpan = static_cast<LSDOUBLE>(m_sKeyFrames.GetByIndex( ui32End ).tTime.GetMilliSeconds()) - static_cast<LSDOUBLE>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds());
LSDOUBLE dFrac = (static_cast<LSDOUBLE>(m_sKeyFrames.GetByIndex( ui32Start + 1UL ).tTime.GetMilliSeconds()) -
static_cast<LSDOUBLE>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds())) / dSpan;
// Interpolate by this much between the start and end keys.
LSDOUBLE dInterp = (m_sKeyFrames.GetByIndex( ui32End ).fValue - m_sKeyFrames.GetByIndex( ui32Start ).fValue) * dFrac + m_sKeyFrames.GetByIndex( ui32Start ).fValue;
LSDOUBLE dActual = m_sKeyFrames.GetByIndex( ui32Start + 1UL ).fValue;
LSDOUBLE dDif = ::abs( dInterp - dActual );
if ( dDif < 0.05 ) {
m_sKeyFrames.RemoveByIndex( ui32Start + 1UL );
++ui32Eliminated;
}
else {
// Move on to the next key frame and repeat.
break;
}
}
}
::printf( "\tOriginal key frames: %u\r\n\tFinal total key frames: %u %f\r\n", ui32Total,
m_sKeyFrames.Length(), m_sKeyFrames.Length() * 100.0f / static_cast<LSFLOAT>(ui32Total) );
break;
}
}
return ui32FrameMode < LSE_ELEMENTS( emModes );
}
At the end it prints the total remaining keyframes after redundancy checking as a percentage, and it is often between 80% and 120% of the original.

L. Spiro

### #2L. Spiro

Posted 11 September 2013 - 09:59 PM

So the thing is, interpolation is almost unavoidable if you choose such technique, because even if your sampling frequency is too high, missmatches between the playback framerate and the framerate it was encoded with can cause artifacts.

Another issue worth mentioning is that high sampling frequency (i.e. 60fps) cause the memory consumption to skyrocket. A modestly detailed walk animation loop for a human rig with around 50 bones sampled @60fps can easily reach 20 MBs. And you won't get much more detail/quality than sampling at 15-30fps (for a videogame).
Also considering that computing power keeps improving (and animation is highly parallelizable) but memory bandwidth growth is stalled, if you're planning to have hundreds of animated objects in your scene, interpolating with relatively low sampling frequencies could give you much more performance than just preprocessing the whole thing at high framerates and playing it with no interpolation.

This is handled by adding a redundancy elimination after the sampling stage.
First you sample between key frames at a fixed rate as mentioned.

Then you go over every triplet of samples, for example froms 0, 1, and 2, and you interpolate between the end samples, checking for error on the middle sample.
In this case that means, interpolate between 0 and 2 and if it is close enough to 1, eliminate 1 and repeat for frames 0 and 3, again checking against 1.
If the interpolation between 0 and 2 is not close enough, 1 is left and the process is repeated for frames 1, 2, and 3.

This gives you the best trade-off between accuracy and memory, as well as run-time performance. You can often end up with fewer frames then were in the original data set while stilling being extremely accurate.

However I would contend with the suggestion that the whole matrices should be stored on each keyframe.
Everything should be track-based, and only the minimum number of tracks should be used. This increased performance greatly and avoids the main problem with storing whole matrices. If you store whole matrices at each keyframe you lose a lot of flexibility.  It’s easier to write the tool chain and the run-time, but you can’t mix tracks etc.  In my previous engine I stored whole matrices at each keyframe and then later made a tool that could allow you to throw custom motions into the mix, such as rotating around Y for some seconds etc.
I had to evaluate the whole transform matrix for the animation system and then overwrite the rotation based on the tool’s parameters, and not only was it quirky but it had bugs that were simply not possible to fix due to limitations with the matrix system.

By going fully track-based, you are only updating the parts that are actually animated, and tracks can be individually turned on and off to allow compliance with other systems.
Plus it is true to the way model authoring software works, and tracks can then be used to animate anything, not just position, scale, rotation, etc.  The same track system can be used to animate lights turning on/off, changes in colors, changes in camera settings, etc.
Tracks are really the way to go.

Here is code for loading a track from the Autodesk® FBX® SDK and extracting the minimum number of keyframes needed.
	/**
* Loads data from an FBX animation curve.
*
* \param _pfacCurve The curve from which to load keyframes.
* \param _pfnNode The node effected by this track.
* \param _ui32Attribute The attribute of that node affected by this track.
* \return Returns true if there are no memory failures.
*/
LSBOOL LSE_CALL CAnimationTrack::Load( FbxAnimCurve * _pfacCurve, FbxNode * _pfnNode, LSUINT32 _ui32Attribute ) {
SetAttributes( _pfnNode, _ui32Attribute );

LSUINT32 ui32Total = _pfacCurve->KeyGetCount();
static const FbxTime::EMode emModes[] = {
FbxTime::eFrames96,
FbxTime::eFrames60,
FbxTime::eFrames48,
FbxTime::eFrames30,
FbxTime::eFrames24,
};
LSUINT32 ui32FrameMode = 0UL;
if ( ui32Total ) {
while ( ui32FrameMode < LSE_ELEMENTS( emModes ) ) {
// Count how many entries we will add.
FbxTime ftTotalTime = _pfacCurve->KeyGetTime( ui32Total - 1UL ) - _pfacCurve->KeyGetTime( 0UL );
// We sample at 48 frames per second.
FbxLongLong fllFrames = ftTotalTime.GetFrameCount( emModes[ui32FrameMode] );
if ( ui32Total + fllFrames >= 0x0000000100000000ULL ) {
// Too many frames!  Holy crazy!  Try to sample at the next-lower resolution.
++ui32FrameMode;
continue;
}

m_sKeyFrames.AllocateAtLeast( static_cast<LSUINT32>(ui32Total + fllFrames) );
// Evaluate at the actual key times.
int iIndex = 0;
for ( LSUINT32 I = 0UL; I < ui32Total; ++I ) {
if ( !SetKeyFrame( _pfacCurve->KeyGetTime( I ), _pfacCurve->Evaluate( _pfacCurve->KeyGetTime( I ), &iIndex ) ) ) {
return false;
}
}
// Extra evaluation between key times.
iIndex = 0;
FbxTime ftFrameTime;
for ( FbxLongLong I = 0ULL; I < fllFrames; ++I ) {
ftFrameTime.SetFrame( I, emModes[ui32FrameMode] );
FbxTime ftCurTime = _pfacCurve->KeyGetTime( 0UL ) + ftFrameTime;
if ( !SetKeyFrame( ftCurTime, _pfacCurve->Evaluate( ftCurTime, &iIndex ) ) ) {
return false;
}
}

// Now simplify.
LSUINT32 ui32Eliminated = 0UL;
for ( LSUINT32 ui32Start = 0UL; m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL; ++ui32Start ) {
const LSUINT32 ui32End = ui32Start + 2UL;
while ( m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL ) {
// Try to remove the key between ui32Start and ui32End.
LSDOUBLE dSpan = static_cast<LSDOUBLE>(m_sKeyFrames.GetByIndex( ui32End ).tTime.GetMilliSeconds()) - static_cast<LSDOUBLE>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds());
LSDOUBLE dFrac = (static_cast<LSDOUBLE>(m_sKeyFrames.GetByIndex( ui32Start + 1UL ).tTime.GetMilliSeconds()) -
static_cast<LSDOUBLE>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds())) / dSpan;
// Interpolate by this much between the start and end keys.
LSDOUBLE dInterp = (m_sKeyFrames.GetByIndex( ui32End ).fValue - m_sKeyFrames.GetByIndex( ui32Start ).fValue) * dFrac + m_sKeyFrames.GetByIndex( ui32Start ).fValue;
LSDOUBLE dActual = m_sKeyFrames.GetByIndex( ui32Start + 1UL ).fValue;
LSDOUBLE dDif = ::abs( dInterp - dActual );
if ( dDif < 0.05 ) {
m_sKeyFrames.RemoveByIndex( ui32Start + 1UL );
++ui32Eliminated;
}
else {
// Move on to the next key frame and repeat.
break;
}
}
}
::printf( "\tOriginal key frames: %u\r\n\tFinal total key frames: %u %f\r\n", ui32Total,
m_sKeyFrames.Length(), m_sKeyFrames.Length() * 100.0f / static_cast<LSFLOAT>(ui32Total) );
break;
}
}
return ui32FrameMode < LSE_ELEMENTS( emModes );
}

L. Spiro

### #1L. Spiro

Posted 11 September 2013 - 09:57 PM

So the thing is, interpolation is almost unavoidable if you choose such technique, because even if your sampling frequency is too high, missmatches between the playback framerate and the framerate it was encoded with can cause artifacts.

Another issue worth mentioning is that high sampling frequency (i.e. 60fps) cause the memory consumption to skyrocket. A modestly detailed walk animation loop for a human rig with around 50 bones sampled @60fps can easily reach 20 MBs. And you won't get much more detail/quality than sampling at 15-30fps (for a videogame).
Also considering that computing power keeps improving (and animation is highly parallelizable) but memory bandwidth growth is stalled, if you're planning to have hundreds of animated objects in your scene, interpolating with relatively low sampling frequencies could give you much more performance than just preprocessing the whole thing at high framerates and playing it with no interpolation.

This is handled by adding a redundancy elimination after the sampling stage.
First you sample between key frames at a fixed rate as mentioned.

Then you go over every triplet of samples, for example froms 0, 1, and 2, and you interpolate between the end samples, checking for error on the middle sample.
In this case that means, interpolate between 0 and 2 and if it is close enough to 1, eliminate 1 and repeat for frames 0 and 3, again checking against 1.
If the interpolation between 0 and 2 is not close enough, 1 is left and the process is repeated for frames 1, 2, and 3.

This gives you the best trade-off between accuracy and memory, as well as run-time performance. You can often end up with fewer frames then were in the original data set while stilling being extremely accurate.

However I would contend with the suggestion that the whole matrices should be stored on each keyframe.
Everything should be track-based, and only the minimum number of tracks should be used. This increased performance greatly and avoids the main problem with storing whole matrices. If you store whole matrices at each keyframe you lose a lot of flexibility.  It’s easier to write the tool chain and the run-time, but you can’t mix tracks etc.  In my previous engine I stored whole matrices at each keyframe and then later made a tool that could allow you to throw custom motions into the mix, such as rotating around Y for some seconds etc.

I had to evaluate the whole transform matrix for the animation system and then overwrite the rotation based on the tool’s parameters, and not only was it quirky but it had bugs that were simply not possible to fix due to limitations with the matrix system.

By going fully track-based, you are only updating the parts that are actually animated, and tracks can be individually turned on and off to allow compliance with other systems.

Plus it is true to the way model authoring software works, and tracks can then be used to animate anything, not just position, scale, rotation, etc.  The same track system can be used to animate lights turning on/off, changes in colors, changes in camera settings, etc.

Tracks are really the way to go.

L. Spiro

PARTNERS