1

我开始在 Python 中为 Blender 开发这个粒子引擎：http ://www.youtube.com/watch?v=uoK4QV3jg58&feature=channel_video_title

所有数据都由我的脚本处理，Blender 只是用于视觉效果。我现在的问题是，在上面的视频中，我计算了所有粒子的每个粒子之间的距离，以检测它们是否相互碰撞。

我开始阅读：

  • 八叉树
  • kd树
  • BVH树
  • AABB树
  • ...还有很多

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

  • 检测大量粒子（250 000 或更多）之间的碰撞
  • 不需要是实时的（无论如何有 250 000 个粒子是不可能的）。200 万个粒子每帧 20 分钟对我来说不是问题。
  • 我的粒子总是球体
  • 检测粒子和多边形对象之间的碰撞
  • 减少必要距离计算的算法（避免为其他粒子或多边形计算所有粒子，即使它们很远）
  • 我的粒子是动态的，我的多边形对象可以是动态的或静态的。

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

4

1 回答 1

0

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

理想情况下，您可以在数据中找到一些结构来简化运行时间。也许移动的多边形都向同一个方向移动，所以您可以将它们用作参考框架，从而有效地使它们保持静止。也许移动很小，因此可以就地更新数据结构，而不是在每次通过时从头开始重建。或者粒子和多边形的运动仅限于小邻域，因此计算上难以处理的大问题可以简化为更小的问题。

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

于 2011-11-24T17:44:48.850 回答