c++ - 如何最有效地对一组球体执行碰撞检测

Question

假设我有一个带有多个内核的 CPU，我想在其上找到哪些球体正在接触。每个球体相连的任何一组球体(即它们都至少接触该组中的一个球体)称为“组”，将组织成一个 vector ，在下面的示例中称为“group_members” ”。为实现这一目标，我目前正在使用一种相当昂贵的操作，从概念上看是这样的:

vector<Sphere*> unallocated_spheres = all_spheres; // start with a copy of all spheres
vector<vector<Sphere*>> group_sequence; // groups will be collected here

while (unallocated_spheres.size() > 0U) // each iteration of this will represent the creation of a new group
{
    std::vector<Sphere*> group_members; // this will store all members of the current group
    group_members.push_back(unallocated_spheres.back()); // start with the last sphere (pop_back requires less resources than erase)
    unallocated_spheres.pop_back(); // it has been allocated to a group so remove it from the unallocated list

    // compare each sphere in the new group to every other sphere, and continue to do so until no more spheres are added to the current group
    for (size_t i = 0U; i != group_members.size(); ++i) // iterators would be unsuitable in this case
    {
        Sphere const * const sphere = group_members[i]; // the sphere to which all others will be compared to to check if they should be added to the group
        auto it = unallocated_spheres.begin();
        while (it != unallocated_spheres.end())
        {
            // check if the iterator sphere belongs to the same group
            if ((*it)->IsTouching(sphere))
            {
                // it does belong to the same group; add it and remove it from the unallocated_spheres vector and repair iterators
                group_members.push_back(*it);
                it = unallocated_spheres.erase(it); // repair the iterator
            }
            else ++it; // if no others were found, increment iterator manually
        }
    }

    group_sequence.push_back(group_members);
}

有没有人对提高这段代码在挂钟时间方面的效率有什么建议？我的程序花费了很大一部分时间来运行这些循环，如有任何关于如何对其进行结构性更改以提高其效率的建议，我们将不胜感激。

请注意，由于这些是球体，“IsTouching()”是一个非常快速的浮点运算(比较两个球体的位置和半径)。它看起来像这样(注意 x、y 和 z 是球体在欧氏维度中的位置):

// input whether this cell is touching the input cell (or if they are the same cell; both return true)
bool const Sphere::IsTouching(Sphere const * const that) const
{
    // Apply pythagoras' theorem in 3 dimensions
    double const dx = this->x - that->x;
    double const dy = this->y - that->y;
    double const dz = this->z - that->z;

    // get the sum of the radii of the two cells
    double const rad_sum = this->radius + that->radius;

    // to avoid taking the square root to get actual distances, we instead compare 
    // the square of the pythagorean distance with the square of the radii sum
    return dx*dx + dy*dy + dz*dz < rad_sum*rad_sum;
}

Answer 1

Does anyone have any suggestions for improving the efficiency of this code in terms of wall time?

改变算法。低级优化对您没有帮助。 (尽管如果将 group_members 移动到 while 循环之外，您将获得非常小的加速)

你需要使用空间划分(bsp-tree, oct-tree)或者sweep and prune算法。

Sweep and prune (维基百科有原始文章的链接，另外你可以谷歌它)可以在单核机器上轻松处理 100000 个移动和潜在碰撞的球体(好吧，只要你不把它们都放在同一个坐标)并且有点比空间分区更容易实现。如果您知道碰撞对象的最大可能大小，扫描和修剪将更适合/更容易实现。

如果你打算使用清除和修剪算法，你应该学习 insertion sort算法。当您处理“几乎”排序的数据时，这种排序算法比几乎任何其他算法都快，扫描和修剪就是这种情况。当然，您还需要一些快速排序或堆排序的实现，但标准库提供了这些。