最近的项目中使用鬼火irrlicht作为3D引擎，项目逐渐有了点规模。随后发现当同屏人数比较多的时候，帧率下降的厉害。使用xcode的timing profile检测之后发现人物获取动画帧比较耗时。

先看一下鬼火的代码：

在void CSkinnedMesh::getFrameData函数中获取position的代码

// 先寻找当前帧附近的帧，如果满足要求则可以快速返回
if (positionHint>=0 && (u32)positionHint < PositionKeys.size())
{
    //check this hint
    if (positionHint>0 && PositionKeys[positionHint].frame>=frame && PositionKeys[positionHint-1].frame<frame )
        foundPositionIndex=positionHint;
    else if (positionHint+1 < (s32)PositionKeys.size())
    {
        //check the next index
        if ( PositionKeys[positionHint+1].frame>=frame &&
                PositionKeys[positionHint+0].frame<frame)
        {
            positionHint++;
            foundPositionIndex=positionHint;
        }
    }
}
// 但是如果动作切换则需要走下面的逻辑，遍历查找
if (foundPositionIndex==-1)
{
    for (u32 i=0; i<PositionKeys.size(); ++i)
    {
        if (PositionKeys[i].frame >= frame) //Keys should to be sorted by frame
        {
            foundPositionIndex=i;
            positionHint=i;
            break;
        }
    }
}

后面scale及rotation使用了相同的逻辑处理。

通过上面的代码，我们可以看出，当动作切换时，基本都会走入下面的遍历查找。对于我们的项目来说，玩家的动画帧已经接近1000帧，则平均查询需要500次比较。只要对这部分查找做一个二分查找优化则可以降低到10次左右。

使用template可以对position scale rotation使用同样的代码

template <class T>
void FunFindKey(const core::array<T>& keys, f32 targetFrame, int& posIndex, int& hint) {
    u32 firstIndex = 0;
    u32 secendIndex = keys.size() - 1;
    // 针对第一帧特殊优化
    if (keys[firstIndex].frame >= targetFrame)
        secendIndex = firstIndex;
    while (secendIndex > firstIndex + 1) {
        u32 search = (firstIndex + secendIndex) / 2;
        if (keys[search].frame < targetFrame) {
            firstIndex = search;
        } else {
            secendIndex = search;
        }
    }
    posIndex = secendIndex;
    hint = secendIndex;
}

修改后的重新查找为：（scale，rotation同）

if (foundPositionIndex==-1)
{
    FindKey(PositionKeys, frame, foundPositionIndex, positionHint);
}

实测该函数时间占比，在30人情况下，从20%降到5%左右