的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

如果「一切都是動態的」，那麼您將失去快速查找和緩慢插入的數據結構的好處。

理想情況下，您可以在數據中找到一些結構來簡化運行時間。也許移動的多邊形都朝着相同的方向移動，所以你可以用它們作爲參照系，有效地使它們變成靜態的。也許這些動作很小，所以數據結構可以在原地進行更新，而不是在每次通過時從頭開始重建。或者粒子和多邊形的運動侷限於小的鄰域，這樣計算上難以解決的大問題就可以減少到更小的問題。

說沒有任何額外的限制，「一切都移動」類似於說，從迭代到迭代的數據是完全隨機的;因此，您的問題的關鍵是確定以前迭代中的任何計算是否可重用。這將決定適當的數據結構和算法。