• Create Account

### #ActualL. Spiro

Posted 08 January 2013 - 06:48 PM

It is a 2-step process.  It begins with raw-interval sampling, which certainly adds a ton more key-frames, but then it does redundancy checking and removes redundant key-frames.  I generally end up with either only a few more key-frames in very simple animations (where there are so few key-frames that just a few more don’t really eat up noticeable extra memory) or with fewer than were originally in the file.

The first step is to decide your sampling rate.  I found that this does not effect the final result in terms of number of key-frames overall so you may as well keep it high.  Sometimes you will end up with a few extra than otherwise, sometimes fewer.  Average is the same (but the conversion time is affected), so I sample at 96 times per second (I have a table of sample rates and if one fails due to too much memory I decrease the sampling rate and try again).

Next is to build a table of times through the animation that you are going to sample.  Since this is offline, std::set works fine, since the times do need to be in sorted (and non-duplicate) order for this to work.
Start by adding all of the original key-frame times to the set.
Then add all the key-frame times as per your selected sampling interval.

Then go over the animation track and use the Autodesk® FBX® SDK to sample at all of those times you have added to your set.

Stage 2 begins afterwards.  This is where you remove redundant key-frames.
In this stage you start with key-frames 0 and 2 and linearly interpolate between them.  If the result is close enough (given your own error metric) to key-frame 1 then key-frame 1 can be eliminated and you then check between 0 and 3 to see if 2 can be eliminated.
When you get to one that can’t, repeat from the next set of key-frames.
Keep doing this until you reach the end of the animation.

The code for all of this follows (but is hard to read).

	/**
* 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, unsigned int _ui32Attribute ) {
SetAttributes( _pfnNode, _ui32Attribute );

unsigned int ui32Total = _pfacCurve->KeyGetCount();
static const FbxTime::EMode emModes[] = {
FbxTime::eFrames96,
FbxTime::eFrames60,
FbxTime::eFrames48,
FbxTime::eFrames30,
FbxTime::eFrames24,
};
unsigned int 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 emModes[ui32FrameMode] 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<unsigned int>(ui32Total + fllFrames) );
// Evaluate at the actual key times.
int iIndex = 0;
for ( unsigned int 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.
unsigned int ui32Eliminated = 0UL;
for ( unsigned int ui32Start = 0UL; m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL; ++ui32Start ) {
const unsigned int ui32End = ui32Start + 2UL;
while ( m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL ) {
// Try to remove the key between ui32Start and ui32End.
double dSpan = static_cast<double>(m_sKeyFrames.GetByIndex( ui32End ).tTime.GetMilliSeconds()) - static_cast<double>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds());
double dFrac = (static_cast<double>(m_sKeyFrames.GetByIndex( ui32Start + 1UL ).tTime.GetMilliSeconds()) -
static_cast<double>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds())) / dSpan;
// Interpolate by this much between the start and end keys.
double dInterp = (m_sKeyFrames.GetByIndex( ui32End ).fValue - m_sKeyFrames.GetByIndex( ui32Start ).fValue) * dFrac + m_sKeyFrames.GetByIndex( ui32Start ).fValue;
double dActual = m_sKeyFrames.GetByIndex( ui32Start + 1UL ).fValue;
double 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 );
}

What makes the biggest difference is the epsilon you use to decide if key-frames should be removed, and my results are as above.  It is common to have the same number as or fewer than the original number of key-frames.  m_sKeyFrames here by the way is a set.

So ultimately memory concerns and extra key-frames are not an issue.  At most you would end up with just a few extra ones, but that is the bare minimum you would need to produce the “same” animation via only linear interpolation, which makes your run-time much faster and is an obvious win.

L. Spiro

### #2L. Spiro

Posted 08 January 2013 - 06:46 PM

It is a 2-step process.  It begins with raw-interval sampling, which certainly adds a ton more key-frames, but then it does redundancy checking and removes redundant key-frames.  I generally end up with either only a few more key-frames in very simple animations (where there are so few key-frames exist that just a few more don’t really eat up noticeable extra memory) or with fewer than were originally in the file.

The first step is to decide your sampling rate.  I found that this does not effect the final result in terms of number of key-frames overall so you may as well keep it high.  Sometimes you will end up with a few extra than otherwise, sometimes fewer.  Average is the same (but the conversion time is affected), so I sample at 96 times per second (I have a table of sample rates and if one fails due to too much memory I decrease the sampling rate and try again).

Next is to build a table of times through the animation that you are going to sample.  Since this is offline, std::set works fine, since the times do need to be in sorted (and non-duplicate) order for this to work.
Start by adding all of the original key-frame times to the set.
Then add all the key-frame times as per your selected sampling interval.

Then go over the animation track and use the Autodesk® FBX® SDK to sample at all of those times you have added to your set.

Stage 2 begins afterwards.  This is where you remove redundant key-frames.
In this stage you start with key-frames 0 and 2 and linearly interpolate between them.  If the result is close enough (given your own error metric) to key-frame 1 then key-frame 1 can be eliminated and you then check between 0 and 3 to see if 2 can be eliminated.
When you get to one that can’t, repeat from the next set of key-frames.
Keep doing this until you reach the end of the animation.

The code for all of this follows (but is hard to read).

	/**
* 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, unsigned int _ui32Attribute ) {
SetAttributes( _pfnNode, _ui32Attribute );

unsigned int ui32Total = _pfacCurve->KeyGetCount();
static const FbxTime::EMode emModes[] = {
FbxTime::eFrames96,
FbxTime::eFrames60,
FbxTime::eFrames48,
FbxTime::eFrames30,
FbxTime::eFrames24,
};
unsigned int 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 emModes[ui32FrameMode] 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<unsigned int>(ui32Total + fllFrames) );
// Evaluate at the actual key times.
int iIndex = 0;
for ( unsigned int 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.
unsigned int ui32Eliminated = 0UL;
for ( unsigned int ui32Start = 0UL; m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL; ++ui32Start ) {
const unsigned int ui32End = ui32Start + 2UL;
while ( m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL ) {
// Try to remove the key between ui32Start and ui32End.
double dSpan = static_cast<double>(m_sKeyFrames.GetByIndex( ui32End ).tTime.GetMilliSeconds()) - static_cast<double>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds());
double dFrac = (static_cast<double>(m_sKeyFrames.GetByIndex( ui32Start + 1UL ).tTime.GetMilliSeconds()) -
static_cast<double>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds())) / dSpan;
// Interpolate by this much between the start and end keys.
double dInterp = (m_sKeyFrames.GetByIndex( ui32End ).fValue - m_sKeyFrames.GetByIndex( ui32Start ).fValue) * dFrac + m_sKeyFrames.GetByIndex( ui32Start ).fValue;
double dActual = m_sKeyFrames.GetByIndex( ui32Start + 1UL ).fValue;
double 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 );
}

What makes the biggest difference is the epsilon you use to decide if key-frames should be removed, and my results are as above.  It is common to have the same number as or fewer than the original number of key-frames.  m_sKeyFrames here by the way is a set.

So ultimately memory concerns and extra key-frames are not an issue.  At most you would end up with just a few extra ones, but that is the bare minimum you would need to produce the “same” animation via only linear interpolation, which makes your run-time much faster and is an obvious win.

L. Spiro

### #1L. Spiro

Posted 08 January 2013 - 06:45 PM

It is a 2-step process.  It begins with raw-interval sampling, which certainly adds a ton more key-frames, but then it does redundancy checking and removes redundant key-frames.  I generally end up with either only a few more key-frames in very simple animations (where there are so few key-frames exist that just a few more don’t really eat up noticeable extra memory) or with fewer than were originally in the file.

The first step is to decide your sampling rate.  I found that this does not effect the final result in terms of number of key-frames overall so you may as well keep it high.  Sometimes you will end up with a few extra than otherwise, sometimes fewer.  Average is the same (but the conversion time is affected), so I sample at 96 times per second (I have a table of sample rates and if one fails due to too much memory I decrease the sampling rate and try again).

Next is to build a table of times through the animation that you are going to sample.  Since this is offline, std::set works fine, since the times do need to be in sorted (and non-duplicate) order for this to work.
Start by adding all of the original key-frame times to the set.
Then add all the key-frame times as per your selected sampling interval.

Then go over the animation track and use the Autodesk® FBX® SDK to sample at all of those times you have added to your set.

Stage 2 begins afterwards.  This is where you remove redundant key-frames.
In this stage you start with key-frames 0 and 2 and linearly interpolate between them.  If the result is close enough (given your own error metric) to key-frame 1 then key-frame 1 can be eliminated and you then check between 0 and 3 to see if 2 can be eliminated.
When you get to one that can’t, repeat from the next set of key-frames.
Keep doing this until you reach the end of the animation.

The code for all of this follows (but is hard to read).

	/**
* 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, unsigned int _ui32Attribute ) {
SetAttributes( _pfnNode, _ui32Attribute );

unsigned int ui32Total = _pfacCurve->KeyGetCount();
static const FbxTime::EMode emModes[] = {
FbxTime::eFrames96,
FbxTime::eFrames60,
FbxTime::eFrames48,
FbxTime::eFrames30,
FbxTime::eFrames24,
};
unsigned int 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<unsigned int>(ui32Total + fllFrames) );
// Evaluate at the actual key times.
int iIndex = 0;
for ( unsigned int 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.
unsigned int ui32Eliminated = 0UL;
for ( unsigned int ui32Start = 0UL; m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL; ++ui32Start ) {
const unsigned int ui32End = ui32Start + 2UL;
while ( m_sKeyFrames.Length() >= 3UL && ui32Start < m_sKeyFrames.Length() - 2UL ) {
// Try to remove the key between ui32Start and ui32End.
double dSpan = static_cast<double>(m_sKeyFrames.GetByIndex( ui32End ).tTime.GetMilliSeconds()) - static_cast<double>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds());
double dFrac = (static_cast<double>(m_sKeyFrames.GetByIndex( ui32Start + 1UL ).tTime.GetMilliSeconds()) -
static_cast<double>(m_sKeyFrames.GetByIndex( ui32Start ).tTime.GetMilliSeconds())) / dSpan;
// Interpolate by this much between the start and end keys.
double dInterp = (m_sKeyFrames.GetByIndex( ui32End ).fValue - m_sKeyFrames.GetByIndex( ui32Start ).fValue) * dFrac + m_sKeyFrames.GetByIndex( ui32Start ).fValue;
double dActual = m_sKeyFrames.GetByIndex( ui32Start + 1UL ).fValue;
double 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 );
}

What makes the biggest difference is the epsilon you use to decide if key-frames should be removed, and my results are as above.  It is common to have the same number as or fewer than the original number of key-frames.  m_sKeyFrames here by the way is a set.

So ultimately memory concerns and extra key-frames are not an issue.  At most you would end up with just a few extra ones, but that is the bare minimum you would need to produce the “same” animation via only linear interpolation, which makes your run-time much faster and is an obvious win.

L. Spiro

PARTNERS