性能更好的四叉树，用于移动和碰撞物体

Question

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

我正在使用四叉树数据结构进行插入和检查冲突。 我保留一个 50K 点的数组并迭代和更新它们，然后插入 Quad-Tree 并再次迭代超过 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 中实现了一些空间索引，插入/更新速率约为 1M 点/秒，查询速率(冲突检查)为每秒 100,000(假设每个点通常有大约 0 或 1 次冲突)。在此处查看一些性能度量(图 16b 用于 3D 查询，图 40b 用于更新)。 最快的是四叉树(参见qthypercube和qthypercube2)和PH树。 它们都使用 z 顺序导航，如此处所述(自我播发)。其中一部分是它在导航/插入/更新/删除期间计算正确的子节点。例如，当在节点上调用insert(element)时，它不会快速尝试所有子节点，而是"计算"哪个子节点是正确的，并直接在该子节点上调用insert()。

Answer 2

具有其他要求的新答案：

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

我只看到一个选项： 由于您使用的是 2D，请尝试以下操作：按 X 坐标对所有点进行排序。然后穿过所有点，并检查与 X 坐标上足够接近的所有点是否发生碰撞，以至于它们可能导致碰撞。这样的算法有一些优点：

• 它比空间索引对缓存更友好，缓存未命中(内存访问)很可能是瓶颈。
它很容易并行化(排序可以大部分并行化
• ，搜索可以大部分并行化)。
• 它非常简单，很可能可以在 GPU 上执行。

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