对数万个粒子进行更快的嵌套循环

Question

我正在 Unity 环境中进行一些视觉艺术研究。我正在尝试实现与微分线增长非常相似的东西 as explained here 但我主要担心的是，在算法的某个地方，每个节点都应该检查每个其他节点，看看它有多近，并从所有这些靠近的粒子构建一个排斥力数组。

这是我的代码片段：

   public void Differentiate()
    {
        int c = nodes.Count;                                 
        Vector3[] repulsionForces = new Vector3[c];

        for (int i = 0; i < c ; i++)
        {

            // Construct nearbies
            List<DifferentialNode> nearby = new List<DifferentialNode>();
            foreach(DifferentialNode n in nodes)
            {
                float d = Vector3.Distance(n.position, nodes[i].position);
                if (d < 5)
                {
                    nearby.Add(n);
                }
            }
            // Get Forces
            Vector3 repulsionForce = nodes[i].RepulsionForce(nearby);

            // Limit Forces
            repulsionForce = Vector3.ClampMagnitude(repulsionForce, maxForce);

            // Apply Multipliers
            repulsionForce *= Repulsion;

            // Put Forces into Array
            repulsionForces[i] = repulsionForce;
        }

        for (int i = 0; i < c; i++)
        {
            nodes[i].applyForce(repulsionForces[i]);
            nodes[i].update();
            nodes[i].velocity = new Vector3(0, 0, 0);
        }

这是我在 DifferentialLineNode 中的 RepulsionForce() 函数 class

public Vector3 RepulsionForce(List<DifferentialNode> nearby)
{
    Vector3 repulsionForce = new Vector3();

    foreach (DifferentialNode n in nearby)
    {
        // calculate distance between both
        float d = Vector3.Distance(n.position, this.position);
        // calculate difference and divide by exp(d) to get less influence when far
        Vector3 diff = ( this.position - n.position ) / (Mathf.Exp(d)); 
        repulsionForce += diff;
    }
    repulsionForce /= (float)nearby.Count;
    repulsionForce.Normalize();

    return repulsionForce;
}

我一开始游戏，一切都降到 1fps 以下，我发现嵌套循环是它的来源，因为 n^n 的复杂性。我一直在研究 Octree / KdTree 实现，但找不到任何解释代码。还有其他路线吗？超过一个？可以任意组合吗？非常感谢

Answer 1

您应该考虑对列表使用 for 而不是 foreach，例如here 当你为性能编码时。不过，我认为你的问题更多的是结构性问题，而不是与这些细节有关。

我建议您看一下 Quadtrees, for example by this implementation 将您的总面积分成多个部分并将每个粒子与一个部分相关联。要找到邻居，您只需遍历树即可。

Answer 2

对于每个点计算距离内的点是O(n^2)，所以如果粒子数量大，性能下降并不奇怪。但这可以很容易地改进。有几个可供使用的搜索结构选项：

3D 网格。这应该很容易实现，只需创建一个列表的 3D 数组即可。选择合适的 bin 大小，以便您有固定数量的 bin 进行迭代。这样做的主要缺点是内存使用，如果您的模拟中存在没有粒子的大空隙，这将更加重要。
稀疏八叉树。如果点间距不均匀，则与网格相比的主要优势是更好的内存使用。如果您需要搜索任意距离，它的扩展性也会更好。缺点是实施起来会更复杂。
KdTree。这是一个非常好的数据结构，因为它使用相当少的内存，可以用连续的内存实现，并且可以很好地扩展。一个缺点是很难处理位置的变化。实现也比网格复杂。

对于网格或八叉树，可以在 bin 之间移动点。对于 kd 树，重建树可能会更好。任何选项都应将搜索时间从 O(N^2) 减少到 O(n log n)。

考虑到您问题的背景，我建议您从简单的 3D 网格开始。如果这还不够，我会考虑使用 kd 树。我会避免组合数据结构，除非有一些特定的理由这样做。八叉树和 kdtrees 应该足够好。

我建议尝试一些 profiling tools to check what actually takes time. I would also recommend setting up some controlled environment to run the algorithm on a known dataset and measure the time. Benchmark.Net 是黄金标准，但在测量较大变化时，简单的秒表应该相当不错。

还应该有一些微优化的机会。避免在紧密循环中创建列表，如果需要，创建可重复使用的列表。避免重复操作。避免昂贵的操作。优先使用数组和列表而不是其他集合，因为运行时对它们进行了特殊优化。首选 for 而不是 foreach，因为前者可以避免创建迭代器对象。

对数万个粒子进行更快的嵌套循环

Faster nested loops over tens of thousands of particles

c#

kdtree

nested-loops

unity3d