优化游戏角度检查中的距离

Question

我正在努力确保此功能尽可能快。

CItem *find_closest_item_within_angle(
    std::vector<CItem *> const &items,
    CItem const *pThisItem,
    float const angleDegrees)
{
    float minDist = FLT_MAX;
    CItem *pClosest = nullptr;
    std::vector<CItem *>::iterator it = items.begin();
    while (it != items.end())
    {
        SVec const thisLoc = pThisItem->GetLocation(ESpace::World);
        SVec const thatLoc = (*it)->GetLocation(ESpace::World);
        SVec const diff = thisLoc – thatLoc;
        float const dist = diff.Length();
        SVec const forward = pThisItem->GetForward(ESpace::World);
        float const dot = SVec::Dot(diff.Normalized(), forward);
        if (acos(dot) > DEGREES_TO_RADIANS * angleDegrees
            && dist < minDist
            && pThisItem != *it)
        {
            minDist = dist;
            pClosest = *it;
        }
        it++;
    }
    return pClosest;
}

我实际上已经尝试过了，主要关注将计算移出循环并更早地跳过迭代，但我对 C++ 有点陌生，所以我可能错过了一些明显的事情。我在优化过程中似乎遗漏了什么吗？

CItem *find_closest_item_within_angle(
    std::vector<CItem *> const &items,
    CItem const *pThisItem,
    float const angleDegrees)
{
    float minDist = FLT_MAX;
    CItem *pClosest = nullptr;
    //This may be a bit of a small optimization, and
    //it might affect readability slightly, but if we are
    //purely optimizing for speed, neither of these calculations
    //will change during the loop and we have access to everything
    //we need for them before we even start the loop, so there
    //is no need to dereference and call the functions every iteration
    SVec const thisLoc = pThisItem->GetLocation(ESpace::World);
    SVec const forward = pThisItem->GetForward(ESpace::World);
    std::vector<CItem *>::iterator it = items.begin();
    while (it != items.end())
    {
        //Since we have access to both our current iteration item and our input item
        //at the beginning, we can early out if the current item is the same as
        //our input item
        if(pThisItem == *it)
        {
            it++;
            continue;
        }
        SVec const thatLoc = (*it)->GetLocation(ESpace::World);
        SVec const diff = thisLoc - thatLoc;
        //Given that we are only needing to compare distances, we
        //really do not need to pay the cost of a square root calculation
        //Most api's are going to support this in some form in their Vector library
        //Length = std::sqrt(diff.x * diff.x + diff.y * diff.y + diff.z * diff.z)
        //Length Squared = (diff.x * diff.x + diff.y * diff.y + diff.z * diff.z)
        //Unity: Vector3.MagnitudeSquared();
        //Unreal: FVector::SizeSquared();
        float const dist = (diff.x * diff.x + diff.y * diff.y + diff.z * diff.z);
        //We have to check the distance to get here, but if our distance is above the
        //the previous min we can early out here since we only care about closer values

        //There is a cost to our normalization below which is a need for a full Length
        //calculation, so skipping it can be a pretty helpful optimization
        //Normalize Vector = diff / diff.Length();
        if(dist > minDist)
        {
            it++;
            continue;
        }
        float const dot = SVec::Dot(diff.Normalized(), forward);
        if (acos(dot) > DEGREES_TO_RADIANS * angleDegrees)
        {
            minDist = dist;
            pClosest = *it;
        }
        it++;
    }
    return pClosest;
}

Answer 1

acos(dot)是一个比较繁重的计算，可以通过比较角度的余弦来去除。 cos(DEGREES_TO_RADIANS * angleDegrees) 也比较重，但它只会计算一次，而不是每个项目。一般来说，根据经验，你不应该做三角函数，尽量保持在线性代数范围内。

此循环也可能受益于 SIMD，尤其是当项目的位置以 SoA 形式可用时。使用 SIMD 实现向量运算不是很好，通常使用 SIMD 一次处理多个项目会更好。

优化游戏角度检查中的距离

Optimizing a distance within angle check for game

c++

optimization

game-engine