的Python：最佳颗粒自碰撞/三角形碰撞算法

Question

我开始在Python这个粒子引擎工作的搅拌机：http://www.youtube.com/watch?v=uoK4QV3jg58&feature=channel_video_title

所有数据都由我的脚本处理，搅拌机就在那里为视觉。我现在的问题是，在上面的视频中，我计算了每个粒子之间所有粒子之间的距离，以检测它们是否相互碰撞。

我开始阅读：

• 八叉树
• kdTree
• BVHTree
• AABBtree
• ...等等

Kdtree似乎是搜索最近的邻居非常高效，但仅适用于静态云。我的粒子总是移动，所以每次迭代必须重新生成kdTree，我认为这消耗了太多的过程。我读了很多游戏使用AABB树。我有点失落......我不知道该选什么。我要的是：

• 碰撞检测量非常大颗粒（250 000或以上）
• 无需之间是实时的（反正有250个000颗粒它不是真的有可能）。对于200万个粒子，每帧20分钟对我来说不是问题。
• 我颗粒总是球体
• 检测粒子和多边形物体
之间的碰撞
• 算法来减少必要的（避免像计算所有粒子相互颗粒或多边形，即使他们离我很远的东西）距离计算
• 我的粒子是动态的，我的多边形对象可以是动态的或静态的。

如果有人能告诉我什么是最好的猜测，我可以在哪里找到Python文档和示例。

Answer 1

如果“一切都是动态的”，那么您将失去快速查找和缓慢插入的数据结构的好处。

理想情况下，您可以在数据中找到一些结构来简化运行时间。也许移动的多边形都朝着相同的方向移动，所以你可以用它们作为参照系，有效地使它们变成静态的。也许这些动作很小，所以数据结构可以在原地进行更新，而不是在每次通过时从头开始重建。或者粒子和多边形的运动局限于小的邻域，这样计算上难以解决的大问题就可以减少到更小的问题。

说没有任何额外的限制，“一切都移动”类似于说，从迭代到迭代的数据是完全随机的;因此，您的问题的关键是确定以前迭代中的任何计算是否可重用。这将决定适当的数据结构和算法。