Well, first of all, I think you should have posted this on the TGC forums as most people go there instead of here and most people here are likely not coders, but anyway...
This is an interesting problem. If the keys were guaranteed to be equal distances apart time-wise, you could simply interpolate the time between 0 and the largest time to find which key, but I assume the keys can be anywhere and everywhere. This makes it a fair bit more difficult.
So the idea I've come up with is basically to create a branching system. It could (depending on implementation....the method I explain below would use no extra memory) use a small amount more memory, but could drastically improve speed.
This would only
(UPDATE: When I say only, I mean mostly - it could actually speed up all objects) help objects with a fair number of keyframes, such as characters, but I assume they have around 700-1000....the greater the number, the greater the speed increase. A simple check before the loop could decide whether to use the old brute-force system (which
may be faster for objects with very few frames).
Let's see if I'm capable of coming up with a plugin replacement for the current code, in my head, without testing and without really wanting to do this....
*several hours later*
I think this should work. It's mostly untested (although I did run through the code by hand line by line with notepad to record variable states
). You should be able to replace the
exact code you showed us with this code and it will be instantly working and instantly faster.
Here's the new code:
//find key
DWORD dwKey=0;
DWORD dwKeyMax=pAnim->dwNumPositionKeys; //I assume this number is 1-based
int keyMin=0;
int keyMax=(int)dwKeyMax;
int keyDiff;
int keyCentre;
if(dwKeyMax<2) //this constant can be changed to anything TWO OR ABOVE and may speed up very low-frame-count objects
{
for(;;)
{
keyDiff=keyMax-keyMin;
keyCentre=keyMin+((keyDiff)/2.0);
if(keyDiff>2) //the divisions are not yet too small; ie, there's still nothing definite to choose from
{
if(pAnim->pPositionKeys[keyCentre+1].dwTime>fTime) //the correct key is in the first half of the divided section
{
keyMax=keyCentre;
} else { //the correct key is in the second half of the divided section
keyMin=keyCentre;
}
} else { //the divisions are now too small and need to be checked on a one-on-one basis
for(int i=keyMin;i<=keyMax;i++) //this could be replaced with simple ifs, but this is easier to handle odd and even keyframes counts
{
if(pAnim->pPositionKeys[i].dwTime<=fTime )
{
dwKey=i;
} else {
break;
}
}
}
}
} else {
for(int i=0;i<=(int)dwKeyMax;i++) //this could be replaced with simple ifs, but this is easier to handle odd and even keyframes counts
{
if(pAnim->pPositionKeys[i].dwTime<=fTime )
{
dwKey=i;
} else {
break;
}
}
}
You're welcome
