用于移动和碰撞对象的性能更好的四叉树

Question

所以基本上我想制作一个场景，其中生成了大约 50,000 颗小行星，其中有一个位置和 AABB（轴对齐边界框），并将它们中的每一个移动到开始时生成的随机方向。移动它们之后，我必须检查是否有任何小行星正在碰撞。

我正在使用四叉树数据结构来插入和检查冲突。我保留了一个包含 50K 点的数组并迭代并更新它们，然后插入四叉树并再次迭代超过 50k 点并通过 QT 查询以查看是否有任何点发生碰撞。

我已经在这里和那里阅读了大约 2 周的时间，并尝试了尽可能多的来源，但我无法挤出最大的性能。大多数来源都使用 c++ 或其他性能更好的语言，但我需要使用 C# 来实现。任何提高性能的建议都将不胜感激。

这是我的代码：

public struct Point
{
    public float x,y; 
    public int ID;

    public void MoveTowards(float posX, float posY)
    {
        position.x = position.x + posX;
        position.y = position.y + posY;
    }
}

public class Controller
{

    Point[] asteroids = new Point[50K];
    Point[] speed = new Point[50K];
    QuadTree qt = new QuadTree();

    //Runs every frame
    void Update() 
    {
        qt.ClearAllNodes();
        for loop asteroids(50K)
        {
            asteroids[i].MoveTowards(speed.x, speed.y);
            qt.Insert(astetoids[i]);
        }

        for loop asteroids(50K)
        {
            int collidingAsteroidID = qt.Query(astetoids[i]);
            if(collidingAsteroidID != -1) { 
                print(collidingAsteroidID + " is colliding with " + i); 
            }
        }
    }

}

class QuadTree 
{
    public Rectangle boundry;
    Point[] nodes;
    bool root = false;
    bool divided = false;
    int numberOfNodesInserted = 0;
    QuadTree northEast, northWest, southEast, southWest;

    public QuadTree(Rectangle boundry) 
    {
        nodes = new Point[4];
        this.boundry = boundry;
    }   

    #region Methods

    //Clear all the nodes in the Quad-Tree
    public void ClearAllNodes() 
    {
        if(numberOfNodesInserted == 0 && !root) return;
        numberOfNodesInserted = 0;
        root = false;

        if(divided) 
        {
            northEast.ClearAllNodes();
            northWest.ClearAllNodes();
            southEast.ClearAllNodes();
            southWest.ClearAllNodes();
        }
        divided = false;
    }

    public bool Insert(Point point) 
    {
        //Checking if the position is in the boundries.
        if(!boundry.Contains(point)) return false;
        if(numberOfNodesInserted < 4 && !root) 
        {
            nodes[numberOfNodesInserted] = point;
            numberOfNodesInserted++;
            return true;
        }
        else if(root)
        {
            if(northEast.Insert(point)) return true;            
            if(northWest.Insert(point)) return true;        
            if(southEast.Insert(point)) return true;
            if(southWest.Insert(point)) return true;    
        }
        else if(!root && numberOfNodesInserted == 4)
        {
            //Making this node a branch and moving all the to sub-leafs 
            root = true;
            numberOfNodesInserted = 0;

            if(!divided)
                SubDivide();

            for (int i = 0; i < 4; i++)
            {
                if(!northEast.Insert(nodes[i]))         
                if(!northWest.Insert(nodes[i]))     
                if(!southEast.Insert(nodes[i]))
                if(!southWest.Insert(nodes[i])) { }
            }

            if(!northEast.Insert(point))            
            if(!northWest.Insert(point))        
            if(!southEast.Insert(point))
            if(!southWest.Insert(point)) { }
            return true;
        }
        return false;
    }

    public int Query(Point point, float radius)
    {

        if(numberOfNodesInserted == 0 && !root) return -1;
        if(!boundry.Contains(point)) return -1;

        if(!root && numberOfNodesInserted != 0)
        {
            for (int i = 0; i < numberOfNodesInserted; i++)
            {
                if(DoOverlap(nodes[i], point, radius)) 
                    return nodes[i].ID; 
            }
        }
        else if(root && numberOfNodesInserted == 0)
        {
            int result;
            result = northEast.Query(point);
            if(result != -1)  return result;

            result = northWest.Query(point);
            if(result != -1)  return result;

            result = southEast.Query(point);
            if(result != -1)  return result;

            result = southWest.Query(point);
            if(result != -1)  return result;
        }
        return -1;
    }
    #endregion

    #region HelperMethods
    private void SubDivide() 
    {
        //Size of the sub boundries 
        if(northEast == null) 
        {   
            float x = boundry.x;
            float y = boundry.y;
            float r = boundry.radius / 2;

            northEast = new QuadTree(new Rectangle(x + r, y + r, r));
            northWest = new QuadTree(new Rectangle(x - r, y + r, r));
            southEast = new QuadTree(new Rectangle(x + r, y - r, r));
            southWest = new QuadTree(new Rectangle(x - r, y - r, r));
        } 
        divided = true; 
    }


    #endregion
}

Answer 1

关于您的实施：

看起来你每一步都在重建整棵树。这是必要的吗？如果你移动一个点，它们通常会留在同一个节点中，所以你可以避免 clearNodes() 和随后插入到同一个节点中。

其他实现：

我在 Java 中实现了一些空间索引，insertion/update 速率约为 1M points/sec，查询速率（碰撞检查）为每秒 100,000 次（假设通常有每个点大约有 0 或 1 个碰撞。参见一些性能测量 here（图 16b 用于 3D 查询，图 40b 用于更新）。最快的是四叉树（参见 qthypercube and qthypercube2) and the PH-Tree。他们都使用 z-order 描述的导航 here （自我广告）。其中一部分是它在导航/insertion/update/删除期间计算正确的 sub-nodes。例如，在一个节点上调用insert(element)时，它很快并没有尝试所有的子节点，而是'calculates'其中sub-node是正确的，直接在那个sub-node上调用了insert()。

Answer 2

有额外要求的新答案：

好的，所以对于 50K 点和 120Hz，您需要每秒进行 50,000*120=6,000,000 次碰撞检查。考虑到 4GHz 的 CPU，这意味着每次碰撞检查大约有 650 CPU 个周期。我不认为你可以用四叉树或类似的东西做到这一点，即使是最有效的编程语言。

我只看到一个选项：由于您使用的是 2D，请尝试以下操作：按 X-coordinate 对所有点进行排序。然后行进通过所有点并检查与 X-coordinate 上足够近的所有点的碰撞，它们可能已经引起了碰撞。这样的算法有一些优点：

它比空间索引 cache-friendly 多得多，缓存未命中（内存访问）很可能是瓶颈。
它很容易并行化（排序大部分可以并行化，搜索大部分可以并行化）。
它很简单，很可能在 GPU 上执行。

一个CPU核心，这仍然可能太慢了。但是使用 4 核机器，您可能会获得所需的帧速率。使用 GPU，有可能获得比您需要的更多的东西。但是，我没有使用 GPU 的经验，所以我不知道如何（容易）做到这一点。

用于移动和碰撞对象的性能更好的四叉树

Better performant quad-tree for moving and colliding objects

c#

performance

quadtree

unity3d

data-structures